catflap.org Online Dictionary Query

  Russell's Paradox
       
           A logical contradiction in set theory
          discovered by Bertrand Russell.  If R is the set of all sets
          which don't contain themselves, does R contain itself?  If it
          does then it doesn't and vice versa.
       
          The paradox stems from the acceptance of the following
          axiom: If P(x) is a property then
       
          	x : P
       
          is a set.  This is the Axiom of Comprehension (actually an
          axiom schema).  By applying it in the case where P is the
          property "x is not an element of x", we generate the paradox,
          i.e. something clearly false.  Thus any theory built on this
          axiom must be inconsistent.
       
          In lambda-calculus Russell's Paradox can be formulated by
          representing each set by its characteristic function - the
          property which is true for members and false for non-members.
          The set R becomes a function r which is the negation of its
          argument applied to itself:
       
          	r = \ x . not (x x)
       
          If we now apply r to itself,
       
          	r r = (\ x . not (x x)) (\ x . not (x x))
          	    = not ((\ x . not (x x))(\ x . not (x x)))
          	    = not (r r)
       
          So if (r r) is true then it is false and vice versa.
       
          An alternative formulation is: "if the barber of Seville is a
          man who shaves all men in Seville who don't shave themselves,
          and only those men, who shaves the barber?"  This can be taken
          simply as a proof that no such barber can exist whereas
          seemingly obvious axioms of set theory suggest the existence
          of the paradoxical set R.
       
          Zermelo Frankel set theory is one "solution" to this
          paradox.  Another, type theory, restricts sets to contain
          only elements of a single type, (e.g. integers or sets of
          integers) and no type is allowed to refer to itself so no set
          can contain itself.
       
          A message from Russell induced Frege to put a note in his
          life's work, just before it went to press, to the effect that
          he now knew it was inconsistent but he hoped it would be
          useful anyway.
       
          (2000-11-01)
       
       

  Russell's paradox /ɹˈʌsəl ˈɛs pˈaɹədˌɒks/ 
  Russellin paradoksi
  paradox in set theory