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.
is uncountable, every ordinal below it is at most countable, it is a cardinal and a limit ordinal, and its existence is a theorem of ZF
Statement
Let (The first uncountable ordinal ). Then:
(a) The bridge. An ordinal (Ordinal (von Neumann)) injects into if and only if is at most countable (Finite, countably infinite, countable, uncountable).
(b) is uncountable.
(c) Every ordinal is at most countable; so is the least uncountable ordinal.
(d) is a cardinal, that is an initial ordinal (Cardinal (initial ordinal) and cardinality): no is equinumerous with .
(e) is a limit ordinal (Successor and limit ordinals).
All of this is a theorem of ZF and uses no choice principle. That matters here and is stated deliberately: Hartogs: an ordinal that does not inject into a given set is choice free, Every subset of an at most countable set is at most countable and A nonempty set is at most countable iff it is a surjective image of are choice free, so and every property listed above exist in ZF alone. The cost begins two items later on this page, at the boundedness theorem for at most countable subsets of , which genuinely needs countable choice.
Facts & Assumptions
Given: , the least ordinal admitting no injection into (The first uncountable ordinal , Hartogs: an ordinal that does not inject into a given set).
is the least ordinal that does not inject into ; in particular every ordinal strictly below does inject into , and does not. The construction is choice free (Hartogs: an ordinal that does not inject into a given set).
is finite when for some , countably infinite when , at most countable when one of the two holds, and uncountable when neither does (Finite, countably infinite, countable, uncountable, Equinumerous sets, and ).
Every subset of an at most countable set is at most countable, and no choice principle is used (Every subset of an at most countable set is at most countable).
A nonempty set is at most countable if and only if there is a surjection , and no choice principle is used (A nonempty set is at most countable iff it is a surjective image of , Injection, surjection, bijection).
An injection is a bijection of onto , and is symmetric and transitive (Injection, surjection, bijection, Equinumerous sets, and ).
An ordinal is a cardinal when no satisfies (Cardinal (initial ordinal) and cardinality).
Every ordinal is exactly one of , a successor, or a limit (Successor and limit ordinals); is an ordinal, iff or , and (Basic closure properties of ordinals); trichotomy holds (Trichotomy and well-ordering of the ordinals).
Every natural number is an ordinal, is an ordinal and a limit ordinal, and for ( is the least limit ordinal, The natural numbers (von Neumann)).
Proof
Claim (a), forwards: if is injective then by [L5], and is at most countable by [L3], so is at most countable by [L2] and transitivity of .
Claim (a), backwards: if is at most countable then for some or ; a bijection followed by the inclusion is an injection by [L8], and a bijection is one outright.
: the identity is an injection , so by [L1]; and or would give by [L7] and hence an injection by inclusion, which [L1] forbids; so by trichotomy.
Claim (b): does not inject into by [L1], so it is not at most countable by step 1.2, that is, it is uncountable.
Claim (c): every injects into by [L1], hence is at most countable by step 1.1; and by [L7] any uncountable ordinal satisfies , since would make at most countable.
Claim (d): suppose satisfies ; then is at most countable by step 2.2, so is at most countable by [L2] and symmetry of , contradicting step 2.1; hence is a cardinal in the sense of [L6].
Claim (e): by step 1.3, since ; and is not a successor, for if then gives by [L7], so is a nonempty ordinal in and is therefore at most countable by step 2.2, so [L4] supplies a surjection , and the function with and is a surjection onto , making at most countable by [L4] and contradicting step 2.1; so is a limit ordinal by [L7].
Claims (a) to (e) are established, and every step used only Hartogs: an ordinal that does not inject into a given set, Every subset of an at most countable set is at most countable and A nonempty set is at most countable iff it is a surjective image of , all of which are choice free, so the whole statement is a theorem of ZF.
Remarks
The bridge is the whole trick. Hartogs: an ordinal that does not inject into a given set produces the least ordinal that does not inject into . What is wanted is the least uncountable ordinal. Claim (a) is what identifies the two notions on ordinals, and it is two lines in each direction; without it, quoting Hartogs for uncountability would be citing a theorem for a claim it does not make.
No choice, and why it is worth saying. A reader who has met through cardinal arithmetic often expects the well-ordering theorem to be somewhere in the background. It is not. Hartogs' construction collects the order types of well-ordered subsets of , and the well-ordering comes with each subset as part of the datum, so nothing is selected (Hartogs: an ordinal that does not inject into a given set, remarks). The first genuine choice principle on this page appears at Assuming countable choice: every at most countable subset of is bounded below , so no at most countable subset of is cofinal in it, and a supremum of at most countably many at most countable ordinals is at most countable, and Choice ledger for this page: exists in ZF, and the boundedness theorem does not keeps the ledger.
" is a cardinal" is a property of an ordinal, not an assignment of a size. Cardinal (initial ordinal) and cardinality separates the two: being an initial ordinal is choice free, whereas attaching a cardinality to an arbitrary set needs the Axiom of Choice. Claim (d) is the first, and only the first.
What is deliberately absent. Nothing here says is regular, or computes its cofinality, or compares it with the size of . Regularity of is the boundedness theorem two items later and costs countable choice; the comparison with is the continuum hypothesis (The continuum hypothesis, and what this page does not prove) and is independent of ZFC.
Depends on
- The first uncountable ordinal $\omega_1 := \aleph(\omega)$
- Hartogs: an ordinal that does not inject into a given set
- Finite, countably infinite, countable, uncountable
- The natural numbers $\mathbb{N}$ (von Neumann)
- Cardinal (initial ordinal) and cardinality
- Equinumerous sets, $A \approx B$ and $A \preceq B$
- Injection, surjection, bijection
- Every subset of an at most countable set is at most countable
- A nonempty set is at most countable iff it is a surjective image of $\mathbb{N}$
- $\omega$ is the least limit ordinal
- Successor and limit ordinals
- Ordinal (von Neumann)
- Basic closure properties of ordinals
- Trichotomy and well-ordering of the ordinals
Used by
- 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
- The closed long ray ω₁ × [0,1) under the lexicographic order, and the long line, with the order topology Definition
- The successor cardinal κ⁺, the alephs ℵ_α, the beths ℶ_α, successor and limit cardinals, and the identifications ℵ₀ = ω and ℵ₁ = ω₁ Definition
- 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
- ω + 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
- ℵ₁ ≤ 2^ℵ₀ under the Axiom of Choice, because 2^ℵ₀ is a cardinal strictly above ℵ₀ and ℵ₁ is the least such; so ω₁ injects into ℝ Example
- FALSE: every sequentially compact space is compact False statement
- Choice ledger for this page: ω₁ exists in ZF, and the boundedness theorem does not Remark
- Assuming countable choice: every at most countable subset of ω₁ is bounded below ω₁, so no at most countable subset of ω₁ is cofinal in it, and a supremum of at most countably many at most countable ordinals is at most countable Theorem
- Every successor ordinal is compact in its order topology and every limit ordinal is not; and, assuming countable choice, ω₁ is countably compact and sequentially compact while ω₁ + 1 is compact Theorem
- The long ray is a linear continuum, hence connected; every one of its at most countable subsets is bounded above, assuming countable choice Theorem
Cited to discharge well-definedness by The first uncountable ordinal ω₁ := ℵ(ω).
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 68 results over 23 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
- First uncountable ordinal (Wikipedia) (standard reference, not scraped)
- Hartogs number (Wikipedia) (standard reference, not scraped)
- T. Jech, Set Theory, 3rd millennium ed., Ch. 3 (Cardinal numbers) (standard reference, not scraped)