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:On→OnF: \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

α=ωα1⋅a1+ωα2⋅a2+⋯+ωαn⋅an\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

ωβ1⋅b1+ωβ2⋅b2+⋯+ωβm⋅bm\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.]

Typos? Please submit corrections to this page on GitHub.