Can you tell me if my answer is correct:

Show that the set $P^{\omega_\omega}(\omega)$ exists.

My answer:

Let $P^0 (\omega) = \omega$, $P^{\alpha + 1}(\omega) = P(P^\alpha (\omega))$ and for a limit ordinal $\lambda$ let $P^\lambda (\omega) =\bigcup_{\beta < \lambda} P^\beta (\omega)$.

The transfinite recursion theorem tells us that if $G: V \to V$ is a class function from the class of all sets to the class of all sets then there exists a unique function $F: ON \to V$ with $F(\alpha) = G(F\mid_\alpha)$.

Hence to show the existence of $P^{\omega_\omega}(\omega)$ we need to define a $G: V \to V$ with $G(F\mid_{\omega_\omega}) = P^{\omega_\omega}(\omega) = F(\omega_\omega)$.

Also we know that for successor ordinals $\alpha$ we want $F\mid_{\beta + 1} = F(\beta) = P^{\beta}(\omega)$. So for successor ordinals $\alpha = \beta + 1$ we define $G(F\mid_{\alpha})= G(F\mid_{\beta + 1}) = G( P^{\beta}(\omega)) := P( P^{\beta}(\omega))$.

We also know that $F\mid_\varnothing = \varnothing$ so $G(F\mid_\varnothing) = G(\varnothing) := P^0 (\omega)$.

Finally, if $\lambda$ is a limit ordinal we want $G(F\mid_\lambda) := \bigcup_{\alpha < \lambda} P^\alpha (\omega)$.

For all other sets we define $G$ to map to the empty set.

Thanks for your help.


Yes, your formalization of this instance of the transfinite recursion is correct.

One quibble is that when defining $G$, you shouldn't refer to $P^\beta(\omega)$ at all, since this makes your definition circular. Similarly, you shouldn't think of $G$ as defined on the unique $F$ you are trying to build, since you don't have it yet when defining $G$. Thus, you should define $G(f)$ to be $P(f(\beta))$, when $f$ is a $\beta+1$-sequence, and in the limit case, $F(f)=\bigcup_{\alpha\lt\lambda}f(\alpha)$, when $f$ is a $\lambda$-sequence for limit ordinal $\lambda$.

But I would add that I don't find it necessary to give a laborious definition of $G$ as you do in the latter part of your post. Your initial definition of $P^\beta(\omega)$ in the fourth line of your post already contains a complete definition of $P^\beta(\omega)$ from earlier instances of $P^\alpha(\omega)$, and thus serves as a complete account of the recursion. The detailed definition of $G$ that you give amounts basically to rewriting that initial definition in more detail. But the recursion is perhaps clearer without the extra detail (provided that one is clear on why recursion works).

  • $\begingroup$ Thanks. So I'll write $G(\langle f_0, f_1, \dots, f_{\alpha}\rangle) := P(f_{\alpha})$ if $\alpha$ is a limit ordinal and $G(\langle f_0, f_1, \dots\rangle) := \bigcup_{\alpha < \lambda}P(f_{\alpha})$ if $\lambda$ is a limit ordinal. $\endgroup$ – Rudy the Reindeer Feb 13 '12 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.