Russell's paradox

Russell's paradox (also known as Russell's antinomy) is a paradox discovered by Bertrand Russell in 1901 which shows that the naive set theory of Frege is contradictory. Consider the set M to be "The set of all sets that do not contain themselves as members". Formally: A is an element of M if and only if A is not an element of A.

M=\{A\mid A\not\in A\}

In Frege's system, M would be a well-defined set. Does M contain itself? If it does, it is not a member of M according to the definition. On the other hand, if we assume that M does not contain itself, then it has to be a member of M, again according to the very definition of M. Therefore, the statements "M is a member of M" and "M is not a member of M" both lead to contradictions (but see Independence from Excluded Middle below).

History

Exactly when Russell discovered the paradox is not clear. 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. In Russell's Principles of Mathematics (not to be confused with the later Principia Mathematica) Chapter X, section 100, where he calls it "The Contradiction", he says that he was led to it by analyzing Cantor's proof that there can be no greatest cardinal. He also mentions it in a 1901 paper in the International Monthly, entitled "Recent work in the philosophy of mathematics." Russell mentioned Cantor's proof that there is no largest cardinal and stated that "the master" had been guilty of a subtle fallacy that he would discuss later.

Famously, Russell wrote to Frege about the paradox in June 1902, just as Frege was preparing the second volume of his Grundgesetze. Frege was forced to prepare an appendix in response to the paradox, but this later proved unsatisfactory. It is commonly supposed that this led Frege to completely abandon his work on the logic of classes.

While Zermelo was working on his version of set theory, he also noticed the paradox, but thought it too obvious and never published anything about it. Zermelo's system avoids the difficulty through the famous Axiom of separation (Aussonderung).

Russell, with Alfred North Whitehead, undertook to accomplish Frege's task, this time using a more restricted version of set theory that, they thought, would not admit Russell's Paradox, but would still produce arithmetic. Kurt Gödel later showed that, even if it was consistent, it did not succeed in reducing all mathematics to logic.

Applied versions

There are some versions of this paradox which 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 everyone who does not shave himself, and no one else. When one thinks about whether the barber should shave himself or not, the paradox begins to emerge.

As illustrated below, consider five lists of encyclopedia entries within the same encyclopedia:

List of articles about Japan
List of articles about places
List of articles about computer science
List of articles about people
List of all lists that do not contain themselves?

List of articles about people:

List of articles about computer science:

List of articles about places:

List of articles about Japan:

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, for example, Barber's paradox seems to be: "Such a barber does not exist". The whole point of Russell's paradox is that the answer "such a set does not exist" means that the definition of the notion of "set" within a given theory is unsatisfactory. Notice the subtle difference between the statements: "such a set does not exist" and "such a set is 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.

Set-theoretic responses

After this paradox was described, Ernst Zermelo proposed an axiomatization of set theory as axiomatic set theory in a way that avoided this and other related problems. Russell himself, together with Alfred North Whitehead, developed a comprehensive system of types in his work Principia Mathematica. This system does indeed avoid the known paradoxes and allows for the formulation of all of mathematics, but it has not been widely accepted. The most common version of axiomatic set theory in use today is Zermelo-Fraenkel set theory including the axiom of choice, ZFC, which avoids the notion of types. ZFC does not assume that, for every property, there is a set of all things satisfying that property. Rather, it assumes that for any given set and any definable property, there is a subset of all elements of the given set satisfying the property. The object M discussed above cannot be constructed like that and is therefore not a set in this theory; in some extensions of ZFC, objects like M can be considered as proper classes.

Through the work of Zermelo and others, such as 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, which are built up from the empty set by transfinitely iterating the powerset operation. Thus it is now again possible to think of set theory non-axiomatically, as reasoning about the sets of the von Neumann universe, without running into Russell's paradox. Whether it is appropriate to think of it that way is a point of contention among various philosophical schools.

Other approaches have been proposed, such as New Foundations.

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 incompleteness theorem by formalizing the paradox, and 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 Ver that Vs all (and only those) who don't V themselves,

Sometimes the "all" is replaced by "all Vers".

An example would be "paint":

The painter that paints all that don't paint themselves.

or "elect"

The elector (representative), that elects all that don't elect themselves.

Paradoxes that fall in this scheme include:

The 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.)

Reciprocation

Russell's paradox arises from the supposition that one can meaningfully define a class in terms of any well-defined property

P(x)

; that is, that we can form the set

P = \{ x | P(x) \mbox{ is true } \}

. When we take

P(x) = x\not\in x

, we get Russell's paradox. This is only the simplest of many possible variations of this theme.

For example, if one takes $P(x) = \neg(\exists z: x\in z\wedge z\in x)$ , one gets a similar paradox; there is no set $P$ of all $x$ with this property. For convenience, let us agree to call a set $S$ reciprocated if there is a set $T$ with $S\in T\wedge T\in S$ ; then $P$ , the set of all non-reciprocated sets, does not exist. If $P\in P$ , we would immediately have a contradiction, since $P$ is reciprocated (by itself) and so should not belong to $P$ . But if $P\not\in P$ , then $P$ is reciprocated by some set $Q$ , so that we have $P\in Q\wedge Q\in P$ , and then $Q$ is also a reciprocated set, and so $Q\not\in P$ , 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 $P$ "nonreciprocated" if and only if there is no adjective $Q$ such that both $P$ describes $Q$ and $Q$ describes $P$ . 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 $A_1,A_2,...,A_n$ a chain of set $A_1$ if $A_{i+1} \in A_i$ for i=1,2,...,n-1. A chain can be infinite (in which case each $A_i$ 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 $P \in P$ , 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

M=\{A\mid A\not\in A\}

is shown to lead to contradiction based upon the law of excluded middle, by showing that absurdity follows from assuming

P

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 M, we have that M∈M ↔ ¬(M∈M). Then M∈M → ¬(M∈M) (biconditional elimination). But also M∈M → M∈M (the law of identity), so M∈M → (M∈M ∧ ¬(M∈M)). But, the law of non-contradiction tells us ¬(M∈M ∧ ¬(M∈M)). Therefore, by modus tollens, we conclude ¬(M∈M).

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

Other related paradoxes

The liar paradox and Epimenides paradox, whose origins are ancient.
Curry's paradox (named after Haskell Curry, b. 1912), which does not need negation.
The smallest uninteresting integer paradox.

External links

Paradoxes | Set theory

Gourt Home::Gourt :: Russell's paradox