OctoInformBeta

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

Lemma 5.2: And no family of valid diagrams, one on {0,…,k−1}\{0, \dots, k-1\} for each kk, is coherent under all order embeddings

Under the continuum hypothesis no color pattern passes every test.

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 color is an element of the palette S=2ω/=*S = 2^\omega/{=^*}, a binary sequence a:ℕ→{0,1}a \colon \mathbb{N} \to \{0, 1\} taken up to equality outside a finite set, a=*b⇔{n∈ℕ:a(n)≠b(n)} is finite,a =^* b \iff \{n \in \mathbb{N} : a(n) \neq b(n)\} \text{ is finite},(1)✦ and [a][a] is the color of aa. A tuple of length n+1n + 1 is an injective map from {0,…,n}\{0, \dots, n\} into a set of positions; its subsequences of length m+1m + 1 are its composites with the order embeddings of {0,…,m}\{0, \dots, m\} into {0,…,n}\{0, \dots, n\}, and a coloring of the tuple gives each such subsequence a color, the color for arity m+1m + 1. Under the continuum hypothesis (CH), 2ℵ0=ℵ12^{\aleph_0} = \aleph_1, colors code diagrams, structures on a set of positions, and the test at each arity matches the colors of a tuple’s subsequences against one diagram on its positions.

A pattern is a sequence (p(m))m∈ℕ(p(m))_{m \in \mathbb{N}} of colors, p(m)p(m) being the color for arity m+1m + 1 on every subsequence alike. The question of Lemma 5.2 is whether, under CH, some pattern passes the test at every arity. Behind it stands a question on diagrams alone, with validity and restriction as defined in the next section: whether a family (dk)k∈ℕ(d_k)_{k \in \mathbb{N}} of valid diagrams, dkd_k on {0,…,k−1}\{0, \dots, k - 1\}, can be coherent, that is, satisfy dm=dn↾ed_m = d_n \restriction e for every order embedding e:{0,…,m−1}→{0,…,n−1}e \colon \{0, \dots, m - 1\} \to \{0, \dots, n - 1\}.

Diagrams and the Test

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).✦ An injection e:A→Be \colon A \to B carries a label (J,i)(J, i) on AA to the label (e[J],i)(e[J], i) on BB.✦ 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 that gives each label a tag in ω1\omega_1, read as a countable ordinal.✦ The restriction D↾eD \restriction e of a diagram DD on BB along an injection e:A→Be \colon A \to B is the diagram on AA in which two labels are related by EE, or by RR, exactly when their images under ee are, and each label has the tag of its image.✦

A diagram D=(E,R,ρ)D = (E, R, \rho) on AA is valid when EE is an equivalence relation, RR and ρ\rho are unchanged when a label is replaced by an EE-equivalent one, and for all labels l,l′l, l' and positions a,ba, b of AA: lRl′⇒ρ(l)<ρ(l′),(∀z(zRl⇔zRl′))⇒lEl′,({a},0)E({b},0)⇒a=b.l \mathrel{R} l' \Rightarrow \rho(l) < \rho(l'), \qquad \bigl(\forall z\, (z \mathrel{R} l \Leftrightarrow z \mathrel{R} l')\bigr) \Rightarrow l \mathrel{E} l', \qquad (\{a\}, 0) \mathrel{E} (\{b\}, 0) \Rightarrow a = b.(2)✦ The quotient QDQ_D of a valid diagram DD is the set of EE-classes [l]E[l]_E of labels✦, with the relation [l]ER[l′]E[l]_E \mathrel{R} [l']_E when lRl′l \mathrel{R} l'✦ and the tag ρ([l]E)=ρ(l)\rho([l]_E) = \rho(l).✦ For valid diagrams DD on AA and D′D' on BB and an injection e:A→Be \colon A \to B with D=D′↾eD = D' \restriction e, the quotient map QD→QD′Q_D \to Q_{D'} along ee sends the class of a label to the class of its image.✦

Assume CH. The coding γ\gamma of diagrams by colors is an injection γ:⨆m∈ℕ{diagrams on {0,…,m}}↪S,\gamma \colon \bigsqcup_{m \in \mathbb{N}} \{\text{diagrams on } \{0, \dots, m\}\} \hookrightarrow S,(3)✦ and γ(m,D)\gamma(m, D) is the color of a diagram DD on {0,…,m}\{0, \dots, m\}. Fix nn, and let ss give a color s(m,e)s(m, e) to each m∈ℕm \in \mathbb{N} and each order embedding e:{0,…,m}→{0,…,n}e \colon \{0, \dots, m\} \to \{0, \dots, n\}, a color for arity m+1m + 1 on the subsequence ee of a tuple of length n+1n + 1. The family ss passes the test at arity n+1n + 1 when there is a diagram dd on {0,…,n}\{0, \dots, n\} such that, for every mm and ee, d↾e is valid and γ(m,d↾e)=s(m,e).d \restriction e \text{ is valid and } \gamma(m, d \restriction e) = s(m, e).(4)✦

Coherent Families and Their Limits

Fix a coherent family dd of valid diagrams and a linear order (L,<)(L, <). For a finite set X⊆LX \subseteq L with kk elements, the stage diagram dXd^X on XX is the restriction of dkd_k along the inverse of the increasing enumeration of XX.✦

The stage quotient F(X)=QdXF(X) = Q_{d^X} carries the stage relation RXR_X and the stage tag ρX\rho_X that dXd^X induces on its classes. For finite sets X⊆YX \subseteq Y the inclusion ιXY:X→Y\iota_{XY} \colon X \to Y is an order embedding✦, and the transition fXY:F(X)→F(Y)f_{XY} \colon F(X) \to F(Y) is the quotient map along it.✦ The limit of dd over LL is the direct limit $\varinjlim_X F(X)$ of the stage quotients along the transitions, XX running over the finite subsets of LL ordered by inclusion.✦ The root r(x)r(x) of a point x∈Lx \in L is the element of the limit represented by the class of the root label ({x},0)(\{x\}, 0) in F({x})F(\{x\}).✦

Let (F(i),fij)(F(i), f_{ij}) be a directed system of sets with injective transitions, each F(i)F(i) carrying a relation RiR_i and a tag ρi:F(i)→Ord\rho_i \colon F(i) \to \mathrm{Ord}, the transitions preserving and reflecting the relations and preserving the tags. The limit relation RR and the limit tag ρ\rho on $\varinjlim_i F(i)$ are given, for x,y∈F(i)x, y \in F(i) with images xˆ,yˆ\hat x, \hat y in the limit, by xˆRyˆ⇔xRiy,ρ(xˆ)=ρi(x).\hat x \mathrel{R} \hat y \iff x \mathrel{R_i} y, \qquad \rho(\hat x) = \rho_i(x).(5)

The Mostowski collapse of a well-founded relation RR on a set QQ is the map π\pi from QQ to sets defined by well-founded recursion as π(x)={π(y):y∈Q,yRx}.\pi(x) = \{\pi(y) : y \in Q,\ y \mathrel{R} x\}.(6)✦

Suppose further that every RiR_i is extensional, elements of F(i)F(i) with the same RiR_i-predecessors being equal, that yRixy \mathrel{R_i} x implies ρi(y)<ρi(x)\rho_i(y) < \rho_i(x), and that every tag lies below an ordinal δ\delta. Then the embedding of the limit into the von Neumann level VδV_\delta is the Mostowski collapse π\pi of the limit relation, an injection $$\pi \colon \varinjlim_i F(i) \hookrightarrow V_\delta.$$(7)✦

Distinct points of LL have distinct roots: r(x)=r(y)⟹x=y(x,y∈L).r(x) = r(y) \implies x = y \qquad (x, y \in L).(8)✦ The roots embedding of LL into Vω1V_{\omega_1} is the injection L↪Vω1,x↦π(r(x)),L \hookrightarrow V_{\omega_1}, \qquad x \mapsto \pi(r(x)),(9)✦ with π\pi the embedding (7) of the limit of the stage quotients, their relations RXR_X and tags ρX\rho_X, and δ=ω1\delta = \omega_1.

The Claim

Theorem 1 (Lemma 5.2). For every family (dk)k∈ℕ(d_k)_{k \in \mathbb{N}} of valid diagrams, dkd_k on {0,…,k−1}\{0, \dots, k - 1\}, there are m,n∈ℕm, n \in \mathbb{N} and an order embedding e:{0,…,m−1}→{0,…,n−1}e \colon \{0, \dots, m - 1\} \to \{0, \dots, n - 1\} with dm≠dn↾e.d_m \neq d_n \restriction e.(10)✦ Assume CH. There is no sequence (p(m))m∈ℕ(p(m))_{m \in \mathbb{N}} of colors such that, for every n∈ℕn \in \mathbb{N}, the family sn(m,e)=p(m)(e:{0,…,m}→{0,…,n} an order embedding)s_n(m, e) = p(m) \qquad \bigl(e \colon \{0, \dots, m\} \to \{0, \dots, n\} \text{ an order embedding}\bigr)(11)✦ passes the test at arity n+1n + 1.

In the paper, the result reads: there is no sequence (sj:j≥1)(s_j : j \ge 1) in SS such that Tk((s|J|)J)T_k((s_{|J|})_J) holds for every k≥1k \ge 1, where sjs_j stands for p(j−1)p(j - 1) and TkT_k for the test at arity kk.

What Is Checked

The claim is stated over CH, the palette SS and the coding γ\gamma, diagrams with their labels, restrictions and validity, the test (4), and families of valid diagrams on {0,…,k−1}\{0, \dots, k - 1\}; the statements (7), (8) and (9) are stated over directed systems with relations and ordinal tags, the stage quotients F(X)F(X) with their transitions, the roots and the Mostowski collapse.

The library proves about these constructions that the quotient map along a restriction is injective, and that every stage diagram dXd^X is valid✦ and, for X⊆YX \subseteq Y, equals dY↾ιXYd^Y \restriction \iota_{XY}.✦ The transitions fXYf_{XY} preserve and reflect the stage relations✦ and preserve the stage tags.✦ For a directed system as in (5), the limit relation is extensional when every RiR_i is✦, and the limit tag is smaller on every predecessor of an element when this holds for every ρi\rho_i and RiR_i.