TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passverified 2026-08-05 (gpt-5.6-sol-codex-subscription)

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.

$cf (α) \leq α$ ; $cf (0) = 0$ and $cf (α + 1) = 1$ ; for a limit ordinal $λ$ the value $cf (λ)$ is an infinite cardinal with $cf (cf (λ)) = cf (λ)$ , so it is regular; and every cofinal subset of $λ$ has cardinality at least $cf (λ)$ , a value that is attained

Statement

Work in ZF; no choice principle is used. Let $cf$ be the cofinality of Cofinality $cf (α)$ , and regular and singular cardinals. Then:

(a) $cf (α) \leq α$ for every ordinal $α$ (Ordinal (von Neumann));

(b) $cf (0) = 0$ , and $cf (α + 1) = 1$ for every ordinal $α$ , where $α + 1 = α \cup {α}$ (Ordinal addition $α + β$ );

(c) for a limit ordinal $λ$ (Successor and limit ordinals), $cf (λ)$ is an infinite cardinal (Cardinal (initial ordinal) and cardinality) and $cf (cf (λ)) = cf (λ)$ , so $cf (λ)$ is a regular cardinal;

(d) for a limit ordinal $λ$ , every cofinal $C \subseteq λ$ (Cofinal subset of an ordinal) satisfies $cf (λ) \leq ∣ C ∣$ , and some cofinal subset of $λ$ has cardinality exactly $cf (λ)$ .

Clause (c) is what discharges the naming obligation of Cofinality $cf (α)$ , and regular and singular cardinals: "regular" is defined through $cf$ , and it is a theorem, not a convention, that $cf$ of a limit ordinal is a cardinal at which the definition can be tested.

Facts & Assumptions

Given: ZF, with no choice principle. Throughout, a map $f : β \to α$ is called cofinal when $f [β]$ is cofinal in $α$ .

[L1]

$cf (α)$ is the least ordinal $β$ admitting a cofinal $f : β \to α$ ; for that $β$ a strictly increasing cofinal $g : β \to α$ exists (Cofinality $cf (α)$ , and regular and singular cardinals, For every ordinal $α$ there is a least ordinal $β$ admitting a map $β \to α$ with cofinal range, and that map may always be taken strictly increasing).

[L2]

$C \subseteq α$ is cofinal when every $ζ \in α$ has some $η \in C$ with $ζ \leq η$ (Cofinal subset of an ordinal).

[L3]

Ordinals: trichotomy; $α \subseteq β$ iff $α \in β$ or $α = β$ ; $α \notin α$ ; every element of an ordinal is an ordinal; every set of ordinals is well ordered by $\in$ (Trichotomy and well-ordering of the ordinals, Basic closure properties of ordinals, Well-order and well-ordered set).

[L4]

Every ordinal is exactly one of $0$ , a successor, or a limit, and $ω$ is the least limit ordinal (Successor and limit ordinals, $ω$ is the least limit ordinal).

[L5]

For a well-orderable $X$ : $X \approx ∣ X ∣$ , the value is a cardinal, equinumerous sets receive the same one, and $∣ α ∣ = α$ exactly when $α$ is a cardinal (A set equinumerous with some ordinal has a least such ordinal, that ordinal is a cardinal, and equinumerous sets get the same one; no choice principle is used, Cardinal (initial ordinal) and cardinality).

[L6]

For cardinals $κ \leq λ$ iff $κ ⪯ λ$ , and $A ⪯ B$ with both well-orderable gives $∣ A ∣ \leq ∣ B ∣$ (claim (a) of Commutativity, associativity, distributivity and monotonicity of $\oplus$ and $\otimes$ , the unit laws, the two exponent laws, and $κ \leq λ$ if and only if $κ$ injects into $λ$ ).

[L7]

Every well-order has a unique order type, and the isomorphism onto it is a bijection (Every well-order has a unique order type, Order embedding and order isomorphism, Equinumerous sets, $A \approx B$ and $A ⪯ B$ ).

[L8]

Precomposing a function with a bijection onto its domain leaves its range unchanged, since $g \circ h$ has image $g [h [μ]] = g [β]$ when $h : μ \to β$ is onto; a strictly increasing map of ordinals is injective, and satisfies $ξ \leq η \Rightarrow g (ξ) \leq g (η)$ , both by trichotomy (Injection, surjection, bijection, Trichotomy and well-ordering of the ordinals).

[L9]

A cardinal $κ$ is infinite exactly when $ω \leq κ$ (Cardinal sum $κ \oplus λ$ , product $κ \otimes λ$ and exponentiation $κ^{λ}$ , and why they are written apart from the ordinal operations).

Proof

technique · direct

1.1

Claim (a): the identity $α \to α$ is cofinal by [L2], so the least length in [L1] is at most $α$ .

L1L2

1.2

Claim (b): for $α = 0$ the empty map $0 \to 0$ is cofinal vacuously, so $cf (0) = 0$ ; for $α + 1$ the map $0 \mapsto α$ is cofinal, since every $ζ \in α + 1$ satisfies $ζ \leq α$ by [L3], while the empty map into the nonempty $α + 1$ is not, so $cf (α + 1) = 1$ .

L1L2L3

1.3

Let $λ$ be a limit ordinal, $β = cf (λ)$ and $g : β \to λ$ strictly increasing and cofinal by [L1]; then $β$ is a limit ordinal, so $ω \leq β$ by [L4]: $β \neq 0$ because $0 \in λ$ and the empty range is not cofinal, and $β = γ + 1$ is impossible, since then $g (η) \leq g (γ)$ for all $η \in β$ by [L8], so cofinality would give $λ \subseteq g (γ) + 1$ while $g (γ) \in λ$ gives $g (γ) + 1 \subseteq λ$ , making $λ = g (γ) + 1$ a successor.

L1L2L3L4L8

1.4

With $λ$ , $β$ , $g$ as above, $β$ is a cardinal: if $μ = ∣ β ∣ \in β$ then a bijection $h : μ \to β$ makes $g \circ h : μ \to λ$ a map with the same range as $g$ , hence cofinal, so the least length would be at most $μ \in β$ , contradicting $β = cf (λ)$ ; so $∣ β ∣ = β$ and [L5] applies.

L1L2L5L8

2.1

Claim (c): $β$ is an infinite cardinal by steps 1.3, 1.4 and [L9]; and writing $γ = cf (β)$ , step 1.1 gives $γ \leq β$ , while a cofinal $k : γ \to β$ makes $g \circ k : γ \to λ$ cofinal — given $ζ \in λ$ pick $ξ \in β$ with $ζ \leq g (ξ)$ , then $ρ \in γ$ with $ξ \leq k (ρ)$ , and $g (ξ) \leq g (k (ρ))$ by [L8] — so $β = cf (λ) \leq γ$ and therefore $cf (cf (λ)) = cf (λ)$ .

step 1.1step 1.3step 1.4L1L2L8L9

3.1

Claim (d): a cofinal $C \subseteq λ$ is a set of ordinals, well ordered by $\in$ by [L3], with order type $δ$ and an order isomorphism $e : δ \to C$ by [L7]; then $e$ is a cofinal map $δ \to λ$ , so $β \leq δ$ by [L1], and applying [L5] and [L6] gives $β = ∣ β ∣ \leq ∣ δ ∣ = ∣ C ∣$ using step 2.1; conversely $g [β]$ is cofinal with $∣ g [β] ∣ = β$ , since $g$ is injective by [L8].

step 2.1L1L2L3L5L6L7L8

4.1

Claims (a), (b), (c) and (d) are established, in ZF.

step 1.1step 1.2step 2.1step 3.1∎

Remarks

Why (c) is restricted to limit ordinals. At $0$ and at a successor the cofinality is $0$ or $1$ , neither of which is an infinite cardinal, and the regular/singular vocabulary is not applied there. Since every infinite cardinal is a limit ordinal, the restriction costs nothing where the notion is used.

What clause (d) is for. It converts a cofinality question into a counting question: to show $cf (λ) \leq κ$ it suffices to exhibit any cofinal subset of size $κ$ , with no attention to its order type. That is how every cofinality on the companion page is computed, and the attainment half is what makes the bound sharp.

Where the strictly increasing witness is spent. Three times, and each time essentially: in step 1.3, to know that a witness of successor length would have a largest value; in step 2.1, to know that $g$ preserves $\leq$ , without which the composite $g \circ k$ need not be cofinal; and in step 3.1, to know that $g$ is injective, without which $g [β]$ need not have cardinality $β$ . That is why For every ordinal $α$ there is a least ordinal $β$ admitting a map $β \to α$ with cofinal range, and that map may always be taken strictly increasing proves claim (b) rather than stopping at the existence of a least length.

Depends on

Used by

…and 11 more results.

Cited to discharge well-definedness by Cofinality cf(α), and regular and singular cardinals.

Dependency tree · two levels

51 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)
Regular cardinal (Wikipedia) (standard reference, not scraped)