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.
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
Statement
Assume the Axiom of Countable Choice (The Axiom of Countable Choice ()). Let be the first uncountable ordinal (The first uncountable ordinal ). Then:
(a) Boundedness. Every at most countable (Finite, countably infinite, countable, uncountable) subset is bounded below : the ordinal lies in and satisfies for every .
(b) No small cofinal set. No at most countable subset of is cofinal in (Cofinal subset of an ordinal).
(c) Suprema stay countable. If is an at most countable set of at most countable ordinals, then is an at most countable ordinal.
The hypothesis is not decoration. is spent at exactly one step, step 1.2 below, and it is spent there only through Countable unions of at most countable sets, assuming , whose own statement carries the same hypothesis. Everything else on this page, including the existence of and all of 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, is a theorem of ZF. The ledger is the choice-ledger remark at the end of this page.
Facts & Assumptions
Given: The Axiom of Countable Choice (The Axiom of Countable Choice ()), and (The first uncountable ordinal ).
is an ordinal for every set of ordinals, and it is the least upper bound of ; ; every element of an ordinal is an ordinal; iff or ; and (Basic closure properties of ordinals, Ordinal (von Neumann)).
Exactly one of , , holds for ordinals (Trichotomy and well-ordering of the ordinals).
is uncountable, every ordinal in is at most countable, and is a limit ordinal ( 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, Successor and limit ordinals).
A nonempty set is at most countable if and only if there is a surjection (A nonempty set is at most countable iff it is a surjective image of , The natural numbers (von Neumann)).
Assuming : if is a family of at most countable sets then is at most countable (Countable unions of at most countable sets, assuming ).
is cofinal in when every satisfies for some (Cofinal subset of an ordinal).
Proof
For a set of ordinals, is an ordinal and is the least upper bound of , so for every ; and .
The one step that spends . Let be a nonempty at most countable set each of whose members is an at most countable set. By [L4] there is a surjection ; putting gives a family of at most countable sets indexed by , with no selection made, and because is onto ; so is at most countable by [L5].
Claim (a): let be at most countable. Every lies in and hence is an at most countable ordinal by [L3], and by [L1], so and is an ordinal with by [L1]. If then by step 1.1 and [L3], since is a nonzero ordinal. If then is at most countable by step 1.2, so because is uncountable by [L3], and therefore by [L1]. In both cases is an upper bound of by step 1.1.
Claim (c): an at most countable set of at most countable ordinals has an ordinal by [L1], equal to when and at most countable by step 1.2 otherwise; in either case is an at most countable ordinal.
Claim (b): suppose is at most countable and cofinal in ; put , which lies in by step 2.1, so because is a limit ordinal by [L3]; cofinality applied to gives with , while by step 1.1, so and hence , which [L1] forbids.
Claims (a), (b) and (c) are established, and the only appeal to a choice principle is the use of [L5] inside step 1.2.
Remarks
Where exactly the choice is spent, and why it cannot be avoided here. Step 1.2 hands an -indexed family of at most countable sets to Countable unions of at most countable sets, assuming , and that theorem selects one enumeration of each member at once. Each ordinal has enumerations by , in general many, and countability alone gives no rule for singling one out. Note that the family itself is produced without choice: it is for a surjection that A nonempty set is at most countable iff it is a surjective image of hands over, and that lemma is choice free.
The hypothesis is genuinely needed, not merely convenient. Without a choice principle the conclusion can fail outright: it is consistent with ZF, granted the consistency of ZF, that is the supremum of an -sequence of at most countable ordinals. That is the Feferman-Levy model, recorded in Choice ledger for this page: exists in ZF, and the boundedness theorem does not with the external citation. So the boundedness proved here is not a fact about alone; it is a fact about plus .
What the statement deliberately avoids at this point in the reading order. The usual formulation is " is a regular cardinal", using the cofinality function . That vocabulary is introduced later in Cofinality , and regular and singular cardinals ↗, so the present theorem states the conclusion in the subset form available here: no at most countable subset is cofinal. That is exactly the form the applications need, for instance the non-normality of the deleted Tychonoff plank, where the countably many ordinals produced by a covering argument must be capped below .
Claim (c) restated. A supremum of at most countably many at most countable ordinals is at most countable. This is the same fact viewed without reference to , and it is the form used when the ambient ordinal is not but some countable limit; see the worked increasing-sequence example on the companion examples page.
Depends on
- The first uncountable ordinal $\omega_1 := \aleph(\omega)$
- $\omega_1$ 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
- Cofinal subset of an ordinal
- The Axiom of Countable Choice ($\mathrm{AC}_\omega$)
- Countable unions of at most countable sets, assuming $\mathrm{AC}_\omega$
- Finite, countably infinite, countable, uncountable
- A nonempty set is at most countable iff it is a surjective image of $\mathbb{N}$
- Basic closure properties of ordinals
- Trichotomy and well-ordering of the ordinals
- Ordinal (von Neumann)
- Successor and limit ordinals
- The natural numbers $\mathbb{N}$ (von Neumann)
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
- 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 countable choice, ω₁ is first countable and countably compact but is not separable or Lindelöf Example
- The long ray is connected and locally connected, every proper initial segment is order-convex and connected, and, assuming countable choice, no at most countable subset is cofinal 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
- Assuming countable choice, the deleted Tychonoff plank is a regular nonnormal open subspace of a compact Hausdorff normal space Lemma
- Choice ledger for this page: ω₁ exists in ZF, and the boundedness theorem does not Remark
- 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
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 74 results over 21 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)
- Axiom of countable choice (Wikipedia) (standard reference, not scraped)
- T. Jech, Set Theory, 3rd millennium ed., Ch. 3 (Cardinal numbers) (standard reference, not scraped)
- A. Karagila, Forcing course notes (2023) (standard reference, not scraped)