Can we define the tower of iterated power sets in ZFC

set-theory

Let $S$ be a set and $n$ be a positive integer.
One can safely say that
$\mathcal{P}^n(S)\overset{\mathrm{def}}{=}\overset{\mathrm{n\;times}\;\;\;\;\;}{\mathcal{P}\mathcal{P}\cdots\mathcal{P}(S)}$ exists, thus for every $n\in\mathbb{N}$, we can define the set ($\mathcal{P}^0(S)\overset{\mathrm{def}}{=}S$)
$$\bigcup_{i=0}^n\mathcal{P}^i(S).$$
But things become different when we replace the $n$ there by $+\infty$.
Does the following set exists in ZFC?
$$\bigcup_{n\in\mathbb{N}}\mathcal{P}^n(S).$$
What I am trying to define seems quite recursive but I don't know how to do it in ZFC.
If we go straight to the recursion theorem, then a function $f:\bigcup_{n\in\mathbb{N}}\mathcal{P}^n(S)\rightarrow\bigcup_{n\in\mathbb{N}}\mathcal{P}^n(S)$ is needed, which is a circular argument.

Best Answer

I was pretty sure this was a duplicate, but right now I can't find this exact question having been asked earlier, so here goes:

Yes, you can do this - the key is the axiom scheme of replacement (or collection depending on how you've seen $\mathsf{ZF}$ presented).

Consider the following (English shorthand for a) formula $\varphi(x,y,z)$:

$y$ is a natural number and there is a finite sequence $b$ of length $y$ such that the initial term of $b$ is $z$, the last term of $b$ is $x$, and whenever $i+1<y$ we have $b(i+1)=\mathcal{P}(b(i))$.

Then "$\varphi(x,y,z)$" should be interpreted as "$x=\mathcal{P}^y(z)$." A quick argument shows that we can apply replacement (and infinity) to prove in $\mathsf{ZF}$ the following:

For every $z$ the class $$C_z:=\{x:\exists y\in\omega(\varphi(x,y,z))\}$$ is a set.

Applying the union axiom to $C_z$ then gives the desired set.


There are two key things worth noting here:

  • The use of the "coding sequence" $b$ exactly parallels a similar technique in the context of arithmetic for talking about computations.

  • By taking unions at limits there's no difficulty in extending this to arbitrary ordinals instead of just natural numbers, where $y$ is concerned - in $\mathsf{ZF}$ we can in fact make sense of $\mathcal{P}^\alpha(S)$ and $\bigcup_{\beta<\alpha}\mathcal{P}^\beta(S)$ for any set $S$ and ordinal $\alpha$.