Paper 1, Section II, G

Logic and Set Theory
Part II, 2013

Write down the recursive definitions of ordinal addition, multiplication and exponentiation.

Given that F:OnOnF: \mathbf{O n} \rightarrow \mathbf{O n} is a strictly increasing function-class (i.e. α<β\alpha<\beta implies F(α)<F(β))F(\alpha)<F(\beta)), show that αF(α)\alpha \leqslant F(\alpha) for all α\alpha.

Show that every ordinal α\alpha has a unique representation in the form

α=ωα1a1+ωα2a2++ωαnan\alpha=\omega^{\alpha_{1}} \cdot a_{1}+\omega^{\alpha_{2}} \cdot a_{2}+\cdots+\omega^{\alpha_{n}} \cdot a_{n}

where nω,αα1>α2>>αnn \in \omega, \alpha \geqslant \alpha_{1}>\alpha_{2}>\cdots>\alpha_{n}, and a1,a2,,anω\{0}a_{1}, a_{2}, \ldots, a_{n} \in \omega \backslash\{0\}.

Under what conditions can an ordinal α\alpha be represented in the form

ωβ1b1+ωβ2b2++ωβmbm\omega^{\beta_{1}} \cdot b_{1}+\omega^{\beta_{2}} \cdot b_{2}+\cdots+\omega^{\beta_{m}} \cdot b_{m}

where β1<β2<<βm\beta_{1}<\beta_{2}<\cdots<\beta_{m} and b1,b2,,bmω\{0}?b_{1}, b_{2}, \ldots, b_{m} \in \omega \backslash\{0\} ? Justify your answer.

[The laws of ordinal arithmetic (associative, distributive, etc.) may be assumed without proof.]