A Very Standard Theorem in Set Theory

[caffeinemachine]

Let $A$ be any set. Show that there is no bijection between $A$ and the power set $\mathcal P(A)$ of $A$.

(The power set of a set is the set of all its subsets including the empty-set.)

 

[Opalg]

Let $A$ be any set. Show that there is no bijection between $A$ and the power set $\mathcal P(A)$ of $A$.

(The power set of a set is the set of all its subsets including the empty-set.)

The proof is a version of Russell's paradox.

Spoiler

Suppose (in order to get a contradiction) that $f:A\to \mathcal P(A)$ is a bijection. Let $X = \{ x\in A: x\notin f(x) \}$. Since $f$ is surjective, $X = f(x_0)$ for some $x_0\in A$. Now ask whether or not $x_0 \in X$.

 

[caffeinemachine]

The proof is a version of Russell's paradox.

Spoiler

Suppose (in order to get a contradiction) that $f:A\to \mathcal P(A)$ is a bijection. Let $X = \{ x\in A: x\notin f(x) \}$. Since $f$ is surjective, $X = f(x_0)$ for some $x_0\in A$. Now ask whether or not $x_0 \in X$.

Here's my version of the same:

We interpret $\mathcal P(A)$ as the set of all the functions from $A$ to $\{0,1\}$. Assume for the sake of a contradiction that there is a bijection $\varphi:A\to \mathcal P(A)$. We write $\varphi_x$ instead of $\varphi(x)$ for $x\in A$. Define $g:A\to \{0,1\}$ as $g(x)=1$ if $\varphi_x(x)=0$ and $g(x)=0$ if $\varphi_x(x)=1$. Let $\varphi_y=g$. Then $\varphi_y(y)=g(y)$ (There exists such a $y$ by assumption). The last equality is impossible by definition of $g$ and thus we achieve a contradiction and the proof is complete.$\blacksquare$