Russell's paradox

The set of all and only those sets that are not members of themselves.

If it's a member of itself, then by definition it is not a member of itself. But if it is not a member of itself, then by definition it is.

Bertrand Russell's formulation of this paradox pointed out the inconsistency in Gottlob Frege's attempt to formalize set theory.

Set Theorists get around this paradox by making a distinction between sets and classes.

The class of sets that do not contain themselves as elements is not represented by a set. (Neither is the class of sets that do contain themselves, for that matter).

In certain axiom systems, a set cannot be a member of itself; in these systems the class of sets that do not contain themselves is equal to the class of all sets (which isn't represented by a set either).

This may sound like circular logic or defining the problem out of existence with empty sophistry. It's not. If you don't understand why not, believe me for now and I hope to eventually node enough to make it clear.

Gödel's second theorem is something of an extension of Russell's paradox. Russell's paradox is a "hole" in his set theory. Gödel did not prove that Russell-Whitehead set theory (or, more accurately, Zermelo-Fraenkel set theory, which is the standardly-used formulation) is inconsistent. His work shows that it is incomplete.

The difference is that an inconsistent system can prove a contradiction: it can both prove a propostion and its negation! Such a system is most likely useless. An incomplete system is unable to prove some true proposition. This parallels the situation we all remember from math class: we know something is true, but are unable to prove it. However, unlike there, in this case our inability to prove a true statement is inherent in the set of axioms we use, and is not due to our necessarily limited talent.

---

Technical notes:

1. Gödel's theorem actually applies to any "sufficiently advanced" system. However, even the full power of arithmetic is way more than is required for the theorem to apply; set theory is certainly sufficiently advanced.
2. In fact, the theorem proves that if the system is consistent then it is incomplete. That is, there is some proposition P such that either both P and not-P are provable, or neither is!
3. Worse yet, a "sufficiently advanced" system which can prove its own consistency is inconsistent...

Let R be the set of all sets which are not members of themselves. Then R is neither a member of itself, nor not a member of itself.

This can be expressed symbolically as:
R = { x : x is not a member of^* x }
This leads to R is a member of R iff not R is a member of R.

This paradox was discovered just as Gottlob Frege was completing his work Grundlagen der Arithmetik and invaildated much if it. Frege added a note at the end:

A scientist can hardly meet with anything more undesirable than to have the foundation give way just as the work is finished. I was put in this position by a letter from Mr. Bertrand Russell when the work was nearly through the press.

^*: I can't get that neat 'e' like character from set notation. ∈ shows up as ∈ and ∈ shows up as ? - oh well.

The best English version of this paradox can be thought of as:

The US Library of Congress requested all the libraries in the United States to index all the books they had and send this index back to the Library of Congress.

Some libraries included the index in the list of books, others did not.

A librarian at the Library of Congress was then instructed to make an index of all the indexes that included themselves in the list of books at that library, and an index of all the index that do not include themselves in the list of books at that library.

The first index (all indexes that include themselves) posed no problem, and the index was included in itself.

Upon composing the second index, however, the librarian had a problem. If he fails to include the index itself in the index, then the index is not complete - for it fails to be an index of all indexes that do not include themselves. On the other hand, if it is included, it is no longer an index that does not include itself, and thus should not be included in itself.

The Barber's paradox is slightly different from Russell's paradox. The Russell's paradox pointed to a problem in the definition of a set. The barber's paradox has its roots in the fact that the barber is "ill defined".

This is a subtle issue but the fact is that when you say that the "barber shaves all those people who dont shave hemselves" the statement is contradictory. So this is a problem of semantics and not equivalent to the Russel's paradox. You have simply not defined the barber properly.