ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-29

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, a strictly increasing $ω$ -sequence of countable ordinals has a countable supremum, which is a countable limit ordinal below $ω_{1}$ ; the instance $\sup_{n} ω \cdot (n + 1) = ω^{2}$ needs no choice

Example

Assume the Axiom of Countable Choice (The Axiom of Countable Choice ( ${A C}_{ω}$ )). Let $(α_{n})_{n \in ω}$ be a strictly increasing sequence of ordinals with every $α_{n} \in ω_{1}$ (The first uncountable ordinal $ω_{1} : = ℵ (ω)$ ). Then

$\sup_{n \in ω} α_{n} = ⋃ {α_{n} : n \in ω}$

is again an ordinal below $ω_{1}$ , hence at most countable (Finite, countably infinite, countable, uncountable), and it is a limit ordinal (Successor and limit ordinals), since a strictly increasing sequence never attains its supremum.

A concrete instance, with everything computed:

$α_{n} = ω \cdot (n + 1), \sup_{n \in ω} ω \cdot (n + 1) = ω \cdot ω = ω^{2} .$

So $ω^{2}$ is a countable limit ordinal strictly below $ω_{1}$ , reached from below by an $ω$ -sequence. That is exactly what Assuming countable choice: every at most countable subset of $ω_{1}$ is bounded below $ω_{1}$ , so no at most countable subset of $ω_{1}$ is cofinal in it, and a supremum of at most countably many at most countable ordinals is at most countable forbids for $ω_{1}$ itself: $ω_{1}$ is not the supremum of any such sequence.

Facts & Assumptions

Given: The Axiom of Countable Choice (The Axiom of Countable Choice ( ${A C}_{ω}$ )), a strictly increasing sequence $(α_{n})_{n \in ω}$ of ordinals in $ω_{1}$ , and the operations of Ordinal addition $α + β$ , Ordinal multiplication $α \cdot β$ and Ordinal exponentiation $α^{β}$ , with the conventions $α^{0} = 1$ and $0^{0} = 1$ ; here $n + 1 = n^{+}$ (Ordinal addition $α + β$ ).

[L1]

Assuming ${A C}_{ω}$ : every at most countable $A \subseteq ω_{1}$ has $\sup A = ⋃ A \in ω_{1}$ , and $α \leq \sup A$ for every $α \in A$ (Assuming countable choice: every at most countable subset of $ω_{1}$ is bounded below $ω_{1}$ , so no at most countable subset of $ω_{1}$ is cofinal in it, and a supremum of at most countably many at most countable ordinals is at most countable).

[L2]

$ω_{1}$ is uncountable, every ordinal in $ω_{1}$ is at most countable, and $ω_{1}$ is a limit ordinal ( $ω_{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).

[L3]

A nonempty set is at most countable if and only if it is a surjective image of $N$ (A nonempty set is at most countable iff it is a surjective image of $N$ ); a subset of an at most countable set is at most countable (Every subset of an at most countable set is at most countable); a product of two at most countable sets is at most countable (A product of two at most countable sets is at most countable); a set equinumerous with an at most countable set is at most countable (Finite, countably infinite, countable, uncountable, Equinumerous sets, $A \approx B$ and $A ⪯ B$ ).

[L4]

$α \cdot β$ is the order type of $α \times β$ under last differences, and an order isomorphism is in particular a bijection ( $α \cdot β$ is the order type of $α \times β$ ordered by last differences, that is $β$ copies of $α$ , Every well-order has a unique order type).

[L5]

From Monotonicity of ordinal $+$ and $\cdot$ : strictly increasing and continuous in the right argument, weakly increasing in the left, with left cancellation, and the identities $0 + β = β$ and $1 \cdot β = β$ : for $μ > 0$ , $ν < θ$ implies $μ ν < μ θ$ (claim (d)); $μ \cdot θ = \sup {μ η : η \in D}$ for $μ > 0$ , $θ$ a limit and $D \subseteq θ$ nonempty with $\sup D = θ$ (claim (f)); $1 \cdot μ = μ$ (claim (a)).

[L6]

$μ^{1^{+}} = μ^{1} \cdot μ$ and $μ^{1} = μ$ (Ordinal exponentiation $α^{β}$ , with the conventions $α^{0} = 1$ and $0^{0} = 1$ , Monotonicity of ordinal $+$ and $\cdot$ : strictly increasing and continuous in the right argument, weakly increasing in the left, with left cancellation, and the identities $0 + β = β$ and $1 \cdot β = β$ ); $ω$ is a limit ordinal, closed under successor, with $⋃ ω = ω$ ( $ω$ is the least limit ordinal, Successor and limit ordinals, The natural numbers $N$ (von Neumann)).

[L7]

$⋃ A$ is an ordinal and the least upper bound of a set $A$ of ordinals; $μ \subseteq ν$ iff $μ \in ν$ or $μ = ν$ ; $μ \notin μ$ ; $μ < ν$ iff $μ^{+} \leq ν$ ; and trichotomy holds (Basic closure properties of ordinals, Trichotomy and well-ordering of the ordinals, Ordinal (von Neumann)).

Verification

technique · direct

1.1

The set $A = {α_{n} : n \in ω}$ is a nonempty subset of $ω_{1}$ and is at most countable, being the image of $N$ under $n \mapsto α_{n}$ , hence a surjective image of $N$ onto $A$ , so [L3] applies.

L3given

1.2

An ordinal $μ$ lies in $ω_{1}$ if and only if it is at most countable: one direction is [L2]; conversely if $μ \notin ω_{1}$ then $ω_{1} \leq μ$ by [L7], so $ω_{1} \subseteq μ$ and $ω_{1}$ would be at most countable by [L3], contradicting [L2].

L2L3L7

2.1

By [L1] the ordinal $β = \sup A = ⋃ A$ lies in $ω_{1}$ and is an upper bound of $A$ , so $β$ is at most countable by [L2].

step 1.1L1L2

2.2

The instance: each $ω \cdot (n + 1)$ is at most countable, because by [L4] it is order isomorphic, hence equinumerous, to $ω \times (n + 1)$ , which is at most countable by [L3]; so $ω \cdot (n + 1) \in ω_{1}$ by step 1.2. The sequence is strictly increasing, since $n + 1 < m + 1$ for $n < m$ gives $ω \cdot (n + 1) < ω \cdot (m + 1)$ by [L5] with $ω > 0$ .

step 1.2L3L4L5

3.1

$β$ is a limit ordinal: it is nonzero because $α_{0} \leq α_{1} \leq β$ with $α_{0} < α_{1}$ , so $β \neq 0$ ; and it is not a successor, since $β = μ^{+}$ would put $μ \in α_{n}$ for some $n$ , whence $μ^{+} \leq α_{n} < α_{n^{+}} \leq β = μ^{+}$ by [L7] and strict increase, which [L7] forbids.

step 2.1L7given

3.2

Its supremum is $ω^{2}$ : the set ${n + 1 : n \in ω}$ is a nonempty subset of $ω$ with supremum $ω$ , because $ω$ is closed under successor and $⋃ ω = ω$ by [L6], so claim (f) of [L5] with $μ = ω > 0$ gives $ω \cdot ω = \sup {ω \cdot (n + 1) : n \in ω}$ ; and $ω \cdot ω = ω^{1} \cdot ω = ω^{1^{+}} = ω^{2}$ by [L6].

step 2.2L5L6

4.1

So for a strictly increasing $ω$ -sequence in $ω_{1}$ the supremum is a limit ordinal below $ω_{1}$ and is at most countable; concretely $\sup_{n} ω \cdot (n + 1) = ω^{2}$ , a countable limit ordinal below $ω_{1}$ .

step 2.1step 3.1step 2.2step 3.2∎

Remarks

Where the choice principle is and is not needed. The general statement uses ${A C}_{ω}$ , at the single step where Assuming countable choice: every at most countable subset of $ω_{1}$ is bounded below $ω_{1}$ , so no at most countable subset of $ω_{1}$ is cofinal in it, and a supremum of at most countably many at most countable ordinals is at most countable is applied. The concrete instance does not: $ω^{2}$ is shown at most countable directly, from $α \cdot β$ is the order type of $α \times β$ ordered by last differences, that is $β$ copies of $α$ and A product of two at most countable sets is at most countable, both of which are choice free. So the example is available in ZF and only the general statement carries the hypothesis.

The contrast with $ω_{1}$ itself. $ω_{1}$ is also a limit ordinal, and it is also the supremum of the ordinals below it; what fails there, under ${A C}_{ω}$ , is that no at most countable family of them suffices. That is Assuming countable choice: every at most countable subset of $ω_{1}$ is bounded below $ω_{1}$ , so no at most countable subset of $ω_{1}$ is cofinal in it, and a supremum of at most countably many at most countable ordinals is at most countable again, and it is not a theorem of ZF alone: consistently with ZF the first uncountable ordinal is the supremum of an $ω$ -sequence of at most countable ordinals, so no choice-free proof of it exists (Choice ledger for this page: $ω_{1}$ exists in ZF, and the boundedness theorem does not).

Strict increase is used only for the limit clause. Boundedness needs only that the set of values is at most countable; strictness is what makes the supremum unattained and hence a limit ordinal. A sequence that is eventually constant has its final value as supremum, and that value need not be a limit ordinal at all, which is why step 2.2 quotes the strictness hypothesis.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

59 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

First uncountable ordinal (Wikipedia) (standard reference, not scraped)
Axiom of countable choice (Wikipedia) (standard reference, not scraped)
Ordinal arithmetic (Wikipedia) (standard reference, not scraped)

Assuming countable choice, a strictly increasing ωω-sequence of countable ordinals has a countable supremum, which is a countable limit ordinal below ω1ω1​; the instance sup⁡nω⋅(n+1)=ω2supn​ω⋅(n+1)=ω2 needs no choice