Source : Free On-Line Dictionary of Computing

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)