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.1L1L2

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

1.2L1L2L3

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$ .

1.3L1L2L3L4L8

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.

1.4L1L2L5L8

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.

2.1step 1.1step 1.3step 1.4L1L2L8L9

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 (λ)$ .

3.1step 2.1L1L2L3L5L6L7L8

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].

4.1step 1.1step 1.2step 2.1step 3.1∎

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

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.

$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

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources