OctoInformBeta

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

Lemma 3.5: A normal form over II and BB has max⁡(|I|,|B|,ℵ0)\max(|I|, |B|, \aleph_0) points, and the structure it codes has as many

The size of a normal form and of its coded structure.

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

A basic structure of the abstract elementary class KK of the library, a structure in the vocabulary LL introduced below, is presented in normal form by an index set II, a base order BB and, for each finite sequence of distinct elements of II, an array of bits indexed by ℕ×B\mathbb{N} \times B. Its points come from II, from BB, from the finite subsets of BB and of ℕ\mathbb{N}, and from the rows and columns of the arrays. The question is how many points that makes in terms of |I||I| and |B||B|: with II and BB of size ℵ1\aleph_1, say, are there more than ℵ1\aleph_1? The library counts the points of a normal form, and the elements of the structure on a von Neumann ordinal that the normal form codes.

Normal Forms

A tuple tt 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}, a sequence of n+1n + 1 distinct elements of II; T(I)T(I) is the set of tuples from II.✦

A normal form MM consists of a nonempty index set II, a base order BB and bits a(t,n,b)∈{0,1}a(t, n, b) \in \{0, 1\}, one for each tuple tt from II, each n∈ℕn \in \mathbb{N} and each b∈Bb \in B; the base order is a nonempty dense linear order without endpoints that is locally countable, every closed interval [a,b][a, b] of BB being countable.✦

The set P(M)P(M) of points of MM is the disjoint union of the index points (the elements of II), the base points (the elements of BB), the group points (the finite subsets of BB), the star points (the finite subsets of ℕ\mathbb{N}), the rows (t,n,s)(t, n, s) with tt a tuple from II, n∈ℕn \in \mathbb{N} and ss a finite subset of BB, and the columns (t,b,v)(t, b, v) with tt a tuple from II, b∈Bb \in B and vv a finite subset of ℕ\mathbb{N}, where [X]<ω[X]^{<\omega} is the set of finite subsets of XX: P(M)=I⊔B⊔[B]<ω⊔[ℕ]<ω⊔(T(I)×ℕ×[B]<ω)⊔(T(I)×B×[ℕ]<ω).P(M) = 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).(1) The number of points of MM is ∥M∥=|P(M)|\|M\| = |P(M)|.

The bit of a row (t,n,s)(t, n, s) and a column (t,b,v)(t, b, v) with the same tuple tt is a(t,n,b)+1b∈s+1n∈vmod⁡2.a(t, n, b) + 1_{b \in s} + 1_{n \in v} \bmod 2.(2)✦

The Vocabulary

The vocabulary LL of basic structures is relational. The unary symbols of LL are the sort symbols for index, base, group and star points, a row symbol Rk,nR_{k,n} and a column symbol CkC_k for all k,n∈ℕk, n \in \mathbb{N}, and a label ℓs\ell_s for each finite s⊆ℕs \subseteq \mathbb{N}. The binary symbols of LL are the order, incidence and the bit symbol, and the ternary symbols of LL are group addition, star addition, the row action and the column action. For all k,n∈ℕk, n \in \mathbb{N}, LL has a row projection symbol pk,np_{k,n} of arity k+2k + 2 and a column projection symbol qkq_k of arity k+3k + 3. For each nn, LnL_n is the set of nn-ary symbols of LL.✦

A normal form MM interprets each symbol of LnL_n as an nn-ary relation on P(M)P(M), true only of the following tuples.✦ A sort symbol holds of the points of its kind; Rk,nR_{k,n} holds of the rows (t,n,s)(t, n, s) with tt of length k+1k + 1, CkC_k of the columns (t,b,v)(t, b, v) with tt of length k+1k + 1, and ℓs\ell_s of the star point ss alone. For such a row and such a column, pk,np_{k,n} holds of ((t,n,s),t(0),…,t(k))((t, n, s), t(0), \dots, t(k)) and qkq_k of ((t,b,v),b,t(0),…,t(k))((t, b, v), b, t(0), \dots, t(k)), with the entries of tt taken as index points and bb as a base point. The order holds of base points a<ba < b, incidence of a base point bb and a group point ss with b∈sb \in s, and the bit symbol of a row and a column with the same tuple whose bit (2) is 11. Group addition holds of the triples (s,s′,s△s′)(s, s', s \triangle s') of group points, △\triangle being symmetric difference, and star addition of the same triples of star points. The row action holds of ((t,n,s),u,(t,n,s△u))((t, n, s), u, (t, n, s \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 \triangle u)) for a star point uu.

The Coded Structure

An LL-structure NN is a set, the universe of NN, together with an interpretation of each symbol of LnL_n as a set of nn-tuples of elements of the universe; ∥N∥\|N\| is the cardinality of the universe.✦

Given a normal form MM, a set AA and a bijection e:P(M)→Ae \colon P(M) \to A, the copy MeM_e of MM on AA is the LL-structure with universe AA in which, for each R∈LnR \in L_n and all x1,…,xn∈Ax_1, \dots, x_n \in A, Me⊨R(x1,…,xn)⇔M⊨R(e−1(x1),…,e−1(xn)).M_e \models R(x_1, \dots, x_n) \iff M \models R(e^{-1}(x_1), \dots, e^{-1}(x_n)).(3)✦

The bijection πX\pi_X of a set XX onto an ordinal is a bijection, chosen once and for all, from XX onto the von Neumann initial ordinal of the cardinal |X||X|.✦

The coded structure 𝒞(M)\mathcal{C}(M) of a normal form MM is the copy of MM along πP(M)\pi_{P(M)}, an LL-structure whose universe is the initial ordinal of ∥M∥\|M\|.✦

The Claim

Theorem 1. Let MM be a normal form with index set II and base order BB. The number of points of MM is ∥M∥=max⁡(|I|,|B|,ℵ0).\|M\| = \max(|I|, |B|, \aleph_0).(4)✦ If κ\kappa is an infinite cardinal with |I|≤κ|I| \le \kappa and |B|≤κ|B| \le \kappa, then ∥M∥≤κ.\|M\| \le \kappa.(5)✦ The coded structure of MM has cardinality ∥𝒞(M)∥=∥M∥.\|\mathcal{C}(M)\| = \|M\|.(6)✦

What Is Checked

Theorem 1 is stated over a normal form MM, with its index set, its base order and its set of points (1), and over its coded structure 𝒞(M)\mathcal{C}(M), the copy of MM along the fixed bijection of P(M)P(M) onto the initial ordinal of ∥M∥\|M\|. The vocabulary LL is countable.