Russell's paradox is the most famous of the logical or set-theoretical paradoxes. The paradox arises within naive set theory by considering the set of all sets that
are not members of themselves. Such a set appears to be a member of itself if and only if it is not a member of itself, hence the paradox.

Some sets, such as the set of all teacups, are not members of themselves. Other sets, such as the set of all non-teacups, are members of themselves. Call the set
of all sets that are not members of themselves "R." If R is a member of itself, then by definition it must not be a member of itself. Similarly, if R is not a
member of itself, then by definition it must be a member of itself. Discovered by Bertrand Russell in 1901, the paradox has prompted much work in logic, set
theory and the philosophy and foundations of mathematics.

History of the paradox

Russell appears to have discovered his paradox in the late spring of 1901, while working on his Principles of Mathematics (1903). Cesare Burali-Forti, an
assistant to Giuseppe Peano, had discovered a similar antinomy in 1897 when he noticed that since the set of ordinals is well-ordered, it too must have an
ordinal. However, this ordinal must be both an element of the set of all ordinals and yet greater than every such element. Unlike Burali-Forti's paradox,
Russell's paradox does not involve either ordinals or cardinals, relying instead only on the primitive notion of set.

Russell wrote to Gottlob Frege with news of his paradox on June 16, 1902. The paradox was of significance to Frege's logical work since, in effect, it showed
that the axioms Frege was using to formalize his logic were inconsistent. Specifically, Frege's Rule V, which states that two sets are equal if and only if their
corresponding functions coincide in values for all possible arguments, requires that an expression such as f(x) be considered both a function of the argument x
and a function of the argument f. In effect, it was this ambiguity that allowed Russell to construct R in such a way that it could both be and not be a member of
itself.

Russell's letter arrived just as the second volume of Frege's Grundgesetze der Arithmetik (The Basic Laws of Arithmetic, 1893, 1903) was in press.
Immediately appreciating the difficulty the paradox posed, Frege added to the Grundgesetze a hastily composed appendix discussing Russell's discovery. In the
appendix Frege observes that the consequences of Russell's paradox are not immediately clear. For example, "Is it always permissible to speak of the extension
of a concept, of a class? And if not, how do we recognize the exceptional cases? Can we always infer from the extension of one concept's coinciding with that of
a second, that every object which falls under the first concept also falls under the second? These are the questions," Frege notes, "raised by Mr Russell's
communication." Because of these worries, Frege eventually felt forced to abandon many of his views about logic and mathematics.

Of course, Russell also was concerned about the contradiction. Upon learning that Frege agreed with him about the significance of the result, he immediately
began writing an appendix for his own soon-to-be-released Principles of Mathematics. Entitled "Appendix B: The Doctrine of Types," the appendix represents
Russell's first detailed attempt at providing a principled method for avoiding what was soon to become known as "Russell's paradox."

The Russell Paradox on the Web

         Considering the great amount of interest in the web, I think it is easier to introduce the reflexive paradox in the context of the internet than in the
         abstract realm of set theory.

         Webmasters can appreciate the Russell Paradox. As everyone knows, the web is about links. Any page worth its salt has links to other pages.
         Some pages (like my little Grand Junction Links Page) have nothing but links.

         A web crawler is a program that crawls through pages on a web site. The typical web crawler reads a web page, then follows each of the links one
         that page.

         Web crawlers have to worry about infinite loops. The simplest infinite loop happens when a page contains a link back to itself. For example, this
         page has the name russ.html. I made the name hot. The page links back on itself. It is "self-referential."

         A web crawler needs to watch out for self-referential pages; Otherwise, it would fall into an infinite loop. If the bot was not programmed to handle
         recursive links, the bot would read a page, then follow the link back to the page, and read it again... To avoid infinite loops, the web crawler
         needs to maintain a database of all the places it has visited.

         Now, we get into the problem that caused Bertrand Russell such angst a century ago:

         It is possible that a programmer is interested in displaying the self-referencing and non-self-referencing web pages on a web page. It's a fiendish
         trick. The web master simply instructs the web crawler to displays its results on a page. In our case, I instruct the unsuspecting bot to display the
         self-referencing pages on the page sr.html, and the non-self-referencing pages on nsr.html.

         The Russell paradox occurs when the web crawler tries to crawl the sr.html and nsr.html pages. The first time the crawler reads nsr.html, it
         won't find a link back to itself. It marks the page as non-self-referential, automatically adding it to nsr.html. The page is now self-referential. The
         unhappy bot notices this. It corrects the mistake and marks the page as self-referential, automatically removing it from the nsr.html page.

         The evil web programmer has created an insolvable paradox for the web crawler. A web page filled with links to non-self-referential pages is not
         stable. Each time the bot looks at the page, it reclassifies the page.

         The web page with links to self-referential pages (sr.html) is stable, but can go either way. If sr.html did not have a link to itself, the bot would
         conclude that it is non-self-referential and leave it off the sr.html page. If sr.html had a link to itself, the bot would see the self-reference and
         leave the page unchanged.

         The paradox of the Barber of Seville does a great job showing this problem. The barber in Seville boasts of having a monopoly. He boasts that
         everyone in Seville either has their hair cut by him, or they cut their own hair. The barber's sentence implies an exclusive or. A person either
         belongs to the set of people who cut their own hair, or whose hair is cut by the barber of Seville. Well, asks the humble logician, what about the
         barber himself? He belongs to both sets.