OctoInformBeta

OpenAI preprint, September 2026 · §5. A bound on uncountable base orders and categoricity on a tail

Lemma 5.9: For countable BB, any two bit arrays on ℕ×B\mathbb{N} \times B differ by finite row and column translations, which gives a map onto all points

Countable base orders and equinumerous index sets give isomorphic structures.

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

Lemma 5.9 compares models of the class KK of the paper whose base orders are countable. A basic structure of KK is handled through its normal form, made of an index set II, a base order BB and arrays of bits on ℕ×B\mathbb{N} \times B, all defined below. The question is when two normal forms with countable base orders present isomorphic structures. Behind it is a question about arrays: for countable BB, which arrays of bits on ℕ×B\mathbb{N} \times B can be carried into which by translating each row by a finite subset of BB and each column by a finite subset of ℕ\mathbb{N}?

Normal Forms

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 image of a tuple tt from II along an injection f:I→Jf\colon I \to J is the tuple f∘tf \circ t from JJ, of the same length.✦

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 linear order <<, the base order, and a bit a(t,n,b)∈{0,1}a(t, n, b) \in \{0, 1\} for each tuple tt from II, each n∈ℕn \in \mathbb{N} and each 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 is countable. A superscript names the normal form, as in IMI^M, BMB^M and aMa^M.

An array aa of bits on ℕ×B\mathbb{N} \times B is a function from ℕ×B\mathbb{N} \times B to {0,1}\{0, 1\}; for such an array, a finite set u⊆Bu \subseteq B and a finite set v⊆ℕv \subseteq \mathbb{N}, the entry of aa at (n,b)(n, b) translated by uu and vv is a(n,b)+1b∈u+1n∈v(mod⁡2).a(n, b) + 1_{b \in u} + 1_{n \in v} \pmod 2.(1)✦

The set Pt⁡(M)\operatorname{Pt}(M) of points of MM has six disjoint kinds of element: an index point for each i∈Ii \in I; a base point for each b∈Bb \in B; a group point for each finite s⊆Bs \subseteq B; a star point for each finite v⊆ℕv \subseteq \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}.✦

The Array Language

The array language is a countable relational vocabulary. Its unary symbols are the sort symbols index, base, group and star, a row symbol rowk,n\mathrm{row}_{k,n} and a column symbol colk\mathrm{col}_k for k,n∈ℕk, n \in \mathbb{N}, and a label ℓs\ell_s for each finite s⊆ℕs \subseteq \mathbb{N}. Its binary symbols are the order, the incidence and the bit symbol, and its ternary symbols are the group and star additions and the row and column actions. For k,n∈ℕk, n \in \mathbb{N} it also has a row projection πk,n\pi_{k,n} of arity k+2k + 2 and a column projection σk\sigma_k of arity k+3k + 3.

A structure RR in a relational vocabulary consists of a set, its universe, and for each nn-ary symbol an nn-ary relation on the universe interpreting it.✦ An isomorphism h:R≅Th\colon R \cong T of structures is a bijection between their universes such that each symbol holds of a tuple x‾\bar x in RR exactly when it holds of h(x‾)h(\bar x) in TT.✦

The structure of a normal form MM is the structure on Pt⁡(M)\operatorname{Pt}(M) in which the symbols hold of the following tuples of points and of no others. A sort symbol holds of the points of its kind, rowk,n\mathrm{row}_{k,n} of the rows (t,n,s)(t, n, s) with tt of length k+1k + 1, colk\mathrm{col}_k of the columns whose tuple has length k+1k + 1, and ℓs\ell_s of the star point ss. The row projection πk,n\pi_{k,n} holds of such a row followed by the index points t(0),…,t(k)t(0), \dots, t(k), and the column projection σk\sigma_k of a column (t,b,v)(t, b, v) with tt of length k+1k + 1, followed by the base point bb and the index points t(0),…,t(k)t(0), \dots, t(k). The order holds of base points b<b′b < b', and incidence of a base point bb and a group point ss with b∈sb \in s. The bit symbol holds of a row (t,n,s)(t, n, s) and a column (t,b,v)(t, b, v) of the same tuple when the entry (1) of a(t,⋅,⋅)a(t, \cdot, \cdot) at (n,b)(n, b), translated by ss and vv, is 11. The group and star additions hold of the triples (s,s′,s△s′)(s, s', s \triangle s') of group points, respectively of star points; the row action holds of ((t,n,s),u,(t,n,s△u))\bigl((t, n, s), u, (t, n, s \triangle u)\bigr) for a group point uu, and the column action of ((t,b,v),z,(t,b,v△z))\bigl((t, b, v), z, (t, b, v \triangle z)\bigr) for a star point zz.

A presentation (M,e)(M, e) of a structure RR in the array language is a normal form MM together with a bijection ee from Pt⁡(M)\operatorname{Pt}(M) onto the universe of RR such that each symbol holds of a tuple x‾\bar x of points in the structure of MM exactly when it holds of e(x‾)e(\bar x) in RR.✦

Maps of 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, a row shift giving a finite set ut(n)⊆BNu_t(n) \subseteq B^N for each tuple tt from IMI^M and each n∈ℕn \in \mathbb{N}, and a column shift giving a finite set wt(b)⊆ℕw_t(b) \subseteq \mathbb{N} for each such tt and each b∈BMb \in B^M, such that the bits agree: for all tt, nn and bb, aN(fI∘t,n,fB(b))+1fB(b)∈ut(n)+1n∈wt(b)≡aM(t,n,b)(mod⁡2).a^N(f_I \circ t, n, f_B(b)) + 1_{f_B(b) \in u_t(n)} + 1_{n \in w_t(b)} \equiv a^M(t, n, b) \pmod 2.(2)✦

The action of a map f:M→Nf\colon M \to N of normal forms on points is the map from Pt⁡(M)\operatorname{Pt}(M) to Pt⁡(N)\operatorname{Pt}(N), also written ff, that sends index points ii, base points bb, group points ss, star points vv, rows and columns as follows: i↦fI(i),b↦fB(b),s↦fB[s],v↦v,(t,n,s)↦(fI∘t,n,ut(n)△fB[s]),(t,b,v)↦(fI∘t,fB(b),wt(b)△v).\begin{gathered} i \mapsto f_I(i), \quad b \mapsto f_B(b), \quad s \mapsto f_B[s], \quad v \mapsto v, \\ (t, n, s) \mapsto \bigl(f_I \circ t, n, u_t(n) \triangle f_B[s]\bigr), \quad (t, b, v) \mapsto \bigl(f_I \circ t, f_B(b), w_t(b) \triangle v\bigr). \end{gathered}(3)✦

The Claim

Theorem 1 (Lemma 5.9). (a) Let BB be a countable set and dd an array of bits on ℕ×B\mathbb{N} \times B. There are finite sets Un⊆BU_n \subseteq B for n∈ℕn \in \mathbb{N} and Vb⊆ℕV_b \subseteq \mathbb{N} for b∈Bb \in B such that, for all nn and bb, d(n,b)≡1b∈Un+1n∈Vb(mod⁡2).d(n, b) \equiv 1_{b \in U_n} + 1_{n \in V_b} \pmod 2.(4)✦

(b) Let BB be a countable set and aa, a′a' arrays of bits on ℕ×B\mathbb{N} \times B. There are finite sets Un⊆BU_n \subseteq B for n∈ℕn \in \mathbb{N} and Vb⊆ℕV_b \subseteq \mathbb{N} for b∈Bb \in B such that, for all nn and bb, a′(n,b)+1b∈Un+1n∈Vb≡a(n,b)(mod⁡2).a'(n, b) + 1_{b \in U_n} + 1_{n \in V_b} \equiv a(n, b) \pmod 2.(5)✦

(c) Let MM and NN be normal forms with countable base orders and index sets of the same cardinality, |IM|=|IN||I^M| = |I^N|. There is a map f:M→Nf\colon M \to N whose index and base parts are bijections: fI[IM]=INandfB[BM]=BN.f_I[I^M] = I^N \quad \text{and} \quad f_B[B^M] = B^N.(6)✦

(d) Let f:M→Nf\colon M \to N be a map of normal forms whose index part fIf_I and base part fBf_B are onto. Then ff is onto the points of NN: f[Pt⁡(M)]=Pt⁡(N).f[\operatorname{Pt}(M)] = \operatorname{Pt}(N).(7)✦

(e) Let (M,e)(M, e) be a presentation of a structure RR and (N,e′)(N, e') a presentation of a structure TT in the array language, and let f:M→Nf\colon M \to N be a map that is onto the points of NN. Then ff induces an isomorphism e′∘f∘e−1:R≅T.e' \circ f \circ e^{-1} \colon R \cong T.(8)✦

In the paper, the result reads: if M,N∈KM, N \in K have countable base orders and |IM|=|IN||I^M| = |I^N|, then M≅NM \cong N.

Parts (c), (d) and (e) give it for structures presented by normal forms as in (c).

What Is Checked

The claim is stated over tuples and their images along injections, normal forms with their dense, locally countable base orders without endpoints, the translated entry (1), maps of normal forms with their action (3) on points, the array language and the structure it receives on the points of a normal form, and structures, their isomorphisms and their presentations in that language.