Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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.

share|cite|improve this answer

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.