OctoInformBeta

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

Lemma 5.6: For |X|≥Λ|X| \ge \Lambda, with Λ\Lambda a strong limit, and at most ξ<cf⁡Λ\xi < \operatorname{cf}\Lambda colors; unbounded prefixes extend by one color, staying unbounded

Large sets realize one color pattern at every finite size.

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

For a set YY and j∈ℕj \in \mathbb{N}, [Y]j[Y]^j is the set of jj-element subsets of YY. Let XX be a set, CC a set of colors, and for each j∈ℕj \in \mathbb{N} let cjc_j be a coloring of [X]j[X]^j by CC. If A⊆XA \subseteq X is finite and each cjc_j with j≤|A|j \le |A| takes a single value on [A]j[A]^j, these values form a sequence of colors indexed by the arities 0,…,|A|0, \dots, |A|, and sets of different sizes may give different sequences. The question is whether, for XX large compared with CC, one sequence of colors p0,p1,p2,…p_0, p_1, p_2, \dots serves every size at once: for each kk, a kk-element set A⊆XA \subseteq X on which cjc_j takes the value pjp_j on all of [A]j[A]^j, for every j≤kj \le k.

Patterns and Their Prefixes

A coloring cc of [X]m[X]^m by CC is constant with value q∈Cq \in C on a subset YY of XX when c(s)=qc(s) = q for every s∈[Y]ms \in [Y]^m.✦

A pattern is a sequence p=(pj)j∈ℕp = (p_j)_{j \in \mathbb{N}} of colors in CC, and its prefix of length nn is (p0,…,pn−1)(p_0, \dots, p_{n-1}). A subset YY of XX realizes the prefix of length nn of a pattern pp when cjc_j is constant with value pjp_j on YY for every j<nj < n.✦ For a cardinal Λ\Lambda, the prefix of length nn of a pattern pp is unbounded below Λ\Lambda when, for every cardinal χ<Λ\chi < \Lambda, some subset of XX of cardinality at least χ\chi realizes it.✦

The Claim

Theorem 1. Let Λ\Lambda be a strong limit cardinal and ξ\xi an infinite cardinal with ξ<Λ\xi < \Lambda and ξ<cf⁡Λ\xi < \operatorname{cf}\Lambda. Let XX be a set with |X|≥Λ|X| \ge \Lambda, CC a set of at most ξ\xi colors, and cjc_j, for each j∈ℕj \in \mathbb{N}, a coloring of [X]j[X]^j by CC.

(a) There is a pattern pp such that every k∈ℕk \in \mathbb{N} has a kk-element subset AA of XX with cj(s)=pjfor every j≤k and every s∈[A]j.c_j(s) = p_j \quad \text{for every } j \le k \text{ and every } s \in [A]^j .(1)✦

(b) If the prefix of length nn of a pattern pp is unbounded below Λ\Lambda, there is a color q∈Cq \in C such that the prefix of length n+1n + 1 of the pattern (p0,…,pn−1,q,pn+1,pn+2,…)(p_0, \dots, p_{n-1}, q, p_{n+1}, p_{n+2}, \dots)(2)✦ is unbounded below Λ\Lambda.

In the paper, the result reads: if |X|≥Λ|X| \ge \Lambda and cj:[X]j→Cjc_j \colon [X]^j \to C_j with |Cj|≤ξ|C_j| \le \xi, there are colors pjp_j such that for every kk some Ak∈[X]kA_k \in [X]^k has cj(s)=pjc_j(s) = p_j for all j≤kj \le k and s∈[Ak]js \in [A_k]^j.

What Is Checked

The claims (1) and (2) are stated over a strong limit cardinal Λ\Lambda, an infinite cardinal ξ\xi below Λ\Lambda and below its cofinality, a set XX of cardinality at least Λ\Lambda, colorings cjc_j of [X]j[X]^j by a set CC of at most ξ\xi colors, and two notions on the prefixes of patterns: realized by a subset of XX, and unbounded below Λ\Lambda.