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.
Cantor normal form: every nonzero ordinal is with and each a nonzero natural number, in exactly one way
Statement
Let be an ordinal (Ordinal (von Neumann)) with . Then there is a natural number , a strictly decreasing list of ordinals and a list of natural numbers with , such that
and , the exponents and the coefficients are uniquely determined by . This expression is the Cantor normal form of ; the uniqueness is what licenses the definite article.
Indices run over the von Neumann natural , so the leading term is the one with index . Sums are unbracketed because ordinal addition is associative (Ordinal addition is associative), and powers bind tighter than products, which bind tighter than sums (Ordinal exponentiation , with the conventions and ).
No choice principle is used.
Facts & Assumptions
Given: An ordinal . A normal-form datum of length , for a natural number , is a pair of functions and with domain the von Neumann natural (The natural numbers (von Neumann)), the ordinals with whenever , and the ordinals with . Its value is , where and for ; this recursion is legitimate by Transfinite recursion along the ordinals: a class rule determines exactly one operation defined at every ordinal, and by associativity of its value is the unbracketed sum displayed in the Statement.
Exponent laws for a base , in particular for : implies ; ; is a limit ordinal for limit ; , , , and ( and ; and for exponentiation is strictly increasing with , Ordinal exponentiation , with the conventions and ).
For and any there are unique with and (For every ordinal is with , in exactly one way).
From Monotonicity of ordinal and : strictly increasing and continuous in the right argument, weakly increasing in the left, with left cancellation, and the identities and : , , (claim (a)); implies , and (claim (b)); (claim (c)); for , implies (claim (d)); implies (claim (e)); if is a limit and is nonempty with then (claim (f)); and is a limit ordinal for and a limit (claim (g)).
, and is associative (Ordinal multiplication is associative, and ).
, , (Ordinal multiplication ); and (Ordinal addition ).
is an ordinal; is an ordinal and the least upper bound of a set of ordinals; iff or ; (Basic closure properties of ordinals); hence iff . Exactly one of , , holds, and every nonempty set of ordinals has an -least element (Trichotomy and well-ordering of the ordinals).
Every ordinal is exactly one of , a successor or a limit; a limit has and is closed under successor (Successor and limit ordinals). is a limit ordinal and every ordinal in is or a successor (claims (iii) and (iv) of is the least limit ordinal).
Transfinite induction over the ordinals: if a property of ordinals fails at some , apply Transfinite induction to the well-order and to ; so if holds at whenever it holds at every ordinal in , then holds at every ordinal.
Proof
Preliminaries on and on powers of : for one has , by induction on over the ordinals in , since , since as is closed under successor, and since no ordinal in is a limit by [L7]; and is a limit ordinal, with for every , by [L1], [L5] and claims (d) and (g) of [L3].
Additive indecomposability: for every ordinal and every one has . By induction on . At , forces and . At : gives with , and claim (f) of [L3] applied to the nonempty gives , where each by [L4], step 1.1 and claim (d) of [L3]; so , and the reverse inequality is claim (c) of [L3]. At a limit: gives with , and is nonempty, contained in and has supremum , because any satisfies for some and may be replaced by the larger of and ; so claim (f) of [L3] gives , using the claim at each such , legitimate since .
The leading exponent exists: for the set contains , because , and it contains every with , because by [L1]; it has a greatest element , since forces and , since gives for some and hence with , and since a limit gives for every , whence and ; and then , the second inequality because .
Closure below a power of : if and then , by claim (b) of [L3] and step 2.1.
Existence, by induction on : take from step 2.2, so ; divide by using [L2] to get with ; here , since would give , and , since would give by claims (d) and (b) of [L3], contradicting . If then is a normal form of length . Otherwise , so the claim at gives a normal-form datum for with leading exponent and leading coefficient , and by [L3], so by [L1] and [L6]; prefixing to that datum therefore yields a normal-form datum whose value is .
Tail bound: if is a normal-form datum then the value of its tail satisfies ; indeed when , and for each term satisfies by claim (d) of [L3], [L1] and , so induction on the number of terms using step 3.1 gives .
Uniqueness, by induction on : let be a normal-form datum of value , with tail value , so that with by step 4.1; then by [L3], and by [L3], [L4] and ; so , which pins down, since a second datum with leading exponent would satisfy the same two inequalities and, say, would give by [L1] and [L6]; with fixed, the two representations with agree by the uniqueness in [L2], so and ; and , so the claim at makes the two tails identical when , while forces both data to have length , since a tail of length at least has value at least .
Existence is step 3.2 and uniqueness is step 5.1, so every ordinal has exactly one Cantor normal form.
Remarks
Where each hypothesis of and ; and for exponentiation is strictly increasing with is spent. The bound is what makes in step 2.2 a set: without it, "the largest with " ranges over the ordinals, which is not a set, and Separation has nothing to cut. Continuity of at limits is what makes attain its supremum; without it the maximum could fail to exist and the leading exponent would not be defined.
Additive indecomposability is the whole content of uniqueness. Step 2.1 says that adding anything strictly smaller than on the left of changes nothing. Its consequence, step 3.1, is that the ordinals below are closed under addition, and that is exactly why a tail with strictly smaller exponents cannot reach up to the leading term and disturb it.
Beyond base . More general base- expansions exist for ordinals , with digits below , but their proof requires a general digit-and-carry argument. The theorem and proof here concern only base .
What is not claimed. Nothing here says the normal form is computable, and nothing here uses or proves anything about . The ordinals with have normal form , whose exponent is itself, so the normal form does not always reduce a problem to strictly smaller data; one such ordinal, , is exhibited on the companion examples page, where it is shown to satisfy and where it is recorded that its leastness among such fixed points is not proved.
Depends on
- $\alpha^{\beta+\gamma} = \alpha^{\beta}\cdot\alpha^{\gamma}$ and $(\alpha^{\beta})^{\gamma} = \alpha^{\beta\cdot\gamma}$; and for $\alpha > 1$ exponentiation is strictly increasing with $\beta \le \alpha^{\beta}$
- For $\alpha > 0$ every ordinal $\beta$ is $\alpha \cdot \xi + \rho$ with $\rho < \alpha$, in exactly one way
- 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 + \beta = \beta$ and $1 \cdot \beta = \beta$
- Ordinal multiplication is associative, and $\alpha \cdot (\beta + \gamma) = \alpha\cdot\beta + \alpha\cdot\gamma$
- Ordinal addition is associative
- Transfinite recursion along the ordinals: a class rule determines exactly one operation defined at every ordinal
- Ordinal exponentiation $\alpha^{\beta}$, with the conventions $\alpha^{0} = 1$ and $0^{0} = 1$
- Ordinal multiplication $\alpha \cdot \beta$
- Ordinal addition $\alpha + \beta$
- $\omega$ is the least limit ordinal
- Transfinite induction
- Successor and limit ordinals
- Basic closure properties of ordinals
- Trichotomy and well-ordering of the ordinals
- Ordinal (von Neumann)
- The natural numbers $\mathbb{N}$ (von Neumann)
Used by
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 60 results over 26 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 arithmetic (Wikipedia) (standard reference, not scraped)
- T. Jech, Set Theory, 3rd millennium ed., Ch. 2 (Ordinal numbers) (standard reference, not scraped)
- A. Marks, Set Theory (standard reference, not scraped)