# Russell's Paradox

(redirected from*List of lists that do not contain themselves*)

Also found in: Dictionary.

Related to List of lists that do not contain themselves: Bertrand Russell Paradox, Russell set

## Russell's paradox

[′rəs·əlz ′par·ə‚däks] (mathematics)

The paradox concerning the concept of all sets which are not members of themselves which forces distinctions in set theory between sets and classes.

McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.

## Russell's Paradox

(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

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 Fr?nkel 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.

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 Fr?nkel 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.

This article is provided by FOLDOC - Free Online Dictionary of Computing (

**foldoc.org**)Want to thank TFD for its existence? Tell a friend about us, add a link to this page, or visit the webmaster's page for free fun content.

Link to this page: