Cantor - No set is equinumerous with its power set.

Theorem:

No set is equinumerous with its power set.

Proof:

Let $A$ be a set. We want to show that if $f: A \to \mathcal{P}A$ (a random function) then $f$ is not surjective.

We define the set $D=\{ x \in A: x \notin f(x)\}$ and obviously $D \in \mathcal{P}A$.

We assume that there is an $a \in A$ such that $f(a)=D$.

Then we have:

$$a \notin D \leftrightarrow a \notin f(a) \leftrightarrow a \in D, \text{ contradiction}$$

Therefore for each $x \in A, f(x) \notin D$, i.e. $f$ is not surjective.

Could you explain me the proof from the point where we assume that there is an $a \in A$ such that $f(a)=D$?

We have show that $D \in \mathcal{P}A$ and we want to show that $D \notin f(A)$ in order to show that $\mathcal{P}A$ isn't the image of $f$. Why do we do it like that? Why do we assume an $a \in A$ such that $f(a)=D$?

Solution 1:

Because if you prove that $D\in \mathcal PA$ and $D\notin f(A)$ proves that $f(A)\neq \mathcal PA$, which is the definition of surjectivity of $f$.

You prove that $D\notin f(A)$ using the definition of $f(a)$: since $D\in f(A) \iff \exists a\in A: f(a)=D$, you only need to prove that there does not exist such an $a\in A$ that $f(a)=D$. You prove this by contradiction, i.e. you assume:

$$\exists a\in A: f(a)=D$$

and arrive at a contradiction, meaning you prove that the statement is false. Since the statement is equivalent to the statement $D\in f(A)$, this statement is also untrue.