Back
  
     

Russell's Paradox

Easy to state, yet difficult or impossible to resolve; self contradictory statements or paradoxes have presented a major challenge to Mathematics and Logic.

Russell's Paradox can be put into everyday language in many ways. The most often repeated is the 'Barber Question.' It goes like this:

In a small town there is only one barber. This man is defined to be the one who shaves all the men who do not shave themselves. The question is then asked,

'Who shaves the barber?'

If the barber doesn't shave himself, then -- by definition -- he does. And, if the barber does shave himself, then -- by definition -- he does not.

Another popular form of Russell's Paradox is the following:
Consider the statement

'This statement is false.'

If the statement is false, then it is true; and if the statement is true, then it is false.

Let's look at this situation as mathematicians do.

You may have noticed the remarkable similarity between logical symbols (like for 'and'; for 'or'; and ~ for 'not') and the symbols used with sets. For example, compare

LogicSet Theory
p qP Q
p qP Q
~pP'

In logic a statement that has a single variable, like

      c(x) = (x is the largest city in Canada)
      b(x) = (x is bigger than 5)

is called a unary predicate. These unary predicates are used to build sets.

Set Formation. For a unary predicate, like

      p(x) = (x is female)
      q(x) = (x is a student at Vanier)

we form a set of all the x's that make the predicate true.
      P = { x | x is female }
      Q = { x | x is a student at Vanier }

Operations on Sets. Set operations are usually defined using logical symbols. For example

      P Q = { x | p(x) q(x)}
      P Q = { x | p(x) q(x)}
      P' = { x | ~p(x) }

We see that set union, intersection, and complement are made up directly from the logical symbols for or, and, and not.

It has been recognized for a long time that the correspondence between logical and set symbols is not one-to-one. For example

      p(x) = (x is an adult human of the female sex)
      q(x) = (x is a woman)

are not the same predicates, but they do give rise to the same sets. But, prior to the discovery of Russell's Paradox, just before the turn of the Twentieth Century, it was thought that any predicate gave rise to a set. Unfortunately -- this also is not the case.

Let's notice first that most ordinary sets do not contain themselves as elements. For example, if


A = {a, b, c}

we have a A and A A, but not A A.

Russell's Paradox. Let S = { x | x is a set}. Notice that not only is S S, but also S S, since S is a set. Next, consider the set


R = { x | (x is a set) (x x)}

S = The set of all sets

We have seen that some sets contain themselves as elements, like the set S; while others, like the set A, do not. We collect together all of the sets that do not contain themselves as elements and call this set R. So the set R shown here is just the set of all sets that do not contain themselves as an element.

Question: Does R contain itself as an element?

Look closely! Each answer leads to the opposite conclusion.

First: Assume that R R, then by definition R R

Second: Assume that R R, then by definition R R

To find a way out of this predicament most mathematicians have chosen to outlaw the formation of sets from just any unary predicate. Although there is not total agreement as to the precise rules for set formation, sets that contain themselves as elements, like S, are definitely ruled out.

This has one major consequence: There can be no truly Universal Set; we must be satisfied with an arbitrary Domain of Discourse D which, although large, is still limited. Whereas we can perform set operations on the elements of D, we cannot treat D itself as a set.

The study of the Foundations of Mathematics, as constructed during this century, has largely been concerned with trying to make sure that no paradoxes or self contradictions get into Mathematics at the lowest levels. But, can we be certain that there are no, as yet, undiscovered contradictions in Mathematics or Logic?

     

Go to the top of this page