OctoInformBeta

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

Lemma 3.12: Under the continuum hypothesis, a subset AA of R∈KR \in K lies in some T≤KRT \le_K R with ∥T∥≤|A|+ℵ0\|T\| \le |A| + \aleph_0, and the same holds for normal forms

Every subset lies in a small strong substructure.

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

Under the continuum hypothesis (CH), 2ℵ0=ℵ12^{\aleph_0} = \aleph_1, the class KK is a class of structures in a countable relational language, each presented by a normal form, an array of bits over an index set and a dense base order. Its strong substructure relation ≤K\le_K comes from the strong maps between normal forms. Lemma 3.12 is the downward Löwenheim-Skolem axiom for KK: given a structure RR in KK and a subset AA of its universe, it asks for a strong substructure of RR that contains AA and has at most |A|+ℵ0|A| + \aleph_0 elements.✦

The library states this for KK and for normal forms, together with two statements on restricting a normal form to part of its index set and part of its base.

Normal Forms

A tuple from a set II is an injective map t:{0,…,n}→It \colon \{0, \dots, n\} \to I, for some n∈ℕn \in \mathbb{N}, of length n+1n + 1.✦ A subsequence of a tuple tt from II is a composite t∘et \circ e with e:{0,…,m}→{0,…,n}e \colon \{0, \dots, m\} \to \{0, \dots, n\} an order embedding, and the image of tt under an injection ff of II into a set I′I' is the tuple f∘tf \circ t from I′I'.

A normal form M=(I,B,<,a)M = (I, B, <, a) consists of a nonempty index set II, a nonempty base set BB with a dense linear order <<, the base order, that has no least or greatest element and 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 every tuple tt from II, every n∈ℕn \in \mathbb{N} and every b∈Bb \in B.✦

The points of MM are of six kinds: the index points i∈Ii \in I; the base points b∈Bb \in B; the group points, finite subsets ss of BB; the star points, finite subsets vv of ℕ\mathbb{N}; the rows (t,n,s)(t, n, s); and the columns (t,b,v)(t, b, v), where tt is a tuple from II, n∈ℕn \in \mathbb{N}, b∈Bb \in B, and ss and vv are as before. The set of points of MM is written |M||M|, and ∥M∥\|M\| is its cardinality.✦

The array language LL is a countable relational language, and each normal form MM is a structure in LL with universe |M||M|. The unary symbols of LL are one for each of the index points, the base points, the group points and the star points, true of the points of that kind; for each kk and nn, a row symbol true of the rows (t,n,s)(t, n, s) with tt of length k+1k + 1; for each kk, a column symbol true of the columns (t,b,v)(t, b, v) with tt of length k+1k + 1; and for each finite v⊆ℕv \subseteq \mathbb{N}, a unary symbol true of the star point vv alone. For each kk and nn, the row projection of arity k+2k + 2 holds of a row (t,n,s)(t, n, s) with tt of length k+1k + 1, followed by the index points t(0),…,t(k)t(0), \dots, t(k), and for each kk, the column projection of arity k+3k + 3 holds of a column (t,b,v)(t, b, v) with tt of length k+1k + 1, followed by the base point bb and t(0),…,t(k)t(0), \dots, t(k). The binary symbols are the base order, incidence b∈sb \in s between a base point and a group point, and the bit relation, true of a row (t,n,s)(t, n, s) and a column (t,b,v)(t, b, v) on the same tuple when their bit, where 1b∈s1_{b \in s} is 11 if b∈sb \in s and 00 otherwise, a(t,n,b)+1b∈s+1n∈vmod⁡2a(t, n, b) + 1_{b \in s} + 1_{n \in v} \bmod 2(1) is 11. The ternary symbols are the additions, true of (s,s′,s△s′)(s, s', s \mathbin{\triangle} s') for group points and for star points, and the actions, true of ((t,n,s),s′,(t,n,s△s′))((t, n, s), s', (t, n, s \mathbin{\triangle} s')) for a row and a group point s′s' and of ((t,b,v),v′,(t,b,v△v′))((t, b, v), v', (t, b, v \mathbin{\triangle} v')) for a column and a star point v′v'. No symbol holds of any other tuple of points.

The palette S=2ω/=*S = 2^\omega/{=^*} is the set of binary sequences modulo equality outside a finite set✦, and [a][a] is the color of a sequence aa✦. The color of a tuple tt from II at a base point bb is ct(b)=[a(t,⋅,b)]∈S.c_t(b) = [a(t, \cdot, b)] \in S.(2)✦

Diagrams and Tests

A label on a set YY of positions is a pair (J,i)(J, i) with JJ a nonempty finite subset of YY and i∈ℕi \in \mathbb{N}✦; the root of a position pp is the label ({p},0)(\{p\}, 0)✦. A diagram D=(E,R,ρ)D = (E, R, \rho) on YY consists of binary relations EE and RR on the labels on YY and a tag ρ(l)∈ω1\rho(l) \in \omega_1 for each label ll.✦ The restriction D↾eD \restriction e of DD along an injection e:Y′→Ye \colon Y' \to Y is the diagram on Y′Y' in which two labels are related by EE, or by RR, when their images (e[J],i)(e[J], i) are so related in DD, and each label has the tag of its image.✦

A diagram (E,R,ρ)(E, R, \rho) is valid when EE is an equivalence relation, RR and ρ\rho are invariant under EE, ρ(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 EE-inequivalent roots.✦

Under CH, the coding of diagrams by colors is an injection D↦⌜D⌝D \mapsto \ulcorner D \urcorner of the set of all diagrams on the sets {0,…,n}\{0, \dots, n\}, n∈ℕn \in \mathbb{N}, into SS.✦ A family of colors γ(e)∈S\gamma(e) \in S, one for each 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\} with d↾e valid and ⌜d↾e⌝=γ(e)for every such e.d \restriction e \text{ valid and } \ulcorner d \restriction e \urcorner = \gamma(e) \quad \text{for every such } e.(3)✦ For a coloring cc of the tuples from II by SS, a tuple tt from II of length n+1n + 1 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.✦

For a normal form MM and a tuple tt from II, the failure set FM(t)F_M(t) is the set of base points bb at which tt does not pass the test for the coloring r↦cr(b)r \mapsto c_r(b). Under CH, a normal form MM is an object when all its failure sets are countable: |FM(t)|≤ℵ0for every tuple t from I.|F_M(t)| \le \aleph_0 \quad \text{for every tuple } t \text{ from } I.(4)✦

Maps and Restrictions

A map f:M→Nf \colon M \to N of normal forms 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 σ(t,n)\sigma(t, n), a finite subset of BNB_N, for each tuple tt from IMI_M and each n∈ℕn \in \mathbb{N}, and a column shift τ(t,b)\tau(t, b), a finite subset of ℕ\mathbb{N}, for each such tt and each b∈BMb \in B_M, such that the bits agree: aN(fI∘t,n,fB(b))+1fB(b)∈σ(t,n)+1n∈τ(t,b)≡aM(t,n,b)(mod⁡2).a_N(f_I \circ t, n, f_B(b)) + 1_{f_B(b) \in \sigma(t, n)} + 1_{n \in \tau(t, b)} \equiv a_M(t, n, b) \pmod 2.(5)✦ Such a map ff sends the points of MM to points of NN: index and base points go to their images under fIf_I and fBf_B, a group point ss to fB[s]f_B[s], a star point to itself, and f(t,n,s)=(fI∘t,n,σ(t,n)△fB[s]),f(t,b,v)=(fI∘t,fB(b),τ(t,b)△v).f(t, n, s) = (f_I \circ t,\, n,\, \sigma(t, n) \mathbin{\triangle} f_B[s]), \qquad f(t, b, v) = (f_I \circ t,\, f_B(b),\, \tau(t, b) \mathbin{\triangle} v).(6)✦

The color along ff 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∈σ(t,n)mod⁡2].c^f_t(b) = [\, n \mapsto a_N(f_I \circ t, n, b) + 1_{b \in \sigma(t, n)} \bmod 2 \,].(7)✦ Under CH, a map f:M→Nf \colon M \to N of normal forms is strong when the image fB[BM]f_B[B_M] is convex in BNB_N and, at every b∈BNb \in B_N outside it, every tuple from IMI_M passes the test for the coloring r↦crf(b)r \mapsto c^f_r(b).✦

For a normal form M=(I,B,<,a)M = (I, B, <, a), a nonempty I′⊆II' \subseteq I and a nonempty B′⊆BB' \subseteq B that is dense and has no least or greatest element in the order of BB, the restriction M↾(I′,B′)M \restriction (I', B') is the normal form with index set I′I', base order B′B' and bits a(t,n,b)a(t, n, b) for tuples tt from I′I', n∈ℕn \in \mathbb{N} and b∈B′b \in B'.✦ The restriction map ι:M↾(I′,B′)→M\iota \colon M \restriction (I', B') \to M is the map of normal forms whose injection and order embedding are the inclusions of I′I' in II and of B′B' in BB, with empty row and column shifts.✦

The Class KK

A structure RR in LL is a set |R||R|, its universe, with an interpretation of each nn-ary symbol of LL as a set of nn-tuples from |R||R|; ∥R∥\|R\| is the cardinality of |R||R|.✦ A presentation PP of RR is a normal form MPM_P with a bijection hP:|MP|→|R|h_P \colon |M_P| \to |R| that is an isomorphism of MPM_P onto RR.✦ For presentations PP of RR and QQ of TT, a map f:MP→MQf \colon M_P \to M_Q of normal forms is an inclusion when hQ(f(x))=hP(x)h_Q(f(x)) = h_P(x) for every point xx of MPM_P.✦

Under CH, the class KK consists of the structures in LL with a presentation whose normal form is an object.✦ The strong substructure relation ≤K\le_K on KK is defined as follows: for structures RR and TT in KK, R≤KTR \le_K T when there are presentations PP of RR and QQ of TT 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. Assume CH.

(a) Let RR be a structure in KK and AA a subset of |R||R|. There is a structure TT in KK with T≤KR,A⊆|T|,∥T∥≤|A|+ℵ0.T \le_K R, \qquad A \subseteq |T|, \qquad \|T\| \le |A| + \aleph_0.(8)✦

(b) Let MM be a normal form that is an object and AA a set of points of MM. There are a normal form NN that is an object and a map f:N→Mf \colon N \to M with f strong,A⊆f[|N|],∥N∥≤|A|+ℵ0.f \text{ strong}, \qquad A \subseteq f[\,|N|\,], \qquad \|N\| \le |A| + \aleph_0.(9)✦

Let M=(I,B,<,a)M = (I, B, <, a) be a normal form, I′I' a nonempty subset of II, and B′B' a nonempty subset of BB that is dense and has no least or greatest element.

(c) If MM is an object, then M↾(I′,B′) is an object.M \restriction (I', B') \text{ is an object.}(10)✦

(d) If B′B' is convex in BB and contains the failure set FM(t)F_M(t) of every tuple tt from I′I', then ι:M↾(I′,B′)→M is strong.\iota \colon M \restriction (I', B') \to M \text{ is strong.}(11)✦

What Is Checked

The four statements are made under CH, over the class KK and its relation ≤K\le_K, defined through presentations by normal forms, and over objects, strong maps of normal forms and the restriction map ι:M↾(I′,B′)→M\iota \colon M \restriction (I', B') \to M.