# Struggling to Prove Cantor's Theorem (textbook guided exercise)

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.

• Confusion... already in 1. above we must have $f(x) = \{ x\}$. Function $f$ maps elements of $A$ into subsets of $A$ (elements of the power-set of $A$). Commented Jul 14, 2023 at 11:44
• Thus, regarding your first concern; having defined a set $B$ which is a subset of $A$, by hypothesis we must have some element of $A$ - call it $a'$ - such that $a'$ is mapped to $B$ by $f$, i.e. $f(a')=B$. Commented Jul 14, 2023 at 11:46
• this YouTube explanation is one I find actually very helpful for self-learners like myself youtube.com/watch?v=92PgdfgWIys Commented Jul 16, 2023 at 22:09
• and one more very understandable explanation youtube.com/watch?v=wOIpKLFOMSE Commented Jul 18, 2023 at 21:50

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\}$$.

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.

• hi @kipf thanks for clarifying that $f$ maps to a set (q1). I'm still struggling with q2, so will give it more time with pen and paper to see if I can figure it out. I understand the point about not being surjective, but I can't see how we show that constructing $B$ shows that $f$ can't be onto. Commented Jul 16, 2023 at 15:32
• Hi @Penelope! I've edited my answer - hopefully it's clearer now. The basic idea is that $B$ disagrees with every set $f(a)$ in the membership of $a$. Thus it cannot be the result of applying $f$ to any set, and so $f$ is not surjective.
– kipf
Commented Jul 16, 2023 at 15:46