- Thread starter
- #1

- Mar 10, 2012

- 834

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

- Thread starter caffeinemachine
- Start date

- Thread starter
- #1

- Mar 10, 2012

- 834

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

- Moderator
- #2

- Feb 7, 2012

- 2,737

The proof is a version of Russell's paradox.

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

- Thread starter
- #3

- Mar 10, 2012

- 834

Here's my version of the same:The proof is a version of Russell's paradox.

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$