OctoInformBeta

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

Lemma 3.8: Colors ct(b)=[a(t,⋅,b)]c_t(b) = [a(t,\cdot,b)], an object under the continuum hypothesis when the base order BB is countable, and a presented realization on an ordinal

Arrays of bits as normal forms, realized on ordinals.

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

The abstract elementary class KK is built on basic structures: many-sorted structures over an index set II and a base order BB, in which rows and columns attached to the tuples from II are joined by a bit relation. The bits give colors, elements of a palette SS; under the continuum hypothesis (CH), 2ℵ0=ℵ12^{\aleph_0} = \aleph_1, colors code diagrams on finite sets of positions, and a test on these codes singles out, among the basic structures, those that are objects of KK.

Take a nonempty set II, a base order BB and an arbitrary array of bits a(t,n,b)a(t, n, b), one for each tuple tt from II (an injective map t:{0,…,k}→It\colon \{0, \dots, k\} \to I), each n∈ℕn \in \mathbb{N} and each b∈Bb \in B. The question is whether some basic structure carries exactly these bits, with which colors, and when it is an object of KK; the library handles a basic structure in normal form and codes the normal forms as structures on ordinals.

Normal Forms

The length of a tuple t:{0,…,n}→It\colon \{0, \dots, n\} \to I is n+1n + 1, and its subsequences are the composites t∘et \circ e with the order embeddings e:{0,…,m}→{0,…,n}e\colon \{0, \dots, m\} \to \{0, \dots, n\}.✦

A normal form M=(I,B,<,a)M = (I, B, <, a) consists of a nonempty set II, the index set; a nonempty set BB with a dense linear order << without least or greatest element in which every closed interval [x,y][x, y] is countable, the base order; and a bit a(t,n,b)∈{0,1}a(t, n, b) \in \{0, 1\} for every tuple tt from II, every n∈ℕn \in \mathbb{N} and every b∈Bb \in B.✦

The points of MM form the set PMP_M, the disjoint union of six kinds: an index point for each element of II, a base point for each element of BB, a group point for each finite subset of BB, a star point for each finite subset of ℕ\mathbb{N}, a row (t,n,s)(t, n, s) for each tuple tt from II, each n∈ℕn \in \mathbb{N} and each finite s⊆Bs \subseteq B, and a column (t,b,v)(t, b, v) for each tuple tt from II, each b∈Bb \in B and each finite v⊆ℕv \subseteq \mathbb{N}.✦ The bit of a row and a column of the same tuple is β((t,n,s),(t,b,v))=a(t,n,b)+𝟏b∈s+𝟏n∈v(mod⁡2).\beta\bigl((t, n, s), (t, b, v)\bigr) = a(t, n, b) + \mathbf{1}_{b \in s} + \mathbf{1}_{n \in v} \pmod 2 .(1)✦

The Array Language

The array language is a countable relational language, and a normal form MM interprets each nn-ary symbol σ\sigma as a relation σM⊆PMn\sigma^M \subseteq P_M^n that fails on points of the wrong kinds. Its unary symbols are the four sort symbols, for the index, base, group and star points; for all kk and nn, a symbol for the rows (t,n,s)(t, n, s) with tt of length k+1k + 1; for each kk, a symbol for the columns whose tuple has length k+1k + 1; and for each finite u⊆ℕu \subseteq \mathbb{N}, a label true of the star point uu alone. The row projection for kk and nn, of arity k+2k + 2, holds of such a row followed by the index points t(0),…,t(k)t(0), \dots, t(k), and the column projection for kk, of arity k+3k + 3, of a column (t,b,v)(t, b, v) with tt of length k+1k + 1 followed by the base point bb and the same index points.

The order holds of base points b<b′b < b', incidence of a base point bb and a group point ss with b∈sb \in s, and the bit relation of a row (t,n,s)(t, n, s) and a column (t′,b,v)(t', b, v) with t=t′t = t' whose bit (1) is 11. Group and star addition hold of the triples (s,u,s△u)(s, u, s \mathbin{\triangle} u) of group points and of star points. The row action holds of ((t,n,s),u,(t,n,s△u))((t, n, s), u, (t, n, s \mathbin{\triangle} u)) for a group point uu, and the column action of ((t,b,v),u,(t,b,v△u))((t, b, v), u, (t, b, v \mathbin{\triangle} u)) for a star point uu.

A structure NN in the array language is a set, its universe, with an nn-ary relation σN\sigma^N on it for each nn-ary symbol σ\sigma.✦ For a set AA and a bijection e:PM→Ae\colon P_M \to A, the structure MeM_e is the structure with universe AA that MM induces through ee: σMe(y1,…,yn)⇔σM(e−1(y1),…,e−1(yn))(y1,…,yn∈A).\sigma^{M_e}(y_1, \dots, y_n) \iff \sigma^M\bigl(e^{-1}(y_1), \dots, e^{-1}(y_n)\bigr) \qquad (y_1, \dots, y_n \in A).(2)✦

A presentation of a structure NN in the array language is a normal form MM together with a bijection ee of PMP_M onto the universe of NN that respects every symbol: σN(e(x1),…,e(xn))\sigma^N(e(x_1), \dots, e(x_n)) holds exactly when σM(x1,…,xn)\sigma^M(x_1, \dots, x_n) does.✦

The canonical bijection πX\pi_X of a set XX is a bijection, fixed once and for all, of XX onto the von Neumann ordinal κX\kappa_X, the initial ordinal of |X||X|.✦ For a normal form MM we write κM\kappa_M and πM\pi_M for κPM\kappa_{P_M} and πPM\pi_{P_M}.

Colors and the Test

A binary sequence is a map a:ℕ→{0,1}a\colon \mathbb{N} \to \{0, 1\}, an element of 2ω2^\omega.✦ Two sequences aa and a′a' are equal outside a finite set, a=*a′a =^* a', when they differ at only finitely many nn.✦ The palette S=2ω/=*S = 2^\omega/{=^*} is the set of =*=^*-classes of binary sequences✦, and the color [a]∈S[a] \in S of a sequence aa is its class.✦

A label on a set AA of positions is a pair (J,i)(J, i) of a nonempty finite J⊆AJ \subseteq A and an i∈ℕi \in \mathbb{N}✦, and the root of a position xx is the label ({x},0)(\{x\}, 0).✦ A diagram on AA is a triple D=(E,R,ρ)D = (E, R, \rho) of binary relations EE and RR on the labels on AA and a tag ρ(l)∈ω1\rho(l) \in \omega_1 for each label ll.✦ For an injection e:A′→Ae\colon A' \to A, the restriction D↾eD \restriction e is the diagram on A′A' that DD induces through ee: a label on A′A' is EE-related or RR-related to another exactly when their images under ee are, and takes the tag of its image, the image of (J,i)(J, i) being (e[J],i)(e[J], i).✦

A diagram (E,R,ρ)(E, R, \rho) is valid when EE is an equivalence relation respected by RR and ρ\rho, ρ(l)<ρ(l′)\rho(l) < \rho(l') whenever lRl′l \mathrel{R} l', labels with the same RR-predecessors are EE-equivalent, and distinct positions have roots in distinct EE-classes.✦

Under CH, the coding γ\gamma of diagrams is an injection into SS of the disjoint union, over n∈ℕn \in \mathbb{N}, of the sets of diagrams on {0,…,n}\{0, \dots, n\}.✦

Assume CH, let cc color the tuples from II by SS, and let tt be a tuple of length n+1n + 1. The tuple tt passes the test of cc when there is a diagram dd on {0,…,n}\{0, \dots, n\} such that for every mm and every order embedding e:{0,…,m}→{0,…,n}e\colon \{0, \dots, m\} \to \{0, \dots, n\} the restriction d↾ed \restriction e is valid and codes the color of the subsequence t∘et \circ e: γ(d↾e)=c(t∘e).\gamma(d \restriction e) = c(t \circ e).(3)✦

The Claim

Theorem 1. Let M=(I,B,<,a)M = (I, B, <, a) be a normal form. The color of a tuple tt from II at a point bb of BB is the color of the sequence of its bits at bb, ct(b)=[n↦a(t,n,b)]∈S.c_t(b) = [\, n \mapsto a(t, n, b) \,] \in S .(4)✦ Under CH, MM is an object when, for every tuple tt from II, the points bb of BB at which tt fails the test of the coloring c⋅(b):r↦cr(b)c_{\cdot}(b)\colon r \mapsto c_r(b) form a countable set.✦ If CH holds and BB is countable, then M is an object.M \text{ is an object.}(5)✦ The coded structure 𝒞(M)\mathcal{C}(M) of MM is the structure on the ordinal κM\kappa_M that MM induces through πM\pi_M, 𝒞(M)=MπM,\mathcal{C}(M) = M_{\pi_M},(6)✦ and (M,πM) is a presentation of 𝒞(M).(M, \pi_M) \text{ is a presentation of } \mathcal{C}(M).(7)✦

In the paper, the result reads: for every nonempty II, every order BB as in Definition 3.2(a) and every family at,b∈2ωa_{t,b} \in 2^\omega, there is a basic structure whose index and base sorts are copies of II and BB and whose colors are ct(b)=[at,b]c_t(b) = [a_{t,b}], and if BB is countable, every basic structure with base BB is an object; the paper’s at,ba_{t,b} is the sequence n↦a(t,n,b)n \mapsto a(t, n, b) here.

What Is Checked

The claim is stated over normal forms with their points and the relations of the array language, the palette SS of colors, the coding γ\gamma of diagrams by colors and the test it defines under CH, the structures MeM_e and their presentations, and the canonical bijections πX\pi_X onto initial ordinals.

The library proves that =*=^* is an equivalence relation on 2ω2^\omega✦, and that for every set AA and every bijection e:PM→Ae\colon P_M \to A the pair (M,e)(M, e) is a presentation of MeM_e.✦