Difference between revisions of "Russell's paradox" - New World Encyclopedia

From New World Encyclopedia
Line 8: Line 8:
 
: <math>R=\{A\mid A\not\in A\}.</math>
 
: <math>R=\{A\mid A\not\in A\}.</math>
  
Since it is assumed in Frege's ''Grundgesetze der Arithmetik'' that sets can be freely defined by any condition''R'' would be a well-defined set. The problem arises when it is considered whether ''R'' is an [[Element (mathematics)|element]] of itself. If ''R'' is an element of ''R'', then according to the definition ''R'' is not an element of ''R''; if ''R'' is not an element of ''R'', then ''R'' has to be an element of ''R'', again by its very definition: hence a contradiction.
+
Assume, as in Frege's ''Grundgesetze der Arithmetik'', that sets can be freely defined by any condition. Then ''R'' is a well-defined set. The problem arises when it is considered whether ''R'' is an element of itself. If ''R'' is an element of ''R'', then according to the definition ''R'' is not an element of ''R''; if ''R'' is not an element of ''R'', then ''R'' has to be an element of ''R'', again by its very definition: hence a contradiction.
  
 
Russell's paradox was a primary motivation for the development of set theories with a more elaborate axiomatic basis than simple extensionality and unlimited set abstraction. The paradox drove Russell to develop type theory and [[Ernst Zermelo]] to develop an [[axiom|axiomatic]] set theory which evolved into the now-canonical Zermelo–Fraenkel set theory.
 
Russell's paradox was a primary motivation for the development of set theories with a more elaborate axiomatic basis than simple extensionality and unlimited set abstraction. The paradox drove Russell to develop type theory and [[Ernst Zermelo]] to develop an [[axiom|axiomatic]] set theory which evolved into the now-canonical Zermelo–Fraenkel set theory.
Line 14: Line 14:
 
==Russell's Paradox==
 
==Russell's Paradox==
 
===Informal Presentation===
 
===Informal Presentation===
Informally, Russell's paradox may be explained in the following way. Let us call a set "normal" if it does not contain itself as a member. For example, take the set of all squares. That set is not itself a square, and therefore is not a member of the set of all squares. So it is "normal." On the other hand, if we take the complementary set of all non-squares, that set is itself not a square and so should be one of its own members. It is "abnormal."
+
An informal explanation of Russell's paradox may be given in the following way. Let us call a set "normal" if it does not contain itself as a member. For example, take the set of all squares. That set is not itself a square, and therefore is not a member of the set of all squares. So it is "normal." On the other hand, if we take the complementary set of all non-squares, that set is itself not a square and so should be one of its own members. It is "abnormal."
  
 
Now we consider the set of all normal sets − let us give it a name: ''R'' – and ask the question: is ''R'' a "normal" set? If it is "normal," then it is a member of ''R'', since ''R'' contains all "normal" sets. But if that is the case, then ''R'' contains itself as a member, and therefore is "abnormal." On the other hand, if ''R'' is "abnormal," then it is not a member of ''R'', since ''R'' contains only "normal" sets. But if that is the case, then ''R'' does not contains itself as a member, and therefore is "normal." Clearly, this is a paradox: if we suppose ''R'' is "normal" we can prove it is "abnormal," and if we suppose ''R'' is "abnormal" we can prove it is "normal." Hence, ''R'' is neither "normal" nor "abnormal," which is a contradiction.
 
Now we consider the set of all normal sets − let us give it a name: ''R'' – and ask the question: is ''R'' a "normal" set? If it is "normal," then it is a member of ''R'', since ''R'' contains all "normal" sets. But if that is the case, then ''R'' contains itself as a member, and therefore is "abnormal." On the other hand, if ''R'' is "abnormal," then it is not a member of ''R'', since ''R'' contains only "normal" sets. But if that is the case, then ''R'' does not contains itself as a member, and therefore is "normal." Clearly, this is a paradox: if we suppose ''R'' is "normal" we can prove it is "abnormal," and if we suppose ''R'' is "abnormal" we can prove it is "normal." Hence, ''R'' is neither "normal" nor "abnormal," which is a contradiction.
Line 25: Line 25:
 
Theorem. Defining a set <math>R\,\!</math> by <math>R=\{x : x \notin x\}\,\!</math> is contradictory.
 
Theorem. Defining a set <math>R\,\!</math> by <math>R=\{x : x \notin x\}\,\!</math> is contradictory.
  
''Proof''. Replace <math>\Phi(x)\,\!</math> in the definition of collection with <math>x \notin x\,\!</math> and obtain for <math>R\,\!</math> as defined: <math>\forall x\,[x \in R \leftrightarrow x \notin x]\,\!</math>. [[Universal instantiation|Instantiating]] <math>x\,\!</math> by <math>R\,\!</math> now yields the contradiction <math>R \in R \leftrightarrow R \notin R. \ \square\,\!</math>
+
''Proof''. Replace <math>\Phi(x)\,\!</math> in the definition of collection with <math>x \notin x\,\!</math> and obtain for <math>R\,\!</math> as defined: <math>\forall x\,[x \in R \leftrightarrow x \notin x]\,\!</math>. Instantiating <math>x\,\!</math> by <math>R\,\!</math> now yields the contradiction <math>R \in R \leftrightarrow R \notin R. \ \square\,\!</math>
  
 
===Remark===
 
===Remark===
 
====Reciprocation====
 
====Reciprocation====
Remark. The force of this argument cannot be evaded by simply deeming <math>x \notin x\,\!</math> an invalid substitution for <math>\Phi(x)\,\!</math>. In fact, there are denumerably many formulae <math>\Phi(x)\,\!</math> giving rise to the paradox.<ref>See Quine, 1938. Incidentally, this theorem and the definition of collection it builds on, are Potter's first theorem and definition, respectively.</ref>
+
The force of this argument cannot be evaded by simply deeming <math>x \notin x\,\!</math> an invalid substitution for <math>\Phi(x)\,\!</math>. In fact, there are denumerably many formulae <math>\Phi(x)\,\!</math> giving rise to the paradox.<ref>See Quine 1938. Incidentally, this theorem and teh definition of collection it builds on, are Potter's first theorem and definition, respectively.</ref>
 
 
 
 
Russell's paradox arises from the supposition that one can meaningfully define a class in terms of any well-defined property <math>\Phi(x)</math>; that is, that we can form the set <math>P = \{ x | \Phi(x) \mbox{ is true } \}</math>. When we take <math>\Phi(x) = x\not\in x</math>, we get Russell's paradox. This is only the simplest of many possible variations of this theme.
 
  
 
For example, if one takes <math>\Phi(x) = \neg(\exists z: x\in z\wedge z\in x)</math>, one gets a similar paradox; there is no set <math>P</math> of all <math>x</math> with this property.  For convenience, let us agree to call a set <math>S</math> ''reciprocated'' if there is a set <math>T</math> with <math>S\in T\wedge T\in S</math>; then <math>P</math>, the set of all non-reciprocated sets, does not exist. If <math>P\in P</math>, we would immediately have a contradiction, since <math>P</math> is reciprocated (by itself) and so should not belong to <math>P</math>. But if <math>P\not\in P</math>, then <math>P</math> is reciprocated by some set <math>Q</math>, so that we have <math>P\in Q\wedge Q\in P</math>, and then <math>Q</math> is also a reciprocated  set, and so <math>Q\not\in P</math>, another contradiction.
 
For example, if one takes <math>\Phi(x) = \neg(\exists z: x\in z\wedge z\in x)</math>, one gets a similar paradox; there is no set <math>P</math> of all <math>x</math> with this property.  For convenience, let us agree to call a set <math>S</math> ''reciprocated'' if there is a set <math>T</math> with <math>S\in T\wedge T\in S</math>; then <math>P</math>, the set of all non-reciprocated sets, does not exist. If <math>P\in P</math>, we would immediately have a contradiction, since <math>P</math> is reciprocated (by itself) and so should not belong to <math>P</math>. But if <math>P\not\in P</math>, then <math>P</math> is reciprocated by some set <math>Q</math>, so that we have <math>P\in Q\wedge Q\in P</math>, and then <math>Q</math> is also a reciprocated  set, and so <math>Q\not\in P</math>, another contradiction.
 
Any of the variations of Russell's paradox described above can be reformulated to use this new paradoxical property. For example, the reformulation of the Grelling paradox is as follows. Let us agree to call an adjective <math>P</math> "nonreciprocated" if and only if there is no adjective <math>Q</math> such that both <math>P</math> describes <math>Q</math> and <math>Q</math> describes <math>P</math>. Then one obtains a paradox when one asks if the adjective "nonreciprocated" is itself nonreciprocated.
 
  
 
This can also be extended to longer chains of mutual inclusion. We may call sets <math>A_1,A_2,...,A_n</math> a chain of set <math>A_1 </math> if <math>A_{i+1} \in A_i</math> for ''i''=1,2,...,''n''-1. A chain can be infinite (in which case each <math>A_i</math> has an infinite chain). Then we take the set ''P'' of all sets which have no infinite chain, from which it follows that ''P'' itself has no infinite chain. But then <math>P \in P</math>, so in fact ''P'' has the infinite chain ''P'',''P'',''P'',... which is a contradiction. This is known as Mirimanoff's paradox.
 
This can also be extended to longer chains of mutual inclusion. We may call sets <math>A_1,A_2,...,A_n</math> a chain of set <math>A_1 </math> if <math>A_{i+1} \in A_i</math> for ''i''=1,2,...,''n''-1. A chain can be infinite (in which case each <math>A_i</math> has an infinite chain). Then we take the set ''P'' of all sets which have no infinite chain, from which it follows that ''P'' itself has no infinite chain. But then <math>P \in P</math>, so in fact ''P'' has the infinite chain ''P'',''P'',''P'',... which is a contradiction. This is known as Mirimanoff's paradox.
  
====Independence from [[excluded middle]]====
+
====Independence from excluded middle====
Often, as is done above, the set <math>R=\{A\mid A\not\in A\}</math> is shown to lead to contradiction based upon the [[law of excluded middle]], by showing that absurdity follows from assuming <math>P</math> true and from assuming it false. Thus, it may be tempting to think that the paradox is avoidable by avoiding the law of excluded middle, as with [[intuitionistic logic]]. However, the paradox still occurs using the [[law of non-contradiction]]:
+
Often, as is done above, the set <math>R=\{A\mid A\not\in A\}</math> is shown to lead to contradiction based upon the [[law of excluded middle]], by showing that absurdity follows from assuming <math>P</math> true and from assuming it false. Thus, it may be tempting to think that the paradox is avoidable by avoiding the law of excluded middle, as with intuitionistic logic. However, the paradox still occurs using the law of non-contradiction:
  
From the definition of ''R'', we have that ''R''&isin;''R''&nbsp;&harr;&nbsp;&not;(''R''&isin;''R''). Then ''R''&isin;''R''&nbsp;&rarr;&nbsp;&not;(''R''&isin;''R'') ([[biconditional elimination]]). But also ''R''&isin;''R''&nbsp;&rarr;&nbsp;''R''&isin;''R'' (the [[law of identity]]), so ''R''&isin;''R''&nbsp;&rarr;&nbsp;(''R''&isin;''R''&nbsp;&and;&nbsp;&not;(''R''&isin;''R'')). But, the law of non-contradiction tells us &not;(''R''&isin;''R''&nbsp;&and;&nbsp;&not;(''R''&isin;''R'')). Therefore, by [[modus tollens]], we conclude &not;(''R''&isin;''R'').  
+
From the definition of ''R'', we have that ''R''&isin;''R''&nbsp;&harr;&nbsp;&not;(''R''&isin;''R''). Then ''R''&isin;''R''&nbsp;&rarr;&nbsp;&not;(''R''&isin;''R'') (biconditional elimination). But also ''R''&isin;''R''&nbsp;&rarr;&nbsp;''R''&isin;''R'' (the law of identity), so ''R''&isin;''R''&nbsp;&rarr;&nbsp;(''R''&isin;''R''&nbsp;&and;&nbsp;&not;(''R''&isin;''R'')). But, the law of non-contradiction tells us &not;(''R''&isin;''R''&nbsp;&and;&nbsp;&not;(''R''&isin;''R'')). Therefore, by modus tollens, we conclude &not;(''R''&isin;''R'').  
  
But since ''R''&isin;''R''&nbsp;&harr;&nbsp;&not;(''R''&isin;''R''), we also have that &not;(''R''&isin;''R'')&nbsp;&rarr;&nbsp;''R''&isin;''R'', and so we also conclude ''R''&isin;''R'' by [[modus ponens]]. So using only intuitionistically valid methods we can still deduce both ''R''&isin;''R'' and its negation.
+
But since ''R''&isin;''R''&nbsp;&harr;&nbsp;&not;(''R''&isin;''R''), we also have that &not;(''R''&isin;''R'')&nbsp;&rarr;&nbsp;''R''&isin;''R'', and so we also conclude ''R''&isin;''R'' by modus ponens. So using only intuitionistically valid methods we can still deduce both ''R''&isin;''R'' and its negation.
  
 
More simply, it is intuitionistically impossible for a proposition to be equivalent to its negation. Assume ''P''&nbsp;↔&nbsp;¬''P''. Then ''P''&nbsp;&rarr;&nbsp;¬''P''. Hence ¬''P''. Symmetrically, we can derive ¬¬''P'', using ¬''P''&nbsp;&rarr;&nbsp;''P''. So we have inferred both ¬''P'' and its negation from our assumption, with no use of excluded middle.
 
More simply, it is intuitionistically impossible for a proposition to be equivalent to its negation. Assume ''P''&nbsp;↔&nbsp;¬''P''. Then ''P''&nbsp;&rarr;&nbsp;¬''P''. Hence ¬''P''. Symmetrically, we can derive ¬¬''P'', using ¬''P''&nbsp;&rarr;&nbsp;''P''. So we have inferred both ¬''P'' and its negation from our assumption, with no use of excluded middle.
  
 
==History==
 
==History==
Exactly when Russell discovered the paradox is not known. It seems to have been May or June 1901, probably as a result of his work on [[Cantor's theorem]] that the number of entities in a certain domain is smaller than the number of subclasses of those entities.<ref>In modern terminology, the [[cardinality]] of a set is strictly less than that of its [[power set]].</ref> He first mentioned the paradox in a 1901 paper in the ''International Monthly'', entitled "Recent work in the philosophy of mathematics." He also mentioned Cantor's proof that there is no greatest [[cardinal number|cardinal]], adding that "the master" had been guilty of a subtle fallacy that he would discuss later. Russell also mentioned the paradox in his ''Principles of Mathematics'' (not to be confused with the later ''[[Principia Mathematica]]''), calling it "The Contradiction."<ref>{{cite book |last=Russell |first=Bertrand |authorlink=Bertrand Russell |title=Principles of Mathematics |year=1903 |publisher=Cambridge University Press |location=Cambridge |isbn=0-393-31404-9 |pages=Chapter X, section 100}}</ref> Again, he said that he was led to it by analyzing Cantor's "no greatest cardinal" proof.
+
Exactly when Russell discovered the paradox is not known. It seems to have been May or June 1901, probably as a result of his work on Cantor's theorem that the number of entities in a certain domain is smaller than the number of subclasses of those entities.<ref>In modern terminology, the cardinality of a set is strictly less than that of its power set.</ref> He first mentioned the paradox in a 1901 paper in the ''International Monthly'', entitled "Recent work in the philosophy of mathematics." He also mentioned Cantor's proof that there is no greatest cardinal, adding that "the master" had been guilty of a subtle fallacy that he would discuss later. Russell also mentioned the paradox in his ''Principles of Mathematics'' (not to be confused with the later ''Principia Mathematica''), calling it "The Contradiction."<ref>{{cite book |last=Russell |first=Bertrand |authorlink=Bertrand Russell |title=Principles of Mathematics |year=1903 |publisher=Cambridge University Press |location=Cambridge |isbn=0-393-31404-9 |pages=Chapter X, section 100}}</ref> Again, he said that he was led to it by analyzing Cantor's "no greatest cardinal" proof.
  
Famously, Russell wrote to Frege about the paradox in June 1902, just as Frege was preparing the second volume of his ''Grundgesetze der Arithmetik''.<ref>Russell's letter and Frege's reply are translated in [[Jean van Heijenoort]], 1967.)</ref> Frege hurriedly wrote an appendix admitting to the paradox, and proposed a solution that was later proved unsatisfactory. In any event, after publishing the second volume of the ''Grundgesetze'', Frege wrote little on [[mathematical logic]] and the [[philosophy of mathematics]]. <!-- Some revisionist historians have argued against this, can someone supply references —>
+
Famously, Russell wrote to Frege about the paradox in June 1902, just as Frege was preparing the second volume of his ''Grundgesetze der Arithmetik''.<ref>Russell's letter and Frege's reply are translated in Jean van Heijenoort, 1967.)</ref> Frege hurriedly wrote an appendix admitting to the paradox, and proposed a solution that was later proved unsatisfactory. In any event, after publishing the second volume of the ''Grundgesetze'', Frege wrote little on [[mathematical logic]] and the [[philosophy of mathematics]]. <!-- Some revisionist historians have argued against this, can someone supply references —>
  
[[Zermelo]], while working on the [[Zermelo set theory|axiomatic set theory]] he published in 1908, also noticed the paradox but thought it beneath notice, and so never published anything about it. Zermelo's system avoids the paradox thanks to replacing arbitrary set comprehension with weaker existence axioms, such as his [[axiom of separation]] (''Aussonderung'').
+
[[Ernst Zermelo|Zermelo]], while working on the axiomatic set theory he published in 1908, also noticed the paradox but thought it beneath notice, and so never published anything about it. Zermelo's system avoids the paradox thanks to replacing arbitrary set comprehension with weaker existence axioms, such as his axiom of separation (''Aussonderung'').
  
Russell and [[Alfred North Whitehead]] wrote the three volumes of ''Principia Mathematica'' (''PM'') hoping to succeed where Frege had failed. They sought to banish the paradoxes of [[naive set theory]] by employing a [[type theory|theory of types]] they devised for this purpose.  While they succeeded in grounding arithmetic in a fashion, it is not at all evident that they did so by logic alone. In any event, [[Kurt Gödel]] in 1930-31 proved that the logic of much of ''PM'', now known as [[first order logic]], is [[Gödel's completeness theorem|complete]], but that [[Peano arithmetic]] is necessarily [[incomplete]] if it is [[consistent]]. There and then, the [[logicist]] program of Frege-''PM'' died.
+
Russell and Alfred North Whitehead wrote the three volumes of ''Principia Mathematica'' (''PM'') hoping to succeed where Frege had failed. They sought to banish the paradoxes of naive set theory by employing a theory of types they devised for this purpose.  While they succeeded in grounding arithmetic in a fashion, it is not at all evident that they did so by logic alone. In any event, [[Kurt Gödel]] in 1930-31 proved that the logic of much of ''PM'', now known as [[Predicate Calculus|first order logic]], is complete, but that Peano arithmetic is necessarily incomplete if it is consistent. There and then, the logicist program of Frege-''PM'' died.
  
 
==Applied versions==
 
==Applied versions==
There are some versions of this paradox that are closer to real-life situations and may be easier to understand for non-logicians. For example, the [[Barber paradox]] supposes a barber who shaves men if and only if they do not shave themselves. When one thinks about whether the barber should shave himself or not, the paradox begins to emerge.
+
There are some versions of this paradox that are closer to real-life situations and may be easier to understand for non-logicians. For example, the Barber paradox supposes a barber who shaves men if and only if they do not shave themselves. When one thinks about whether the barber should shave himself or not, the paradox begins to emerge.
  
As another example, consider five lists of [[encyclopedia]] entries within the same encyclopedia:
+
As another example, consider five lists of encyclopedia entries within the same encyclopedia:
  
 
{| class="wikitable"
 
{| class="wikitable"
 
|- valign="top"
 
|- valign="top"
 
| width="20%" | List of articles about people:
 
| width="20%" | List of articles about people:
*[[Ptolemy VII of Egypt]]
+
*Ptolemy VII of Egypt
*[[Hermann Hesse]]
+
*Hermann Hesse
*[[Don Nix]]
+
*Don Nix
*[[Don Knotts]]
+
*Don Knotts
*[[Biography of Nikola Tesla]]
+
*Biography of Nikola Tesla
*[[Sherlock Holmes]]
+
*Sherlock Holmes
*[[Emperor Kōnin]]
+
*Emperor Kōnin
 
| width="20%" | List of articles starting with the letter L:
 
| width="20%" | List of articles starting with the letter L:
*[[L]]
+
*L
*[[L!VE TV]]
+
*L!VE TV
*[[L&H]]
+
*L&H
 
...
 
...
 
*List of articles starting with the letter K
 
*List of articles starting with the letter K
Line 83: Line 78:
 
...
 
...
 
| width="20%" | List of articles about places:
 
| width="20%" | List of articles about places:
*[[Leivonmäki]]
+
*Leivonmäki
*[[Katase River]]
+
*Katase River
*[[Enoshima]]
+
*Enoshima
 
| width="20%" | List of articles about Japan:
 
| width="20%" | List of articles about Japan:
*[[Emperor Kōnin]]
+
*Emperor Kōnin
*[[Katase River]]
+
*Katase River
*[[Enoshima]]
+
*Enoshima
 
| width="20%" | List of all lists that do not contain themselves:
 
| width="20%" | List of all lists that do not contain themselves:
 
*List of articles about Japan
 
*List of articles about Japan
Line 103: Line 98:
 
If the "List of all lists that do not contain themselves" contains itself, then it does not belong to itself and should be removed. However, if it does not list itself, then it should be added to itself.
 
If the "List of all lists that do not contain themselves" contains itself, then it does not belong to itself and should be removed. However, if it does not list itself, then it should be added to itself.
  
While appealing, these [[layman]]'s versions of the paradox share a drawback: an easy refutation of the Barber paradox seems to be that such a barber does not exist. The whole point of Russell's paradox is that the answer "such a set does not exist" means the definition of the notion of set within a given theory is unsatisfactory. Note the difference between the statements "such a set does not exist" and "such a set is [[empty set|empty]]."
+
While appealing, these layman's versions of the paradox share a drawback: an easy refutation of the Barber paradox seems to be that such a barber does not exist. The whole point of Russell's paradox is that the answer "such a set does not exist" means the definition of the notion of set within Frege's system is unsatisfactory. This motivated the investigation of axiomatic set theory that does not suffer from the paradox of the kind.
 
 
A notable exception to the above may be the [[Grelling-Nelson paradox]], in which words and meaning are the elements of the scenario rather than people and hair-cutting. Though it is easy to refute the Barber's paradox by saying that such a barber does not (and ''cannot'') exist, it is impossible to say something similar about a meaningfully defined word.
 
  
 
==Set-theoretic responses==
 
==Set-theoretic responses==
Russell, together with [[Alfred North Whitehead]], sought to banish the paradox by developing [[type theory]]. The culmination of this research is the work, ''[[Principia Mathematica]]''. While Principia Mathematica avoided the known paradoxes and allows the derivation of a great deal of mathematics, other challenges to predominant set theory arose.
+
Russell, together with [[Alfred North Whitehead]], sought to banish the paradox by developing type theory. The culmination of this research is the work, ''Principia Mathematica''. While Principia Mathematica avoided the known paradoxes and allows the derivation of a great deal of mathematics, other challenges to predominant set theory arose.
 
 
In 1908, [[Ernst Zermelo]] proposed an [[axiomatic system|axiomatization]] of set theory that avoided Russell's and other related paradoxes. Modifications to this axiomatic theory proposed in the 1920s by [[Abraham Fraenkel]], [[Thoralf Skolem]], and by Zermelo himself resulted in the axiomatic set theory called [[ZFC]]. This theory became widely accepted once Zermelo's [[axiom of choice]] ceased to be controversial, and ZFC has remained the canonical [[axiomatic set theory]] down to the present day. ZFC does not assume that, for every property, there is a set of all things satisfying that property. Rather, it asserts that given any set ''X'', any subset of ''X'' definable using first order logic exists. The object ''R'' discussed above cannot be constructed in this fashion, and is therefore not a ZFC set. In some [[Von Neumann-Bernays-Godel set theory|extensions of ZFC]], objects like ''R'' are called [[proper class]]es. ZFC is silent about types, although some contend that Zermelo's axioms tacitly presupposes a background type theory.
 
 
 
Through the work of Zermelo and others, especially [[John von Neumann]], the structure of what some see as the "natural" objects described by ZFC eventually became clear; they are the elements of the [[von Neumann universe]], ''V'', built up from the [[empty set]] by [[transfinite recursion|transfinitely iterating]] the [[power set]] operation. It is thus now possible again to reason about sets in a non-axiomatic fashion without running afoul of Russell's paradox, namely by reasoning about the elements of ''V''. Whether it is ''appropriate'' to think of sets in this way is a point of contention among the rival points of view on the [[philosophy of mathematics]].
 
  
Other resolutions to Russell's paradox, more in the spirit of [[type theory]], include the axiomatic set theories [[New Foundations]] and [[Scott-Potter set theory]].
+
In 1908, [[Ernst Zermelo]] proposed an [[axiomatic system|axiomatization]] of set theory that avoided Russell's and other related paradoxes. Modifications to this axiomatic theory proposed in the 1920s by Abraham Fraenkel, Thoralf Skolem, and by Zermelo himself resulted in the axiomatic set theory called ZFC. This theory became widely accepted once Zermelo's axiom of choice ceased to be controversial, and ZFC has remained the canonical axiomatic set theory down to the present day. ZFC does not assume that, for every property, there is a set of all things satisfying that property. Rather, it asserts that given any set ''X'', any subset of ''X'' definable using first order logic exists. The object ''R'' discussed above cannot be constructed in this fashion, and is therefore not a ZFC set. In some extensions of ZFC, objects like ''R'' are called proper classes. ZFC is silent about types, although some contend that Zermelo's axioms tacitly presupposes a background type theory.
  
== Other related paradoxes ==
+
Through the work of Zermelo and others, especially John von Neumann, the structure of what some see as the "natural" objects described by ZFC eventually became clear; they are the elements of the von Neumann universe, ''V'', built up from the empty set by transfinitely iterating the power set operation. It is thus now possible again to reason about sets in a non-axiomatic fashion without running afoul of Russell's paradox, namely by reasoning about the elements of ''V''. Whether it is ''appropriate'' to think of sets in this way is a point of contention among the rival points of view on the [[philosophy of mathematics]].
*The [[liar paradox]] and [[Epimenides paradox]], whose origins are ancient.
 
*[[Curry's paradox]] (named after [[Haskell Curry]]) which does not require [[negation]].
 
*The [[Interesting number paradox|smallest uninteresting integer]] paradox.
 
  
== See also ==
+
Other resolutions to Russell's paradox, more in the spirit of type theory, include the axiomatic set theories New Foundations (by Quine) and Scott-Potter set theory.
*[[Self-reference]]
 
  
 
== Footnotes and references==
 
== Footnotes and references==
 
<references />
 
<references />
 
*Potter, Michael, 2004. ''Set Theory and its Philosophy''. Oxford Univ. Press.
 
*Potter, Michael, 2004. ''Set Theory and its Philosophy''. Oxford Univ. Press.
*[[Willard Quine]], 1938, "On the theory of types," ''Journal of Symbolic Logic 3''.
+
*Willard Quine, 1938, "On the theory of types," ''Journal of Symbolic Logic 3''.
  
 
== External links ==
 
== External links ==

Revision as of 06:26, 20 July 2007


Part of the foundation of mathematics, Russell's paradox (also known as Russell's antinomy), discovered by Bertrand Russell in 1901, showed that the naive set theory of Frege leads to a contradiction.

Consider the set R of all sets that do not contain themselves as members. In set-theoretic notation:

Assume, as in Frege's Grundgesetze der Arithmetik, that sets can be freely defined by any condition. Then R is a well-defined set. The problem arises when it is considered whether R is an element of itself. If R is an element of R, then according to the definition R is not an element of R; if R is not an element of R, then R has to be an element of R, again by its very definition: hence a contradiction.

Russell's paradox was a primary motivation for the development of set theories with a more elaborate axiomatic basis than simple extensionality and unlimited set abstraction. The paradox drove Russell to develop type theory and Ernst Zermelo to develop an axiomatic set theory which evolved into the now-canonical Zermelo–Fraenkel set theory.

Russell's Paradox

Informal Presentation

An informal explanation of Russell's paradox may be given in the following way. Let us call a set "normal" if it does not contain itself as a member. For example, take the set of all squares. That set is not itself a square, and therefore is not a member of the set of all squares. So it is "normal." On the other hand, if we take the complementary set of all non-squares, that set is itself not a square and so should be one of its own members. It is "abnormal."

Now we consider the set of all normal sets − let us give it a name: R – and ask the question: is R a "normal" set? If it is "normal," then it is a member of R, since R contains all "normal" sets. But if that is the case, then R contains itself as a member, and therefore is "abnormal." On the other hand, if R is "abnormal," then it is not a member of R, since R contains only "normal" sets. But if that is the case, then R does not contains itself as a member, and therefore is "normal." Clearly, this is a paradox: if we suppose R is "normal" we can prove it is "abnormal," and if we suppose R is "abnormal" we can prove it is "normal." Hence, R is neither "normal" nor "abnormal," which is a contradiction.

Formal Presentation

More formally, the paradox is expressed as follows. The following derivation of the paradox [1] reveals that the paradox requires nothing more than first-order logic with the unrestricted use of set abstraction.

Definition The set , in which is any predicate of first-order logic in which is a free variable, denotes the set satisfying .

Theorem. Defining a set by is contradictory.

Proof. Replace in the definition of collection with and obtain for as defined: . Instantiating by now yields the contradiction

Remark

Reciprocation

The force of this argument cannot be evaded by simply deeming an invalid substitution for . In fact, there are denumerably many formulae giving rise to the paradox.[2]

For example, if one takes , one gets a similar paradox; there is no set of all with this property. For convenience, let us agree to call a set reciprocated if there is a set with ; then , the set of all non-reciprocated sets, does not exist. If , we would immediately have a contradiction, since is reciprocated (by itself) and so should not belong to . But if , then is reciprocated by some set , so that we have , and then is also a reciprocated set, and so , another contradiction.

This can also be extended to longer chains of mutual inclusion. We may call sets a chain of set if for i=1,2,...,n-1. A chain can be infinite (in which case each has an infinite chain). Then we take the set P of all sets which have no infinite chain, from which it follows that P itself has no infinite chain. But then , so in fact P has the infinite chain P,P,P,... which is a contradiction. This is known as Mirimanoff's paradox.

Independence from excluded middle

Often, as is done above, the set is shown to lead to contradiction based upon the law of excluded middle, by showing that absurdity follows from assuming true and from assuming it false. Thus, it may be tempting to think that the paradox is avoidable by avoiding the law of excluded middle, as with intuitionistic logic. However, the paradox still occurs using the law of non-contradiction:

From the definition of R, we have that RR ↔ ¬(RR). Then RR → ¬(RR) (biconditional elimination). But also RR → RR (the law of identity), so RR → (RR ∧ ¬(RR)). But, the law of non-contradiction tells us ¬(RR ∧ ¬(RR)). Therefore, by modus tollens, we conclude ¬(RR).

But since RR ↔ ¬(RR), we also have that ¬(RR) → RR, and so we also conclude RR by modus ponens. So using only intuitionistically valid methods we can still deduce both RR and its negation.

More simply, it is intuitionistically impossible for a proposition to be equivalent to its negation. Assume P ↔ ¬P. Then P → ¬P. Hence ¬P. Symmetrically, we can derive ¬¬P, using ¬P → P. So we have inferred both ¬P and its negation from our assumption, with no use of excluded middle.

History

Exactly when Russell discovered the paradox is not known. It seems to have been May or June 1901, probably as a result of his work on Cantor's theorem that the number of entities in a certain domain is smaller than the number of subclasses of those entities.[3] He first mentioned the paradox in a 1901 paper in the International Monthly, entitled "Recent work in the philosophy of mathematics." He also mentioned Cantor's proof that there is no greatest cardinal, adding that "the master" had been guilty of a subtle fallacy that he would discuss later. Russell also mentioned the paradox in his Principles of Mathematics (not to be confused with the later Principia Mathematica), calling it "The Contradiction."[4] Again, he said that he was led to it by analyzing Cantor's "no greatest cardinal" proof.

Famously, Russell wrote to Frege about the paradox in June 1902, just as Frege was preparing the second volume of his Grundgesetze der Arithmetik.[5] Frege hurriedly wrote an appendix admitting to the paradox, and proposed a solution that was later proved unsatisfactory. In any event, after publishing the second volume of the Grundgesetze, Frege wrote little on mathematical logic and the philosophy of mathematics.

Zermelo, while working on the axiomatic set theory he published in 1908, also noticed the paradox but thought it beneath notice, and so never published anything about it. Zermelo's system avoids the paradox thanks to replacing arbitrary set comprehension with weaker existence axioms, such as his axiom of separation (Aussonderung).

Russell and Alfred North Whitehead wrote the three volumes of Principia Mathematica (PM) hoping to succeed where Frege had failed. They sought to banish the paradoxes of naive set theory by employing a theory of types they devised for this purpose. While they succeeded in grounding arithmetic in a fashion, it is not at all evident that they did so by logic alone. In any event, Kurt Gödel in 1930-31 proved that the logic of much of PM, now known as first order logic, is complete, but that Peano arithmetic is necessarily incomplete if it is consistent. There and then, the logicist program of Frege-PM died.

Applied versions

There are some versions of this paradox that are closer to real-life situations and may be easier to understand for non-logicians. For example, the Barber paradox supposes a barber who shaves men if and only if they do not shave themselves. When one thinks about whether the barber should shave himself or not, the paradox begins to emerge.

As another example, consider five lists of encyclopedia entries within the same encyclopedia:

List of articles about people:
  • Ptolemy VII of Egypt
  • Hermann Hesse
  • Don Nix
  • Don Knotts
  • Biography of Nikola Tesla
  • Sherlock Holmes
  • Emperor Kōnin
List of articles starting with the letter L:
  • L
  • L!VE TV
  • L&H

...

  • List of articles starting with the letter K
  • List of articles starting with the letter L
  • List of articles starting with the letter M

...

List of articles about places:
  • Leivonmäki
  • Katase River
  • Enoshima
List of articles about Japan:
  • Emperor Kōnin
  • Katase River
  • Enoshima
List of all lists that do not contain themselves:
  • List of articles about Japan
  • List of articles about places
  • List of articles about people

...

  • List of articles starting with the letter K
  • List of articles starting with the letter M

...

  • List of all lists that do not contain themselves?

If the "List of all lists that do not contain themselves" contains itself, then it does not belong to itself and should be removed. However, if it does not list itself, then it should be added to itself.

While appealing, these layman's versions of the paradox share a drawback: an easy refutation of the Barber paradox seems to be that such a barber does not exist. The whole point of Russell's paradox is that the answer "such a set does not exist" means the definition of the notion of set within Frege's system is unsatisfactory. This motivated the investigation of axiomatic set theory that does not suffer from the paradox of the kind.

Set-theoretic responses

Russell, together with Alfred North Whitehead, sought to banish the paradox by developing type theory. The culmination of this research is the work, Principia Mathematica. While Principia Mathematica avoided the known paradoxes and allows the derivation of a great deal of mathematics, other challenges to predominant set theory arose.

In 1908, Ernst Zermelo proposed an axiomatization of set theory that avoided Russell's and other related paradoxes. Modifications to this axiomatic theory proposed in the 1920s by Abraham Fraenkel, Thoralf Skolem, and by Zermelo himself resulted in the axiomatic set theory called ZFC. This theory became widely accepted once Zermelo's axiom of choice ceased to be controversial, and ZFC has remained the canonical axiomatic set theory down to the present day. ZFC does not assume that, for every property, there is a set of all things satisfying that property. Rather, it asserts that given any set X, any subset of X definable using first order logic exists. The object R discussed above cannot be constructed in this fashion, and is therefore not a ZFC set. In some extensions of ZFC, objects like R are called proper classes. ZFC is silent about types, although some contend that Zermelo's axioms tacitly presupposes a background type theory.

Through the work of Zermelo and others, especially John von Neumann, the structure of what some see as the "natural" objects described by ZFC eventually became clear; they are the elements of the von Neumann universe, V, built up from the empty set by transfinitely iterating the power set operation. It is thus now possible again to reason about sets in a non-axiomatic fashion without running afoul of Russell's paradox, namely by reasoning about the elements of V. Whether it is appropriate to think of sets in this way is a point of contention among the rival points of view on the philosophy of mathematics.

Other resolutions to Russell's paradox, more in the spirit of type theory, include the axiomatic set theories New Foundations (by Quine) and Scott-Potter set theory.

Footnotes and references

  1. Adapted from Potter, 2004: 24-25.
  2. See Quine 1938. Incidentally, this theorem and teh definition of collection it builds on, are Potter's first theorem and definition, respectively.
  3. In modern terminology, the cardinality of a set is strictly less than that of its power set.
  4. Russell, Bertrand (1903). Principles of Mathematics. Cambridge: Cambridge University Press, Chapter X, section 100. ISBN 0-393-31404-9. 
  5. Russell's letter and Frege's reply are translated in Jean van Heijenoort, 1967.)
  • Potter, Michael, 2004. Set Theory and its Philosophy. Oxford Univ. Press.
  • Willard Quine, 1938, "On the theory of types," Journal of Symbolic Logic 3.

External links

Credits

New World Encyclopedia writers and editors rewrote and completed the Wikipedia article in accordance with New World Encyclopedia standards. This article abides by terms of the Creative Commons CC-by-sa 3.0 License (CC-by-sa), which may be used and disseminated with proper attribution. Credit is due under the terms of this license that can reference both the New World Encyclopedia contributors and the selfless volunteer contributors of the Wikimedia Foundation. To cite this article click here for a list of acceptable citing formats.The history of earlier contributions by wikipedians is accessible to researchers here:

The history of this article since it was imported to New World Encyclopedia:

Note: Some restrictions may apply to use of individual images which are separately licensed.