OctoInformBeta

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

Lemma 3.6: A color ignores finite edits, and colors along a map agree with the source's colors at the images of the source's base points

Tests along a map match the target’s off countable sets.

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 basic structures of the abstract elementary class KK are handled in normal form, by an index set, a base order and an array of bits, and each tuple of indices has a color at each base point. A map of normal forms matches the bits of its source with those of its target only up to finite corrections, defined below, so a color of the source can be read in the target in more than one way, and so can a test, a condition on the colors of the subtuples of a tuple. The question is how much of a color, and of a test, depends on these translations. The library answers it along a single map and along a composite of two.

Throughout, the continuum hypothesis (CH) is the statement 2ℵ0=ℵ12^{\aleph_0} = \aleph_1.✦

Normal Forms and Their Maps

A binary sequence is a function a:ℕ→{0,1}a : \mathbb{N} \to \{0, 1\}, and 2ω2^\omega is the set of them.✦ Two binary sequences aa and a′a' differ at finitely many places when the set of nn with a(n)≠a′(n)a(n) \neq a'(n) is finite✦, and equality outside a finite set, written =*=^*, is the equivalence relation on 2ω2^\omega of differing at finitely many places.✦ The palette S=2ω/=*S = 2^\omega/{=^*} is the set of its classes, the colors✦, and the color [a][a] of a sequence aa is its class.✦

A tuple from a set II is an injective map t:{0,…,k}→It : \{0, \dots, k\} \to I for some k∈ℕk \in \mathbb{N}.✦ For an order embedding e:{0,…,m}→{0,…,k}e : \{0, \dots, m\} \to \{0, \dots, k\}, the subtuple of tt along ee is the tuple t∘et \circ e✦; for an injection f:I→Jf : I \to J, the image of tt is the tuple f(t)=f∘tf(t) = f \circ t from JJ, of the same length.✦

A normal form M=(I,B,<,a)M = (I, B, <, a) of a basic structure consists of a nonempty index set II, a nonempty set BB of base points 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 base point 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] of BB being countable.✦ The color of tt at bb is ctM(b)=[a(t,⋅,b)]∈S.c^M_t(b) = [\, a(t, \cdot, b) \,] \in S.(1)✦ With several normal forms in play, IMI_M, BMB_M and aMa_M are those of MM.

A map f:M→Nf : M \to N of normal forms consists of an embedding fI:IM→INf_I : I_M \to I_N of the index sets, an order embedding fB:BM→BNf_B : B_M \to B_N of the base orders, a finite set uf(t,n)⊆BNu_f(t, n) \subseteq B_N, the row translation, for each tuple tt from IMI_M and each n∈ℕn \in \mathbb{N}, and a finite set vf(t,b)⊆ℕv_f(t, b) \subseteq \mathbb{N}, the column translation, for each such tt and each b∈BMb \in B_M, such that the bit of NN at fI(t)f_I(t), nn and fB(b)f_B(b), corrected by the indicator that fB(b)f_B(b) lies in uf(t,n)u_f(t, n) and by the indicator that nn lies in vf(t,b)v_f(t, b), is the bit of MM at tt, nn and bb: aN(fI(t),n,fB(b))+𝟏fB(b)∈uf(t,n)+𝟏n∈vf(t,b)≡aM(t,n,b)(mod⁡2).a_N(f_I(t), n, f_B(b)) + \mathbf{1}_{f_B(b) \in u_f(t, n)} + \mathbf{1}_{n \in v_f(t, b)} \equiv a_M(t, n, b) \pmod 2.(2)✦

The composite g∘f:M→Pg \circ f : M \to P of ff with a map g:N→Pg : N \to P of normal forms has index embedding gI∘fIg_I \circ f_I, base embedding gB∘fBg_B \circ f_B, and translations, where △\triangle is the symmetric difference and gB[u]g_B[u] the image of uu under gBg_B, ug∘f(t,n)=ug(fI(t),n)△gB[uf(t,n)],vg∘f(t,b)=vg(fI(t),fB(b))△vf(t,b).u_{g \circ f}(t, n) = u_g(f_I(t), n) \mathbin{\triangle} g_B[u_f(t, n)], \qquad v_{g \circ f}(t, b) = v_g(f_I(t), f_B(b)) \mathbin{\triangle} v_f(t, b).(3)

The color of a tuple tt from IMI_M along a map f:M→Nf : M \to N, at a base point bb of NN, is the color of the bits of fI(t)f_I(t) at bb with the rows translated by ufu_f: ctf(b)=[n↦aN(fI(t),n,b)+𝟏b∈uf(t,n)mod⁡2].c^f_t(b) = \bigl[\, n \mapsto a_N(f_I(t), n, b) + \mathbf{1}_{b \in u_f(t, n)} \bmod 2 \,\bigr].(4)✦

The exceptional set Xf(t)X_f(t) of a map f:M→Nf : M \to N at a tuple t:{0,…,k}→IMt : \{0, \dots, k\} \to I_M is the set of base points of NN that lie in a row translation at a subtuple of tt, Xf(t)=⋃m∈ℕ⋃e⋃n∈ℕuf(t∘e,n),X_f(t) = \bigcup_{m \in \mathbb{N}} \ \bigcup_{e} \ \bigcup_{n \in \mathbb{N}} u_f(t \circ e, n),(5)✦ the middle union taken over the order embeddings e:{0,…,m}→{0,…,k}e : \{0, \dots, m\} \to \{0, \dots, k\}.

Diagrams and Tests

A label on a set AA of positions 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 the image of (J,i)(J, i) under an injection ee of AA into a set A′A' is (e[J],i)(e[J], i).✦ A diagram D=(E,R,ρ)D = (E, R, \rho) on AA consists of binary relations EE and RR on the labels on AA and a map ρ\rho giving each label a tag, an ordinal in ω1\omega_1.✦ The restriction D↾eD \restriction e of a diagram DD on A′A' along an injection e:A→A′e : A \to A' is the diagram on AA under which two labels are related by EE, or by RR, exactly when their images under ee are so related in DD, and a label has the tag of its image.✦

A diagram D=(E,R,ρ)D = (E, R, \rho) 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, any two labels with the same RR-predecessors are EE-equivalent, and positions with EE-equivalent roots are equal.✦

Assuming CH, the coding of diagrams by colors is an injection D↦code(D)D \mapsto \mathrm{code}(D) into SS of the disjoint union, over m∈ℕm \in \mathbb{N}, of the sets of diagrams on {0,…,m}\{0, \dots, m\}.✦

Let cc color the tuples from II by colors in SS, and assume CH. The test of a tuple t:{0,…,k}→It : \{0, \dots, k\} \to I holds for cc, written Tc(t)T_c(t), when the family e↦c(t∘e)e \mapsto c(t \circ e) of the colors of its subtuples passes✦: there is a diagram dd on {0,…,k}\{0, \dots, k\} such that for every mm and every order embedding e:{0,…,m}→{0,…,k}e : \{0, \dots, m\} \to \{0, \dots, k\} the restriction d↾ed \restriction e is valid and code(d↾e)=c(t∘e).\mathrm{code}(d \restriction e) = c(t \circ e).(6)✦

For a normal form MM and a base point bb of MM, the colors give the coloring cM(b):s↦csM(b)c^M(b) : s \mapsto c^M_s(b) of the tuples from IMI_M; for a map f:M→Nf : M \to N and a base point bb of NN, the colors along ff give the coloring cf(b):s↦csf(b)c^f(b) : s \mapsto c^f_s(b) of the tuples from IMI_M.

The Claim

Theorem 1. Let aa be a binary sequence and vv a finite subset of ℕ\mathbb{N}. Then [n↦a(n)+𝟏n∈vmod⁡2]=[a].[\, n \mapsto a(n) + \mathbf{1}_{n \in v} \bmod 2 \,] = [a].(7)✦ Let f:M→Nf : M \to N be a map of normal forms and tt a tuple from IMI_M. Then for every base point bb of MM ctf(fB(b))=ctM(b),c^f_t(f_B(b)) = c^M_t(b),(8)✦ and the exceptional set of ff at tt satisfies |Xf(t)|≤ℵ0.|X_f(t)| \le \aleph_0.(9)✦ If moreover CH holds and bb is a base point of NN outside Xf(t)X_f(t), then Tcf(b)(t)⇔TcN(b)(fI(t)).T_{c^f(b)}(t) \iff T_{c^N(b)}(f_I(t)).(10)✦ If g:N→Pg : N \to P is a second map of normal forms and bb is a base point of PP outside the image of gBg_B, then ctg∘f(b)=cfI(t)g(b).c^{g \circ f}_t(b) = c^g_{f_I(t)}(b).(11)✦

In the paper, the result reads: the color ctz(b)c^z_t(b) of tt at bb computed with a system zz of row representatives does not depend on the column representative; two systems of row choices give colors that agree outside a countable set, so that the test for a fixed tuple has the same truth value outside a countable set; and for basic structures M0M_0 and M1M_1 with a basic inclusion M0⊆bM1M_0 \subseteq_b M_1, the colors at new base points computed with old row representatives do not depend on the choice, with no exceptions.

What Is Checked

The claim is stated over normal forms whose base order is dense, locally countable and without endpoints, over maps of normal forms with their row and column translations and the composite (3), over the colors (1) and the colors along a map (4), over the exceptional set (5), and, for the test, over valid diagrams and their coding by colors under CH.

Two facts about these constructions hold beyond the claim: equality outside a finite set is an equivalence relation on 2ω2^\omega✦, and the composite of two maps of normal forms is again a map, its translations (3) satisfying the agreement of bits (2).✦