Range of the "power set" function

Question

Let $f: \mathcal{P}(A) \to \mathcal{U}$ be the function given by $f(x) = \mathcal{P}(x)$ for every $x \in \mathcal{P}(A)$. Here, $\mathcal{U}$ is the universe, and $A$ might be a set or it might be a proper class (we can assume it is non-empty).

Note: In the case that $A$ is a proper class, $P(A)$ is the usual definition, except $A \not \in P(A)$. That is, when $A$ is a proper class, $P(A)$ is the set of all proper subsets of $A$.

It is not difficult to show that $\text{range}(f) \subseteq \mathcal{P(P}(A))$. However, I need to show that there exists some non-empty $z \in \mathcal{P(P}(A)) \setminus \text{range}(f)$, i.e. $\text{range}(f) \subsetneq \mathcal{P(P}(A))$. The formal definition of the range of a function f is: $\text{range}(f) = \{f(x) : x \in \text{domain}(f)\}$.

I am struggling to prove this (and I have yet to even convince myself that it is true as it seems quite counterintuitive to me). Any advice to point me in the correct direction is appreciated.

Answer 1

I'm going to use 'set' throughout this answer, but substitute 'class' at your leisure.

Think about what $\mathrm{range}(f)$ and $\mathcal{P}(\mathcal{P}(A))$ mean:

• The elements of $\mathrm{range}(f)$ are of the form $\mathcal{P}(U)$ for some $U \subseteq A$—in particular, $\varnothing \in \mathcal{X}$ for all $\mathcal{X} \in \mathrm{range}(f)$.
• The elements of $\mathcal{P}(\mathcal{P}(A))$ are arbitrary sets of subsets of $A$.

So suppose $A \ne \varnothing$ and fix some $a \in A$. Then $\{ a \} \in \mathcal{P}(A)$, so $\{ \{ a \} \} \in \mathcal{P}(\mathcal{P}(A))$, however $\{ \{ a \} \} \ne \mathcal{P}(x)$ for any $x \in \mathcal{P}(A)$ since $\varnothing \not\in \{ \{ a \} \}$.

Hence $\{ \{ a \} \} \in \mathcal{P}(\mathcal{P}(A)) \setminus \mathrm{range}(f)$.

Answer 2

Let $f$ be any function.

Then $\{x\in\mathrm{dom}(f):x\notin\mathrm{ran}(f)\}\notin\mathrm{ran}(f)$.

The above statement is essentially Cantor's Theorem (there does not exist a surjection from $\color{blue}{X}$ to $\mathcal{P}(\color{blue}{X})$).

You have $f:\color{blue}{\mathcal{P}(A)}\to \mathcal{P}(\color{blue}{\mathcal{P}(A)}):x\mapsto \mathcal{P}(x)$.

To convince oneself of the codomain, it might be useful to recall $X\subseteq Y\iff \mathcal{P}(X)\subseteq \mathcal{P}(Y)$.

Now your question is to show that the range of $f$ is not the entire codomain. You can invoke Cantor's theorem to say that there does not exist a surjection from $\color{blue}{\mathcal{P}(A)}$ to $ \mathcal{P}(\color{blue}{\mathcal{P}(A)})$, or you can simply look at the following set that is not in the range of $f$ $$\{\xi\in\mathrm{dom}(f):\xi\notin\mathrm{ran}(f)\}.$$

You are interested in finding a nonempty set not in the range of $f$, but that remains in the codomain. Then Clive's answer suffices!