OctoInformBeta

OpenAI preprint, September 2026 · §4. An exponential bound for order-reversing images · §4

Lemma 4.2 [Restriction of a relation corner]: For an idempotent PP in ℛH\mathcal{R}_H and F⊆HF \subseteq H with IFPIF=IFI_FPI_F = I_F, restriction to FF maps the corner of PIFPPI_FP isomorphically onto ℛF\mathcal{R}_F

Corners of a relation monoid that are full relation monoids.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A nondeterministic finite automaton with state set HH lets each input word act on HH as a binary relation, and reading two words one after the other composes their relations in the order the words are read. The behaviours of words therefore live in the monoid ℛH\mathcal{R}_H of all binary relations on HH, and an idempotent PP of ℛH\mathcal{R}_H, such as the behaviour of a word that acts the same when read twice, cuts out the corner PℛHPP\mathcal{R}_HP.

Lemma 4.2 of the paper asks when a corner of ℛH\mathcal{R}_H is itself the full relation monoid of a smaller set. It takes a subset FF of HH such that PP relates every point of FF to itself and no point of FF to a different point of FF, and it looks at the relation that follows PP, stops at a point of FF and follows PP again.

Relations and Corners

The relation monoid ℛH\mathcal{R}_H of a set HH is the set of binary relations on HH under the path-order product, with the identity relation IHI_H as unit: for relations PP and RR on HH, (x,z)∈PR⇔(x,y)∈P and (y,z)∈R for some y∈H.(x, z) \in PR \iff (x, y) \in P \text{ and } (y, z) \in R \text{ for some } y \in H.(1)✦

The restricted identity IFI_F of a subset FF of HH is the relation on HH that relates each point of FF to itself and relates nothing else: IF={(x,x):x∈F}.I_F = \{(x, x) : x \in F\}.(2)✦

An idempotent dd of a monoid is nested in an idempotent ee, written d⊴ed \trianglelefteq e, when de=ed=dde = ed = d.

The corner eMeeMe of an idempotent ee of a monoid MM is the monoid of elements of MM fixed by multiplication with ee on both sides, eMe={z∈M:eze=z},eMe = \{z \in M : eze = z\},(3) under the product of MM, with identity ee.

The Claim

Theorem 1. Let HH be a set, PP an idempotent relation on HH and ii a relation on HH with iPi=iiPi = i, and let Q=PiPQ = PiP. Then Q2=QandQ⊴P.Q^2 = Q \quad\text{and}\quad Q \trianglelefteq P.(4)✦ Every relation ZZ on HH with QZQ=ZQZQ = Z and every relation AA on HH with iAi=AiAi = A satisfy P(iZi)P=Z,Q(PAP)Q=PAP,i(PAP)i=A.P(iZi)P = Z, \qquad Q(PAP)Q = PAP, \qquad i(PAP)i = A.(5)✦ If ii is idempotent as well, any two relations AA and BB on HH with iAi=AiAi = A and iBi=BiBi = B satisfy (PAP)(PBP)=P(AB)P.(PAP)(PBP) = P(AB)P.(6)✦ If i=IFi = I_F for a subset FF of HH, there is a monoid isomorphism ρ\rho from the corner QℛHQQ\mathcal{R}_HQ onto ℛF\mathcal{R}_F that restricts each relation to FF: ρ(Z)={(x,y)∈F×F:(x,y)∈Z}(Z∈QℛHQ).\rho(Z) = \{(x, y) \in F \times F : (x, y) \in Z\} \qquad (Z \in Q\mathcal{R}_HQ).(7)✦

In the paper, the result reads: for an idempotent P∈ℛHP \in \mathcal{R}_H, a subset F⊆HF \subseteq H and i=IFi = I_F with iPi=iiPi = i, the relation Q=PiPQ = PiP is idempotent, Q⊴PQ \trianglelefteq P, and Z↦iZiZ \mapsto iZi is a unital monoid isomorphism QℛHQ→ℛFQ\mathcal{R}_HQ \to \mathcal{R}_F with inverse A↦PAPA \mapsto PAP.

For i=IFi = I_F, the map ρ\rho of (7) is Z↦iZiZ \mapsto iZi with iZiiZi read as a relation on FF, and (5) makes A↦PAPA \mapsto PAP its inverse.

What Is Checked

The claim is stated over the relation monoid ℛH\mathcal{R}_H of a set HH, with the path-order product (1) and unit IHI_H, over the restricted identity (2) of a subset FF of HH, and over the corner (3) of the idempotent Q=PiPQ = PiP in ℛH\mathcal{R}_H, for an idempotent relation PP on HH and a relation ii on HH with iPi=iiPi = i.