Prove that there exists no surjection between $X\rightarrow P(X)$ -Proof question

Question

There is a hint that I shound take an arbitrary function $F:X\rightarrow P(X)$ and show that the subset $\{ x\in X|x\notin F(x) \}$ is not an element of $F(X)$. I don't know how one could came up with something like that what was the Intuition behind that and how do we even know that such a subset even exists?

Answer 1

Given an arbitrary function $F:X\to P(X)$, you want to produce a subset $Z$ of $X$ that is not in $F(X)$; I'll try to explain how one might guess the $Z$ that seemed to be invented magically and just happened to work.

The desired property of $Z$, namely $Z\notin F(X)$, means that, for each $x\in X$, we have $Z\neq F(x)$. That, in turn, means that, for each $x\in X$, there is some $y\in X$ "witnessing that $Z\neq F(x)$", by which I mean that either $y\in Z$ but $y\notin F(x)$ or else $y\notin Z$ but $y\in F(x)$.

When constructing $Z$, we have to make sure that, for each $x\in X$, there is some $y\in X$ as described in the previous paragraph. We have considerable freedom as to which $y$ we should use to do this job; we only have to make sure that each $x$ gets at least one appropriate $y$.

Now comes the (only?) clever idea in the construction: For each $x$, I'll choose, as the associated $y$, the simplest choice that comes to mind, namely $x$ itself. (I'll comment later on what would happen if we made different choices here.) So we want that, for each $x\in X$, either $x\in Z$ but $x\notin F(x)$ or else $x\notin Z$ but $x\in F(x)$. That says exactly that $Z=\{x\in X:x\notin F(x)\}$. So that's where the set in your hint came from.

What if I had chosen, for various (perhaps all) $x$'s, some $y$ other than $x$ itself? Well, if I chose the same $y$ for two different $x$'s, say $x_1$ and $x_2$, then I might get into trouble. Namely, if $y\in F(x_1)$ and $y\notin F(x_2)$, then I'll want $y\notin Z$ (for the sake of $x_1$) and $y\in Z$ (for the sake of $x_2$), and so there won't be any suitable $Z$. So I'd better make sure I pick different $y$'s for different $x$'s. In other words, the function $x\mapsto y$ should be one-to-one. But that's all that I need to watch out for. Given any one-to-one function $w:X\to X$, there will exist a $Z$ such that, for each $x\in X$, $w(x)$ serves as the desired $y$ above. In other words, there is $Z\subseteq X$ such that, for all $x\in X$, we have $w(x)\in Z\iff w(x)\notin F(x)$. (If $w$ is not surjective, then there will be more than one such $Z$ because nothing constrains $Z$ outside the range of $w$.)

Answer 2

See Axiom schema of Specification : given a set (in this case $X$), the axiom states that every subset that we can "specify" by way of a suitable formula exists.

The intuition is quite simple. Consider an $a ∈ X$ whatever: either $a ∈ F(a)$ or not.

If not, put it into the new defined set. At the end, either the new set will be empty (in which case is a subset of $X$) or not: in which case is "made of" elements of $X$, and again is a subset of $X$.

Consider the simple example of $F : X → \mathcal P(X)$ such that $F(a) = \{ a \}, for each $a ∈ X$.

Obviously : $a ∈ \{ a \} = F(a)$ and thus : $Y = \{ x ∈ X \mid x ∉ F(x) \} = \emptyset$.

But in the above example $F$ is "arbitrary"; thus, in principle we may have $a ∉ F(a)$ for some (maybe none) $a ∈ X$.

---

The construction is the core of the fundamental Cantor's Theorem, stating that the set of all subsets of a set $A$ has a strictly greater cardinality than $A$ itself.