9
$\begingroup$

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.

  • 0
    Well no harm done either way.2012-10-28

2 Answers 2

7

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.

4

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.

  • 0
    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$.2012-10-28