Russell's Paradox

 

Poincaré disliked Peano's work on a formal language for mathematics, then called "logistic." He wrote of Russell's paradox, with evident satisfaction, "Logistic has finally proved that it is not sterile. At last it has given birth - to a contradiction."

from R.Hersh, What is Mathematics, Really?
Oxford University Press, 1997

Sets are defined by the unique properties of their elements. One may not mention sets and elements simultaneously, but one notion has no meaning without other. The widely used Peano's notation

A = {x: x has property P}

incorporates all the pertinent attributes: a set A, a property P, elements x. But, of course, one does not always use the formal notations. For example, it's quite acceptable to talk of the set of all students at the East Brunswick High or the set of fingers I use to type this sentence. The space being limited, some sets are described on this page and some are not. Let's call russell the set of all sets described on this page. Just driving the point in: russell's elements are sets described on this page. Note that this page is where you met russell. For it's where it was defined after all. So russell has an interesting property of being its own element: russell∈russell.

With the example of russell it's apparent that some sets contain themselves as elements while others do not. Let RUSSELL stand for the set of all sets that are not their own elements. What may be said about RUSSELL? Which is it?

Assuming RUSSELL∈RUSSELL leads to a contradiction for, by definition, RUSSELL does not contain itself. Assuming RUSSELL∉RUSSELL implies that RUSSELL satisfies the definition and, hence, RUSSELL∈RUSSELL. Impossibility.

That RUSSELL is such a set that neither RUSSELL∈RUSSELL nor RUSSELL∉RUSSELL has been discovered by Bertrand Russell (1872-1970) in 1901. This is how he described the event in his Autobiography:

At the end of the Lent Term, Alys and I went back to Femhurst, where I set to work to write out the logical deduction of mathematics which afterwards became Principia Mathematica. I thought the work was nearly finished, but in the month of May I had an intellectual set-back almost as severe as the emotional set-back which I had had in February. Cantor had a proof that there is no greatest number, and it seemed to me that the number of all the things in the world ought to be the greatest possible. Accordingly, I examined his proof with some minuteness, and endeavoured to apply it to the class of all the things there are. This led me to consider those classes which are not members of themselves, and to ask whether the class of such classes is or is not a member of itself. I found that either answer implies its contradictory. At first I supposed that I should be able to overcome the contradiction quite easily, and that probably there was some trivial error in the reasoning. Gradually, however, it became clear that this was not the case. Burali-Forti had already discovered a similar contradiction, and it turned out on logical analysis that there was an affinity with the ancient Greek contradiction about Epimenides the Cretan, who said that all Cretans are liars. A contradiction essentially similar to that of Epimenides can be created by giving a person a piece of paper on which is written: 'The statement on the other side of this paper is false.' The person turns the paper over, and finds on the other side: 'The statement on the other side of this paper is true.' It seemed unworthy of a grown man to spend his time on such trivialities, but what was I to do? There was something wrong, since such contradictions were unavoidable on ordinary premises. Trivial or not, the matter was a challenge. Throughout the latter half of 1901 I supposed the solution would be easy, but by the end of that time I had concluded that it was a big job. I therefore decided to finish The Principles of Mathematics, leaving the solution in abeyance. In the autumn Alys and I went back to Cambridge, as I had been invited to give two terms' lectures on mathematical logic. These lectures contained the outline of Principia Mathematica, but without any method of dealing with the contradictions.

Principia Mathematica is the book Russell wrote with Alfred North Whitehead where they gave a logical foundation of Mathematics by developing the Theory of Types that obviated the Russell's paradox. This assertion may become more convincing after a look at the page 362 of Principia Mathematica where Russell and Whitehead finally proved that 1 + 1 = 2.

There are a few more things that should be mentioned in this context. I'll leave the discussion for now. There might be a chance I'd return to this page after settling the question whether or not RUSSELL∈russell. (Of course, russell∉RUSSELL.) Meanwhile you may ponder a question concerning the set RuSSeLL of all sets not described on this page. Is it true that RuSSeLL∈russell?

It may not be quite obvious but Russell's Paradox is just a variant of the diagonal argument.

Reference

  1. W. Dunham, The Mathematical Universe, John Wiley & Sons, NY, 1994.
  2. M. Gardner, aha! Gotcha. Paradoxes to puzzle and delight, Freeman & Co, NY, 1982
  3. D. R. Hofstadter, Metamagical Themas, Basic Books, Inc., 1985, Chapter 16.
  4. J. A. Paulos, Beyond Numeracy, Vintage Books, 1992
  5. Rudy Rucker, Infinity and the Mind, Princeton University Press, Princeton, NJ, 1955

Self-reference and apparent self-reference

  1. Does It Blink?
  2. Apparent paradox
  3. Set of all subsets
  4. An Impossible Page
  5. Russell's paradox
  6. An Impossible Machine
  7. A theorem with an obvious proof
  8. The Diagonal Argument
  9. A link to a very similar puzzle

|Front page| |Contents| |Algebra| |Up|

Copyright © 1996-2018 Alexander Bogomolny

71471431