OctoInformBeta

OpenAI preprint, September 2026 · §2. Countable diagrams and their tests

Lemma 2.4: For valid D=D′↾eD = D'{\restriction}e, [x]D↦[e(x)]D′[x]_D \mapsto [e(x)]_{D'} is injective; between stages of Lemma 5.2 it keeps tags and preserves and reflects RR

Restriction along an injection gives an injective map of quotients.

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 diagram on a set AA of positions presents a structure, its quotient, whose elements are named by labels built from finite subsets of AA. When the positions move along an injection e:A→Be\colon A \to B, the labels move with them, and the question is when this induces a map between the presented structures, and whether that map is injective. Lemma 2.4 of the paper takes the case of a diagram on AA that is the restriction along ee of a diagram on BB; it also takes the finite stages in the proof of Lemma 5.2 of the paper, diagrams on finite sets X⊆YX \subseteq Y of a linear order, where one asks in addition whether the maps respect the relation and the tags of the diagrams.

Diagrams and Their Quotients

A label on a set AA of positions is a pair (J,i)(J, i) with JJ a nonempty finite subset of AA and i∈ℕi \in \mathbb{N}✦; the root of a position p∈Ap \in A is the label ({p},0)(\{p\}, 0).✦ An injection e:A→Be\colon A \to B carries a label on AA to the label on BB with the image set and the same index: e(J,i)=(e[J],i).e(J, i) = (e[J], i).(1)✦

A diagram DD on AA is a triple (E,R,ρ)(E, R, \rho) in which EE and RR are binary relations on the labels on AA and ρ\rho assigns to each label a tag in ω1\omega_1, tags being compared as ordinals.✦ A diagram D=(E,R,ρ)D = (E, R, \rho) on AA is valid when EE is an equivalence relation, RR and ρ\rho are invariant under EE, distinct positions have EE-inequivalent roots, and for all labels aa and bb aRb⟹ρ(a)<ρ(b),(∀z(zRa⇔zRb))⟹aEb.a \mathrel{R} b \implies \rho(a) < \rho(b), \qquad \bigl(\forall z\;(z \mathrel{R} a \iff z \mathrel{R} b)\bigr) \implies a \mathrel{E} b.(2)✦

The restriction of a diagram D′=(E′,R′,ρ′)D' = (E', R', \rho') on BB along an injection e:A→Be\colon A \to B is the diagram D′↾e=(E,R,ρ)D'{\restriction}e = (E, R, \rho) on AA that D′D' induces through ee: for labels aa and bb on AA, aEb⇔e(a)E′e(b),aRb⇔e(a)R′e(b),ρ(a)=ρ′(e(a)).a \mathrel{E} b \iff e(a) \mathrel{E'} e(b), \qquad a \mathrel{R} b \iff e(a) \mathrel{R'} e(b), \qquad \rho(a) = \rho'(e(a)).(3)✦

The quotient QDQ_D of a valid diagram D=(E,R,ρ)D = (E, R, \rho) on AA is the set of EE-classes [a]D[a]_D of labels on AA✦, with the relation and the tag passed to the classes: [a]DR[b]D⇔aRb,ρ([a]D)=ρ(a).[a]_D \mathrel{R} [b]_D \iff a \mathrel{R} b, \qquad \rho([a]_D) = \rho(a).(4)

Finite Stages

The proof of Lemma 5.2 fixes a linear order LL and, for each n∈ℕn \in \mathbb{N}, a diagram dnd_n on the positions {0,…,n−1}\{0, \dots, n-1\}, such that every dnd_n is valid and the sequence is coherent: for m≤nm \le n, dmd_m is the restriction of dnd_n along every order embedding of {0,…,m−1}\{0, \dots, m-1\} into {0,…,n−1}\{0, \dots, n-1\}. For a finite set X⊆LX \subseteq L, let εX:X→{0,…,|X|−1}\varepsilon_X\colon X \to \{0, \dots, |X|-1\} be the order isomorphism; the stage diagram on XX is ΔX=d|X|↾εX,\Delta_X = d_{|X|}{\restriction}\varepsilon_X,(5)✦ and its quotient F(X)=QΔXF(X) = Q_{\Delta_X} carries the relation RXR_X and the tag ρX\rho_X of (4). For finite sets X⊆Y⊆LX \subseteq Y \subseteq L, ιXY:X→Y\iota_{XY}\colon X \to Y is the inclusion✦, and the transition map tXY:F(X)→F(Y)t_{XY}\colon F(X) \to F(Y) is the map of quotients that carries labels along ιXY\iota_{XY}.✦

The Claim

Theorem 1. Let D′D' be a valid diagram on BB, let e:A→Be\colon A \to B be an injection, and let D=D′↾eD = D'{\restriction}e be valid. Then carrying labels along ee gives a well-defined injective map e‾:QD→QD′\bar e\colon Q_D \to Q_{D'}✦ with e‾([x]D)=[e(x)]D′for every label x on A.\bar e([x]_D) = [e(x)]_{D'} \quad \text{for every label } x \text{ on } A.(6)✦ Let X⊆YX \subseteq Y be finite subsets of LL. Then the transition map tXYt_{XY} is injective, and for all x,y∈F(X)x, y \in F(X) xRXy⇔tXY(x)RYtXY(y),x \mathrel{R_X} y \iff t_{XY}(x) \mathrel{R_Y} t_{XY}(y),(7)✦ ρX(x)=ρY(tXY(x)).\rho_X(x) = \rho_Y(t_{XY}(x)).(8)✦

In the paper, the result reads: if the test passes and ∅≠J⊆[k]\emptyset \neq J \subseteq [k], then ℓJ\ell_J induces an injective map QDJ→QD[k]Q_{D_J} \to Q_{D_{[k]}} that preserves tags and preserves and reflects RR, and these maps compose, with J⊆[k]J \subseteq [k] in the role of X⊆YX \subseteq Y; here [k][k] is the paper’s finite set of positions, DJD_J and D[k]D_{[k]} are the paper’s diagrams on JJ and on [k][k], ℓJ\ell_J is the paper’s map carrying JJ into [k][k], and the test is the paper’s check that these diagrams fit together.

What Is Checked

The claim is stated over valid diagrams D′D' on BB and D=D′↾eD = D'{\restriction}e on AA, for an injection e:A→Be\colon A \to B, with their quotients QDQ_D and QD′Q_{D'}; and over a linear order LL with diagrams dnd_n on {0,…,n−1}\{0, \dots, n-1\} under the validity and coherence hypotheses, through the stage quotients F(X)F(X), their relations RXR_X and tags ρX\rho_X, and the transition maps tXYt_{XY}.

From those hypotheses the library proves that every stage diagram ΔX\Delta_X is valid✦, and that ΔX=ΔY↾ιXY\Delta_X = \Delta_Y{\restriction}\iota_{XY} whenever X⊆YX \subseteq Y.✦