OctoInformBeta

OpenAI preprint, September 2026 · §3. The abstract elementary class

Definition 3.2: How bits a(t,n,b)a(t,n,b) become a relational structure on rows and columns, presented up to isomorphism and coded on an ordinal

Basic structures in normal form and their coded copies.

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

Section 3 builds its abstract elementary class KK on basic structures, and Definition 3.2 says what a basic structure is. It starts from a family of matrices with entries in {0,1}\{0,1\}: an index set II, a dense linear order BB, and for each tuple tt of distinct elements of II a matrix with rows n∈ℕn \in \mathbb{N}, columns b∈Bb \in B and entries a(t,n,b)a(t,n,b).

The entries are not elements of the structure. Each row and each column of each matrix is spread into a fiber of points, the finite subsets of BB acting on the row fibers and those of ℕ\mathbb{N} on the column fibers by symmetric difference, and a bit relation between a row fiber and a column fiber shows the entry up to the flips these translations make. A structure of this kind is handled through a normal form, the data II, BB, aa with an isomorphism from the structure they build onto it, and each normal form is coded as a structure whose universe is an ordinal.

Tuples and Relational Structures

A tuple from a set II is an injective map t:{0,…,k}→It : \{0,\dots,k\} \to I for some k∈ℕk \in \mathbb{N}, of length k+1k+1.✦ The set of tuples from II is T(I)T(I).

A vocabulary L=(Ln)n∈ℕL = (L_n)_{n \in \mathbb{N}} gives for each nn a set LnL_n of nn-ary relation symbols. A relational structure ℛ\mathcal{R} in LL consists of a set RR, its universe, and for each nn and each σ∈Ln\sigma \in L_n an interpretation σℛ⊆Rn\sigma^{\mathcal{R}} \subseteq R^n.✦

The Definition

Definition 1 (Basic structures in normal form). A normal form MM consists of a nonempty set II, the index set; a nonempty dense linear order (B,<)(B,<) without endpoints in which every closed interval [b,b′][b,b'] is countable, the base order; and a bit a(t,n,b)∈{0,1}a(t,n,b) \in \{0,1\} for each tuple t∈T(I)t \in T(I), each n∈ℕn \in \mathbb{N} and each b∈Bb \in B: M=(I,B,<,a),a:T(I)×ℕ×B→{0,1}.M = (I, B, <, a), \qquad a : T(I) \times \mathbb{N} \times B \to \{0,1\}.(1)✦ For sets II and BB, the set of points is P(I,B)=I⊔B⊔[B]<ω⊔[ℕ]<ω⊔(T(I)×ℕ×[B]<ω)⊔(T(I)×B×[ℕ]<ω),P(I,B) = I \sqcup B \sqcup [B]^{<\omega} \sqcup [\mathbb{N}]^{<\omega} \sqcup \bigl(T(I) \times \mathbb{N} \times [B]^{<\omega}\bigr) \sqcup \bigl(T(I) \times B \times [\mathbb{N}]^{<\omega}\bigr),(2)✦ the points of MM are P(M)=P(I,B)P(M) = P(I,B), with rows (t,n,s)(t,n,s) and columns (t,b,v)(t,b,v).

The relation symbols form a countable set Σ\Sigma; by their arity ar⁡(σ)\operatorname{ar}(\sigma) they are ar⁡=1:PI,PB,PG,P*,Rowk,n,Colk,Labv,ar⁡=2:<,Inc,Bit,ar⁡=3:+G,+*,αrow,αcol,ar⁡=k+2:πk,nrow,ar⁡=k+3:πkcol,k,n∈ℕ,v∈[ℕ]<ω,\begin{array}{ll} \operatorname{ar} = 1: & P_I,\ P_B,\ P_G,\ P_*,\ \mathrm{Row}_{k,n},\ \mathrm{Col}_k,\ \mathrm{Lab}_v,\\ \operatorname{ar} = 2: & <,\ \mathrm{Inc},\ \mathrm{Bit},\\ \operatorname{ar} = 3: & {+_G},\ {+_*},\ \alpha_{\mathrm{row}},\ \alpha_{\mathrm{col}},\\ \operatorname{ar} = k+2: & \pi^{\mathrm{row}}_{k,n},\\ \operatorname{ar} = k+3: & \pi^{\mathrm{col}}_{k}, \end{array} \qquad k, n \in \mathbb{N},\ v \in [\mathbb{N}]^{<\omega},(3)✦ and the language of arity nn is Ln={σ∈Σ:ar⁡(σ)=n},L=(Ln)n∈ℕ.L_n = \{\sigma \in \Sigma : \operatorname{ar}(\sigma) = n\}, \qquad L = (L_n)_{n \in \mathbb{N}}.(4)✦

For a matrix μ:ℕ×B→{0,1}\mu : \mathbb{N} \times B \to \{0,1\}, the bit at a row index nn, a finite s⊆Bs \subseteq B, a column index bb and a finite v⊆ℕv \subseteq \mathbb{N} is βμ(n,s,b,v)=μ(n,b)+1b∈s+1n∈v(mod⁡2).\beta_\mu(n,s,b,v) = \mu(n,b) + 1_{b \in s} + 1_{n \in v} \pmod 2.(5)✦

The raw relation RM(σ,x‾)R_M(\sigma,\bar x) of MM, between a symbol σ∈Σ\sigma \in \Sigma and a finite sequence x‾\bar x of points of any length, holds exactly in the cases below, written σ(x‾)\sigma(\bar x), where i∈Ii \in I, b,b′∈Bb, b' \in B, n∈ℕn \in \mathbb{N}, s,s′,u∈[B]<ωs, s', u \in [B]^{<\omega}, v,v′,w∈[ℕ]<ωv, v', w \in [\mathbb{N}]^{<\omega}, t∈T(I)t \in T(I) has length k+1k+1, and at=a(t,⋅,⋅)a_t = a(t,\cdot,\cdot) is the matrix of tt: PI(i),PB(b),PG(s),P*(v),Labv(v),Rowk,n((t,n,s)),Colk((t,b,v)),πk,nrow((t,n,s),t(0),…,t(k)),πkcol((t,b,v),b,t(0),…,t(k)),b<b′ for b<b′ in B,Inc(b,s) for b∈s,Bit((t,n,s),(t,b,v)) for βat(n,s,b,v)=1,+G(s,s′,s△s′),+*(v,v′,v△v′),αrow((t,n,s),u,(t,n,s△u)),αcol((t,b,v),w,(t,b,v△w)).\begin{aligned} &P_I(i),\quad P_B(b),\quad P_G(s),\quad P_*(v),\quad \mathrm{Lab}_v(v),\quad \mathrm{Row}_{k,n}\bigl((t,n,s)\bigr),\quad \mathrm{Col}_k\bigl((t,b,v)\bigr),\\ &\pi^{\mathrm{row}}_{k,n}\bigl((t,n,s), t(0),\dots,t(k)\bigr),\quad \pi^{\mathrm{col}}_k\bigl((t,b,v), b, t(0),\dots,t(k)\bigr),\\ &b < b' \text{ for } b < b' \text{ in } B,\quad \mathrm{Inc}(b,s) \text{ for } b \in s,\quad \mathrm{Bit}\bigl((t,n,s),(t,b,v)\bigr) \text{ for } \beta_{a_t}(n,s,b,v) = 1,\\ &{+_G}(s,s',s \mathbin{\triangle} s'),\quad {+_*}(v,v',v \mathbin{\triangle} v'),\\ &\alpha_{\mathrm{row}}\bigl((t,n,s),u,(t,n,s \mathbin{\triangle} u)\bigr),\quad \alpha_{\mathrm{col}}\bigl((t,b,v),w,(t,b,v \mathbin{\triangle} w)\bigr). \end{aligned}(6)✦ For σ∈Ln\sigma \in L_n, the relation of MM is σM={x‾∈P(M)n:RM(σ,x‾)}.\sigma^M = \{\bar x \in P(M)^n : R_M(\sigma,\bar x)\}.(7)✦

A presentation of a relational structure ℛ\mathcal{R} in LL is a normal form MM with a bijection π:P(M)→R\pi : P(M) \to R such that for all nn, σ∈Ln\sigma \in L_n and x‾∈P(M)n\bar x \in P(M)^n πx‾∈σℛ⇔x‾∈σM,\pi\bar x \in \sigma^{\mathcal{R}} \iff \bar x \in \sigma^M,(8)✦

For a normal form MM, a set AA and a bijection θ:P(M)→A\theta : P(M) \to A, the structure 𝒜θ(M)\mathcal{A}_\theta(M) of MM on AA is the relational structure in LL with universe AA and relations σ𝒜θ(M)={θx‾:x‾∈σM}\sigma^{\mathcal{A}_\theta(M)} = \{\theta\bar x : \bar x \in \sigma^M\}.✦ Let κM\kappa_M be the initial ordinal of cardinality |P(M)||P(M)|, as a von Neumann ordinal, and θM:P(M)→κM\theta_M : P(M) \to \kappa_M a fixed bijection.✦ The coded structure of MM is the structure of MM on κM\kappa_M: 𝒞(M)=𝒜θM(M).\mathcal{C}(M) = \mathcal{A}_{\theta_M}(M).(9)✦

In the paper, the result reads: a basic structure has sorts II and BB, with BB a nonempty dense linear order without endpoints whose bounded intervals are countable, groups G(B)≅[B]<ωG(B) \cong [B]^{<\omega} and G*≅[ω]<ωG_* \cong [\omega]^{<\omega} under symmetric difference, for every tuple tt row fibers Zt,nZ_{t,n} that are G(B)G(B)-torsors and column fibers Wt,bW_{t,b} that are G*G_*-torsors, and a bit relation ee with e(z+u,w+v)=e(z,w)+1b∈supp⁡u+1n∈v(mod⁡2)e(z+u,w+v) = e(z,w) + 1_{b \in \operatorname{supp} u} + 1_{n \in v} \pmod 2 for z∈Zt,nz \in Z_{t,n} and w∈Wt,bw \in W_{t,b}, in the countable relational language listed after the definition, its fibers Zt,nZ_{t,n} and Wt,bW_{t,b} standing for the rows (t,n,s)(t,n,s) and the columns (t,b,v)(t,b,v) here.

What Is Checked

Definition 3.2 is stated over the tuples T(I)T(I) from the index set and over the relational structures in LL whose universe is a set.