LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)verified 2026-07-29 (claude-fable-5)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

For every ordinal $α$ there is a least ordinal $β$ admitting a map $β \to α$ with cofinal range, and that map may always be taken strictly increasing

Statement

Let $α$ be an ordinal (Ordinal (von Neumann)). Say that a function $f : β \to α$ is cofinal when its range $f [β] = {f (ξ) : ξ \in β}$ is a cofinal subset of $α$ (Cofinal subset of an ordinal), that is, when for every $ζ \in α$ there is $ξ \in β$ with $ζ \leq f (ξ)$ . Then, in ZF:

(a) there is a least ordinal $β$ for which some cofinal $f : β \to α$ exists;

(b) for that least $β$ a cofinal $g : β \to α$ can be taken strictly increasing: $η \in ξ \in β$ implies $g (η) \in g (ξ)$ .

No choice principle is used. The least ordinal of claim (a) is a least element of a set of ordinals, and the map of claim (b) is built by transfinite recursion from a formula.

Facts & Assumptions

Given: An ordinal $α$ , in ZF, with no choice principle. For a set $D$ of ordinals write $\sup D = ⋃ D$ .

[L1]

$C \subseteq α$ is cofinal in $α$ when for every $ζ \in α$ there is $η \in C$ with $ζ \leq η$ ; a subset that is not cofinal is bounded, that is, there is $ζ \in α$ with $η < ζ$ for every $η \in C$ (Cofinal subset of an ordinal).

[L2]

Every nonempty set of ordinals has an $\in$ -least element and is well ordered by $\in$ ; ordinals satisfy trichotomy; $α \subseteq β$ iff $α \in β$ or $α = β$ (Trichotomy and well-ordering of the ordinals, Well-order and well-ordered set).

[L3]

For a set $D$ of ordinals, $\sup D = ⋃ D$ is an ordinal and is the least upper bound of $D$ ; $α \cup {α}$ is an ordinal; every element of an ordinal is an ordinal (Basic closure properties of ordinals, Ordinal (von Neumann)).

[L4]

For a well-order $(W, <)$ and a class rule $G$ defined on functions with domain a proper initial segment of $W$ , there is exactly one $F$ on $W$ with $F (a) = G (F ↾ W_{< a})$ (Transfinite recursion).

[L5]

The range of a function is a set, and $f [β] \subseteq α$ for $f : β \to α$ (Injection, surjection, bijection).

Proof

technique · direct

1.1

The identity map $α \to α$ is cofinal, since $ζ \leq ζ$ for every $ζ \in α$ ; so at least one ordinal, namely $α$ , admits a cofinal map into $α$ .

L1L5

2.1

Put $T = {β \in α \cup {α} : some f : β \to α is cofinal}$ , a set by Power Set and Separation, and nonempty by step 1.1; let $β_{0}$ be its $\in$ -least element, which exists by [L2]. Then $β_{0}$ is least among all ordinals admitting a cofinal map into $α$ : such a $γ$ either lies in $α \cup {α}$ , hence in $T$ , giving $β_{0} \leq γ$ ; or it does not, in which case $α \in γ$ by [L2] and $β_{0} \leq α \in γ$ . This is claim (a).

step 1.1L2L3

3.1

Fix a cofinal $f : β_{0} \to α$ and define $g$ on the well-order $(β_{0}, \in)$ of [L2] by the recursion of [L4]: for $h$ a function with domain $ξ \in β_{0}$ , let $G (h)$ be the $\subseteq$ -larger of $f (ξ)$ and $\sup {η^{'} \cup {η^{'}} : η^{'} \in ran (h)}$ when that value lies in $α$ , and $f (ξ)$ otherwise; [L4] then supplies exactly one $g : β_{0} \to α$ with $g (ξ) = G (g ↾ ξ)$ for every $ξ \in β_{0}$ .

step 2.1L2L3L4

4.1

The exceptional branch of $G$ is never taken, and $g$ is strictly increasing and cofinal: both branches of $G$ take values in $α$ , so $g [ξ] \subseteq α$ for every $ξ \in β_{0}$ ; and $g ↾ ξ$ is a map $ξ \to α$ with $ξ \in β_{0}$ , so its range is not cofinal by the minimality of step 2.1, whence [L1] supplies $ζ \in α$ with $g (η) < ζ$ for every $η \in ξ$ , so $g (η) \cup {g (η)} \leq ζ$ and $\sup {g (η) \cup {g (η)} : η \in ξ} \leq ζ \in α$ by [L2] and [L3]; that supremum therefore lies in $α$ , the first branch applies, and $g (η) \in g (η) \cup {g (η)} \subseteq g (ξ)$ gives $g (η) \in g (ξ)$ for every $η \in ξ$ ; finally $f (ξ) \subseteq g (ξ)$ for every $ξ$ , so $g$ is cofinal because $f$ is, which is claim (b).

step 2.1step 3.1L1L2L3L5∎

Remarks

The degenerate values, and why they are not special cases in the proof. For $α = 0$ the empty function $0 \to 0$ is cofinal, vacuously, so the least $β$ is $0$ . For a successor $α = γ \cup {γ}$ the one-point map $0 \mapsto γ$ is cofinal and no map from $0$ is, so the least $β$ is $1$ . Both are read off the definition and neither needs separate treatment above: step 4.1 runs vacuously when $β_{0} = 0$ , and at $β_{0} = 1$ the supremum in step 3.1 is a supremum over the empty set.

Why minimality is what makes the strictly increasing map exist. The construction needs the partial range $g [ξ]$ to be bounded below $α$ at every stage $ξ < β_{0}$ , and that is exactly the statement that no shorter map is cofinal. For a length that is not least the claim genuinely fails: there is a cofinal map $ω \cup {ω} \to ω$ , namely $ξ \mapsto ξ$ on $ω$ together with $ω \mapsto 0$ , but there is no strictly increasing map $ω \cup {ω} \to ω$ at all, since its value at $ω$ would have to exceed every natural number.

What is not claimed. Nothing here says the least $β$ is a cardinal, or even a limit ordinal; that is a theorem about limit $α$ , and it is proved separately once the cofinality function has been given a name.

Depends on

Used by

Dependency tree · two levels

19 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

UCL, Axiomatic Set Theory, Ch. 4: Cardinal Arithmetic (standard reference, not scraped)
Cofinality (Wikipedia) (standard reference, not scraped)
T. Jech, Set Theory, 3rd millennium ed., Ch. 3 (Cardinal numbers) (standard reference, not scraped)

For every ordinal αα there is a least ordinal ββ admitting a map β→αβ→α with cofinal range, and that map may always be taken strictly increasing