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.

  • $\begingroup$ 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. $\endgroup$ – Henning Makholm Sep 3 '11 at 19:34
  • $\begingroup$ hint For each element $y\in Y$, either it is contained in $g(y)$ or it is not. $\endgroup$ – Willie Wong Sep 3 '11 at 19:42

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.
  • $\begingroup$ Thanks for very clear explanation. Now I can tackle the proof with absolute confidence. $\endgroup$ – Joe Sep 3 '11 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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