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.
Trichotomy and well-ordering of the ordinals
Statement
For ordinals and (Ordinal (von Neumann)), exactly one of
holds. Moreover every nonempty set of ordinals has an -least element, and consequently ordered by is a well-order (Well-order and well-ordered set) whose strict part is membership.
So the ordinals are linearly ordered by , every set of them is well ordered, and Transfinite induction is available on any such set. No choice principle is used.
Facts & Assumptions
Given: Ordinals , , and a nonempty set whose members are all ordinals.
An ordinal is a transitive set on which is a strict well-order (Ordinal (von Neumann)).
Every element of an ordinal is an ordinal; ; if and only if or ; and any two ordinals are comparable under inclusion (Basic closure properties of ordinals).
A partial order is a reflexive, antisymmetric and transitive relation; a total order is a partial order any two of whose elements are comparable; and the strict part of is and (Partial order and partially ordered set).
A well-order is a total order in which every nonempty subset has a least element (Well-order and well-ordered set).
Transfinite induction holds on every well-order (Transfinite induction).
Proof
At least one alternative holds: by [L1] either or , and in the first case [L1] gives or , in the second or .
At most one alternative holds: together with gives ; together with gives ; and together with gives by transitivity of and hence ; each contradicts [L1].
Least elements: fix ; if then is -least in , because with would lie in , so trichotomy leaves or ; otherwise is a nonempty subset of and has an -least element there, and is -least in , because with would satisfy by transitivity of and so lie in strictly below , and trichotomy again leaves or .
On the relation satisfies the three axioms of [L2], since inclusion is reflexive, antisymmetric by extensionality, and transitive, so it is a partial order; it is total by [L1] and step 1.1; its strict part in the sense of [L2] is membership, since with is by [L1]; and every nonempty subset of has a least element by step 3.1, so is a well-order in the sense of [L3] and [L4] applies to it.
Exactly one of the three alternatives holds, every nonempty set of ordinals has an -least element, and every set of ordinals is well ordered by inclusion.
Remarks
Why this is not circular. The trichotomy of on a single ordinal is part of Ordinal (von Neumann); what is proved here is trichotomy between arbitrary ordinals, which is a statement about the whole class and not about any one set. The bridge is inclusion comparability, proved in Basic closure properties of ordinals by intersecting the two ordinals, and the intersection argument is where the two levels meet.
The class of ordinals behaves like a well-order without being a set. Every nonempty set of ordinals has a least element, and in fact so does every nonempty definable collection of them: if holds for some , apply the statement to the set , which is nonempty. That the collection of all ordinals is nevertheless not a set is Burali-Forti: there is no set of all ordinals.
A set of ordinals need not be an ordinal. Well-ordering by is only half of the definition; transitivity is the other half. The set , that is , is well ordered by membership but is not transitive, so it is not an ordinal. A transitive set of ordinals is one, which is the form in which this lemma gets used in Every well-order has a unique order type and Hartogs: an ordinal that does not inject into a given set.
Depends on
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
- Ordinal addition exists and is unique: the clauses at 0, at a successor and at a limit determine one operation, and its values are ordinals Corollary
- Ordinal exponentiation exists and is unique, with the limit clause taken over 0 < β < λ so that 0^λ = 0 Corollary
- Ordinal multiplication exists and is unique, and its values are ordinals 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
- Refuted, assuming countable choice: every Hausdorff space built from ordinal spaces is normal. The deleted Tychonoff plank ((ω₁ + 1) × (ω + 1)) ∖ {(ω₁, ω)} is Hausdorff and not normal Counterexample
- Refuted: every limit ordinal has an at most countable cofinal subset — ω₁ has none, assuming countable choice Counterexample
- Cardinal (initial ordinal) and cardinality Definition
- Cardinal sum κ ⊕ λ, product κ ⊗ λ and exponentiation κ^λ, and why they are written apart from the ordinal operations Definition
- Cofinal subset of an ordinal Definition
- Successor and limit ordinals Definition
- The closed long ray ω₁ × [0,1) under the lexicographic order, and the long line, with the order topology Definition
- The first uncountable ordinal ω₁ := ℵ(ω) Definition
- The order topology on an ordinal, with the half-open intervals (α, β] and the initial segments [0, β] as a basis Definition
- 1 + ω = ω and ω + 1 > ω, computed both from the recursion and as order types Example
- 2 · ω = ω while ω · 2 = ω + ω, pictured as order types Example
- An ordinal α with ℵ_α = α, built as the supremum of the tower ℵ₀, ℵ_ℵ₀, ℵ_ℵ_ℵ₀, …, and its cofinality is ℵ₀ Example
- Assuming countable choice, a strictly increasing ω-sequence of countable ordinals has a countable supremum, which is a countable limit ordinal below ω₁; the instance supₙ ω·(n+1) = ω² needs no choice 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
- Solving ω + γ = ω· 2 and dividing ω² + ω + 3 by ω Example
- The Cantor normal form of (ω² + ω· 3 + 5) · ω², computed by the division algorithm Example
- ω + 1 as a convergent sequence together with its limit, and, assuming countable choice, [0, ω₁), in which every sequence lies inside an at most countable initial segment Example
- ω + ω is at most countable although it is not order isomorphic to ω: order type and cardinality are different invariants Example
- ω², ω^ω, and ε₀ = sup{ω, ω^ω, ω^ω^ω, …} satisfying ω^ε₀ = ε₀ 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
- Every category is locally small False statement
- FALSE: (β + γ)·α = β·α + γ·α for all ordinals False statement
- FALSE: 2^ℵ₀ = ℵ_ω False statement
- FALSE: ordinal addition is commutative False statement
- FALSE: ordinal multiplication is commutative False statement
- FALSE: the ordinal 2^ω is uncountable False statement
- FALSE: β < γ implies β + α < γ + α False statement
- FALSE: κ < λ implies κ^μ < λ^μ False statement
- FALSE: κ ⊕ μ = λ ⊕ μ implies κ = λ False statement
- FALSE: ℵ_α is regular for every ordinal α False statement
…and 38 more results.
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 30 results over 13 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
- Ordinal number (Wikipedia) (standard reference, not scraped)
- Well-order (Wikipedia) (standard reference, not scraped)
- A. Marks, Set Theory (standard reference, not scraped)