OctoInformBeta

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

Proposition 5.7: Under CH, |I|<Λ|I| < \Lambda when every tuple fails its test at only countably many points of a base of size ℵ1\aleph_1

Objects with uncountable base have fewer than Λ\Lambda index points.

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 tuple from a set II is an injective map t:{0,…,n}→It \colon \{0, \dots, n\} \to I for some n∈ℕn \in \mathbb{N}; its length is n+1n + 1.✦ The subsequence of a tuple tt 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, of length m+1m + 1.✦

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 << on it, 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 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.✦

Under the continuum hypothesis (CH), 2ℵ0=ℵ12^{\aleph_0} = \aleph_1, the objects of this page are certain normal forms, defined below by a condition on the colors of their tuples. Proposition 5.7 asks how large the index set of an object can be once its base order is uncountable. Two cardinals enter the answer: ξ=2ℵ1\xi = 2^{\aleph_1}✦ and the tail threshold Λ=ℶξ+,\Lambda = \beth_{\xi^+},(1)✦ the value of the beth function at the initial ordinal of the successor cardinal ξ+\xi^+. The library states the answer for objects, and also for tuples from an index set colored at the points of an arbitrary set of size at most ℵ1\aleph_1, with colors and tests as defined below, together with two facts on colors.

Colors

A binary sequence is a map a:ℕ→{0,1}a \colon \mathbb{N} \to \{0, 1\}, and 2ω2^\omega is the set of binary sequences.✦ Two binary sequences aa and bb are equal outside a finite set when they differ at finitely many places: a=*b⇔{n∈ℕ:a(n)≠b(n)} is finite.a =^* b \iff \{\, n \in \mathbb{N} : a(n) \neq b(n) \,\} \text{ is finite}.(2)✦ The palette S=2ω/=*S = 2^\omega/{=^*} is the set of colors, the equivalence classes of =*=^*✦, and the color [a][a] of a binary sequence aa is its class.✦ The color of a tuple tt from the index set of a normal form MM at a point bb of its base order is ct(b)=[a(t,⋅,b)]c_t(b) = [a(t, \cdot, b)].✦

When II is linearly ordered, the increasing enumeration of a finite subset ss of II with n+1n + 1 elements is the tuple s→:{0,…,n}→I\vec s \colon \{0, \dots, n\} \to I that lists ss in increasing order.✦ For a coloring cc of the tuples from II by a set CC and an element qq of CC, the color of a finite subset rr of II is c[r]=c(r→) if r≠∅,c[∅]=q.c[r] = c(\vec r) \ \text{ if } r \neq \emptyset, \qquad c[\emptyset] = q.(3)✦

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 a∈Aa \in A is the label ({a},0)(\{a\}, 0)✦, and an injection e:A→A′e \colon A \to A' carries a label (J,i)(J, i) on AA to the label (e[J],i)(e[J], i) on A′A'.✦ A tag is an element of ω1\omega_1, a countable ordinal.✦

A diagram DD on a set AA of positions is a triple (E,R,ρ)(E, R, \rho) in which EE and RR are binary relations on the labels on AA and ρ\rho assigns a tag to each label.✦ A diagram (E,R,ρ)(E, R, \rho) on AA is valid when EE is an equivalence relation, RR is unchanged when a label is replaced by an EE-equivalent one, ρ\rho is constant on EE-classes, ρ(x)<ρ(y)\rho(x) < \rho(y) whenever xRyx \mathrel{R} y, labels with the same RR-predecessors are EE-equivalent, and positions with EE-equivalent roots are equal.✦ The restriction D↾eD{\restriction}e of a diagram DD on A′A' along an injection e:A→A′e \colon A \to A' is the diagram on AA that relates two labels by EE, or by RR, when DD so relates their images under ee, and gives each label the tag of its image.✦

Let 𝒟n\mathcal{D}_n be the set of diagrams on {0,…,n}\{0, \dots, n\}. Under CH, code\operatorname{code} is a one-to-one map from the disjoint union of the sets 𝒟n\mathcal{D}_n to the palette SS, as in (4), code⁡:⨆n∈ℕ𝒟n→S,\operatorname{code} \colon \bigsqcup_{n \in \mathbb{N}} \mathcal{D}_n \to S,(4)✦ written code⁡(n,D)\operatorname{code}(n, D) at a diagram D∈𝒟nD \in \mathcal{D}_n.

Let n∈ℕn \in \mathbb{N}. A family φ\varphi of colors φ(e)∈S\varphi(e) \in S, one for each order embedding e:{0,…,m}→{0,…,n}e \colon \{0, \dots, m\} \to \{0, \dots, n\} with m∈ℕm \in \mathbb{N}, passes when there is a diagram d∈𝒟nd \in \mathcal{D}_n such that for every such ee d↾e is valid and code⁡(m,d↾e)=φ(e).d{\restriction}e \text{ is valid and } \operatorname{code}(m, d{\restriction}e) = \varphi(e).(5)✦ A tuple tt from II of length n+1n + 1 passes the test for a coloring cc of the tuples from II by SS when the family e↦c(t∘e)e \mapsto c(t \circ e) of the colors of its subsequences passes, and fails it otherwise.✦

Under CH, a normal form MM is an object when for every tuple tt from its index set II the set {b∈B:t fails the test for the coloring u↦cu(b)}\{\, b \in B : t \text{ fails the test for the coloring } u \mapsto c_u(b) \,\}(6)✦ is countable.

The Claim

Theorem 1 (Proposition 5.7).

  1. Assume CH, and let MM be an object whose base order BB is uncountable. Then its index set II satisfies |I|<Λ.|I| < \Lambda.(7)✦

  2. Assume CH. Let II be a set, let BB be an uncountable set with |B|≤ℵ1|B| \le \aleph_1, and let cc assign to every tuple tt from II and every b∈Bb \in B a color c(t,b)∈Sc(t, b) \in S. If for every tuple tt from II the points b∈Bb \in B at which tt fails the test for the coloring u↦c(u,b)u \mapsto c(u, b) form a countable set, then |I|<Λ.|I| < \Lambda.(8)✦

  3. If BB is a set with |B|≤ℵ1|B| \le \aleph_1, then the set SBS^B of maps from BB to SS, the color profiles on BB, satisfies |SB|≤ξ.|S^B| \le \xi.(9)✦

  4. Let II be a linearly ordered set, cc a coloring of the tuples from II by a set CC, qq an element of CC and p0,p1,…p_0, p_1, \dots a sequence in CC, with the colors of finite sets as in (3). Let ss be a finite subset of II with n+1n + 1 elements such that c[r]=pjc[r] = p_j for every j≤n+1j \le n + 1 and every subset rr of ss with jj elements. Then for every order embedding e:{0,…,m}→{0,…,n}e \colon \{0, \dots, m\} \to \{0, \dots, n\}, c(s→∘e)=pm+1.c(\vec s \circ e) = p_{m+1}.(10)✦

In the paper, the result reads: if M∈KM \in K and BMB^M is uncountable, then |IM|<Λ|I^M| < \Lambda, with KK the paper’s class and IMI^M, BMB^M the index set and the base order of MM.

What Is Checked

The claim is stated over CH, the cardinals ξ\xi and Λ\Lambda of (1), tuples and their subsequences, the palette SS and the colors [a][a], increasing enumerations and the colors of finite sets (3), labels, tags and diagrams with their validity, restrictions and code (4), the test of a tuple (5), and normal forms, their colors ct(b)c_t(b) and the objects among them (6).