OctoInformBeta

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

Definition 3.3: An embedding of index sets and base orders with finite row and column translations keeping the bits, preserving and reflecting every relation

Basic inclusion as a map of normal forms.

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 is handled in normal form: an index set, a base order and an array of bits, from which its points and its relations are built. Definition 3.3, in the section on the abstract elementary class KK, is the basic inclusion ⊆b\subseteq_b, which says when one basic structure sits inside another. The library gives it as a map from the normal form of the smaller structure to that of the larger.

Normal Forms

A tuple tt from a set II is an injective map from {0,…,k}\{0, \dots, k\} into II for some k∈ℕk \in \mathbb{N}, said to have length k+1k + 1; along an injection ee of II into a set JJ it becomes the tuple e∘te \circ t from JJ.✦

A normal form MM consists of a nonempty index set IMI^M; a nonempty dense linear order BMB^M without endpoints in which every closed interval is countable, the base order; and a bit aM(t,n,b)∈{0,1}a^M(t, n, b) \in \{0, 1\} for each tuple tt from IMI^M, each n∈ℕn \in \mathbb{N} and each b∈BMb \in B^M.✦ The points of a normal form MM are the index points i∈IMi \in I^M, the base points b∈BMb \in B^M, the finite subsets s,us, u of BMB^M, the finite subsets v,wv, w of ℕ\mathbb{N}, the rows (t,n,s)(t, n, s) and the columns (t,b,v)(t, b, v), with tt a tuple from IMI^M.✦ The bit of the row (t,n,s)(t, n, s) and the column (t,b,v)(t, b, v) is aM(t,n,b)+1b∈s+1n∈vmod⁡2.a^M(t, n, b) + 1_{b \in s} + 1_{n \in v} \bmod 2 .(1)✦

The language of normal forms is relational, and MM interprets it on its points. The unary symbols of the language of normal forms pick out the index points, the base points, the finite subsets of BMB^M and those of ℕ\mathbb{N}; the rows (t,n,s)(t, n, s) with tt of length k+1k + 1, one symbol for each kk and nn; the columns (t,b,v)(t, b, v) with tt of length k+1k + 1, one for each kk; and, for each finite w⊆ℕw \subseteq \mathbb{N}, the point ww alone. The binary ones are the order b<b′b < b' of base points, the incidence b∈sb \in s, and the bit relation, which holds of a row (t,n,s)(t, n, s) and a column (t,b,v)(t, b, v) when (1) is 11. Of arity three come the graphs of symmetric difference on the finite subsets of BMB^M and on those of ℕ\mathbb{N}, and the translations, holding of ((t,n,s),u,(t,n,s△u))\bigl((t, n, s), u, (t, n, s \mathbin{\triangle} u)\bigr) for rows and of ((t,b,v),w,(t,b,v△w))\bigl((t, b, v), w, (t, b, v \mathbin{\triangle} w)\bigr) for columns. Last, for tt of length k+1k + 1, a row projection of arity k+2k + 2, one for each kk and nn, holds of ((t,n,s),t(0),…,t(k))\bigl((t, n, s), t(0), \dots, t(k)\bigr), and a column projection of arity k+3k + 3, one for each kk, holds of ((t,b,v),b,t(0),…,t(k))\bigl((t, b, v), b, t(0), \dots, t(k)\bigr).

A relational structure RR in this language is a set, its universe, with an interpretation of each nn-ary symbol as a set of nn-tuples from the universe.✦ A presentation (M,π)(M, \pi) of RR is a normal form MM with an isomorphism π\pi of its points, under the relations above, onto RR.✦

The Claim

Definition 1 (Basic inclusion). Let MM and NN be normal forms. 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, and finite sets r(t,n)⊆BNr(t, n) \subseteq B^N and c(t,b)⊆ℕc(t, b) \subseteq \mathbb{N}, the row and column translations, for each tuple tt from IMI^M, each n∈ℕn \in \mathbb{N} and each b∈BMb \in B^M, such that for all such tt, nn and bb aN(fI∘t,n,fB(b))+1fB(b)∈r(t,n)+1n∈c(t,b)≡aM(t,n,b)(mod⁡2).a^N(f_I \circ t, n, f_B(b)) + 1_{f_B(b) \in r(t, n)} + 1_{n \in c(t, b)} \equiv a^M(t, n, b) \pmod 2 .(2)✦ The map fˆ\hat f it induces on points is fˆ(i)=fI(i),fˆ(b)=fB(b),fˆ(s)=fB[s],fˆ(v)=v,fˆ(t,n,s)=(fI∘t,n,r(t,n)△fB[s]),fˆ(t,b,v)=(fI∘t,fB(b),c(t,b)△v),\begin{gathered} \hat f(i) = f_I(i), \quad \hat f(b) = f_B(b), \quad \hat f(s) = f_B[s], \quad \hat f(v) = v, \\ \hat f(t, n, s) = \bigl(f_I \circ t, n, r(t, n) \mathbin{\triangle} f_B[s]\bigr), \\ \hat f(t, b, v) = \bigl(f_I \circ t, f_B(b), c(t, b) \mathbin{\triangle} v\bigr), \end{gathered}(3)✦ and it preserves and reflects every relation: for each nn-ary symbol SS and points x1,…,xnx_1, \dots, x_n of MM, N⊨S(fˆ(x1),…,fˆ(xn))⇔M⊨S(x1,…,xn).N \models S\bigl(\hat f(x_1), \dots, \hat f(x_n)\bigr) \iff M \models S(x_1, \dots, x_n) .(4)✦ If (M,π)(M, \pi) presents RR and (N,σ)(N, \sigma) presents TT, the map ff is an inclusion of RR in TT when fˆ\hat f is the identity on elements: σ(fˆ(x))=π(x)for every point x of M.\sigma\bigl(\hat f(x)\bigr) = \pi(x) \quad \text{for every point } x \text{ of } M .(5)✦

In the paper, the definition reads: for basic structures M0M_0 and M1M_1, M0⊆bM1M_0 \subseteq_b M_1 when M0M_0 is an induced substructure of M1M_1 with the same group G*G_* of finite subsets of ℕ\mathbb{N}, the base order BM0B^{M_0} is convex in BM1B^{M_1}, and the finite-set codes of M0M_0 keep their supports in M1M_1.

What Is Checked

The definition is stated over normal forms with their index sets, base orders and bits, over tuples and their images along injections, over the points of a normal form with the relations of the language, and over relational structures whose universe is a set, together with their presentations by normal forms.