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,

  • 0
    There is a typo in the question, and I presume you are confused because of that. $X$ is the ground set. For any $x \in X$, $\theta(x)$ is an element of $Pow(X)$; in other words, $\theta(x) \subseteq X$. The set $\theta(X)$ represents the range of the function; it is a collection of elements of $Pow(X)$ (which btw are subsets of $X$). The set $\theta(X)$ does not play any role in this proof. (Also, if you think about it no $x\in X$ can be an element of $\theta(X)$; so $x \not\in \theta(X)$ will be always true.) Correct your $\theta(X)$ to $\theta(x)$, and see if things make sense.2011-09-12
  • 0
    Can you more clearly define $x$ for me. Is this a single base element or is $x$ a set2011-09-12
  • 0
    Ok. An example. $X$ is the set of all natural numbers. $x$ is a particular natural number, like $17$ or $42$. $\theta(x)$ is some subset of $\mathbb N$; that is, some set containing natural numbers. E.g. $\theta(17) = \{ 1, 5, 17, 22 \}$ and $\theta(42)$ is the set of all odd numbers. Question: Is $17 \not\in \theta(17)$ true? Is $42 \not\in \theta(42)$ true?2011-09-12
  • 0
    Thanks, the clarification helps.2011-09-12
  • 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.

  • 0
    Are $x and $y sets or elements of a specific subset. When I say elements I mean concrete elements such as a natural number or symbol?2011-09-12
  • 0
    Note that it isn’t necessary to assume that $\theta$ is a bijection: the argument actually shows that if $\theta:X\to\wp(X)$ is *any* function, $Y_\theta=\{x\in X:x\notin\theta(x)\}$ is a member of $\wp(X)\setminus\operatorname{ran}\theta$ definable from $\theta$, which therefore cannot map $X$ *onto* $\wp(X)$.2011-09-12
  • 0
    @Matthew: William was careful to use $x$ and $y$ consistently to represent elements of $X$. (These elements of $X$ might themselves be sets of other things, but that’s irrelevant to the argument.) $Y$, $\theta(x)$, and $\theta(y)$, on the other hand, represent subsets of $X$. I’m not quite sure what you’re getting at in your second question; the letter $y$ is a symbol representing a particular member of the set $X$, but we’ve no idea what kinds of things the elements of $X$ are.2011-09-12
  • 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