Paper 1, Section II, G

Logic and Set Theory
Part II, 2009

Prove that if G:G: On ×VV\times V \rightarrow V is a definable function, then there is a definable function F:F: On V\rightarrow V satisfying

F(α)=G(α,{F(β):β<α})F(\alpha)=G(\alpha,\{F(\beta): \beta<\alpha\})

Define the notion of an initial ordinal, and explain its significance for cardinal arithmetic. State Hartogs' lemma. Using the recursion theorem define, giving justification, a function ω:\omega: On \rightarrow On which enumerates the infinite initial ordinals.

Is there an ordinal α\alpha with α=ωα?\alpha=\omega_{\alpha} ? Justify your answer.