Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If $g$ is a function from a set $Y$ to the collection of all subsets of $Y$, how does one show that there exists a subset of $Y$ that is not in the range of $g$?

An explanation of how to attempt a proof would be great. Thanks.

share|improve this question
    
It's hard to give a hint that does not reveal everything. Do you know Cantor's diagonal argument that the real numbers are not countable? It's very similar to that. –  Henning Makholm Sep 3 '11 at 19:34
    
hint For each element $y\in Y$, either it is contained in $g(y)$ or it is not. –  Willie Wong Sep 3 '11 at 19:42
add comment

1 Answer 1

up vote 5 down vote accepted

In short. you are asking for a proof that there is no surjection $Y\to \mathcal{P}(Y)$, where $\mathcal{P}(Y)$ is the power set of $Y$ (the set of all subsets of $Y$).

This is known as Cantor's Theorem, and the proof is standard. Given $g\colon Y\to\mathcal{P}(Y)$, define $$W_g = \{ y \in Y \mid y\notin g(y)\}.$$ I call this set "$W_g$" to stand for "the witness for $g$". This is a witness to the fact that $g$ is not surjective.

To see how $W_g$ is defined, let's consider a couple of examples with finite sets and functions:

Let $Y = \{1,2,3\}$, so that $\mathcal{P}(Y)$ consists of the eight subsets: $$\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}.$$

Let's take one function: $g\colon Y\to \mathcal{P}(Y)$ defined by, say, $g(1) = \{2,3\}$, $g(2)=\emptyset$, $g(3)=\{1,2,3\}$.

Note that $1\notin g(1)$, $2\notin g(2)$, and $3\in g(3)$. That means that $W_g=\{1,2\}$. Now notice that $\{1,2\}$ is not in the range of $g$.

Another function: now let's take $h\colon Y\to \mathcal{P}(Y)$ given by $h(1)=\emptyset$, $h(2) = \{1\}$, $h(3)=\{2\}$. Then $1\notin h(1)$, $2\notin h(2)$, and $3\notin h(3)$, so $W_h = \{1,2,3\}$... which is not in the range of $h$.

Another function: now let's take $k\colon Y\to\mathcal{P}(Y)$ given by $k(1)=\{1\}$, $k(2)=\{2\}$, and $k(3)=\{3\}$. Then $1\in k(1)$, $2\in k(2)$, and $3\in k(3)$, so $W_k = \emptyset$... which is not in the range of $k$.

Now, there are many sets that are not in the ranges of $g$, of $h$, and of $k$. But one set that is not in the range is the "witness."

So... try proving that

  1. For any $g\colon Y\to\mathcal{P}(Y)$, $W_g$ is an element of $\mathcal{P}(Y)$ (easy);
  2. There does not exist a $y\in Y$ such that $g(y)=W_g$ (meat of the proof);
  3. Conclude that $g$ is not onto.
share|improve this answer
    
Thanks for very clear explanation. Now I can tackle the proof with absolute confidence. –  Joe Sep 3 '11 at 20:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.