OctoInformBeta

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

Lemma 5.5: For each arity and infinite χ<Λ\chi<\Lambda, some μ<Λ\mu<\Lambda makes every coloring of μ\mu points by ξ\xi colors homogeneous on χ\chi points

Large homogeneous sets below a strong limit cardinal.

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.5 is a partition estimate of Erdős-Rado type below a strong limit cardinal. Fix a strong limit cardinal Λ\Lambda and an infinite cardinal ξ<Λ\xi<\Lambda bounding the number of colors; the tail threshold Λ=ℶξ+\Lambda=\beth_{\xi^+} with ξ=2ℵ1\xi=2^{\aleph_1} is such a pair. The question is whether homogeneous sets of every infinite size χ<Λ\chi<\Lambda can be forced from below Λ\Lambda: for each arity mm, is there μ<Λ\mu<\Lambda with μ→(χ)ξm\mu\to(\chi)^m_\xi?

The library states the estimate in two forms, on a well-ordered set and inside a large subset of an arbitrary set, together with an existence theorem for end-homogeneous sequences, defined below, and a step from arity mm to arity m+1m+1 along them.

Colorings and Homogeneous Sets

For a set XX, [X]<ω[X]^{<\omega} is the set of finite subsets of XX and [X]m[X]^m the set of its mm-element subsets. A coloring cc of the finite subsets of XX by a set CC of colors is a map c:[X]<ω→Cc\colon[X]^{<\omega}\to C.

Let Y⊆XY\subseteq X and p∈Cp\in C. A coloring cc of the finite subsets of XX by CC is constant on [Y]m[Y]^m with value pp when c(s)=pc(s)=p for every s∈[Y]ms\in[Y]^m.✦ A subset YY of XX is homogeneous in arity mm for a coloring cc of the finite subsets of XX by CC when cc is constant on [Y]m[Y]^m with some value: there is p∈C with c(s)=p for every s∈[Y]m.\text{there is } p\in C \text{ with } c(s)=p \text{ for every } s\in[Y]^m.(1)✦

Let JJ and XX be linearly ordered sets and cc a coloring of the finite subsets of XX by CC. An end-homogeneous sequence for cc is a pair (r,x)(r,x) of an order embedding r:J→Xr\colon J\to X and a point x∈Xx\in X such that for every α∈J\alpha\in J and every finite set aa of elements of JJ below α\alpha, adding r(α)r(\alpha) or adding xx to the image r[a]r[a] gives the same color: c({r(α)}∪r[a])=c({x}∪r[a])for every α∈J and every finite a⊆{β∈J:β<α}.c(\{r(\alpha)\}\cup r[a])=c(\{x\}\cup r[a]) \quad\text{for every } \alpha\in J \text{ and every finite } a\subseteq\{\beta\in J:\beta<\alpha\}.(2)

The Claim

Theorem 1. Let mm be a natural number.

(a) Let Λ\Lambda be a strong limit cardinal and ξ\xi and χ\chi infinite cardinals below Λ\Lambda. There is an infinite cardinal μ<Λ\mu<\Lambda such that for every well-ordered set XX of cardinality μ\mu, every set CC with |C|≤ξ|C|\le\xi and every coloring cc of the finite subsets of XX by CC, some Y⊆X with |Y|≥χ is homogeneous for c in arity m.\text{some } Y\subseteq X \text{ with } |Y|\ge\chi \text{ is homogeneous for } c \text{ in arity } m.(3)✦

(b) For Λ\Lambda, ξ\xi and χ\chi as in (a), there is a cardinal μ<Λ\mu<\Lambda such that for all sets XX and CC with |C|≤ξ|C|\le\xi, every Y⊆XY\subseteq X with |Y|≥μ|Y|\ge\mu and every coloring cc of the finite subsets of XX by CC, some Z⊆Y with |Z|≥χ is homogeneous for c in arity m.\text{some } Z\subseteq Y \text{ with } |Z|\ge\chi \text{ is homogeneous for } c \text{ in arity } m.(4)✦

(c) Let JJ and XX be well-ordered sets and cc a coloring of the finite subsets of XX by a set CC, with |J|⋅|C||[J]<ω|<|X||J|\cdot|C|^{|[J]^{<\omega}|}<|X|. There are an order embedding r:J→Xr\colon J\to X and a point x∈Xx\in X such that (r,x) is an end-homogeneous sequence for c and r(α)<x for every α∈J.(r,x) \text{ is an end-homogeneous sequence for } c \text{ and } r(\alpha)<x \text{ for every } \alpha\in J.(5)✦

(d) Let JJ and XX be linearly ordered sets, cc a coloring of the finite subsets of XX by a set CC and (r,x)(r,x) an end-homogeneous sequence for cc. If Y⊆JY\subseteq J is homogeneous in arity mm for the coloring a↦c({x}∪r[a])a\mapsto c(\{x\}\cup r[a]) of the finite subsets of JJ, then r[Y] is homogeneous for c in arity m+1.r[Y] \text{ is homogeneous for } c \text{ in arity } m+1.(6)✦

In the paper, the result reads: for every positive mm and every infinite χ<Λ\chi<\Lambda there is μ<Λ\mu<\Lambda such that every c:[μ]m→Cc\colon[\mu]^m\to C with |C|≤ξ|C|\le\xi has a homogeneous subset of cardinality χ\chi.

What Is Checked

The claim is stated over colorings of the finite subsets of a set, homogeneity in arity mm (1) as constancy on the mm-element subsets, end-homogeneous sequences (2) of one linear order in another, and a strong limit cardinal Λ\Lambda with infinite cardinals ξ,χ<Λ\xi,\chi<\Lambda.