# How is Cantor's diagonal argument related to Russell's paradox in naive set theory?

I was wondering whether anyone can shed proper light on this issue. I read both and it seems like they are somewhat similar, yet I can't quite see it.

-
I don't think the (fake-proofs) tag is appropriate here, so I've removed it. –  EuYu Oct 28 '12 at 19:50
I was trying to find the tag paradoxes, but couldn't find it and for whatever reason fake-proofs had paradoxes within parentheses, so I went for that –  user43901 Oct 28 '12 at 22:54
Well no harm done either way. –  EuYu Oct 28 '12 at 22:56

It is perhaps worth recalling that in his Introduction to Mathematical Philosophy, Russell writes

When I first came upon this contradiction [in the idea that there is a greatest cardinal], in the year 1901, I attempted to discover some flaw in Cantor's proof that there is no greatest cardinal ... Applying this proof to the supposed class of all imaginable objects, I was led to a new and simpler contradiction, namely, the following :-

The comprehensive class we are considering, which is to embrace everything, must embrace itself as one of its members. In other words, if there is such a thing as "everything" then "everything" is something, and is a member of the class " everything." But normally a class is not a member of itself. Mankind, for example, is not a man. Form now the assemblage of all classes which are not members of themselves. This is a class: is it a member of itself or not? If it is, it is one of those classes that are not members of themselves, i.e. it is not a member of itself. If it is not, it is not one of those classes that are not members of themselves, i.e. it is a member of itself. Thus of the two hypotheses - that it is, and that it is not, a member of itself - each implies its contradictory. This is a contradiction.

So yes, Russell came upon his paradox in analysing what is happening in the Cantor proof applied to the limiting case of a (supposed) universal set. There is indeed that close relationship between the arguments.

-

The connection is not quite through the familiar proof that the reals are not equinumerous with the natural numbers. It is through Cantor's proof that the powerset of a set $A$ cannot be put in one to one correspondence with $A$.

That proof starts as follows. Suppose to the contrary that there is a bijection $\varphi$ between $A$ and the powerset of $A$. Consider the subset $X$ of $A$ that consists of all $a$ such that $a\not\in \varphi(a)$. It is not hard to show that there cannot be an $x\in A$ such that $\varphi(x)=X$.

The description of the set $X$ is very reminiscent of the construction in the Russell Paradox.

The above argument is also often called a diagonal argument. We can see the connection by letting $A$ be the natural numbers. Then the powerset of $A$ can be identified with the set of all infinite sequences of $0$'s and/or $1$'s. For any set $S$ of natural numbers can be identified with its characteristic function $f_S$, defined by $f_S(s)=1$ if $s\in S$, and $f_S(s)=0$ if $s\not\in S$. Indeed subsets can be identified with characteristic functions in general.

Assume that $\varphi$ is a bijection between $\mathbb{N}$ and the set of all such sequences. Then consider the sequence $x_1,x_2,x_3,\dots$ such that $x_i=0$ if $\varphi(i)(i)=1$, and $x_i=1$ if $\varphi(i)(i)=0$. That is essentially the same as the set $X$ described above. More precisely, it is the characteristic function of $X$. This version of the argument has a much clearer connection with the familiar diagonal argument. It can be generalized to arbitrary sets.

-
More precisely, Russell's paradox arises automatically from Cantor's theorem if we ask why the identity function is not a bijection between $V$ and $\mathcal P(V)=V$ where $V$ is the (assumed) set of all sets. –  Henning Makholm Oct 28 '12 at 21:33
@andre: I was wondering whether you could elaborate on the concept of a characteristic function. Moreover, where did you get the φ(i)(i)indexing from? As in, should it just be φ(i)? –  user43901 Oct 28 '12 at 23:00
Will try on characteristic function later. The notation $\varphi(i)(i)$ is admittedly pretty awful. But $\varphi(i)$ is a characteristic function, and $\varphi(i)(i)$ is its value at $i$. Probably I should have called the value of $\\varphi(i)$ by the name $\varphi_i$. –  André Nicolas Oct 28 '12 at 23:54