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.
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
Statement
Call a set well-orderable when some relation well-orders it (Well-order and well-ordered set). Work in ZF, with no choice principle. Then:
(a) is well-orderable if and only if (Equinumerous sets, and ) for some ordinal (Ordinal (von Neumann)).
(b) If is well-orderable there is a least ordinal equinumerous with . It is written and called the cardinality of .
(c) is a cardinal (Cardinal (initial ordinal) and cardinality).
(d) If and is well-orderable, then is well-orderable and .
(e) for every ordinal , and exactly when is a cardinal.
Assuming the Axiom of Choice (The Axiom of Choice) every set is well-orderable (The well-ordering theorem), so is then defined for every set and is exactly the cardinality of Cardinal (initial ordinal) and cardinality.
Why this item exists. Cardinal (initial ordinal) and cardinality introduces under the hypothesis "Assume the Axiom of Choice", and it needs that hypothesis only to know that carries a well-order at all. Everything below is about well-orderable sets and is a theorem of ZF, which is what makes it possible to state Hessenberg's theorem and Tarski's theorem, one of which is choice-free and the other of which is precisely about the gap between ZF and ZFC.
Facts & Assumptions
Given: The axioms of ZF, in particular Separation and Replacement. No choice principle is assumed except where the Axiom of Choice is named.
Every well-order is order isomorphic to exactly one ordinal, its order type (Every well-order has a unique order type).
An order isomorphism is in particular a bijection (Order embedding and order isomorphism, Injection, surjection, bijection).
is an ordinal, every element of an ordinal is an ordinal, , and if and only if or (Basic closure properties of ordinals, Ordinal (von Neumann)).
For ordinals exactly one of , , holds, and every nonempty set of ordinals has an -least element (Trichotomy and well-ordering of the ordinals).
is reflexive, symmetric and transitive, and the order relation on ordinals is (Equinumerous sets, and , Ordinal (von Neumann)).
An ordinal is a cardinal when no satisfies ; under the Axiom of Choice, is the least ordinal equinumerous with (Cardinal (initial ordinal) and cardinality).
Assuming the Axiom of Choice, every set carries a well-order (The Axiom of Choice, The well-ordering theorem).
Proof
If well-orders then has an order type and the collapsing map is an order isomorphism, hence a bijection , so .
Conversely, if is a bijection then is a well-order of , since transports irreflexivity, transitivity, trichotomy and the least-element property of on back to ; this proves claim (a).
Assume now for an ordinal , and put , a set by Separation inside the ordinal , all of whose elements are ordinals, and nonempty because and .
By [L4] the set has an -least element , and .
is least among all ordinals equinumerous with : given , trichotomy gives , in which case and by minimality; or else , in which case gives , while gives , so again . This proves claim (b), with .
Claim (c): if had then by [L5], so by step 3.1, whence and , which [L3] forbids; so is a cardinal.
Claim (d): if then an ordinal is equinumerous with exactly when it is equinumerous with , by symmetry and transitivity of , so the two least such ordinals coincide; and makes well-orderable by step 1.2.
Claim (e): , so by step 3.1; if is a cardinal then no is equinumerous with , so the least ordinal equinumerous with is itself; and conversely makes a cardinal by step 4.1.
Assuming the Axiom of Choice, every set carries a well-order by [L7], hence by step 1.1 and is defined for every set; and by step 3.1 it is the least ordinal equinumerous with , which is what [L6] calls the cardinality of .
Remarks
What is choice-free and what is not. Claims (a) to (e) are theorems of ZF: they say what happens for a well-orderable set, and the hypothesis of well-orderability is carried explicitly rather than supplied by an axiom. The Axiom of Choice enters only in the last step, where it removes the hypothesis by making every set well-orderable. Without choice a set may be equinumerous with no ordinal at all, and then simply does not exist; that is the situation Hartogs: an ordinal that does not inject into a given set is designed for.
Nothing is chosen. The one place a selection might be expected is step 2.1, and there the element taken is the -least member of , which is determined by and not selected from it. Step 3.1 then shows that the bound , which exists only to turn "the least ordinal equinumerous with " into an instance of Separation over a set, does not affect the answer.
Notation. From here on always means the ordinal of claim (b). For a finite set this is not yet known to agree with the natural number written in The cardinality of a finite set; that agreement is a theorem and is proved on this page.
Depends on
- Cardinal (initial ordinal) and cardinality
- Ordinal (von Neumann)
- Basic closure properties of ordinals
- Trichotomy and well-ordering of the ordinals
- Equinumerous sets, $A \approx B$ and $A \preceq B$
- Injection, surjection, bijection
- Every well-order has a unique order type
- Well-order and well-ordered set
- Order embedding and order isomorphism
- The well-ordering theorem
- The Axiom of Choice
Used by
- Absorption: for cardinals κ, λ with κ infinite and λ ≤ κ, κ ⊕ λ = κ, and κ ⊗ λ = κ when λ ≠ 0 Corollary
- Assuming the Axiom of Choice: κ < κ^cf(κ) for every infinite cardinal κ, and cf(2^κ) > κ; in particular cf(2^ℵ₀) > ℵ₀ Corollary
- The clauses at 0, at a successor and at a limit determine exactly one operation α ↦ ℵ_α, in ZF, and — assuming the Axiom of Choice — exactly one operation α ↦ ℶ_α; each value is an infinite cardinal, each is strictly increasing and continuous at limits, and α ≤ ℵ_α Corollary
- Cardinal sum κ ⊕ λ, product κ ⊗ λ and exponentiation κ^λ, and why they are written apart from the ordinal operations Definition
- The sum ∑_i ∈ I κᵢ and the product ∏_i ∈ I κᵢ of an indexed family of cardinals, defined under the Axiom of Choice Definition
- An ordinal α with ℵ_α = α, built as the supremum of the tower ℵ₀, ℵ_ℵ₀, ℵ_ℵ_ℵ₀, …, and its cofinality is ℵ₀ Example
- Assuming countable choice, cf(ℵ_ω₁) = ℵ₁, so singular does not mean of countable cofinality Example
- Assuming the Axiom of Choice: ℵ₀^ℵ₀ = 2^ℵ₀ and | ℝ^ℝ | = 2^2^ℵ₀, computed from the exponent laws and Hessenberg Example
- Assuming the Axiom of Choice: ℶ₀ = ℵ₀, ℶ₁ = 2^ℵ₀ = | ℝ |, ℶ₂ = | P(ℝ) |, and ℶ_ω has cofinality ℵ₀ Example
- cf(ℵ_ω) = ℵ₀, computed from the cofinal map n ↦ ℵₙ Example
- ℝ ≈ P(ℕ) in ZF, by the Cantor set for one injection and by the cuts {q ∈ ℚ : q < x} for the other; so | ℝ | = 2^ℵ₀ under the Axiom of Choice Example
- ℵ₀ ⊕ ℵ₀ = ℵ₀ ⊗ ℵ₀ = ℵ₀, ℵ₁ ⊕ ℵ₀ = ℵ₁ and 5 ⊕ ℵ₀ = ℵ₀, computed from absorption and, in the countable cases, independently from the published bijection ω × ω ≈ ω Example
- ℵ₁ ≤ 2^ℵ₀ under the Axiom of Choice, because 2^ℵ₀ is a cardinal strictly above ℵ₀ and ℵ₁ is the least such; so ω₁ injects into ℝ Example
- Commutativity, associativity, distributivity and monotonicity of ⊕ and ⊗, the unit laws, the two exponent laws, and κ ≤ λ if and only if κ injects into λ Lemma
- Disjoint union, cartesian product, function space and power set respect equinumerosity, and for ordinals α, β the sets α sqcup β and α × β carry explicit well-orders, so their cardinalities exist in ZF Lemma
- For every set A the Hartogs number ℵ(A) is a cardinal, and for every cardinal κ it is the least cardinal strictly above κ; this is a theorem of ZF Lemma
- Under choice, c(X) is a well-defined cardinal Lemma
- Under choice, χ(x,X) and χ(X) are well-defined cardinals Lemma
- What each result on this page costs in choice, and where the continuum escapes what ZFC can decide Remark
- Assuming the Axiom of Choice, 2^κ = | P(κ) |, and Cantor's theorem in cardinal form: κ < 2^κ Theorem
- cf(α) ≤ α; 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 Theorem
- Comparability of arbitrary sets, that any two sets admit an injection one way or the other, is equivalent to the Axiom of Choice Theorem
- Every infinite cardinal is ℵ_α for exactly one ordinal α, in ZF; and, assuming the Axiom of Choice, every infinite set is equinumerous with exactly one aleph Theorem
- Every natural number and ω are cardinals, every infinite cardinal is a limit ordinal, and on the natural numbers the cardinal operations are the published finite counting operations, with | A | in the finite sense equal to | A | in the cardinal sense Theorem
- Hessenberg: κ ⊗ κ = κ for every infinite cardinal κ, proved in ZF from the canonical well-order of κ × κ Theorem
- König's theorem: assuming the Axiom of Choice, if κᵢ < λᵢ for every i ∈ I then ∑_i ∈ I κᵢ < ∏_i ∈ I λᵢ Theorem
- Tarski: the Axiom of Choice is equivalent to the statement that A × A ≈ A for every infinite set A, so extending Hessenberg's theorem from the alephs to arbitrary sets is exactly as strong as choice Theorem
- ℵ₀ is regular in ZF; assuming the Axiom of Choice every successor aleph ℵ_α+1 is regular; cf(ℵ_ω) = ℵ₀, so ℵ_ω is singular, and under choice it is the least singular infinite cardinal Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 64 results over 22 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- P. Koellner, Set Theory: The Independence Phenomenon, Ch. 3 (standard reference, not scraped)
- Cardinal number (Wikipedia) (standard reference, not scraped)
- Von Neumann cardinal assignment (Wikipedia) (standard reference, not scraped)
- T. Jech, Set Theory, 3rd millennium ed., Ch. 3 (Cardinal numbers) (standard reference, not scraped)