Russell's Paradox

Russell's paradox is a counterexample to naive set theory, which defines a set as any definable collection. The paradox defines the set $R$ of all sets that are not members of themselves, and notes that

• if $R$ contains itself, then $R$ must be a set that is not a member of itself by the definition of $R$, which is contradictory;
• if $R$ does not contain itself, then $R$ is one of the sets that is not a member of itself, and is thus contained in $R$ by definition--also a contradiction.

This contradiction is Russell's paradox. It was significant due to reshaping the definitions of set theory, which was of particular interest at the time as the fundamental axioms of mathematics (e.g. the Peano axioms that define arithmetic) were being redefined in the language of sets.

Russell's paradox (and similar issues) was eventually resolved by an axiomatic set theory called ZFC, after Zermelo, Franekel, and Skolem, which gained widespread acceptance after the axiom of choice was no longer controversial. In short, ZFC's resolved the paradox by defining a set of axioms in which it is not necessarily the case that there is a set of objects satisfying some given property, unlike naive set theory in which any property defines a set of objects satisfying it.

Consider a barber who shaves exactly those men who do not shave themselves (i.e. the barber shaves everyone who doesn't shave themselves and shaves nobody else). Then

• if the barber shaves himself, then the barber is an example of "those men who do not shave themselves," a contradiction;
• if the barber does not shave himself, then the barber is an example of "those men who do not shave themselves," and thus the barber shaves himself--also a contradiction.

Hence the barber does not shave himself, but he also does not not shave himself, hence the paradox.

In the above example, an easy resolution is "no such barber exists," but the point of Russell's paradox is that such a "barber" (i.e. a set) must exist if naive set theory were consistent. Since this barber leads to a paradox, naive set theory must be inconsistent.

Set theory was of particular interest just prior to the 20$^\text{th}$ century, as its language is extremely useful in formalizing general mathematics. For instance, just a few applications are

• Arithmetic can be formalized using sets as in the Peano axioms. As much of mathematics depends solely on the completeness of arithmetic, this allows for a large amount of mathematics to be implicitly formalized.
• Bijection can be understood as a statement about one-to-one correspondence of sets, which also leads to...
• Formalization of infinity and cardinality, especially in defining different types of infinity such as Cantor's proof that there are more real numbers than there are integers.

As a result of this incredibly useful formalization, much of mathematics was repurposed to be defined in terms of Cantorian set theory, to the point that it (literally) formed the foundation of mathematics.

Russell's paradox served to show that Cantorian set theory led to contradictions, meaning not only that set theory had to be rethought, but most of mathematics (due to resting on set theory) was technically in doubt. Fortunately, the field was repaired a short time later by new axioms (ZFC), and set theory remains the main foundational system of mathematics today.

Naive set theory is the theory of predicate logic with binary predicate $\in$, that satisfies

$$\exists y\forall x\big(x \in y \iff \phi(x)\big)$$

for any predicate $\phi$. This is called unrestricted comprehension, and means

There exists a set $y$ whose members are exactly the objects satisfying the predicate $\phi$.

Naive set theory also contains two other axioms (which ZFC also contains):

Existential instantiation:

Given a formula of the form $(\exists x)\phi(x)$, one can infer $\phi(c)$ for some new symbol $c$.

All this is saying is that if there exists some object satisfying a given property, that element can be given a name $c$ (in such a way that $c$ was not previously used). For instance,

• There exists a number satisfying the equation $x^2 + 1 = 0$.
• Define $i$ to be a number satisfying the equation $i^2 + 1 = 0$.

is valid logic.

Universal instantiation:

Given a formula of the form $\forall x\phi(x)$, one can infer $\phi(c)$ for any $c$ in the universe.

Intuitively speaking, this axiom states that if everything satisfies some property, any one of those things also satisfies that property. For instance,

• All people living in California live in the U.S.A. (hypothesis)
• John lives in California. (implying that John is part of the universe)
• John lives in the U.S.A. (invocation of universal instantiation)

is valid logic.

These axioms are sufficient to illustrate Russell's paradox:

• Consider the predicate $\phi: x \not\in x$.
• By unrestricted comprehension, there exists a set $y$ consisting of elements satisfying the predicate $\phi$.
• By existential instantiation, there exists a $z$ such that $\forall x\big(x \in z \iff \phi(x)\big)$.
• By universal instantiation, $z$ (which is in the universe) satisfies the predicate $x \in z \iff \phi(x)$, so $z \in z \iff z \not\in z$,

which is a contradiction, implying that naive set theory is inconsistent.

Roughly speaking, there are two ways to resolve Russell's paradox: either to

• alter the logical language, i.e. first order logic, that the axioms of set theory are expressed in, or
• alter the axioms of set theory, while retaining the logical language they are expressed in.

Russell took the first approach in his attempt at redefining set theory with Whitehead in Principia Mathematica, developing type theory in the process. However, though they eventually succeeded in defining arithmetic in such a fashion, they were unable to do so using pure logic, and so other problems arose.

In fact, Godel showed that Peano arithmetic is incomplete (assuming Peano arithmetic is consistent), essentially showing that Russell's approach was impossible to formalize. In doing so, Godel demonstrated his acclaimed incompleteness theorems.

The second approach, in which the axioms of set theory are altered, was favored by Zermelo (later joined by Franekel and Skolem) in his derivation of ZFC. This resolves the paradox by replacing unrestricted comprehension with restricted comprehension (also called specification):

Given a predicate $\phi$ with free variables in $x, z, w_1, w_2, \ldots, w_n$, $$\forall z\forall w_1 \forall w_2 \ldots \forall w_n \exists y \forall x(x \in y \iff \big(x \in z \land \phi)\big).$$

Essentially, this means that given a set $z$ and a predicate $\phi$, the subset

$$\{x \in z: \phi(x)\}$$

(i.e. all elements of $z$ satisfying the predicate $\phi$) exists.

This resolves Russell's paradox as only subsets can be constructed, rather than any set expressible in the form $\{x:\phi(x)\}$. In this sense, Russell's paradox serves to show that

There does not exist a set containing all sets,

which is also a useful result in its own right.

• Set Theory
• ZFC
• Peano Axioms
• Axiom of Choice