Struggling to Prove Cantor’s Theorem (textbook guided exercise)

cardinalselementary-set-theory

I am self-teaching and have hit a barrier learning about power sets and Cantor's Theorem (pages 34-35 Understanding Analysis, Abbott, 2nd ed).

The theorem is presented as:

Theorem 1.6.2 (Cantor’s Theorem). Given any set $A$, there does not exist a function $f : A \rightarrow P(A)$ that is onto.

The theorem itself feels intuitively correct for finite sets, but is applicable to infinite sets too.

The text guides the reader through exercises which together form a proof of Cantor's Theorem.

  • We start by assuming, for later contradiction, that there is a function $f: A \rightarrow P(A)$ that is onto.

  • Since $f$ is onto, every subset of $A$ appears as $f(a)$ for $a \in A$.

The idea is to construct a set $B \subseteq A$ in such a way that it leads to a contradiction, thus exposing the assumption that $f$ can be onto is false.

  • We construct $B= \{ a \in A: a \notin f(a) \}$. That is, $B$ contains $a$ if $a$ does not appear in $f(a)$.

I wanted to check I understood this so the following are two examples of possible sets, $A$, $f$ and $B$:

  1. $A = \{a,b,c\}$, $f(x)=x$, and so $B=\emptyset$.
  2. $A = \{a,b\}$, $f(a)=b$ and $f(b)=a$, and so $B=\{a,b\}$.

The textbook then claims:

Because we have assumed that our function $f : A \rightarrow P(A)$ is onto, it must be that $B = f(a′)$ for some $a′ \in A$.

This is where my problems start:

  • First, the statement $B = f(a')$ confuses me as the LHS $B$ is a set, but the RHS is an expression $f(a')$. I guess it means the elements of $B$ are $f(a')$ but I wanted to check as the author of this book is normally very precise elsewhere.

  • Second, the truth of the statement is not obvious to me. Let me try. First, because $f$ is onto, then every subset of $A$ is in in $P(A)$. That includes the individual elements of $A$. That is $A \subseteq P(A)$. Now $B$ is defined to be a subset of $A$, so $B \subseteq A \subseteq P(A)$, which includes the possibility $B=\emptyset$. I agree that some $a'\in A$ give $f(a') \in A$, but I can't agree that this all omeans $f(a') \in B$. What am I missing?

Question: I would appreciate help understanding the above two points.

The above problems prevent me continuing to the desired contraditicion and hence proof that $f$ can't be onto.

Best Answer

First of all, your examples for $f$ aren't quite correct. $f$ is a function from $A$ to the powerset of $A$, $\mathcal P(A)$, meaning it maps an element of $A$ to a subset of $A$. Your examples could instead look like

  • $A = \{a,b,c\}$, $f(x) = \{x\}$, and so $B = \varnothing$.
  • $A = \{a,b\}$, $f(a) = \{b\}$ and $f(b) = \{a\}$, and so $B = A$.

That is, $f(a)$ for any $a \in A$ must be a set.

You could also have an example like

  • $A = \{a,b,c\}$, $f(x) = \{a,b\}$ for all $x \in A$, and so $B = \{c\}$.

Now your two questions.

  1. $f(a')$ is a set, since as above $f$ is a function to $\mathcal P(A)$. So $B = f(a')$ means that $B$ and the set $f(a')$ contain the same elements.
  2. The point of the construction of $B$, is that it cannot be equal to $f(a)$ for any $a \in A$. That is, we have found an element of $\mathcal P(A)$ that is not mapped to by $f$, so $f$ cannot be surjective (or onto).

Why does 2. hold? I'll write $\operatorname{Im}f$ for the image of $f$, so $$\operatorname{Im}f = \{ f(a) : a \in A \}.$$ That is, $\operatorname{Im}f$ is all the possible sets in $\mathcal P(A)$ that $f$ maps to.

We now show that $B \notin \operatorname{Im} f$. That is, for every set $f(a) \in \operatorname{Im} f$, there is some element which is in $B$ and not in $f(a)$, or not in $B$ and in $f(a)$.

Suppose $a \in A$ and $a \notin f(a)$. Then, by the definition of $B$, $a \in B$. Similarly, if $a \in f(a)$, then $a \notin B$. That is to say, $B$ disagrees with every element of $\operatorname{Im} f$ in the membership of at least one element.

So $B$ is in $\mathcal P(A)$ but not in $\operatorname{Im}f$, and thus $f$ cannot be onto.

Related Question