OctoInformBeta

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

Theorem 3.13: Under the continuum hypothesis, KK with its strong substructure relation ≤K\le_K meets every axiom, chains included, and has Löwenheim-Skolem number ℵ0\aleph_0

The array class is an abstract elementary class.

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 continuum hypothesis (CH) is the statement 2ℵ0=ℵ12^{\aleph_0} = \aleph_1.✦ Under CH one has a class KK of structures in a countable relational language, the array class, built from arrays of bits over dense linear orders, with a relation ≤K\le_K of strong substructure given by maps of arrays. The question is whether (K,≤K)(K, \le_K) satisfies the axioms of an abstract elementary class, the chain axioms included, and how small a Löwenheim-Skolem bound it admits.

Abstract Elementary Classes

Fix a vocabulary LL, a set of relation symbols, each with an arity n∈ℕn \in \mathbb{N}. A relational structure MM in LL is a set |M||M|, its universe, with an interpretation of each nn-ary symbol of LL as a set of nn-tuples from |M||M|; its cardinality ∥M∥\|M\| is that of |M||M|.✦ A substructure MM of a structure NN, written M⊆NM \subseteq N, is a structure in LL whose universe is contained in |N||N| and whose relations are the restrictions to |M||M| of those of NN.✦ An isomorphism of MM onto NN is a bijection of |M||M| onto |N||N| that preserves every relation in both directions.✦ A structure UU is the union of a family (Mi)i∈ι(M_i)_{i \in \iota} of structures, indexed by a set ι\iota, when every MiM_i is a substructure of UU and every element of |U||U| lies in some |Mi||M_i|.✦

A class with strong maps (K,≤K)(K, \le_K) in LL is a class KK of structures in LL, the models of KK, together with a binary relation ≤K\le_K on structures in LL; M≤KNM \le_K N says that MM is a strong substructure of NN.✦

A Löwenheim-Skolem bound for KK is an infinite cardinal θ\theta, at least the number of symbols of LL, such that for every model MM of KK and every subset AA of |M||M| there is a model N≤KMN \le_K M with A⊆|N|A \subseteq |N| and ∥N∥≤|A|+θ.\|N\| \le |A| + \theta .(1)✦ The Löwenheim-Skolem number LS(K)\mathrm{LS}(K) of KK is the least Löwenheim-Skolem bound for KK.✦

A class with strong maps (K,≤K)(K, \le_K) in LL is an abstract elementary class when it satisfies the following axioms.

  1. The relation ≤K\le_K holds only between models of KK and is a partial order on them.

  2. If M≤KNM \le_K N, then M⊆NM \subseteq N.

  3. Coherence: if M0⊆M1M_0 \subseteq M_1, M0≤KM2M_0 \le_K M_2 and M1≤KM2M_1 \le_K M_2, then M0≤KM1M_0 \le_K M_1.

  4. A structure isomorphic to a model of KK is a model of KK, and if M≤KNM \le_K N and isomorphisms ee of MM onto M′M' and ff of NN onto N′N' agree on |M||M|, then M′≤KN′M' \le_K N'.

  5. Chains: for every nonzero ordinal γ\gamma and every family (Mi)i<γ(M_i)_{i < \gamma} of models of KK with Mi≤KMjM_i \le_K M_j for i≤ji \le j, there is a model UU of KK that is the union of the family, with Mi≤KUM_i \le_K U for every ii, and with U≤KNU \le_K N for every model NN such that Mi≤KNM_i \le_K N for every ii.

  6. KK has a Löwenheim-Skolem bound.

The Array Class

A tuple from a set II is an injective map tt from {0,…,n}\{0, \dots, n\} into II, for some n∈ℕn \in \mathbb{N}, and n+1n + 1 is the length of tt.✦ The subsequence of tt along an order embedding ee of {0,…,m}\{0, \dots, m\} into {0,…,n}\{0, \dots, n\} is the tuple t∘et \circ e✦, and the image of tt under an injection ff of II into a set JJ is the tuple f∘tf \circ t from JJ.✦

The palette S=2ω/=*S = 2^\omega/{=^*} is the set of binary sequences a:ℕ→{0,1}a\colon \mathbb{N} \to \{0, 1\} modulo equality outside a finite set, a=*a′a =^* a' holding when aa and a′a' differ at only finitely many places.✦ The color [a][a] of a sequence aa is its class in SS.✦

Let AA be a set of positions. A label on AA 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 aa is the label ({a},0)(\{a\}, 0)✦, and an injection ee of a set A′A' into AA carries a label (J,i)(J, i) on A′A' to the label (e[J],i)(e[J], i) on AA.✦ A diagram on AA is a triple D=(E,R,ρ)D = (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.✦ The diagram DD is valid when EE is an equivalence relation, RR and ρ\rho are compatible with EE, ρ(x)<ρ(y)\rho(x) < \rho(y) as ordinals whenever xRyx \mathrel{R} y, any two labels with the same RR-predecessors are EE-equivalent, and positions with EE-equivalent roots are equal.✦ The restriction D↾eD \upharpoonright e of DD along an injection ee of A′A' into AA is the diagram (E′,R′,ρ′)(E', R', \rho') on A′A' with xE′yx \mathrel{E'} y when e(x)Ee(y)e(x) \mathrel{E} e(y), xR′yx \mathrel{R'} y when e(x)Re(y)e(x) \mathrel{R} e(y), and ρ′(x)=ρ(e(x))\rho'(x) = \rho(e(x)).✦

Under CH, fix an injection of the set of all diagrams on the positions {0,…,n}\{0, \dots, n\}, for all n∈ℕn \in \mathbb{N} together, into SS; the code of a diagram is its image under this injection.✦ A family ss assigning a color s(e)∈Ss(e) \in S to every order embedding ee of some {0,…,m}\{0, \dots, m\} into {0,…,n}\{0, \dots, n\} passes when there is a diagram dd on {0,…,n}\{0, \dots, n\} such that, for every such ee, the restriction d↾ed \upharpoonright e is valid and its code is s(e)s(e).✦ If cc assigns a color to each tuple from II, a tuple tt from II passes the test for cc when the family e↦c(t∘e)e \mapsto c(t \circ e) of the colors of its subsequences passes.✦

A normal form M=(I,B,<,a)M = (I, B, <, a) consists of a nonempty index set II, a nonempty set BB with a linear order <<, 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 base order is dense, has no least and no greatest element, and is locally countable, every closed interval [x,y][x, y] being countable.✦ The color of tt at bb is ct(b)=[a(t,⋅,b)]c_t(b) = [a(t, \cdot, b)].✦

The carrier of MM is the set of its points✦, which 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 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, n∈ℕn \in \mathbb{N} and finite s⊆Bs \subseteq B, and a column (t,b,v)(t, b, v) for each tuple tt from II, b∈Bb \in B and finite v⊆ℕv \subseteq \mathbb{N}.✦

The array language is the countable vocabulary whose symbols are the unary sort symbols for index, base, group and star points, a unary row symbol for each k,n∈ℕk, n \in \mathbb{N}, a unary column symbol for each kk and a unary label for each finite s⊆ℕs \subseteq \mathbb{N}; the binary order, incidence and bit symbols; the ternary group addition, star addition, row action and column action; a row projection of arity k+2k + 2 for each kk and nn; and a column projection of arity k+3k + 3 for each kk.✦

The points of MM form a structure in the array language, in which a symbol holds of a list of points only in the following cases. A sort symbol holds of the points of its sort. The row symbol for kk, nn holds of the rows (t,n,s)(t, n, s) with tt of length k+1k + 1, the column symbol for kk of the columns (t,b,v)(t, b, v) with tt of length k+1k + 1, and the label of ss of the star point ss. The row projection for kk, nn 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 such a column (t,b,v)(t, b, v) followed by the base point bb and then t(0),…,t(k)t(0), \dots, t(k). The order holds of base points b<b′b < b', and incidence of a base point bb and a group point ss with b∈sb \in s. The bit holds of a row (t,n,s)(t, n, s) and a column (t,b,v)(t, b, v) on the same tuple when a(t,n,b)+1b∈s+1n∈v≡1(mod⁡2).a(t, n, b) + 1_{b \in s} + 1_{n \in v} \equiv 1 \pmod 2 .(2) Group and star addition hold of triples (s,s′,s△s′)(s, s', s \mathbin{\triangle} s') of group, respectively star, points; the row action holds of (t,n,s)(t, n, s), a group point uu and (t,n,s△u)(t, n, s \mathbin{\triangle} u), and the column action of (t,b,v)(t, b, v), a star point uu and (t,b,v△u)(t, b, v \mathbin{\triangle} u).

Under CH, a normal form MM is an object when, for every tuple tt from II, {b∈B:t fails the test for s↦cs(b)} is countable.\{\, b \in B : t \text{ fails the test for } s \mapsto c_s(b) \,\} \text{ is countable}.(3)✦

A map ff from a normal form MM to a normal form NN consists of an injection fIf_I of IMI_M into INI_N, an order embedding fBf_B of BMB_M into BNB_N, a row shift uf(t,n)u_f(t, n), a finite subset of BNB_N, and a column shift vf(t,b)v_f(t, b), a finite subset of ℕ\mathbb{N}, for every tuple tt from IMI_M, n∈ℕn \in \mathbb{N} and 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∈vf(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 v_f(t, b)} \equiv a_M(t, n, b) \pmod 2 .(4)✦ The map ff sends an index point ii of MM 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], a star point to itself, a row (t,n,s)(t, n, s) to (fI∘t,n,uf(t,n)△fB[s])(f_I \circ t, n, u_f(t, n) \mathbin{\triangle} f_B[s]) and a column (t,b,v)(t, b, v) to (fI∘t,fB(b),vf(t,b)△v)(f_I \circ t, f_B(b), v_f(t, b) \mathbin{\triangle} v).

Along such a map ff, the color of a tuple tt from IMI_M at a point b∈BNb \in B_N is ctf(b)=[n↦aN(fI∘t,n,b)+1b∈uf(t,n)mod⁡2]c^f_t(b) = [\, n \mapsto a_N(f_I \circ t, n, b) + 1_{b \in u_f(t, n)} \bmod 2 \,].✦ Under CH, the map ff is strong when fB[BM]f_B[B_M] is a convex subset of BNB_N and every b∈BNb \in B_N outside it passes the tests: every tuple tt from IMI_M passes the test for the coloring s↦csf(b)s \mapsto c^f_s(b).✦

A presentation of a structure ℳ\mathcal{M} in the array language is a normal form MM with a bijection ee of the points of MM onto |ℳ||\mathcal{M}| that respects every relation: a symbol holds in ℳ\mathcal{M} of e∘x‾e \circ \bar{x} exactly when it holds of x‾\bar{x} among the points of MM.✦ For presentations (M,e)(M, e) of ℳ\mathcal{M} and (N,e′)(N, e') of 𝒩\mathcal{N}, a map ff from MM to NN is an inclusion when e′(f(x))=e(x)e'(f(x)) = e(x) for every point xx of MM.✦

Under CH, the array class KK is the class of structures in the array language that have a presentation whose normal form is an object, and ℳ≤K𝒩\mathcal{M} \le_K \mathcal{N} holds when ℳ\mathcal{M} and 𝒩\mathcal{N} have presentations (M,e)(M, e) and (N,e′)(N, e') with MM and NN objects and a strong map from MM to NN that is an inclusion.✦

The Claim

Theorem 1. Assume CH, and let KK be the array class with its strong substructure relation ≤K\le_K. Then (K,≤K) is an abstract elementary class,(K, \le_K) \text{ is an abstract elementary class},(5)✦ ℵ0 is a Löwenheim-Skolem bound for K,\aleph_0 \text{ is a Löwenheim-Skolem bound for } K,(6)✦ and LS(K)=ℵ0.\mathrm{LS}(K) = \aleph_0 .(7)✦

In the paper, the result reads: KK is an abstract elementary class in a fixed countable finitary relational language, with LS(K)=ℵ0\mathrm{LS}(K) = \aleph_0 and with the union and common-upper-bound properties for every nonempty set-indexed directed family.

What Is Checked

The claim is stated over the array class KK and its strong substructure relation ≤K\le_K, defined under CH from presentations by normal forms that are objects and from strong maps of normal forms, and over the notions of abstract elementary class, Löwenheim-Skolem bound and Löwenheim-Skolem number.