A Very Standard Theorem in Set Theory

caffeinemachine

Well-known member
MHB Math Scholar
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

MHB Oldtimer
Staff member
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.
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

Well-known member
MHB Math Scholar
The proof is a version of Russell's paradox.
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$