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 Cantor and Frege is contradictory.

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.

Related Topics:
Kurt Gödel - Incompleteness theorem - Turing - Halting problem - Entscheidungsproblem

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Russell-like paradoxes

As illustrated above for Barbers and Lists, the Russell paradox is not hard to extend. Needed is

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• 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 are

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• 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

The Russell 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 otin x, we get the Russell paradox. This is only the simplest of many possible variations of this theme.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

For example, if one takes P(x) = eg(exists z: xin zwedge zin 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 Sin Twedge Tin S; then P, the set of all non-reciprocated sets, does not exist. If Pin P, we would immediately have a contradiction, since P is reciprocated (by itself) and so should not belong to P. But if P otin P, then P is reciprocated by some set Q, so that we have Pin Qwedge Qin P, and then Q is also a reciprocated set, and so Q otin P, another contradiction.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Any of the variations of the Russell 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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Independence from excluded middle

The paradoxical argument like the one at the start of this article has the form of constructing a purported proposition P which

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

would be true if and only if it were false, entailing that the construction

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

is defective.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Often, as is done above, showing the absurdity of such a proposition

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

is 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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

On the contrary,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

assume P iff not P.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Then P implies not P.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Hence not P.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

And hence, again using our assumption in the opposite

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

direction, we infer P. So we have inferred both P and its negation from our assumption, with no use of excluded middle.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~