OctoInformBeta

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

Lemma 3.9: Under the continuum hypothesis, the class KK is closed under isomorphism, ≤K\le_K refines substructure, and being an object does not depend on the presentation

Strong substructure in the array class is a coherent order.

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 array class KK is a class of structures in a countable relational language with a relation ≤K\le_K of strong substructure, built under the continuum hypothesis (CH), 2ℵ0=ℵ12^{\aleph_0}=\aleph_1. A structure belongs to KK, and one structure is a strong substructure of another, according to how the structures are presented by normal forms, descriptions of a structure by an index set, a dense base order and a family of bits, and to the maps between those normal forms. The question is whether KK meets the axioms of an abstract elementary class on isomorphism, on the order ≤K\le_K and on coherence, and whether the membership of a structure in KK is independent of the normal form chosen to present it, a normal form being an object when it satisfies the condition that defines KK.

Structures

A structure 𝒜\mathcal A in a relational vocabulary LL is a set, the universe of 𝒜\mathcal A, with an interpretation of each nn-ary symbol of LL as a set of nn-tuples from it.✦ A substructure 𝒜\mathcal A of ℬ\mathcal B, written 𝒜⊆ℬ\mathcal A\subseteq\mathcal B, is a structure whose universe is a subset of that of ℬ\mathcal B and whose relations are the restrictions of those of ℬ\mathcal B.✦ An isomorphism from 𝒜\mathcal A onto ℬ\mathcal B is a bijection between their universes under which each relation holds of a tuple exactly when it holds of the image of that tuple.✦

A class with strong maps in LL is a class KK of structures in LL together with a binary relation ≤K\le_K on structures in LL, called strong substructure.✦

Normal Forms

The array language is the relational language with unary sort symbols for the index, base, group and star points of a normal form, a unary row symbol for each pair k,n∈ℕk,n\in\mathbb N, a unary column symbol for each kk, and a unary symbol for each finite v⊆ℕv\subseteq\mathbb N that marks the star point vv. It also has a row projection of arity k+2k+2 for each k,nk,n, a column projection of arity k+3k+3 for each kk, binary symbols for order, incidence and bit, and ternary symbols for group addition, star addition, row action and column action.

A tuple tt from a set II is an injective map t:{0,…,n}→It\colon\{0,\dots,n\}\to I, and n+1n+1 is its length.✦ The subsequences of a tuple t:{0,…,n}→It\colon\{0,\dots,n\}\to I are the composites t∘et\circ e with order embeddings e:{0,…,m}→{0,…,n}e\colon\{0,\dots,m\}\to\{0,\dots,n\}, and the image of tt under an injection ff of II into another set is f∘tf\circ t.

A normal form M=(I,B,<,a)M=(I,B,<,a) consists of a nonempty index set II, a nonempty base order (B,<)(B,<) that is a dense linear order without endpoints in which every closed interval [x,y][x,y] is countable, and a bit a(t,n,b)∈{0,1}a(t,n,b)\in\{0,1\} for each tuple tt from II, each n∈ℕn\in\mathbb N and each b∈Bb\in B.✦ The points of MM are of six distinct kinds: an index point for each element of II, a base point for each element of BB, a group point for each finite s⊆Bs\subseteq B, a star point for each finite v⊆ℕv\subseteq\mathbb N, and a row (t,n,s)(t,n,s) and a column (t,b,v)(t,b,v) for each tuple tt from II, each n∈ℕn\in\mathbb N, each b∈Bb\in B and all finite s⊆Bs\subseteq B and v⊆ℕv\subseteq\mathbb N.✦ The bit of a row (t,n,s)(t,n,s) and a column (t,b,v)(t,b,v) is a(t,n,b)+1b∈s+1n∈vmod⁡2.a(t,n,b)+1_{b\in s}+1_{n\in v}\bmod 2.(1)✦

The structure of MM is the structure in the array language whose universe is the set of points of MM. In the structure of MM, each sort symbol holds of the points of its kind, the row symbol for (k,n)(k,n) of the rows (t,n,s)(t,n,s) with tt of length k+1k+1, the column symbol for kk of the columns whose tuple has length k+1k+1, and the symbol for vv of the star point vv alone. The row projection for (k,n)(k,n) holds of such a row (t,n,s)(t,n,s) followed by the index points t(0),…,t(k)t(0),\dots,t(k), and the column projection for kk of such a column (t,b,v)(t,b,v) followed by the base point bb and the index points t(0),…,t(k)t(0),\dots,t(k).✦ 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 symbol of a row (t,n,s)(t,n,s) and a column (t,b,v)(t,b,v) on the same tuple whose bit (1) is 11.✦ The group and star additions hold of the triples (s,s′,s△s′)(s,s',s\triangle s') of group points and of star points, the row action of a row (t,n,s)(t,n,s), a group point s′s' and the row (t,n,s△s′)(t,n,s\triangle s'), and the column action of a column (t,b,v)(t,b,v), a star point v′v' and the column (t,b,v△v′)(t,b,v\triangle v'); no symbol holds of any other tuple of points.✦

A presentation PP of a structure 𝒜\mathcal A in the array language is a normal form MPM_P together with an isomorphism πP\pi_P from the structure of MPM_P onto 𝒜\mathcal A.✦

For normal forms M=(IM,BM,<,aM)M=(I_M,B_M,<,a_M) and N=(IN,BN,<,aN)N=(I_N,B_N,<,a_N), a map f:M→Nf\colon M\to N consists of an injection fI:IM→INf_I\colon I_M\to I_N, an order embedding fB:BM→BNf_B\colon B_M\to B_N, a row shift ufu_f giving a finite uf(t,n)⊆BNu_f(t,n)\subseteq B_N for each tuple tt from IMI_M and each n∈ℕn\in\mathbb N, and a column shift wfw_f giving a finite wf(t,b)⊆ℕw_f(t,b)\subseteq\mathbb N for each such tt and each b∈BMb\in B_M, such that for all tt, nn and bb aN(fI∘t,n,fB(b))+1fB(b)∈uf(t,n)+1n∈wf(t,b)≡aM(t,n,b)(mod⁡2).a_N(f_I\circ t,\,n,\,f_B(b))+1_{f_B(b)\in u_f(t,n)}+1_{n\in w_f(t,b)}\equiv a_M(t,n,b) \pmod 2.(2)✦ The map ff sends an index point ii to fI(i)f_I(i), a base point bb to fB(b)f_B(b), a group point ss to fB[s]f_B[s] and a star point to itself, and it sends rows and columns by (t,n,s)↦(fI∘t,n,uf(t,n)△fB[s]),(t,b,v)↦(fI∘t,fB(b),wf(t,b)△v).(t,n,s)\mapsto\bigl(f_I\circ t,\,n,\,u_f(t,n)\triangle f_B[s]\bigr),\qquad (t,b,v)\mapsto\bigl(f_I\circ t,\,f_B(b),\,w_f(t,b)\triangle v\bigr).(3)✦ The composite g∘fg\circ f of f:M→Nf\colon M\to N and g:N→N′g\colon N\to N' is the map from MM to N′N' with index and base maps gI∘fIg_I\circ f_I and gB∘fBg_B\circ f_B and with the shifts ug∘f(t,n)=ug(fI∘t,n)△gB[uf(t,n)],wg∘f(t,b)=wg(fI∘t,fB(b))△wf(t,b).u_{g\circ f}(t,n)=u_g(f_I\circ t,n)\triangle g_B[u_f(t,n)],\qquad w_{g\circ f}(t,b)=w_g(f_I\circ t,f_B(b))\triangle w_f(t,b).(4)✦

Colors and Tests

The palette S=2ω/=*S=2^\omega/{=^*} is the set of binary sequences modulo equality outside a finite set✦, x=*yx=^*y when xx and yy differ at only finitely many places✦, and [x][x] is the color of xx✦. In a normal form MM the color of a tuple tt at b∈Bb\in B, and along a map f:M→Nf\colon M\to N the color of a tuple tt from IMI_M at b∈BNb\in B_N, are ct(b)=[a(t,⋅,b)],ctf(b)=[n↦aN(fI∘t,n,b)+1b∈uf(t,n)mod⁡2].c_t(b)=[a(t,\cdot,b)],\qquad c^f_t(b)=\bigl[\,n\mapsto a_N(f_I\circ t,n,b)+1_{b\in u_f(t,n)}\bmod 2\,\bigr].(5)

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✦, and the root of a position aa is ({a},0)(\{a\},0)✦. A diagram D=(E,R,ρ)D=(E,R,\rho) on AA consists 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.✦ A diagram DD is valid when EE is an equivalence relation, RR and ρ\rho respect EE, ρ(l)<ρ(l′)\rho(l)<\rho(l') whenever lRl′l\,R\,l', labels with the same RR-predecessors are EE-equivalent, and positions with EE-equivalent roots are equal.✦ The restriction D↾eD\restriction e of a diagram DD on AA along an injection e:A′→Ae\colon A'\to A is the diagram on A′A' under which labels are related and tagged as their images are under DD✦, the image of (J,i)(J,i) being (e[J],i)(e[J],i)✦. Under CH, fix an injection γ\gamma of the disjoint union over nn of the sets of diagrams on {0,…,n}\{0,\dots,n\} into SS; it is the coding of diagrams by colors.✦

A family of colors σe∈S\sigma_e\in S, one for each order embedding e:{0,…,m}→{0,…,n}e\colon\{0,\dots,m\}\to\{0,\dots,n\} with m∈ℕm\in\mathbb N, passes when there is a diagram dd on {0,…,n}\{0,\dots,n\} such that for every such ee d↾eis valid andγ(d↾e)=σe.d\restriction e\ \text{is valid and}\ \gamma(d\restriction e)=\sigma_e.(6)✦ For a coloring cc of the tuples from II by colors, a tuple tt from II of length n+1n+1 passes the test for cc when the family (c(t∘e))e(c(t\circ e))_e of the colors of its subsequences passes.✦

The Array Class

Assume CH. A normal form MM is an object when, for every tuple tt from II, the set {b∈B:tfails the test fors↦cs(b)}\{\,b\in B: t\ \text{fails the test for}\ s\mapsto c_s(b)\,\}(7)✦ is countable. A map f:M→Nf\colon M\to N of normal forms is strong when fB[BM]f_B[B_M] is convex in BNB_N and, at every b∈BN\fB[BM]b\in B_N\setminus f_B[B_M], every tuple tt from IMI_M passes the test for s↦csf(b)s\mapsto c^f_s(b).✦ For presentations PP of 𝒜\mathcal A and QQ of ℬ\mathcal B, a map f:MP→MQf\colon M_P\to M_Q is an inclusion when πQ(f(x))=πP(x)\pi_Q(f(x))=\pi_P(x) for every point xx of MPM_P, the action of ff on points being (3).✦

The array class KK is the class with strong maps in the array language whose members are the structures with a presentation whose normal form is an object. The strong substructure relation ≤K\le_K of KK is defined by: for structures 𝒜\mathcal A and ℬ\mathcal B in the array language, 𝒜≤Kℬ\mathcal A\le_K\mathcal B when there are presentations PP of 𝒜\mathcal A and QQ of ℬ\mathcal B whose normal forms are objects and a strong map f:MP→MQf\colon M_P\to M_Q that is an inclusion.

The Claim

Theorem 1 (Lemma 3.9). Assume CH, and let 𝒜\mathcal A, ℬ\mathcal B, 𝒞\mathcal C, 𝒜′\mathcal A' and ℬ′\mathcal B' be structures in the array language. If 𝒜∈K\mathcal A\in K and 𝒜\mathcal A is isomorphic to ℬ\mathcal B, then ℬ∈K.\mathcal B\in K.(8)✦ If 𝒜≤Kℬ\mathcal A\le_K\mathcal B, and φ\varphi is an isomorphism from 𝒜\mathcal A onto 𝒜′\mathcal A' and ψ\psi one from ℬ\mathcal B onto ℬ′\mathcal B' with φ(x)=ψ(x)\varphi(x)=\psi(x) for every element xx of 𝒜\mathcal A, then 𝒜′≤Kℬ′.\mathcal A'\le_K\mathcal B'.(9)✦ For 𝒜∈K\mathcal A\in K, 𝒜≤K𝒜.\mathcal A\le_K\mathcal A.(10)✦ If 𝒜≤Kℬ\mathcal A\le_K\mathcal B and ℬ≤K𝒜\mathcal B\le_K\mathcal A, then 𝒜=ℬ,\mathcal A=\mathcal B,(11)✦ and if 𝒜≤Kℬ\mathcal A\le_K\mathcal B and ℬ≤K𝒞\mathcal B\le_K\mathcal C, then 𝒜≤K𝒞.\mathcal A\le_K\mathcal C.(12)✦ If 𝒜≤Kℬ\mathcal A\le_K\mathcal B, then 𝒜⊆ℬ.\mathcal A\subseteq\mathcal B.(13)✦ If 𝒜⊆ℬ\mathcal A\subseteq\mathcal B, 𝒜≤K𝒞\mathcal A\le_K\mathcal C and ℬ≤K𝒞\mathcal B\le_K\mathcal C, then 𝒜≤Kℬ.\mathcal A\le_K\mathcal B.(14)✦ Let MM, NN and N′N' be normal forms. If f:M→Nf\colon M\to N and g:N→N′g\colon N\to N' are strong maps, then g∘fis strong.g\circ f\ \text{is strong}.(15)✦ If f:M→N′f\colon M\to N' is a strong map, and k:M→Nk\colon M\to N and g:N→N′g\colon N\to N' are maps with g∘k=fg\circ k=f, then kis strong.k\ \text{is strong}.(16)✦ If PP and QQ are presentations of the same structure 𝒜\mathcal A, then MPis an object⇔MQis an object.M_P\ \text{is an object}\iff M_Q\ \text{is an object}.(17)✦

What Is Checked

The claims (8) through (17) are stated under CH over structures in the array language, each with a set as its universe; over the array class KK and its relation ≤K\le_K, defined through presentations by normal forms that are objects and strong maps that are inclusions; and over maps of normal forms, their composites and the strong maps among them.

The library also shows that equality outside a finite set is an equivalence relation on 2ω2^\omega✦.