localize Russell's paradox to prove Cantor's theorem

Here, Terence Tao writes:

Proposition 4 (No universal set) There does not exist a set which contains all sets (including itself).

Proof: Suppose for contradiction that there existed a universal set ${X}$ which contained all sets. Using the axiom schema of specification, one can then construct the set

$\displaystyle Y := \{ A \in X: A \not \in A\}$

of all sets in the universe which did not contain themselves. As ${X}$ is universal, ${Y}$ is contained in ${X}$. But then, by definition of ${Y}$, one sees that ${Y \in Y}$ if and only if ${Y \not \in Y}$, a contradiction. $\Box$

[…]

One can “localise” the above argument to a smaller domain than the entire universe, leading to the important

Proposition 5 (Cantor’s theorem) Let ${X}$ be a set. Then the power set ${2^X := \{ A: A \subset X \}}$ of ${X}$ cannot be enumerated by ${X}$, i.e. one cannot write ${2^X := \{ A_x: x \in X \}}$ for some collection ${(A_x)_{x \in X}}$ of subsets of ${X}$.

Proof: Suppose for contradiction that there existed a set ${X}$ whose power set ${2^X}$ could be enumerated as ${\{ A_x: x \in X \}}$ for some ${(A_x)_{x \in X}}$. Using the axiom schema of specification, one can then construct the set

$\displaystyle Y := \{ x \in X: x \not \in A_x \}$.

The set ${Y}$ is an element of the power set ${2^X}$. As ${2^X}$ is enumerated by ${\{ A_x: x \in X \}}$, we have ${Y = A_y}$ for some ${y \in X}$. But then by the definition of ${Y}$, one sees that ${y \in A_y}$ if and only if ${y \not \in A_y}$, a contradiction. $\Box$

What does Terence Tao mean with this:

One can “localise” the above argument to a smaller domain than the entire universe, leading to the important [Cantor's theorem]

But for me the arguments of proposition 4 and 5 seem not to be the same. Of course, there are somewhat similar but however, it doesn't seem to be an easy job to prove Cantor's theorem if one already knows Russell's paradox. Can you guess what Tao had in mind when saying this quote ("one can 'localise' the above …")? Or isn't there something deep behind it, and he is just trying to say that we use a similar argument to prove something about "sets" rather than "classes"?

• He just means that we can adapt the method to a Q about subsets of a set... BTW Russell's Paradox is that existence of some $X$ such that $\forall Y\;(Y\in X \iff Y\not \in Y)$ leads to a contradiction. It requires no set-theoretic axioms at all. – DanielWainfleet Jan 27 '17 at 20:51

The idea is that we think of the proposed bijection taking $x$ to $A_x$ as an identification - so we're thinking of $x$ and $A_x$ as being the same thing. Our universe is $X$. In this argument, we then interpret Russell's set within this universe: $\{x \in X : x \notin x\}$. But we're thinking of $x$ and $A_x$ as being the same thing, so the set is $\{x \in X : x \notin A_x\}$. By the same argument as Russell's Paradox, this set can't be (the $A$ identified with) any member of $X$.

It's not completely the same, which is why Tao doesn't list Cantor's Theorem as a corollary rather than a proposition in its own right; but Cantor's Theorem and Russell's Paradox are "basically" the same thing. It might be easier to see in the other direction: if we had a universal set $X$, then $2^X$ would have to be a subset of it, and then we could use the identity function as the map from $X$ to $2^X$ (so $A_x = x$). Then the set used in Cantor's Theorem, $\{x \in X : x \notin A_x\}$ is exactly Russell's set.

• I have problems to understand your very first sentence. "The idea is that we think of the proposed bijection taking $x$ to $A_x$ as an identification […]" But the proposed thing isn't necessarily a bijection, but it is a surjection. Of course, using the theorem of Cantor-Schröder-Bernstein, one can prove that there is a bijection if one has a surjection. But this tool (Cantor-Bernstein-Schröder) seems to be a little overpowered for this kind of job. – user7280899 Jan 29 '17 at 0:14
• @user7280899 Sure, surjection then, or just "map". Whether or not it's a bijection isn't relevant to the rest of the argument. It costs us nothing to identify all $x$ that map to the same $A_x$ - we can't possibly lose an enumeration that way. – Reese Jan 29 '17 at 0:19
• You speak about an "identification" which identifies $x$ and $A_x$. In my opinion this phrase only makes sense if this identification is bijective. But Cantor's theorem is more naturally understood as saying that there is no surjection from $X$ to $2^X$. – user7280899 Jan 29 '17 at 0:21
• If we have two different $x$-values $x_1$ and $x_2$ with $A_{x_1} = A_{x_2}$, then you would identify $x_1$ with $x_2$, but these are different objects. – user7280899 Jan 29 '17 at 0:23
• Also, what do you mean by "Sure, surjection then, or just "map"."? Cantor's theorem says "there is no surjection $X\to 2^X$". If we would replace "surjection" with "map", then we would get the statement "there is no map $X\to 2^X$", but this is false. – user7280899 Jan 29 '17 at 0:24

There isn't really anything much deeper going on than what you've observed. You can make the connection between Russell's paradox and Cantor's theorem more direct by tweaking the statement and proof of Cantor's theorem to talk about $\{A_x: x\in W\}$ for some subset $W\subseteq X$, which may not be all of $X$. With this modification, Russell's paradox is really a special case of Cantor's theorem.

Indeed, if you assume that there exists a universal set $X$, then every subset of $X$ is an element of $X$ (since every set is an element of $X$!). Writing $W=2^X\subseteq X$, this means that you can enumerate $2^X$ as $\{A_x:x\in W\}$ where $A_x=x$ for all $x\in W$. Cantor's theorem then gives a contradiction. Moreover, the proof of Cantor's theorem for this particular choice of enumeration is exactly the same as the proof of Russell's paradox. So Russell's paradox is really just a special case of Cantor's theorem, for one particular enumeration that would exist if there were a universal set.

• Thanks, Eric. Your explanation helpfully adds to Reese's answer. – user7280899 Feb 1 '17 at 17:52