1
$\begingroup$

In my book Cantor's proof starts off as, assume there is a one to one correspondence for a set X and its power set $Pow(X)$, and we have the following function that represents that $\theta\ :\ X\ \to\ Pow(X)$, and then we are told to form the set $Set\ Y = \{x \in\ X\ |\ x\ \notin\ \theta(x)\}$ to continue the proof of Cantor's theorem (that our initial assumption is not true). I can't seem to understand how this set helps us in disproving our assumption thus leading to the contradiction, and conclusion that there is no one to one correspondance between the power set of a set and the set itself. I am sure I am not understanding the notation, in specific the theta function.

I have looked at the post How does Cantor's diagonal argument work? but there is too much information there and does not address my question specifically. Your help is greatly appreciated.

Thanks,

  • 1
    You can also look at [this](http://math.stackexchange.com/questions/61650/how-to-show-that-a-subset-of-a-domain-is-not-in-the-range/61653#61653) for explicit computations of what $Y$ is in some simple cases.2011-09-12

1 Answers 1

1

This is proved by contradiction. So assume $\theta$ is a bijection between $X$ and $\mathscr{P}(X)$, its power set.

Now since $\theta$ maps each element of $X$ into a subset of $X$, one can ask if $x$ is in the subset $\theta(x)$, i.e. is $x$ in its own image. The set $Y$ you wrote above is precise the set of all $x$ such that $x$ is not in its own image under $\theta$.

Now $Y$ is a perfectly good subset of $X$. Hence $Y \in \mathscr{P}(X)$. If $\theta$ is surjective, then there must be a $y \in X$ such that $\theta(y) = Y$.

Now where is $y$? If $y \in Y = \theta(y)$, then $y \notin Y$, by definition of $Y$ being the set of all $x$ such that $x \notin \theta(x)$. If $y \notin Y = \theta(y)$, then $y \in Y$ by definition of $Y$ being the set of all $x$ such that $x \notin \theta(x)$. Contradiction. A bijection $\theta$ must not have existed.

  • 1
    @William: Again, there is no need to prove the whole theorem by contradiction (though one part of it will be given by contradiction). $\theta$ can be *any* function, and one proves *directly* that $\theta$ is not surjective. You prove that $Y\notin \mathrm{Im}(\theta)$ by contradiction, but one contradiction is more than enough for the proof, no need for two of them...2011-09-12