Search in: Word
Vietnamese keyboard: Off
Virtual keyboard: Show
Computing (FOLDOC) dictionary
mathematics 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
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