Why is "$Y = \mathbb{P}(X)$ not a $\Delta_0$?

Question

I am taking a class on Set Theory, and using the book $\textit{Set Theory}$ by Thomas Jech. Both in class and in the book, it was mentioned that the statement $X = \mathbb{P}(Y)$ is not a $\Delta_0$ (bounded quantifiers) formula, with my professor claiming that there is no $\Delta_0$ representation for this formula in particular because $\forall z \in X(z \subseteq Y)$ is not $\Delta_0$. I can't exactly figure out why. Can't we express this statement in the form $\forall z \in X \forall t\in z(t\in Y)$? Could we not then express the whole statement by saying $\forall z \in X \forall t\in z(t\in Y) \wedge [\forall y\in z (y \in Y) \Rightarrow z \in X]$? All these quantifiers seem bounded. Thanks in advance for any response.

Answer 1

I think you've switched your "$Y$" and "$X$" - your formulas read like you're trying to describe "$X=\mathcal{P}(Y)$." I'll use that interpretation below.

"$\forall z\in X(z\subseteq Y)$" is definitely $\Delta_0$, so you're right there. However, to say that $X$ is the powereset of $Y$ you need to say that every subset of $Y$ occurs in $X$, and this requires unbounded quantification (or if you prefer, quantification over the powerset of $Y$ - which you don't have as a parameter).

In particular, in your purported definition $$"\forall z \in X \forall t\in z(t\in Y) \wedge [\forall y\in z (y \in Y) \Rightarrow z \in X],"$$ note that something weird is going on with the second occurrence of "$z$." Previously, $z$ was required to be an element of $X$ ("$\forall z\in X$"), but that makes the clause "$\forall y\in z(y\in Y)\implies z\in X$" trivial. Really, that clause has an implicit "$\forall z$" preceding it - but that's an unbounded quantifier!

Summary: The problem is that, while it's easy to express "every element of $X$ is a subset of $Y$" ($X\subseteq\mathcal{P}(Y)$) in a $\Delta_0$ way, saying "every subset of $Y$ is an element of $X$" ($X\supseteq\mathcal{P}(Y)$) is something we can't do in a bounded way. It's possible you either misheard your professor or they misspoke when describing the key obstacle here.

---

A bit of advanced content:

Note that the above doesn't prove that "$X=\mathcal{P}(Y)$" isn't $\Delta_0$-expressible, it just shows why your particular approach doesn't work. To show that it really isn't $\Delta_0$-expressible at all is harder: we need to find two models $M, N$ of ZFC and some objects $X,Y\in M$ such that

• $N$ is an end extension of $M$. (This means that sets in $M$ don't "gain elements" when we pass to $N$; formally, $M\subseteq N$ as models and for each $m\in M$, we have $$\{n\in M: M\models n\in m\}=\{n\in N: N\models n\in m\}.$$ The point is - and this is a good exercise if you haven't done it already - that $\Delta_0$ formulas are preserved under end extensions.)

• $M$ thinks $X$ is the powerset of $Y$: for every $z\in M$, if $z\subseteq Y$ (in the sense of $M$) then $z\in X$ (in the sense of $M$) and conversely.

• $N$ doesn't think $X$ is the powerset of $Y$: there is some $z\in N$ with $z\not\in X$ (in the sense of $N$) but $z\subseteq Y$ (in the sense of $N$).

This is difficult, since building models of ZFC is hard (it's a really complicated theory!). But once we've developed the machinery of forcing, this becomes quite easy: if $M$ is a model of ZFC, $\mathbb{P}$ is any nontrivial forcing notion in $M$, and $G$ is $\mathbb{P}$-generic over $M$, then $M[G]$ is an end extension of $M$ which is a model of ZFC and $\mathcal{P}^M(\mathbb{P})\not=\mathcal{P}^{M[G]}(\mathbb{P})$ (since $M[G]$ contains a subset of $\mathbb{P}$ which doesn't appear in $M$ - namely, $G$ itself).

Maybe more interestingly: if $M$ is any countable model of ZFC, $Y\in M$, and $M$ thinks $Y$ is infinite, then there is a forcing notion which adds a new subset of $Y$; if $G$ is generic for this forcing over $M$ (and such a $G$ will exist since $M$ is countable), then $M[G]$ contains a subset of $Y$ which isn't in $M$, so the powerset of $Y$ changes when we go from $M$ to $M[G]$. In particular: even being $\mathcal{P}(\omega)$ isn't $\Delta_0$!