How Bertrand Russell discovered the ``Russell Paradox''

Bertrand Russell was working in what is now called ``naive set theory''. That is, he believed that any property $P$ could define a set. $S = \{ x : P ( x ) \}$ The various restrictions on set formation did not exist. They were the result of the Russell Paradox!

Bertrand Russell was reading Cantor's theorem stating that $2^{\aleph} > \aleph .$ That is, for any set $S$ the cardinality of the set of all subsets of $S$, $\tmop{Power} ( S ) = \{ x : x \subset S \}$ is greater than the cardinality of $S$. When the definition of cardinality is stripped away, Cantor was saying that there could be no one to one mapping $f$ which maps the set of all subsets of $S$, $\tmop{Power} ( S )$, into a subset of $S$.

How did Cantor prove his result? He used the traditional mathematical technique of assuming the opposite, and proving a contradiction. That is he assumed the existence of a one to one function $f$ which mapped the power set of $S$ into a subset of $S$.

$$f : \tmop{Power} ( S ) = \{ x : x \subset S \} \longrightarrow S$$

Cantor showed his contradiction using the following diagonalization argument: He defined the following set:

$$C = \{ f ( x ) : x \in \tmop{Power} ( S ) \wedge f ( x ) \nin x \}$$ (1)

Now clearly $C$ is a subset of $S$ so $C \in \tmop{Power} ( S )$. So we can consider $f ( C )$. The question is, is $f ( C ) \in C$? Looking at the definition of C, and the fact that $f$ is one to one, we see immediately that:

$$f ( C ) \in C \tmop{if} \tmop{and} \tmop{only} \tmop{if} f ( C ) \nin C$$

And this chortled Cantor is the contradiction that proves my Theorem.

Well, when Russell read this, he thought nonsense! Consider the set $E = \{ x : x = x \}$, everything. Clearly for all $x$, $x \in E$ and for every set $T$, $T \subset E$. $E$ is everything. $E$ is the biggest set, its cardinality is the largest. In particular, $\tmop{Power} ( E ) \subset E$. And the identity map, $\tmop{id} ( x ) = x$, is a one to one map that maps $\tmop{Power} ( E )$ into a subset of $E$. This, thought Russell, contradicts Cantor's Theorem.

Well, thought Russell, let us look at Cantor's proof in this context. In (), putting $S = E$, and $f = \tmop{id}$, Russell got:

$$C_{E, \tmop{id}} = \{ \tmop{id} ( x ) : x \in \tmop{Power} ( E ) \wedge \tmop{id} ( x ) \nin x \}$$

Noting $\tmop{id} ( x ) = x$, this is:

$$C_{E, \tmop{id}} = \{ x : x \in \tmop{Power} ( E ) \wedge x \nin x \}$$

This is the famous ``set of all sets not members of themselves''. Just as clearly:

$$C_{E, \tmop{id}} \in C_{E, \tmop{id}} \tmop{if} \tmop{and} \tmop{only} \tmop{if} C_{E, \tmop{id}} \nin C_{E, \tmop{id}}$$

And the contradiction that proved Cantor's Theorem, now became a contradiction in set theory. Russell's brain now began to hurt!

Russell considered other related paradoxes such as ``This sentence is false'', as he worked to rescue his monumental work Principia Mathematica. He invented a type theory, which he believed solved the problem. However, he said that from that point on his mind had difficulties with extremely complex abstract problems, and his work began to center on Philosophy rather than Mathematics.