A silly doubt on the impossibility of surjection $A\to P(A)$?

Question

I'm trying to understand a minor detail in this proof:

2.21. Theorem (Cantor). For every set $A$, $$ A <_c \mathcal{P}(A), $$ i.e., $A \leq_c \mathcal{P}(A)$ but $A \neq_c \mathcal{P}(A)$; in fact there is no surjection $\pi \colon A \twoheadrightarrow \mathcal{P}(A)$.

Proof. That $A \leq_c \mathcal{P}(A)$ follows from the fact that the function $$ (x \mapsto \{x\}) $$ which associates with each member $x$ of $A$ its singleton $\{x\}$ is an injection. (Careful here: the singleton $\{x\}$ is a set with just the one member $x$ and it is not the same object as $x$, which is probably not a set to begin with!)

To complete the proof, we assume (towards a contradiction) that there exists a surjection $$ \pi \colon A \twoheadrightarrow \mathcal{P}(A), $$ and we define the set $$ B = \{ x \in A \mid x \notin \pi(x) \}, $$ so that for every $x \in A$, $$ x \in B \iff x \notin \pi(x). $$ Now $B$ is a subset of $A$ and $\pi$ is a surjection, so there must exist some $b \in A$ such that $B = \pi(b)$; and setting $x = b$ and $\pi(b) = B$, we get $$ b \in B \iff b \notin B $$

I am confused with the choice of $B$ here. I understand that we could make a surjection this way, after all we are mapping each $a\in A$ to an element of $P(A)$ that does not contain $a$, that is: Something like:

$$1\to\{2,3\}\\ 2\to \{1,3\}$$

And this yields that problematic conclusion. I understood the proof, but I don't understand why this choice of $B$ proves that there is no surjection. That is: Why couldn't we construct $B$ in another form such that the surjection is achievable? Does the sole existence of this construction of $B$ denies the surjection? Why?

Answer 1

The better way to formulate the proof is not by contradiction, but rather by contrapositive: let $\pi\colon A\to\mathcal P(A)$ be any function, we define a set $B_\pi\in\mathcal P(A)$ such that $\pi(a)\neq B_\pi$ for all $a\in A$. In other words, we show that $\pi$ is not surjective.

Now, the important thing to note is that the definition of $B$ depends on $\pi$, and it works for any $\pi$. It's not just for surjective functions; and different $\pi$ will produce different $B$'s.

---

Let's look at two examples:

Example I:

$A=\{0,1,2\}$ and $\pi(a)=\{a\}$.

Then we define $B$ to be $\{a\in A\mid a\notin\pi(a)\}$, which in turn translates with this specific $\pi$ to be $B=\{a\in A\mid a\notin\{a\}\}$. Of course, this $B$ has to be empty. But lo and behold, $\pi(0),\pi(1)$ and $\pi(2)$ are all non-empty. So $B$ is not in the range of $\pi$.

Example II:

$A=\Bbb N$ and $\pi(n)=\{k\mid\ n^2\mid k\}$, namely $\pi(n)$ is the set of all those $k$ such that $n^2$ divides $k$ (in this context, every number—including $0$—divides itself).

What does the definition of $B$ gives us now? It's the set $\{n\mid\ n^2\nmid n\}$, which is exactly $\Bbb N\setminus\{0,1\}$. But now we ask if there is a number $n$ such that $n^2$ divides all the natural numbers except $0$ and $1$? Since every number divides $0$, the answer is easily negative; but also by arguing through prime numbers if you prefer: $n^2\nmid 2$ for any natural number except $1$, but since $1^2\mid 1$, and $1\notin B$, it is impossible that $B=\pi(1)$, so $B$ is not $\pi(n)$ for any $n$.

---

TL;DR

So to recap, $B$ is defined from $\pi$ to conclude that $B$ is not in the image of $\pi$. This definition depends on $\pi$, but it works for every $\pi\colon A\to\mathcal P(A)$.

Answer 2

The point is that if $\pi$ is surjective, then every subset of $A$ is in its range; in particular, the $B$ from the proof.

Answer 3

The construction of $B$ occurs after the construction of the surjection. That is, as long as there is a function from $A$ to $\mathcal{P}(A)$, we can define such a set $B$. You can't "construct $B$ in another way" because regardless of what other set you construct, $B$ will still exist if you have a function, and hence $B$ gives us the desired contradiction.

Answer 4

You could think about Cantor's theorem as a "corollary" to what is truly proven.

Proposition. For each set $ X $ and for each $ f:X\to \mathscr{P}\left(X\right) $, there exists $ Y\in\mathscr{P}\left(X\right) $ such that $ Y\notin \operatorname{ran}\left(f\right) $.

Proof. Let $ X $ be an arbitrary set. Let $ f:X\to\mathscr{P}\left(X\right) $ be arbitrary. Define $ Y:=\left\{z\in X:z\notin f\left(z\right)\right\} $. By contradiction, suppose $ Y\in\operatorname{ran}\left(f\right) $. Therefore there exists $ x\in X $ such that $ f\left(x\right)=Y $.

(I) Assume $ x\in Y $. Therefore $ x\in X $ and $ x\notin f\left(x\right) $. Because $ f\left(x\right)=Y $, $ x\notin Y $---a contradiction.

(II) Assume $ x\notin Y $. Therefore $ x\notin X $ or $ x\in f\left(x\right) $. Because $ x\in X $, $ x\in f\left(x\right) $. Because $ f\left(x\right)=Y $, $ x\in Y $---a contradiction.

As a result, $ Y\notin\operatorname{ran}\left(f\right) $.

---

EDIT: To elaborate further:

Recall

• A function $f:A\to B$ is surjective if for each $b\in B$, there exists $a\in A$ such that $f(a)=b$.
• The range of a function $f:A\to B$ is $\mathrm{ran}(f):=\{b\in B:(\exists a)[a\in A\,\wedge\, f(a)=b]\}$.

Corollary. For each set $X$, there does not exist a surjection $f:X\twoheadrightarrow \mathscr{P}(X)$.

Proof. Let $X$ be an arbitrary set. By contradiction, suppose there exists a surjection $f:X\twoheadrightarrow \mathscr{P}(X)$. Because $f$ is a function from $X$ to $\mathscr{P}(X)$, there exists $Y\in\mathscr{P}(X)$ such that $Y\notin \mathrm{ran}(f)$. Because $f$ is surjective and $Y\in \mathscr{P}(X)$, there exists $x\in X$ such that $f(x)=Y$. Therefore $Y\in\mathrm{ran}(f)$---a contradiction. As a result, there does not exist a surjection $f:X\twoheadrightarrow \mathscr{P}(X)$.