Past exam of the logic and set theory course of the University of Oxford / 2009 / B / 4

The ordinal operations are defined by transfinite recursion in the right argument. Addition satisfies $\alpha +0=\alpha$, $\alpha +(\beta +1)=(\alpha +\beta )+1$, and $\alpha +\lambda ={\sup }_{\beta <\lambda }(\alpha +\beta )$ at a nonzero limit. Multiplication satisfies $\alpha \cdot 0=0$, $\alpha \cdot (\beta +1)=\alpha \cdot \beta +\alpha$, and $\alpha \cdot \lambda ={\sup }_{\beta <\lambda }\alpha \cdot \beta$. Exponentiation satisfies ${\alpha }^0=1$, ${\alpha }^{\beta +1}={\alpha }^{\beta }\cdot \alpha$, and ${\alpha }^{\lambda }={\sup }_{\beta <\lambda }{\alpha }^{\beta }$ at nonzero limits. These are ordinal operations, not commutative cardinal arithmetic.

For a normal function on an ordinal, prove domination by transfinite induction. At zero, $0\le \Phi (0)$ automatically. If $\alpha \le \Phi (\alpha )$, strict increase at successors gives $\alpha +1\le \Phi (\alpha )+1\le \Phi (\alpha +1)$. At a nonzero limit $\lambda$, continuity and the induction hypotheses giveTherefore $\boxed{\alpha \le \Phi (\alpha )\text{ for every ordinal }\alpha }$. No axiom of choice is needed for this ordinal induction.

For fixed $\beta$, the recursion defining $\beta +\alpha$ makes it continuous in $\alpha$ at every nonzero limit, and $(\beta +\alpha )+1>\beta +\alpha$. Thus $\alpha \mapsto \beta +\alpha$ is normal, including when $\beta =0$.

For $\beta >0$, take $\lambda =\beta \cdot \omega$. If $\alpha <\lambda$, choose a natural number $n$ with $\alpha <\beta n$; then $\alpha +\beta \le \beta (n+1)<\lambda$. Since $\alpha +\beta \ge \alpha$, their supremum as $\alpha \uparrow \lambda$ is $\lambda$. But $\lambda +\beta >\lambda$, soHence right addition by a nonzero fixed ordinal fails continuity and is not normal.

Normality and argument order in ordinal arithmetic also give the multiplication statements: $\alpha \mapsto \beta \cdot \alpha$ is normal for $\beta >0$, while $\alpha \mapsto \alpha \cdot \beta$ is normal exactly when $\beta =1$. At $\beta =0$ it is constant. For fixed $\beta >1$, let $\kappa ={\omega }^{\beta \cdot \omega }$. Cantor normal form shows that $\xi \beta <\kappa$ whenever $\xi <\kappa$: leading exponents below $\beta \omega$ remain below it after adding the leading exponent of $\beta$. Thus ${\sup }_{\xi <\kappa }\xi \beta =\kappa$, but $\kappa \beta >\kappa$, again violating continuity. Left-fixed multiplication is strictly increasing and continuous by its recursion.

For exponentiation, $\alpha \mapsto {\beta }^{\alpha }$ is normal for $\beta \ge 2$; bases zero and one are exceptions. The reverse map $\alpha \mapsto {\alpha }^{\beta }$ is normal exactly when $\beta =1$. Exponent zero gives the constant one. For $\beta >1$, use the same $\kappa$ and put $\lambda ={\omega }^{\kappa }$. For each $\alpha <\lambda$ choose $0<\zeta <\kappa$ with $\alpha \le {\omega }^{\zeta }$. Then ${\alpha }^{\beta }\le {\omega }^{\zeta \beta }<\lambda$, while ${\alpha }^{\beta }\ge \alpha$ for positive $\alpha$. Consequently its left supremum is $\lambda$, but ${\lambda }^{\beta }={\omega }^{\kappa \beta }>\lambda$. The bound by ${\omega }^{\zeta }$ also handles finite bases, where an unqualified leading-exponent multiplication formula would need care. All these are ordinal facts and use no choice.

For a countable fixed point of a normal ordinal function, first show that $\Phi$ maps every countable ordinal to a countable ordinal. Use transfinite induction below ${\omega }_1$. The zero case is assumed, and the successor case is the stated preservation property. If $\lambda$ is a countable limit, normality gives $\Phi (\lambda )={\bigcup }_{\alpha <\lambda }\Phi (\alpha )$, a countable union of countable sets, hence countable. This countable-union step is where axiom of countable choice is used; the assumed axiom of choice supplies it.

Now set ${\alpha }_0=0$, ${\alpha }_{n+1}=\Phi ({\alpha }_n)$. The preceding result makes every term countable, and the domination proved earlier makes the sequence nondecreasing. If it ever stabilizes, it already gives the required fixed point. Otherwise $\alpha ={\sup }_{n<\omega }{\alpha }_n$ is a countable nonzero limit, using axiom of countable choice again for countability of the union. Its defining sequence is cofinal, so monotonicity and continuity giveApply this to $\Phi (\alpha )={\omega }^{\alpha }$. This is normal, begins at $1$, and ${\omega }^{\alpha +1}={\omega }^{\alpha }\cdot \omega$ is countable whenever ${\omega }^{\alpha }$ is countable. Thus a countable $ϵ$ satisfies $\boxed{ϵ={\omega }^{ϵ}}$. Starting at zero gives the familiar tower sequence $0,1,\omega ,{\omega }^{\omega },\dots$, whose supremum is ${ϵ}_0$. The finite recursion, ordinal identities and fixed-point continuity do not require choice; the uses of choice above concern countable unions of countable ordinals.