OnlineWoerterBuecher.de - Lexikon, Free On-line Dictionary of Computing



	OnlineWoerterBuecher.de

Navigation

Start

Deutsch-Englisch

Deutsch-Spanisch

Enzyklopädie

Internes

Impressum

Kontakt

Lexikon

Russell' s Paradox

A logical contradiction in ref="module.php?name=Lexikon&file=search&eid=1&query=set theory">set theory discovered by ref="module.php?name=Lexikon&file=search&eid=1&query=Bertrand Russell">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 ref="module.php?name=Lexikon&file=search&eid=1&query=axiom">axiom: If P(x) is a property then ref="module.php?name=Lexikon&file=search&eid=1&query=x : P">x : P is a set. This is the ref="module.php?name=Lexikon&file=search&eid=1&query=Axiom of Comprehension">Axiom of Comprehension (actually an ref="module.php?name=Lexikon&file=search&eid=1&query=axiom schema">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 ref="module.php?name=Lexikon&file=search&eid=1&query=lambda-calculus">lambda-calculus Russell' s Paradox can be formulated by representing each set by its ref="module.php?name=Lexikon&file=search&eid=1&query=characteristic function">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 ref="module.php?name=Lexikon&file=search&eid=1&query=set theory">set theory suggest the existence of the paradoxical set R. ref="module.php?name=Lexikon&file=search&eid=1&query=Zermelo FrÃ¤nkel set theory">Zermelo FrÃ¤nkel set theory is one "solution" to this paradox. Another, ref="module.php?name=Lexikon&file=search&eid=1&query=type theory">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 ref="module.php?name=Lexikon&file=search&eid=1&query=Frege">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)

[ Go Back ]

Free On-line Dictionary of Computing

	All logos and trademarks in this site are property of their respective owner. Page Generation in 0.1031 Seconds, with 16 Database-Queries