OctoInformBeta

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

Definition 3.7: Objects fail each tuple's test at countably many base points; strong maps have convex base image and pass every tuple's test outside it

Objects and strong substructures of the class KK..

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 class KK is a class of structures in a countable relational language LL, each presented by a normal form, also called a basic structure. A normal form has an index set II and a base order BB, and at every base point bb it gives each tuple tt from II, an injective finite sequence of elements of II, a color ct(b)c_t(b) in a palette SS of binary sequences modulo finite differences. Assuming the continuum hypothesis (CH), 2ℵ0=ℵ12^{\aleph_0} = \aleph_1, a test is defined for each tuple at each base point, as a condition on the colors there of its subtuples.

Definition 3.7 decides, by where these tests fail, which structures are the objects of KK and when one is a strong substructure R≤KTR \le_K T of another. The definition goes through a presentation of each structure, and the question is whether a different presentation would change the answer.

Normal Forms and Their Presentations

A tuple tt from a set II is an injective map from {0,…,n}\{0, \dots, n\} into II, for some n∈ℕn \in \mathbb{N}; its length is n+1n + 1.✦ The subtuple of a tuple tt from II along an order embedding e:{0,…,m}→{0,…,n}e \colon \{0, \dots, m\} \to \{0, \dots, n\} is the tuple t∘et \circ e.✦ The image of tt under an injection gg of II into a set JJ is the tuple g∘tg \circ t from JJ.✦

A binary sequence is a map a:ℕ→{0,1}a \colon \mathbb{N} \to \{0, 1\}.✦ Two binary sequences aa and a′a' are equal outside a finite set, written a=*a′a =^* a', when they differ at only finitely many places.✦ The palette S=2ω/=*S = 2^\omega/{=^*} is the set of classes of binary sequences under =*=^*✦, and the class [a][a] of a binary sequence aa is its color.✦

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 << without least or greatest element, 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 color of tt at bb is ct(b)=[a(t,⋅,b)]c_t(b) = [a(t, \cdot, b)].✦ The points of MM are of six kinds: an index point for each i∈Ii \in I, a base point for each b∈Bb \in B, 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, each n∈ℕn \in \mathbb{N} and each finite s⊆Bs \subseteq B, and a column (t,b,v)(t, b, v) for each tuple tt from II, each b∈Bb \in B and each finite v⊆ℕv \subseteq \mathbb{N}.✦

A normal form MM is a structure in LL whose universe is the set of its points. The unary symbols of LL are four sort symbols, each true exactly of the points of one of the first four kinds; for k,n∈ℕk, n \in \mathbb{N}, a row symbol true of the rows (t,n,s)(t, n, s) with tt of length k+1k + 1, and a column symbol true of the columns whose tuple has length k+1k + 1; and, for each finite s⊆ℕs \subseteq \mathbb{N}, a label symbol true of the star point ss alone. The row projection for kk and nn, of arity k+2k + 2, 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 arity k+3k + 3, holds of such a column (t,b,v)(t, b, v) followed by the base point bb and the same index points. The binary symbols are the order << on base points, incidence, true of bb and ss when b∈sb \in s, and the bit, true of a row (t,n,s)(t, n, s) and a column (t,b,v)(t, b, v) 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.(1) The ternary symbols are the group and star additions, true of the triples (s,s′,s△s′)(s, s', s \mathbin{\triangle} s') of group points and of star points, and the row and column actions, true of ((t,n,s),u,(t,n,s△u))((t, n, s), u, (t, n, s \mathbin{\triangle} u)) for a group point uu and of ((t,b,v),u,(t,b,v△u))((t, b, v), u, (t, b, v \mathbin{\triangle} u)) for a star point uu. Every symbol is false of every tuple of points not of these shapes.

A relational structure RR in LL has a set as its universe and interprets each nn-ary symbol as a set of nn-tuples from it.✦ A presentation PP of RR is a normal form MPM_P together with a bijection ePe_P from the points of MPM_P onto the universe of RR that is an isomorphism: for every nn-ary symbol and every nn-tuple x‾\bar x of points, RR satisfies the symbol at eP(x‾)e_P(\bar x) exactly when MPM_P does at x‾\bar x.✦

Maps and the Test

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 fIf_I of IMI_M into INI_N, an order embedding fBf_B of BMB_M into BNB_N, a finite row shift uf(t,n)⊆BNu_f(t, n) \subseteq B_N and a finite column shift vf(t,b)⊆ℕv_f(t, b) \subseteq \mathbb{N} for each tuple tt from IMI_M, each n∈ℕn \in \mathbb{N} and each b∈BMb \in B_M, such that the bits agree: 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.(2)✦ A map ff acts on points: it sends index, base and group points to their images under fIf_I and fBf_B, fixes star points, and sends 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).✦ For a tuple tt from IMI_M and a base point bb of NN, the color of tt at bb along ff is ctf(b)=[n↦aN(fI∘t,n,b)+1b∈uf(t,n)mod⁡2].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].(3)✦

For presentations PP of RR and QQ of TT, a map f:MP→MQf \colon M_P \to M_Q is an inclusion of PP into QQ when eQ(f(x))e_Q(f(x)) and eP(x)e_P(x) are the same set for every point xx of MPM_P.✦

A diagram D=(E,R,ρ)D = (E, R, \rho) on a set AA of positions has binary relations EE and RR on the labels (J,i)(J, i) on AA, with JJ a nonempty finite subset of AA and i∈ℕi \in \mathbb{N}, and a tag ρ(x)∈ω1\rho(x) \in \omega_1 for each label xx.✦ A diagram DD is valid when EE is an equivalence relation, RR and ρ\rho are invariant under EE, ρ(x)<ρ(y)\rho(x) < \rho(y) whenever xRyx \mathrel{R} y, labels with the same RR-predecessors are EE-equivalent, and positions whose roots ({a},0)(\{a\}, 0) are EE-equivalent are equal.✦ The restriction D↾eD \restriction e of a diagram DD on AA along an injection ee of a set A′A' into AA is the diagram on A′A' in which each label (J,i)(J, i) on A′A' is related and tagged as its image (e[J],i)(e[J], i) is in DD.✦ Under CH, the code of diagrams by colors is an injection code\operatorname{code} of the disjoint union over n∈ℕn \in \mathbb{N} of the sets of diagrams on {0,…,n}\{0, \dots, n\} into SS.✦

For a coloring cc of the tuples from II by colors in SS, the test of a tuple tt of length n+1n + 1 passes for cc when there is a diagram DD on {0,…,n}\{0, \dots, n\} such that, for every order embedding e:{0,…,m}→{0,…,n}e \colon \{0, \dots, m\} \to \{0, \dots, n\}, the restriction D↾eD \restriction e is valid and code⁡(D↾e)=c(t∘e).\operatorname{code}(D \restriction e) = c(t \circ e).(4)✦

Objects and Strong Maps

A normal form MM is an object when, for every tuple tt from II, the bad set Et={b∈B:the test of t fails for the coloring s↦cs(b)}E_t = \{\, b \in B : \text{the test of } t \text{ fails for the coloring } s \mapsto c_s(b) \,\}(5)✦ is countable.

A map f:M→Nf \colon M \to N of normal forms is strong when its base image fB[BM]f_B[B_M] is convex in BNB_N and the test of t passes for s↦csf(b)for every tuple t from IM and every b∈BN\fB[BM].\text{the test of } t \text{ passes for } s \mapsto c^f_s(b) \quad \text{for every tuple } t \text{ from } I_M \text{ and every } b \in B_N \setminus f_B[B_M].(6)✦

The Claim

Definition 1. Assume CH. The class KK consists of the structures in LL given by the first line below, its objects, with the strong substructure relation ≤K\le_K given by the second: for relational structures RR and TT in LL, R∈K⇔MP is an object for some presentation P of R,R≤KT⇔for some presentations P of R and Q of T with MP,MQ objects,some strong map f:MP→MQ is an inclusion of P into Q.\begin{aligned} R \in K &\iff M_P \text{ is an object for some presentation } P \text{ of } R,\\ R \le_K T &\iff \text{for some presentations } P \text{ of } R \text{ and } Q \text{ of } T \text{ with } M_P,\, M_Q \text{ objects,}\\ &\qquad \text{some strong map } f \colon M_P \to M_Q \text{ is an inclusion of } P \text{ into } Q. \end{aligned}(7)✦ If RR is an object of KK, then for every presentation PP of RR, MP is an object.M_P \text{ is an object.}(8)✦ If R≤KTR \le_K T, then for any presentations PP of RR and QQ of TT there is a strong map f:MP→MQ that is an inclusion of P into Q.\text{a strong map } f \colon M_P \to M_Q \text{ that is an inclusion of } P \text{ into } Q.(9)✦

In the paper, the result reads: an object is a basic structure whose bad set EtE_t is countable for every tuple tt, and for basic structures M0M_0 and M1M_1, M0≤KM1M_0 \le_K M_1 when M0⊆bM1M_0 \subseteq_b M_1, the basic inclusion, and at every new base point the full test for every old tuple passes with old row representatives.

What Is Checked

The definition of KK and its two consequences are stated, under CH, over relational structures in LL whose universes are sets, their presentations by normal forms, the test of a tuple through the code of diagrams by colors, and the maps of normal forms, with their colors along a map and their inclusions of presentations.