Russell's Paradox
Let X and Y be sets. Define Y = {X | X Ï X}, then Y Î Y if and only if Y Ï Y.
Let's illustrate the above statement with a discrete example. Let's say a doctor claims that he/she only treats all the people who do not treat themselves. A patient walks into this doctor's office seeking treatment does not contradict the doctor's claim. The patient does not treat himself and the doctor treats the patient, perfect. However, if the doctor is sick, who is going to treat him? If he treats himself, then he does not belong to the group "who do not treat themselves" and therefore he should not treat himself. However, if he goes to another doctor, then he belongs to the group "who do not treat themselves" and therefore he should treat himself. Whatever this doctor does, for sure he contradicts himself.
This famous paradox was discovered by Bertrand Russell in 1902. This is probably one of the more dramatic story in the history of logic.
As we know, our language is finite. The problem is that if we try to define everything, eventually we will run out of words and at the end we have a circular definition. For instance, the Random House Dictionary defines "left" as "...the side of a person...toward the west when the subject is facing north". If you look up "west", it is defined as "the direction to left of a person facing north". If someone does not know what "left" and "west" are at the beginning, after looking up the dictionary, he still does not know what they are. In mathematical logic, circular argument is not acceptable. This problem can be avoided if we use a axiomatic approach. That is to say, we accept certain undefined objects as our basis and then build a whole system based on these objects. Euclid had used this approach 2,500 years ago in his Elements. He assumed everyone knows what a point is and what a straight line (We still cannot define a point and a straight line today!) is and then he built the whole branch of mathematics called geometry. At the end of the 19th century, the trend in mathematics was toward building mathematical systems based on axioms, especially axiomatic set theory.
It was at this setting that Gottlob Frege, a famous German logician, finished his The Fundamentals of Arithmetic. He thought he had developed a axiomatic system to set theory (He attempted to define what a set is.) and therefore would serve as the foundation of all mathematics. He sent a copy of his book to the famous logician Bertrand Russell in England. When the book was about to print, Frege received a letter from Russell stating that his definition of sets gave rise to what we now called the Russell's paradox. Frege's definition allowed the formation of the set of all sets not members of themselves. What followed next you can imagine. The book falls apart since the basic building block is flawed. Frege added an appendix to his book. "A scientist can hardly encounter anything more undesirable than to have the foundation collapse just as the work is finished". The word "undesirable" in Frege's appendix has been said to be the greatest understatement in the mathematical history.
We can find many variations of Russell's paradox. Grelling's paradox involves dividing all adjectives into two sets: self-descriptive and non-self-descriptive. Words like "English", "written" and "short" are self-descriptive while "Russian", "spoken" and "long" are non-self-descriptive. Now which set does "non-self-descriptive" belong to? Berry's paradox concerns with "the smallest integer that cannot be expressed in less than thirteen words". Where does this integer that Berry described belong to? The set of integers that can be expressed in less than thirteen words or the set of integers that can be expressed with thirteen words or more? And I came up with my own: "The king was such an evil person that what he did was inhumane." Here I use the word "inhumane" in its strict sense, that is "things not pertaining to the human race".
Such is the problem when we try to define something with a finite language. Russell himself used "theory of types" to eliminate his paradox. He arranges sets in a hierarchy of types so that a set cannot be a member of itself. The Polish mathematician, Alfred Tarski suggested the use of a metalanguage. Again, the metalanguage is arranged in a hierarchy manner. At the very bottom are statements about objects such as "Snow is white." Words like "true" or "false" cannot appear at this level. To speak about the truth value about "Snow is white" involves the next level. We have to use "The statement 'Snow is white' is true." Under this system, the doctor's claim is not allowed and therefore the paradox avoided. Using induction, we can see the metalanguage is infinite because there is always a next level to talk about the truth value of the previous one.