Past exam of the logic and set theory course of the University of Oxford / 2010 / B / 5

The recursive definitions of ordinal addition and ordinal multiplication arewhere the limit clauses apply to nonzero limit ordinals. Ordinal exponentiation has ${\alpha }^0=1$, ${\alpha }^{\beta +1}={\alpha }^{\beta }\cdot \alpha$, and for $\alpha >0$, ${\alpha }^{\lambda }={\sup }_{\beta <\lambda }{\alpha }^{\beta }$. Complete the zero-base convention by $0^{\beta }=0$ for $\beta >0$, with $0^0=1$. Stating the zero-base exception avoids including the value $0^0$ in a naive supremum at a positive limit.

For finite $n$, induction gives $1+n=n+1$. Now prove commutativity for finite $m,n$ by induction on $m$. The case $m=0$ is immediate. Associativity, the finite identity just obtained, and the induction hypothesis giveThus $\boxed{m+n=n+m\text{ for finite ordinals}}$.

It fails for general ordinals: $\boxed{1+\omega =\omega <\omega +1}$. The equality follows from the limit clause, since the finite sums $1+n$ are cofinal in $\omega$.

For nonzero $\alpha$, consider the exponents $\eta$ with ${\omega }^{\eta }\le \alpha$. The set is nonempty because it contains zero, and bounded because ${\omega }^{\eta }\ge \eta$ by transfinite induction. Let $\delta$ be its supremum. If this supremum is a successor it is attained; if it is a limit, continuity of ordinal exponentiation gives ${\omega }^{\delta }\le \alpha$. The zero case is immediate. Thus $\delta$ itself belongs to the set and is its maximum. Maximality givesPut $\rho ={\omega }^{\delta }>0$. Since ${\omega }^{\delta +1}=\rho \cdot \omega ={\sup }_{N<\omega }\rho N$, there is a least positive natural number $N$ with $\alpha <\rho N$. We have $N\ge 2$ because $\rho \le \alpha$. Set $n=N-1$. ThenFor ordinals $\xi \le \alpha$, the final segment of $\alpha$ after its initial segment $\xi$ has an order type $\zeta$ satisfying $\alpha =\xi +\zeta$. Apply this with $\xi =\rho n$. If $\zeta \ge \rho$, monotonicity would give $\alpha \ge \rho n+\rho =\rho (n+1)$, a contradiction. ThereforeThese intervals also make the leading exponent and coefficient unique. The remainder is unique because addition by a fixed left prefix is strictly increasing in its right operand.

Use transfinite induction on nonzero $\alpha$. Part (b) gives $\alpha ={\omega }^{\delta }n+\zeta$, with $n$ a positive natural number and $\zeta <{\omega }^{\delta }\le \alpha$.

If $\zeta =0$, this is already a one-term Cantor normal form. Otherwise $0<\zeta <\alpha$, so the induction hypothesis supplies a finite Cantor normal form for $\zeta$. Its leading exponent $\eta$ satisfies ${\omega }^{\eta }\le \zeta <{\omega }^{\delta }$, hence $\eta <\delta$. All later exponents are smaller still. Prefixing ${\omega }^{\delta }n$ therefore givesThe number of terms is finite because the inductive representation of the strictly smaller remainder is finite. Equivalently, repeated extraction cannot produce an infinite strictly descending sequence of ordinals. Since $\alpha \ne 0$, the number of terms is positive.

Yes, with the stated strict decrease and positive coefficients. In any displayed Cantor normal form, the first exponent is the unique $\delta$ with ${\omega }^{\delta }\le \alpha <{\omega }^{\delta +1}$. The leading coefficient is the unique positive integer $n$ withThe remaining tail is the unique $\zeta <{\omega }^{\delta }$ satisfying $\alpha ={\omega }^{\delta }n+\zeta$, by strict monotonicity of ordinal addition in the right operand.

Thus any two such representations have the same first exponent and coefficient and the same remainder. Repeat the argument on that remainder. Their finite lists agree term by term and reach zero at the same step, so the lengths agree as well. Allowing zero coefficients or repeated exponents would spoil this normalized uniqueness, which is why those conditions are required.