Can we define the tower of iterated power sets in ZFC? 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.
 A: 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$.
A: Noah Schweber has provided a satisfactory answer for this problem. I am writing to discuss two things. First, how can we generalize this? And second, what role does replacement play here?
First, let's give a formal definition to a term. We say that $A$ is an indexed set over $I$ if $A$ is a function whose domain is $I$ (and whose range is a collection of sets). This situation is often written $\{A_i\}_{i \in I}$.
Given a relation $R$, we write $R^{-1}(a) = \{b \mid (b, a) \in R\}$.
Now, let's proceed to the "recursion theorem" (which is technically a theorem schema). Let $\phi(a, b, c)$ be a predicate.

Let $R$ be a well-founded relation on $S$. Write $R^{-1}(a) = \{s \in S \mid (i, s) \in R\}$. Suppose that for all $a \in S$, if $b$ is an indexed set $\{b_i\}_{i \in R^{-1}(a)}$ then there exists a unique $c$ such that $\phi(a, b, c)$. Then there is an indexed set $\{C_i\}_{s \in S}$ such that for all $s \in S$, $\phi(s, \{C_i\}_{i \in R^{-1}(s)}, C_s)$.

There are two definitions of $R$ being well-founded. The nicer one is the inductive definition. This definition essentially says that $R$ is a relation you can do induction on.

Definition 1: $R \subseteq S^2$ is well-founded if and only if $\forall A \subseteq S . (\forall s \in S . (\forall a \in R^{-1}(s) . a \in A) \to s \in A) \to \forall s \in S (s \in A)$.

The second definition is the more well-known one. It states that any non-empty set has an $R$-least element.

Definition 2: $R \subseteq S^2$ is well-founded if and only if $\forall A \subseteq S . (\exists s \in S . s \in A) \to \exists s \in S . s \in A \land R^{-1}(s) = \emptyset$.

With these definitions in mind, let's prove the recursion theorem.
Let $R$, $S$, $\phi$ be as mentioned.
An indexed set $\{D_i\}{i \in I}$ is called an "attempt" whenever the following conditions are satisfied:

*

*$I \subseteq S$, and for all $i \in I$, $R^{-1}(i) \subseteq I$

*For all $i \in I$, $\phi(i, \{D_j\}_{j \in R^{-1}(i)}, D_i)$
Let us note that given any two attempts $\{D_i\}_{i \in I}$, $\{C_j\}_{j \in J}$, the two attempts agree on $I \cap J$.
More formally, let $A = \{s \in S \mid $ if $a \in I \cap J$ then $D_a = C_a\}$. We will use well-founded induction to show that $A = S$. For consider some $s \in S$, and suppose that for all $b \in R^{-1}(s)$, if $b \in I \cap J$ then $D_b = C_b$. Suppose that $s \in I \cap J$. Then $s \in I$ and $s \in J$, so $R^{-1}(s) \subseteq I$ and $R^{-1}(S) \subseteq J$. Then $R^{-1}(s) \subseteq I \cap J$. And for all $b \in R^{-1}(s)$, we therefore see that $D_b = C_b$. Thus, we see that $\{C_j\}_{j \in R^{-1}(s)} = \{D_i\}_{i \in R^{-1}(s)}$. Now let us note that $\phi(s, \{C_j\}_{j \in R^{-1}(s)}, C_s)$. And also $\phi(s, \{D_i\}_{i \in R^{-1}(s)}, D_s)$. Since $\{C_j\}_{j \in R^{-1}(s)} = \{D_i\}_{i \in R^{-1}(s)}$, we see that $\phi(s, \{D_i\}_{i \in R^{-1}(s)}, C_s)$. Therefore, $C_s = D_s$. So $s \in A$.
Thus, we see that $S = A$. This demonstrates that $D$ and $C$ agree on $I \cap J$, as required.
Now if we have two attempts $\{D_i\}_{i \in I}$ and $\{C_j\}_{j \in J}$, we say $D \leq C$ if and only if $I \subseteq J$. It's easy to show that this is a partial order. It's also easy to see, given the previous lemma, that $D \leq C$ if and only if $D \subseteq C$ (where we're considering the underlying set of ordered pairs that makes up the function).
Now, let's suppose we have some indexed set $\{\{(D_j)_i\}_{i \in I_j}\}_{j \in J}$ of attempts. Then we see that we can construct the union of these attempts $\{(\bigcup\limits_{j \in J} D_j)_i\}_{i \in \bigcup\limits_{j \in J} J}$, which is defined by taking the union of the underlying functions. Note that $\bigcup\limits_{j \in J} D_j$ is the smallest attempt such that for all $j \in J$, $D_j \leq \bigcup\limits_{j \in J} D_j$.
I claim that for all $s \in S$, there is a least attempt $\{D_i\}_{i \in I}$ such that $s \in I$.
To do this, we define $A = \{s \in S \mid$ there is a least attempt $\{D_i\}_{i \in I}$ such that $s \in I\}$. We proceed by well-founded induction.
Suppose $s \in S$. Suppose that for all $b \in R^{-1}(s)$, $b \in A$. That is, for all $b \in R^{-1}(s)$, there is a least attempt $\{(D_b)_i\}_{i \in I_b}$. Such a least attempt is necessarily unique. So using a combination of the axiom scheme of replacement, we can form the indexed set $\{D_b\}_{b \in R^{-1}(s)}$. Then let $C = \bigcup\limits_{b \in R^{-1}(S)} D_b$. Now $\{C_i\}_{i \in \bigcup\limits_{b \in R^{-1}(s)} I_b}$ is the smallest attempt which is defined on all elements of $R^{-1}(s)$. Consider the unique $c$ such that $\phi(s, \{C_b\}_{b \in R^{-1}(s)}, c)$. Define the indexed collection $\{D_i\}_{i \in \{s\} \cup \bigcup\limits_{b \in R^{-1}(s)} I_b}$ by $D_s = c$ and, for all $i \in \bigcup\limits_{b \in R^{-1}(s)} I_b$, $D_i = C_i$. Note that in the event that $s \in \bigcup\limits_{b \in R^{-1}(s)} I_b$, we must have $C_s = c$ by the definition of an attempt, so $D$ is well-defined.
Then we see that $D$ is an attempt, and $D_s$ is defined. We can also see pretty easily that $D$ is the smallest attempt for which $D_s$ is defined, since any attempt $\{K_i\}_{i \in I}$ where $s \in I$ must also have $b \in I$ for all $b \in R^{-1}(s)$, and thus must have $I_b \subseteq I$ for all $b \in R^{-1}(s)$. So we must have $\bigcup\limits_{b \in R^{-1}(s)} I_b \subseteq I$, and also $s \in I$. Thus, we must have $\{s\} \cup \bigcup\limits_{b \in R^{-1}(s)} I_b \subseteq I$.
Thus, we see that $A = S$. Then for all $s$, there is a least attempt $D_s$ where $s$ is defined.
Define $K = \bigcup\limits_{s \in S} D_s$. Then $K$ is an attempt, and the domain of $K$ is clearly all of $S$. $K$ is also the only attempt defined on all of $S$, since if we also had an attempt $J$ defined on all $S$, then $K$ and $J$ would agree on $S \cap S$. Therefore, we have proved what we set out to show.
So we have proved the recursion theorem. Let's apply it to the case of constructing $\bigcup\limits_{n \in \mathbb{N}} P^n(\mathbb{N})$.
Consider the following relation on $\mathbb{N}$: $aRb$ if and only if $b = a + 1$. Then $R$ is well-founded - in fact, traditional induction on $\mathbb{N}$ is equivalent to well-founded induction on $R$. For note that $R^{-1}(0) = \emptyset$, and $R^{-1}(n + 1) = \{n\}$. Saying that $\forall n \in \mathbb{N} (R^{-1}(n) \subseteq A \to n \in A)$ is the same as saying that $0 \in A$ and for all $n \in A$, $n + 1 \in A$.
Define $\phi(a, b, c)$ to be the statement "Either $a = 0$ and $c = S$, or $a > 0$ and $c = P(b_{a - 1})$". Clearly, for all $a \in \mathbb{N}$ and for all indexed families $\{b_m\}_{m \in R^{-1}(n)}$, there is a unique $c$ such that $\phi(a, b, c)$.
Therefore, there exists a unique indexed set $\{C_n\}_{n \in \mathbb{N}}$ satisfying $\forall n \in \mathbb{N} (\phi(n, \{C_m\}_{m \in R^{-1}(n)}, C_n))$.
This particularly means that $C_0 = S$ and that $C_{n + 1} = P(C_n)$. This is exactly the definition of $P^n(S)$.
Now because $C$ is an indexed set over $\mathbb{N}$, we see that $\bigcup\limits_{n \in \mathbb{N}} C_n = \bigcup\limits_{n \in \mathbb{N}} P^n(S)$ does indeed exist.
However, in set theories without the axiom of replacement, the situation is quite different. It turns out that the set $\bigcup\limits_{n \in \mathbb{N}} P^n(\mathbb{N})$ is actually a model of ZFC without replacement. That is, if you take any of the axioms of set theory (other than the axiom scheme of replacement), the axioms are true in $\bigcup\limits_{n \in \mathbb{N}} P^n(\mathbb{N})$. But what is not true within $\bigcup\limits_{n \in \mathbb{N}} P^n(\mathbb{N})$ is the statement "$\bigcup\limits_{n \in \mathbb{N}} P^n(\mathbb{N})$ exists".
This means that replacement is a critical and unavoidable part of the theory.
It's also the case that in set theories without the law of excluded middle, replacement alone does not guarantee the existence of $\bigcup\limits_{n \in \mathbb{N}} P^n(\mathbb{N})$. It actually takes both replacement and separation to guarantee that such a set exists.
