Ordinal Arithmetic and the First Uncountable Ordinal — Examples

The two smallest infinite sums behave differently:

$1+\omega =\omega ,\omega +1={\omega }^{+}>\omega \mathrm{.}$

Each is computed twice below: once from the recursive clauses of Ordinal addition $\alpha +\beta$, and once from the order-type description of $\alpha +\beta$ is the order type of $\alpha$ followed by $\beta$, where $\alpha +\beta$ is the order type of a copy of $\alpha$ followed by a copy of $\beta$. The two routes are independent, and agreeing is the point of the exercise.

In pictures: putting one extra point before a copy of $\omega$ gives a copy of $\omega$ again, since the result still looks like $0,1,2,\dots$; putting one extra point after it gives something with a greatest element, which $\omega$ does not have.

What the two routes cost. The recursive computation needs the limit clause of Ordinal addition $\alpha +\beta$ together with the fact that $\omega$ is closed under adding a natural number, which is On $\omega$ the ordinal $+$ and $\cdot$ are the Peano operations: $\omega$ is closed under ordinal $+$, $\cdot$ and exponentiation, and for naturals $m,n$ the ordinal $m+n$ and $m\cdot n$ are the natural-number sum and product. The order-type computation needs only an explicit bijection and $\alpha +\beta$ is the order type of $\alpha$ followed by $\beta$. Neither is shorter than the other; the second is the one that generalises, since it makes the answer visible before it is computed.

This is the whole of non-commutativity, in miniature. The general statement is FALSE: ordinal addition is commutative, and its proof is exactly the computation above. Everything else about the failure of commutativity is a variation on prepending versus appending.

$\omega +1$ is not $\omega$ even though the two sets have the same size. $\omega +1=\omega \cup \{\omega \}$ is countably infinite, being $\omega$ with one point added, so the difference between $\omega$ and $\omega +1$ is entirely a difference of order type. That distinction is taken up in $\omega +\omega$ is at most countable although it is not order isomorphic to $\omega$: order type and cardinality are different invariants.

$2\cdot \omega =\omega ,\omega \cdot 2=\omega +\omega >\omega \mathrm{.}$

Under the convention of Ordinal multiplication $\alpha \cdot \beta$, $\alpha \cdot \beta$ is $\beta$ copies of $\alpha$ ($\alpha \cdot \beta$ is the order type of $\alpha \times \beta$ ordered by last differences, that is $\beta$ copies of $\alpha$). So $2\cdot \omega$ is $\omega$ copies of a two element set, laid end to end:

$\underset{}{\underbrace{\bullet \bullet }}\underset{}{\underbrace{\bullet \bullet }}\underset{}{\underbrace{\bullet \bullet }}\cdots$

which is a copy of $\omega$ once the points are counted off $0,1,2,\dots$. And $\omega \cdot 2$ is two copies of $\omega$, one entirely above the other:

$0,1,2,\dots \text{ then }{0}^{\mathrm{\prime }},1^{\mathrm{\prime }},2^{\mathrm{\prime }},\dots$

which is $\omega +\omega$ and is strictly larger than $\omega$.

Both values are computed below from the recursive clauses, and both pictures are justified by the order-type lemmas rather than left as pictures.

Which convention this depends on. Everything above uses the convention fixed in Ordinal multiplication $\alpha \cdot \beta$, that the successor clause appends a copy of the left factor on the right. Under the opposite convention the two values are exchanged, and $2\cdot \omega$ would be $\omega +\omega$. Both conventions appear in the literature; this library uses the one stated, throughout.

The general statement. That ordinal multiplication is not commutative is FALSE: ordinal multiplication is commutative, whose refutation is the computation of step 2.1 and step 1.2. The related failure of right distributivity, $(1+1)\cdot \omega \mathrm{\ne }1\cdot \omega +1\cdot \omega$, is FALSE: $(\beta +\gamma )\cdot \alpha =\beta \cdot \alpha +\gamma \cdot \alpha$ for all ordinals and uses the same value $2\cdot \omega =\omega$.

Why the block picture is a proof and not an illustration. $\alpha \cdot \beta$ is the order type of $\alpha \times \beta$ ordered by last differences, that is $\beta$ copies of $\alpha$ says the product is the order type of the block arrangement, so reading a value off the picture is legitimate once the picture is identified with $\alpha \times \beta$ under last differences. What is not legitimate is reading it off an unlabelled diagram, which is why step 3.1 names the lemma at each use.

The ordinal $\omega +\omega$ is at most countable as a set (Finite, countably infinite, countable, uncountable), and it is not order isomorphic to $\omega$ (Order embedding and order isomorphism).

There is no tension. Countability is a statement about bijections and ignores order; order type is a statement about order isomorphisms and is finer. Two well-orders on the same countably infinite set can have different order types: $\omega$ and $\omega +1$ already show it, as the first example of this page records, and $\omega$ and $\omega +\omega$ show it with the two copies visible.

$\omega +\omega =\mathrm{o}\mathrm{t}\left(\underset{\text{first copy}}{\underbrace{0,1,2,\dots }}\underset{\text{second copy}}{\underbrace{0^{\mathrm{\prime }},1^{\mathrm{\prime }},2^{\mathrm{\prime }},\dots }}\right)\mathrm{.}$

How far this goes. Every ordinal strictly below ${\omega }_1$ is at most countable (${\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), and there are a great many of them: $\omega +\omega$ and $\omega \cdot \omega ={\omega }^2$ are at most countable by the argument above, and no two distinct ordinals are isomorphic as orders. So a single countably infinite set carries uncountably many mutually non-isomorphic well-orders, one for each infinite ordinal below ${\omega }_1$. Nothing here says the same of ${\omega }^{\omega }$ or of ${\epsilon }_0$ (${\omega }^2$, ${\omega }^{\omega }$, and ${\epsilon }_0=\sup \{\omega ,{\omega }^{\omega },{\omega }^{{\omega }^{\omega }},\dots \}$ satisfying ${\omega }^{{\epsilon }_0}={\epsilon }_0$): those are ordinals of larger order type, and their cardinality is a question no item on these pages settles, as that item's last remark records.

Why the argument does not need a choice principle. The bijection used at step 2.1 is the collapsing isomorphism of Every well-order has a unique order type, which is unique and therefore never chosen, and A product of two at most countable sets is at most countable is choice free too. Countability of a countable union of countable sets is a different matter and does cost ${\mathrm{A}\mathrm{C}}_{\omega }$; that is Countable unions of at most countable sets, assuming ${\mathrm{A}\mathrm{C}}_{\omega }$ and it is not used here.

The confusion this item exists to prevent. "$\omega +\omega$ is bigger than $\omega$" is true as a statement about ordinals, where bigger means further along the ordinal order, and false as a statement about size. The two readings of "bigger" are exactly order type and cardinality.

The first few powers of $\omega$ are

${\omega }^1=\omega ,{\omega }^2=\omega \cdot \omega ,{\omega }^{\omega }=\sup \{{\omega }^n:0<n<\omega \},$

and each is strictly larger than the one before (${\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 }$, clause (b)). Iterating the exponential produces the $\omega$-tower

$t_0=\omega ,t_{n+1}={\omega }^{t_n},$

so $t_1={\omega }^{\omega }$, $t_2={\omega }^{{\omega }^{\omega }}$, and so on. Its supremum

${\epsilon }_0:=\sup \{t_n:n\in \omega \}$

is a limit ordinal satisfying

${\omega }^{{\epsilon }_0}={\epsilon }_0,$

so it is a fixed point of $\beta \mapsto {\omega }^{\beta }$. This is exhibited here by hand: the tower is written down, its supremum is taken, and the fixed point equation is proved from continuity at limits. No fixed-point theorem is used, and none that this library proves applies here: every fixed-point theorem on disk is stated for a set carrying an order or a metric, whereas $\beta \mapsto {\omega }^{\beta }$ is a class operation on the ordinals, which are not a set.

Why Transfinite recursion along the ordinals: a class rule determines exactly one operation defined at every ordinal and not the recursion theorem over $\mathbb{N}$. The published The recursion theorem builds $g:\mathbb{N}\to A$ from a function $f:A\to A$ on a set $A$. Here the step is $\beta \mapsto {\omega }^{\beta }$, a class operation with no set-sized codomain available at this point, so the recursion theorem does not apply as stated. Transfinite recursion along the ordinals: a class rule determines exactly one operation defined at every ordinal is exactly the class-valued version, and Replacement then makes the range $\{t_n:n\in \omega \}$ a set.

What is proved and what is not. That ${\epsilon }_0$ is a fixed point of $\beta \mapsto {\omega }^{\beta }$ is proved above. That it is the least such fixed point is true and is not proved here; it would follow from the observation that any fixed point is closed under the tower, and it needs nothing new, but nothing on these pages uses it. No general theory of normal functions or of the Veblen hierarchy is developed, and none is needed for the statement above.

${\epsilon }_0$ and the Cantor normal form. By Cantor normal form: every nonzero ordinal is ${\omega }^{{\beta }_0}\cdot c_0+\cdots +{\omega }^{{\beta }_{k-1}}\cdot c_{k-1}$ with ${\beta }_0>\cdots >{\beta }_{k-1}$ and each $c_i$ a nonzero natural number, in exactly one way every nonzero ordinal has a unique base-$\omega$ normal form. For ${\epsilon }_0$ that form is ${\omega }^{{\epsilon }_0}\cdot 1$, whose exponent is ${\epsilon }_0$ itself, so the normal form does not reduce ${\epsilon }_0$ to strictly smaller data. Below ${\epsilon }_0$ it always does, and that is the sense in which ${\epsilon }_0$ is where base-$\omega$ notation runs out.

Cardinality is a separate question, and this page does not settle it. Nothing above says how large ${\omega }^{\omega }$ or ${\epsilon }_0$ is as a set. Showing them at most countable would need the countable ordinals to be closed under ordinal exponentiation, which is not proved anywhere in this library; the natural route runs through Assuming countable choice: every at most countable subset of ${\omega }_1$ is bounded below ${\omega }_1$, so no at most countable subset of ${\omega }_1$ is cofinal in it, and a supremum of at most countably many at most countable ordinals is at most countable and a transfinite induction that no item here carries out. What the tower demonstrates is growth in order type, which is the invariant this page is about.

Put $\alpha ={\omega }^2+\omega \cdot 3+5$, which is already in Cantor normal form (Cantor normal form: every nonzero ordinal is ${\omega }^{{\beta }_0}\cdot c_0+\cdots +{\omega }^{{\beta }_{k-1}}\cdot c_{k-1}$ with ${\beta }_0>\cdots >{\beta }_{k-1}$ and each $c_i$ a nonzero natural number, in exactly one way): the exponents $2>1>0$ strictly decrease and the coefficients $1,3,5$ are nonzero natural numbers, since $\omega \cdot 3={\omega }^1\cdot 3$ and $5={\omega }^0\cdot 5$. Then

$\alpha \cdot {\omega }^2={\omega }^4,$

whose Cantor normal form is ${\omega }^4\cdot 1$: the entire tail $\omega \cdot 3+5$ is annihilated by multiplying on the right by ${\omega }^2$. Multiplying on the right by a limit ordinal keeps only the leading behaviour.

Addition behaves quite differently. Also computed below:

$({\omega }^2+\omega \cdot 3+5)+(\omega \cdot 2+7)={\omega }^2+\omega \cdot 5+7,$

where the coefficients of the matching power add and the lower tail of the left summand is swallowed.

Why the tail vanishes under multiplication on the right. The squeeze in step 3.1 is the whole mechanism: $\alpha$ is trapped between ${\omega }^2$ and ${\omega }^2\cdot 2$, and multiplying either bound on the right by $\omega$ gives ${\omega }^3$, because ${\omega }^2\cdot 2\cdot n={\omega }^2\cdot (2n)$ runs through the same cofinal family as ${\omega }^2\cdot n$. Anything of the form "leading term plus smaller stuff" therefore behaves, under multiplication by a limit on the right, exactly like its leading term.

Why the tail does not vanish under addition. In step 2.2 the lower part of the left summand, here $5$, is absorbed by the leading term of the right summand, but the term ${\omega }^2$ of the left summand survives, and the two coefficients of ${\omega }^1$ add. The general rule is the same computation: adding on the left of ${\omega }^{\beta }$ anything smaller than ${\omega }^{\beta }$ changes nothing, which is the additive indecomposability used inside the proof of Cantor normal form: every nonzero ordinal is ${\omega }^{{\beta }_0}\cdot c_0+\cdots +{\omega }^{{\beta }_{k-1}}\cdot c_{k-1}$ with ${\beta }_0>\cdots >{\beta }_{k-1}$ and each $c_i$ a nonzero natural number, in exactly one way.

A check on the answer. ${\omega }^4$ has Cantor normal form of length $1$, so $\alpha \cdot {\omega }^2$ is a power of $\omega$; that is consistent with the previous remark, since $\alpha$ has leading term ${\omega }^2\cdot 1$ and ${\omega }^2\cdot {\omega }^2={\omega }^4$ by the sum law in [L4].

Two computations with the two "inverse" operations of this page.

Left subtraction. The equation $\omega +\gamma =\omega \cdot 2$ has exactly one solution, and it is $\gamma =\omega$. Existence and uniqueness are For $\alpha \le \beta$ there is exactly one ordinal $\gamma$ with $\alpha +\gamma =\beta$, applicable because $\omega \le \omega \cdot 2$; finding the solution is the computation $\omega \cdot 2=\omega +\omega$.

Division with remainder. Dividing ${\omega }^2+\omega +3$ by $\omega$ gives

${\omega }^2+\omega +3=\omega \cdot (\omega +1)+3,3<\omega ,$

so the quotient is $\omega +1$ and the remainder is $3$, and by the uniqueness in For $\alpha >0$ every ordinal $\beta$ is $\alpha \cdot \xi +\rho$ with $\rho <\alpha$, in exactly one way there is no other answer. The step that does the work is ${\omega }^2+\omega =\omega \cdot (\omega +1)$, which is left distributivity.