Russell’s Paradox

Bertrand Russell

Bertrand Russell was a British scholar based at Trinity College, Cambridge, renowned for his brilliance. Although Frege’s works had made little impact on the scientific community and had received a rather cool reception, Russell took notice of the Grundgesetze der Aritmetik, published in 1894. In this work, the German mathematician sought to ground the concept of number and, by extension, all of Arithmetic in logical notions, using explicit and precise definitions and mechanical deductions. The idea captivated Russell and would profoundly influence his entire academic output.

Nevertheless, it was Russell who, by discovering the paradox that bears his name, would call into question Frege’s achievements and the entire logicist approach.

Frege’s Logic

As we saw in the previous article, Frege defines a concept \(P(x)\) as a type of function that takes any object \(x\) as its argument and returns a truth value, either “true” or “false.” If, for example, we interpret the concept \(P(x)\) as “\(x\) is a scientist,” and then replace the variable \(x\) with “Albert Einstein,” the result is the value true. This gives rise to the proposition “Albert Einstein is a scientist,” which, in this case, is correct. We say that “Albert Einstein” satisfies or falls under the function \(P\). “Picasso is a scientist” is another proposition, one that, by contrast, does not satisfy \(P\).

Clearly, “Albert Einstein” is not the only object that satisfies this predicate function. All those objects that make a concept true form the extension of that concept: in this case, all those objects are scientists. For a concept \(P\), we denote its extension by \(\varepsilon P\) .

The Principle of Comprehension

The Principle of Comprehension states that every concept (\(\forall X\)) has a corresponding extension (\(\alpha\)).

$$\forall X\,\exists \alpha\,\forall x\bigl(X(x)\leftrightarrow x\in\alpha\bigr)$$

We may therefore treat concepts and extensions of concepts equivalently. We will use the symbol ∈ to denote membership in a class.

From this notion, Frege develops what is known as Basic Law V: the extensions of two concepts (\(\varepsilon F\) and \(\varepsilon P\)) are equal whenever exactly the same objects fall under both concepts.

$$\forall F\,\forall P\Bigl((\varepsilon F=\varepsilon P) \leftrightarrow \forall x\bigl(F(x)\leftrightarrow P(x)\bigr)\Bigr)$$

This law states that two concepts may be different—such as “x is a living descendant of the dinosaurs” and “x is a feathered vertebrate”—yet, if the same objects fall under both, they share the same extension: the class of birds.

This assertion is fundamental to the system because Frege uses it to define numbers, as we saw in the previous article.

Russell’s Paradox

As we can see, to refer to an arbitrary collection of elements we may use a predicative statement: a concept expressing a property shared by those elements (“being a member of the Apollo 11 crew”). Definitions of this kind are known as intensional. Alternatively, we may enumerate the elements that make up the collection (“Neil Armstrong,” “Michael Collins,” “Buzz Aldrin”), producing what is called an extensional definition. The relationship between these two kinds of definition can be problematic, since different intensional definitions may refer to the same extension. Russell called extensions classes and showed that Frege’s Basic Law V did indeed entail a contradiction that endangered the logicist project.

Classes of Classes

Let \(\varepsilon X\) be a variable representing any extension or class. Does there exist a class of all classes, containing every possible value of \(\varepsilon X\)? The language of logic allows us to express this without difficulty. In modern logical notation, the claim is:

$$\exists \Psi\,\forall X\bigl(\varepsilon X\in\varepsilon\Psi\bigr)$$

which may be read informally as:

“There exists a class \(\psi\) such that every class belongs to \(\psi\).”

\(\psi\) is the class containing all classes.

Self-Membered Classes

If there is a class that contains every class, then that class must contain itself; otherwise, there would be one class it failed to contain: itself. Thus, \(\psi \exists \psi \).

There is nothing contradictory about classes that contain themselves. One example would be a book that catalogues every book in a library. Since the catalogue is itself a book in the library, it is also listed in itself. Another example is the class of all objects that are not chairs: that class is an abstract object that is not a chair and therefore belongs to itself. Classes that contain themselves in this way are called self-membered classes. We may then speak of all of them as forming a class: the class of all classes that contain themselves. Likewise, there will be a disjoint class: the class of all classes that do NOT contain themselves.

$$\exists \Xi\,\forall X\Bigl( (\varepsilon X\notin\varepsilon X) \leftrightarrow (\varepsilon X\in\varepsilon\Xi) \Bigr)$$

Formulating Russell’s Paradox

Let us focus on this last class. Does it belong to itself? In other words, is the class of all classes that are not self-membered itself self-membered? If it were self-membered, that class would be among the objects that satisfy it. But this is impossible, because we have said that only classes that do not contain themselves belong to it. The other possibility—that the class were not self-membered—would mean that it does not contain itself. Yet this is contradictory, since we defined the class precisely as the one collecting every class that does not contain itself. We have therefore reached an unavoidable contradiction.

In summary, the paradox may be stated as follows: Does the class of all classes that do not contain themselves contain itself or not? Here is Russell’s Paradox in logical notation, obtained simply by replacing the variable \(\varepsilon X \) in the previous expression with \(\varepsilon\Xi \):

$$\exists \Xi\Bigl( (\varepsilon\Xi\notin\varepsilon\Xi) \leftrightarrow (\varepsilon\Xi\in\varepsilon\Xi) \Bigr)$$

Consequences of Russell’s Paradox

Crisis of the Logicist Project

The idea of using the language of logic to express every possible mathematical theorem is what we have called the logicist project. The paradox discovered by Russell endangered that project. A single contradiction in a formal system—an expression that cannot consistently be classified as true or false—renders the system incapable of distinguishing correct theorems from incorrect ones. The entire system collapses.

Russell made the paradox public in 1903, but one year earlier he had sent Frege a letter setting out the contradiction. The consequences were especially devastating. For thirty years, Frege had devoted himself to a work intended to unite Mathematics and Logic once and for all. When he received Russell’s letter containing the paradox, Frege was deeply shaken and was forced to acknowledge its impact in the second volume of the Grundsetzte, his definitive work.

– Nothing is more distressing to a scientific writer than to have one of the foundations of his edifice shaken after the work is finished – 

Gottlob Frege. Appendices to the Grundgesetze. 1903

Russell, for his part, believed that the logicist project itself could be saved and continued pursuing it until the publication of his magnum opus, the Principia Mathematica, a vast work written in collaboration with his former teacher Alfred North Whitehead. In the Principia, Russell acknowledges the paradoxes and develops the so-called Theory of Types, which avoids them and will be the subject of our next article.

Cantor and Russell’s Paradox

What about Cantor and his transfinite numbers? Although Cantor began from premises very different from those of the logicist projects, Bertrand Russell discovered the paradox under the influence of Cantor’s findings.

The consequences of Russell’s Paradox for Cantorian Set Theory have been widely debated. Logicists such as Frege and Russell conceived classes as groupings of objects unified by some law or rule—that is, by intensional definitions. Cantor’s approach was quite different: a set is not determined by the reasons that give unity to its elements, but by its numerosity and by the possibility of enumerating them. Cantor’s framework offers no way to provide an intensional definition of sets and therefore no way to formulate self-containing sets. Two sets are equal if and only if they have exactly the same elements, which commits the theory only to an extensional perspective. For Cantor, his definition of set therefore shielded him from the contradiction discovered by Russell. 

Russell’s Paradox and Set Theory

We have argued here that Russell’s Paradox scarcely affects the soundness of Cantorian Set Theory. Nevertheless, that theory carried problems of its own. It will be useful to review them in order to understand the subsequent development of Set Theory.

Ordinal Numbers

Cantor’s definition of a set began from the notion of a well-ordering: the possibility of linearly ordering a sequence of elements so that one element comes first. Since Cantor, unlike Frege, began with the counting of elements in order to define a collection, well-ordering was a fundamental principle throughout his theory.

Only when a set is linearly ordered can it be counted by another linearly ordered set. If two sets can count one another—that is, if there is a bijection between them—then both sets share an order type or ordinal number.

Ordinal numbers, or simply numbers, arose from these order types as an abstraction from the possibility of counting.

The Burali-Forti Paradox

Numbers can themselves be counted. The set of ordinal numbers is also well-ordered, and for that reason we say that it is a set and can therefore be counted. We may then ask: which ordinal corresponds to the set of all numbers?

In fact, assuming that there is a set of all ordinals leads to a contradiction known as the Burali-Forti Paradox. Counting all ordinal numbers would yield a number: the ordinal of that set. But that number would itself have to belong to the very set we are trying to count. Such an ordinal would define a section within the infinite set, implying that the sequence of ordinals continues with still greater ordinals. It therefore could not be the ordinal of the set of all ordinals, contradicting the original premise. If a collection has no ordinal, is it legitimate to treat it as a set?

Cantor’s Paradox

For cardinal numbers, Cantor had discovered another paradox closely related to the Burali-Forti Paradox. Cantor’s Theorem, discussed in previous articles, states that if a cardinal \(\aleph_0\)​ exists, then a greater cardinal \(\aleph_1\) must necessarily exist. The same theorem also guarantees an \(\aleph_2\)​ and an \(\aleph_3\)​, and so on: an endless succession of transfinite infinities. The theorem can always be applied again to generate ever larger infinities. A set containing all cardinals would fail to contain the cardinality of its own power set and therefore would not be the set of all cardinals. This is known as Cantor’s Paradox because it follows from the theorem of the same author.

Cantor’s Absolute

Just as Russell’s Paradox exposed the difficulties involved in speaking of a class of all classes, these paradoxes made it impossible for either the set of all ordinals or the set of all cardinals to exist, despite their being well-ordered and therefore qualifying as sets according to Cantor’s definition.

Cantor cautiously acknowledged the existence of these paradoxes. For him, they were examples of what he called “inconsistent multiplicities,” or absolute infinities. For a devout spirit such as Cantor, the human mind can recognize these infinities, but only a divine intelligence can comprehend them. He therefore also referred to them as the Absolute. They were, then, collections of elements that could not form a set despite being well-ordered.

Conclusions

Russell’s Paradox and the other paradoxes were intensely debated during the opening years of the twentieth century. In any formal language to which a mathematical theory aspires, the presence of a single contradiction is a genuine catastrophe. It is well known that from an inconsistency one can derive every theorem, even mutually contradictory ones. Attempts to ground mathematics in sets or classes seemed corrupted at their deepest foundations. The edifice of mathematics was trembling.

Grounding Set Theory in the idea of well-ordering brought paradoxes with it. So did grounding it in Cantor’s power-set theorem. During his lifetime, Cantor was unable to prove the Continuum Hypothesis, which was needed to ensure that the aleph cardinals follow one another in succession. Nor did the highly prominent role assigned to well-ordering as a justification for sets win general acceptance.

Nevertheless, Cantor’s discoveries and Frege’s logicist project had made major contributions to the foundations of mathematics. They could be salvaged. In the following articles, we will examine the development of both traditions.

Recommended Reading

 – Lombraña, J. V. (1999) History of Logic.

– Torretti, R. (1998) Cantor’s Paradise: The Set-Theoretic Tradition in the Philosophy of Mathematics.

– Ferreiros, J. (1999) Labyrinth of Thought: A History of Set Theory and Its Role in Modern Mathematics.