OctoInformBeta

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

Definition 2.1: A diagram (E,R,ρ)(E, R, \rho) is valid when EE is a congruence, ρ\rho rises along RR, RR is extensional and distinct roots are inequivalent

Valid diagrams on labels and their 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

Over a finite set of positions, a diagram presents a countable structure by naming its elements with labels and saying which labels name the same element, how the named elements are related and which countable ordinal each one carries. The definition says when such a presentation is valid and what structure a valid one presents.

Labels and Diagrams

A label on a set AA of positions is a pair (J,i)(J, i) with JJ a nonempty finite subset of AA and ii a natural number; LAL_A is the set of labels on AA: LA={(J,i):J⊆A finite,J≠∅,i∈ℕ}.L_A = \{(J, i) : J \subseteq A \text{ finite},\ J \neq \emptyset,\ i \in \mathbb{N}\}.(1)✦ The root of a position a∈Aa \in A is the label root⁡(a)=({a},0)∈LA.\operatorname{root}(a) = (\{a\}, 0) \in L_A.(2)✦

A tag is a countable ordinal, an element of ω1={α:α is an ordinal and |α|≤ℵ0}.\omega_1 = \{\alpha : \alpha \text{ is an ordinal and } |\alpha| \le \aleph_0\}.(3)✦ A diagram DD on AA is a triple (E,R,ρ)(E, R, \rho) of binary relations EE and RR on LAL_A and a map ρ\rho giving each label a tag: D=(E,R,ρ),E,R⊆LA×LA,ρ:LA→ω1.D = (E, R, \rho), \qquad E, R \subseteq L_A \times L_A, \qquad \rho : L_A \to \omega_1.(4)✦

The Definition

Definition 1. Let D=(E,R,ρ)D = (E, R, \rho) be a diagram on a set AA of positions. Then DD is valid when EE is an equivalence relation on LAL_A that is a congruence for RR and ρ\rho, that is, EE-equivalent labels are related by RR in the same way and carry the same tag, and, for all labels x,x′,y,y′∈LAx, x', y, y' \in L_A and all positions a,b∈Aa, b \in A, the remaining conditions hold: RR raises tags, RR is extensional (labels with the same RR-predecessors are EE-equivalent), and distinct roots are EE-inequivalent: xEx′ and yEy′⟹(xRy⇔x′Ry′),xEx′⟹ρ(x)=ρ(x′),xRy⟹ρ(x)<ρ(y),(zRx⇔zRy for every z∈LA)⟹xEy,root⁡(a)Eroot⁡(b)⟹a=b.\begin{gathered} x \mathrel{E} x' \text{ and } y \mathrel{E} y' \implies (x \mathrel{R} y \iff x' \mathrel{R} y'), \qquad x \mathrel{E} x' \implies \rho(x) = \rho(x'),\\ x \mathrel{R} y \implies \rho(x) < \rho(y),\\ \bigl(z \mathrel{R} x \iff z \mathrel{R} y \text{ for every } z \in L_A\bigr) \implies x \mathrel{E} y,\\ \operatorname{root}(a) \mathrel{E} \operatorname{root}(b) \implies a = b. \end{gathered}(5)✦ For a valid diagram DD, writing x/Ex/E for the EE-class of a label xx, the quotient of DD is the set QD=LA/E={x/E:x∈LA},Q_D = L_A/E = \{x/E : x \in L_A\},(6)✦ with the relation R‾\bar R induced by RR, (x/E)R‾(y/E)⇔xRy,(x/E) \mathrel{\bar R} (y/E) \iff x \mathrel{R} y,(7)✦ and the tag ρ‾\bar\rho induced by ρ\rho, ρ‾(x/E)=ρ(x).\bar\rho(x/E) = \rho(x).(8)✦

In the paper, the definition reads: for the set [k][k] of kk positions, with labels Lk={(J,i):∅≠J⊆[k],i<ω}L_k = \{(J, i) : \emptyset \neq J \subseteq [k],\ i < \omega\}, an arity-kk diagram is a triple (E,R,ρ)(E, R, \rho) of binary relations EE and RR on LkL_k and a map ρ:Lk→ω1\rho : L_k \to \omega_1, and it is valid if EE is an equivalence relation respected by RR and ρ\rho, if on the quotient by EE the relation yRxy \mathrel{R} x implies ρ(y)<ρ(x)\rho(y) < \rho(x) and RR is extensional, and if the labels ({j},0)(\{j\}, 0) for j∈[k]j \in [k] lie in distinct EE-classes.

What Is Checked

The definition is stated over an arbitrary set AA of positions: the labels (1) with the roots (2), the tags in ω1\omega_1 (3), the diagrams (4), the conditions for validity (5), and, for a valid diagram, the quotient QDQ_D (6) with the induced relation R‾\bar R (7) and the induced tag ρ‾\bar\rho (8).