Russell's paradox
46095
222280176
2008-06-28T14:06:12Z
96.231.198.197
/* Informal presentation */
Part of the [[foundations of mathematics]], '''Russell's paradox''' (also known as '''Russell's antinomy'''), discovered by [[Bertrand Russell]] in [[1901]], showed that the [[naive set theory]] of [[Gottlob Frege|Frege]] leads to a contradiction.
It might be assumed that, for any formal criterion, a set exists whose members are those objects (and only those objects) that satisfy the criterion; but this assumption is disproved by a set containing exactly the sets that are not members of themselves. If such a set qualifies as a member of itself, it would contradict its own definition as ''a set containing sets that are not members of themselves''. On the other hand, if such a set is not a member of itself, it would qualify as a member of itself by the same definition. This contradiction is Russell's paradox.
In 1908, two ways of avoiding the paradox were proposed, Russell's [[type theory]] and [[Ernst Zermelo]]'s [[Zermelo set theory|axiomatic set theory]], the first consciously constructed [[axiomatic set theory]]. Zermelo's axioms went well beyond Frege's axioms of [[extensionality]] and unlimited [[set builder notation|set abstraction]], and evolved into the now-canonical [[ZFC]] set theory.
==Informal presentation==
Let us call a set "abnormal" if it is a member of itself, and "normal" otherwise. 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''. If ''R'' were abnormal, that is, if ''R'' were a member of itself, then ''R'' would be normal since all its members are. So, ''R'' cannot be abnormal, which means ''R'' is normal. Further, since every normal set is a member of ''R'', ''R'' itself must be a member of ''R'', making ''R'' abnormal. Paradoxically, we are led to the contradiction that ''R'' is both normal and abnormal.
A longer argument often given for this contradiction, by Russell himself, for example, proceeds by cases. 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 contain 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 both normal ''and'' abnormal, which is a contradiction.
==Formal derivation==
Let ''R'' be "the set of all sets that do not contain themselves as members". Formally: ''A'' is an element of ''R'' if and only if ''A'' is not an element of ''A''. In [[set-builder notation]]:
: <math>R=\{A\mid A\not\in A\}.</math>
Nothing in the system of Frege's ''Grundgesetze der Arithmetik'' rules out ''R'' being 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. The statements "''R'' is an element of ''R''" and "''R'' is not an element of ''R''" cannot both be true, thus the contradiction.
The following fully formal yet elementary derivation of Russell's paradox<ref>Adapted from Potter (2004: 24-25).</ref> makes plain that the paradox requires nothing more than [[first-order logic]] with the unrestricted use of [[set abstraction]]. The proof is given in terms of collections (all sets are collections, but not conversely). It invokes neither [[axiomatic set theory|set theory axioms]] nor the law of [[excluded middle]] explicitly or tacitly.
'''Definition'''. The collection <math>\{x : \Phi(x)\}\,\!</math>, in which <math>\Phi(x)\,\!</math> is any [[predicate (logic)|predicate]] of first-order logic in which <math>x\,\!</math> is a [[free variable]], denotes the individual <math>A\,\!</math> satisfying <math>\forall x\,[x \in A \leftrightarrow \Phi(x)]\,\!</math>.
'''Theorem'''. The collection <math>R=\{x : x \notin x\}\,\!</math> is contradictory.
''Proof''. Replace <math>\Phi(x)\,\!</math> in the definition of collection by <math>x \notin x\,\!</math>, so that the implicit definition of <math>R\,\!</math> becomes <math>\forall x\,[x \in R \leftrightarrow x \notin x].\,\!</math> [[Universal instantiation|Instantiating]] <math>x\,\!</math> by <math>R\,\!</math> then yields the contradiction <math>R \in R \leftrightarrow R \notin R. \ \square\,\!</math>
''Remark''. The above definition and theorem are the first theorem and definition in Potter (2004), consistent with the fact that Russell's paradox requires no set theory whatsoever. Incidentally, the force of this argument cannot be evaded by simply proscribing the substitution of <math>x \notin x\,\!</math> for <math>\Phi(x)\,\!</math>. In fact, there are denumerably many formulae <math>\Phi(x)\,\!</math> giving rise to the paradox.<ref>See [[Willard Quine]], 1938, "On the theory of types," ''Journal of Symbolic Logic 3''.</ref> For some examples, see [[#reciprocation|reciprocation]] below.
=== The paradox holds in intuitionistic logic ===
The formal derivation described above shows that the set <math>R=\{A\mid A\not\in A\}</math> leads to a contradiction by showing that assuming <math>R</math> true and assuming it false both lead to absurdity; the resulting contradiction implicitly assumes the [[law of excluded middle]]. Thus it may be tempting to conclude that the paradox is avoided if the law of excluded middle is disallowed, as with [[intuitionistic logic]]. However, as is clear from the first of the two informal arguments presented above, the law of excluded middle is not needed for the paradoxical argument. Here we show that the paradox can still be generated formally by means of the intuitionistically valid [[law of non-contradiction]].
'''Theorem'''. The collection <math>R=\{x : x \notin x\}\,\!</math> is contradictory even if the background logic is intuitionistic.
''Proof''. From the definition of ''R'', we have that ''R''∈''R'' ↔ ¬(''R''∈''R''). Then ''R''∈''R'' → ¬(''R''∈''R'') ([[biconditional elimination]]). But also ''R''∈''R'' → ''R''∈''R'' (the [[law of identity]]), so ''R''∈''R'' → (''R''∈''R'' ∧ ¬(''R''∈''R'')). But by the law of non-contradiction we know that ¬(''R''∈''R'' ∧ ¬(''R''∈''R'')). By [[modus tollens]] we conclude ¬(''R''∈''R'').
But since ''R''∈''R'' ↔ ¬(''R''∈''R''), we also have that ¬(''R''∈''R'') → ''R''∈''R'', and so we also conclude ''R''∈''R'' by [[modus ponens]]. Hence we have deduced both ''R''∈''R'' and its negation using only intuitionistically valid methods. <math> \square\,\!</math>
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.
=== Reciprocation ===
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.
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.
==Set-theoretic responses==
In 1908, [[Ernst Zermelo]] proposed an [[axiomatic system|axiomatization]] of set theory that avoided the paradoxes of naive set theory by replacing arbitrary set comprehension with weaker existence axioms, such as his [[axiom of separation]] (''Aussonderung''). 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 argue 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]].
==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.
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, and in Frege’s ''Philosophical and Mathematical Correspondence.''</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 --> <!-- To my knowledge, nothing in this paragraph has been the subject of revisionism. It is true, however, that Boolos and others have significantly rehabilitiated Frege's system by replacing Basic Law V by Hume's Principle, then showing that the resulting system is free of contradiction. -->
[[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.
In 1923, [[Ludwig Wittgenstein]] proposed to "dispose" of Russell's paradox as follows:
<blockquote>
"The reason why a function cannot be its own argument is that the sign
for a function already contains the prototype of its argument, and it
cannot contain itself. For let us suppose that the function F(fx) could be
its own argument: in that case there would be a proposition 'F(F(fx))', in
which the outer function F and the inner function F must have different
meanings, since the inner one has the form O(f(x)) and the outer one has
the form Y(O(fx)). Only the letter 'F' is common to the two functions, but
the letter by itself signifies nothing. This immediately becomes clear if
instead of 'F(Fu)' we write '(do) : F(Ou) . Ou = Fu'. That disposes of
Russell's paradox." (''[[Tractatus Logico-Philosophicus]]'', 3.333)
</blockquote>
Russell and [[Alfred North Whitehead]] wrote their three-volume ''[[Principia Mathematica]]'' (''PM'') hoping to achieve what Frege had been unable to do. 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 purely logical means. While ''PM'' avoided the known paradoxes and allows the derivation of a great deal of mathematics, its system gave rise to new problems.
In any event, [[Kurt Gödel]] in 1930–31 proved that while the logic of much of ''PM'', now known as [[first-order logic]], is [[Gödel's completeness theorem|complete]], [[Peano axioms|Peano arithmetic]] is necessarily [[incomplete]] if it is [[consistent]]. This is very widely – though not universally – regarded as having shown the [[logicist]] program of Frege to be impossible to complete.
==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:
{| class="wikitable"
|- valign="top"
| width="20%" | List of articles about people:
*[[Ptolemy VII of Egypt]]
*[[Hermann Hesse]]
*[[Don Nix]]
*[[Don Knotts]]
*[[Nikola Tesla]]
*[[Sherlock Holmes]]
*[[Emperor Kōnin]]
*[[Chuck Norris]]
| width="20%" | 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
...
| width="20%" | List of articles about places:
*[[Leivonmäki]]
*[[Katase River]]
*[[Enoshima]]
| width="20%" | List of articles about Japan:
*[[Emperor Kōnin]]
*[[Katase River]]
*[[Enoshima]]
| width="20%" | 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 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]]".
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.
One way that the paradox has been dramatised is as follows:
Suppose that every public library has to compile a catalog of all its books. The catalog is itself one of the library's books, but while some librarians include it in the catalog for completeness, others leave it out, as being self-evident.
Now imagine that all these catalogs are sent to the national library. Some of them include themselves in their listings, others do not. The national librarian compiles two master catalogs - one of all the catalogs that list themselves, and one of all those which don't.
The question is now, should these catalogs list themselves? The 'Catalog of all catalogs that list themselves' is no problem. If the librarian doesn't include it in its own listing, it is still a true catalog of those catalogs that do include themselves. If he does include it, it remains a true catalog of those that list themselves.
However, just as the librarian cannot go wrong with the first master catalog, he is doomed to fail with the second. When it comes to the 'Catalog of all catalogs that don't list themselves', the librarian cannot include it in its own listing, because then it would belong in the other catalog, that of catalogs that do include themselves. However, if the librarian leaves it out, the catalog is incomplete. Either way, it can never be a true catalog of catalogs that do not list themselves.
==Applications and related topics==
The Barber paradox, in addition to leading to a tidier set theory, has been used twice more with great success: [[Kurt Gödel]] proved his [[Gödel's incompleteness theorem|incompleteness theorem]] by formalizing the paradox, and [[Alan Turing|Turing]] proved the undecidability of the [[Halting problem]] (and with that the [[Entscheidungsproblem]]) by using the same trick.
=== Russell-like paradoxes ===
As illustrated above for the Barber paradox, Russell's paradox is not hard to extend. Take:
* A [[transitive verb]] <V>, that can be applied to its [[substantive]] form.
Form the sentence:
:The <V>er that <V>s all (and only those) who don't <V> themselves,
Sometimes the "all" is replaced by "all <V>ers".
An example would be "paint":
:The ''paint''er that ''paint''s all (and only those) that don't ''paint'' themselves.
or "elect"
:The ''elect''or ([[Group representation|representative]]), that ''elect''s all that don't ''elect'' themselves.
Paradoxes that fall in this scheme include:
* The [[Barber paradox|barber]] with "shave".
* The original Russell's paradox with "contain": The container (Set) that contains all (containers) that don't contain themselves.
* The [[Grelling-Nelson paradox]] with "describer": The describer (word) that describes all words, that don't describe themselves.
* [[Richard's paradox]] with "denote": The denoter (number) that denotes all denoters (numbers) that don't denote themselves. (In this paradox, all descriptions of numbers get an assigned number. The term "that denotes all denoters (numbers) that don't denote themselves" is here called ''Richardian''.)
* "Groucho's Paradox": [[Groucho Marx]] said that he would never belong to a club that would accept him as a member.
== Related paradoxes ==
* The [[liar paradox]] and [[Epimenides paradox]], whose origins are ancient.
* The [[Kleene-Rosser paradox]], showing that the original [[lambda calculus]] is inconsistent, by means of a self-negating statement.
* [[Curry's paradox]] (named after [[Haskell Curry]]) which does not require [[negation]].
* The [[Interesting number paradox|smallest uninteresting integer]] paradox.
== See also ==
*[[Self-reference]]
*[[Universal set]]
*[[On Denoting]], one of Russell's first attempts at critiquing Frege
== Footnotes==
<references />
==References==
*Potter, Michael, 2004. ''Set Theory and its Philosophy''. Oxford Univ. Press.
== External links ==
*[[Stanford Encyclopedia of Philosophy]]: "[http://plato.stanford.edu/entries/russell-paradox/ Russell's Paradox]" -- by A. D. Irvine.
* [http://www.cut-the-knot.org/selfreference/russell.shtml Russell's Paradox] at [[cut-the-knot]]
* [http://www.paradoxes.co.uk/ Some paradoxes - an anthology]
[[Category:Bertrand Russell]]
[[Category:Paradoxes of naive set theory]]
[[Category:1900s in science]]
[[bg:Парадокс на Ръсел]]
[[cs:Russellova antinomie]]
[[da:Russells paradoks]]
[[de:Russellsche Antinomie]]
[[et:Russelli paradoks]]
[[es:Paradoja de Russell]]
[[fr:Paradoxe de Russell]]
[[ko:러셀의 역설]]
[[is:Russell mótsögnin]]
[[it:Paradosso di Russell]]
[[he:הפרדוקס של ראסל]]
[[hu:Russell-paradoxon]]
[[nl:Russellparadox]]
[[ja:ラッセルのパラドックス]]
[[no:Russells paradoks]]
[[pl:Paradoks Russella]]
[[pt:Paradoxo de Russell]]
[[ru:Парадокс Рассела]]
[[sr:Раселов парадокс]]
[[fi:Russellin paradoksi]]
[[sv:Russells paradox]]
[[th:ปฏิทรรศน์ของรัสเซิลล์]]
[[uk:Парадокс Рассела]]
[[zh:罗素悖论]]