Produced by Charles Wells.  Home.   Website Contents     Website Index   

Posted 15 April 2008

SETS: RUSSELL’S PARADOX

The setbuilder notation has a bug: for some assertions P(x), the notation  does not define a set.

Example

Let P(x) be the assertion "x is a set".  Then if  were a set, it would be the set of all sets. However, there is no such thing as the set of all sets. This can be proved using the theory of infinite cardinals, but not here.   (See the discussion following Theorem 5 in Suber’s presentation of set theory.)

Russell’s impossible set

I now give another example of a definition  which does not give a set, and I will prove this time that it does not give a set. It is due to Bertrand Russell.  He took P(x) to be " x is a set and x is not an element of itself." This gives the expression "  ”. 

Now let’s prove by contradiction that that expression does not denote a set.

Suppose  is a set.  Call is S.  There are two possibilities:

(i)              .  Then by definition of S, S is not an element of itself, i.e., . This follows from the first part of the method of comprehension.  So it is not possible that .

(ii)             .  In this case, P(S) is true, so by the second part of the method of comprehension, we know that SS. So it is not possible that .

It follows by this contradiction that S is not a set.

Consequences of Russell’s Paradox

We now know that setbuilder notation can't be depended on to give a set.  To get around this difficulty, set theory as a mathematical science (as opposed to a useful language) had to be developed on more abstract grounds instead of in the naive way using setbuilder notation. The most widely-accepted approach is via Zermelo-Fraenkel set theory, which unfortunately is complicated and not very natural.   Many other approaches to defining sets have been developed (my preferred one is via topos theory) but they are not widely known.  Most mathematicians have at least heard of the Zermelo-Fraenkel axioms, but I’ll bet the majority of them could not quote all the axioms! 

Then a miracle occurs…

Luckily, for most practitioners of mathematics, this difficulty with the setbuilder notation is rarely a problem. In most applications, the notation "  ” has x varying over a specific type whose instances (unlike the type "set") are already known to constitute a set (for example,  x is real - the real numbers form a set). In that case, any meaningful assertion defines a set  of elements of that type.  In fact, that statement is one of the Zermelo-Fraenkel axioms.

Something else not to worry about…

Sets which are elements of themselves rarely come up in mathematical practice!  In fact many approaches to set theory forbid them.