Russell's Antinomy

The Set of All Sets Which Do Not Contain Themselves
Fields: Algebra, Number Theory, and Algebra
Image Created By: Peter Weck

The Set of All Sets Which Do Not Contain Themselves

The blob on the right represents the set of all sets which are not elements of themselves. At first such a set might seem logically acceptable, but it leads straight to a famous contradiction known as Russell’s Antinomy or Russell’s Paradox.

Basic Description

In the most basic sense of the word, a set is just a collection of objects, or elements. When we say a set contains or includes something, we mean the thing is an element of the set. These elements could be teacups, ideas, numbers, or other sets. Sets can even contain themselves as elements. For example, the set of all ideas is itself an idea. Of course, not all sets contain themselves. The set of all teacups is most definitely not a teacup.

This allows us to divide all imaginable sets into two distinct categories, two enormous sets: the set of all sets which contain themselves (e.g., the set of all ideas) and the set of all sets which do not contain themselves (e.g., the set of all teacups). The blob in the main image represents the set of all sets which do not contain themselves. We can see a few examples of elements of this set floating around the blob's interior. The set of all numbers is an element because it is not a number, and the set of all people is an element because it is obviously not a person. This is all well and good, until we consider whether the set of all sets which do not contain themselves contains itself as an element. The resulting antinomy is best illustrated with an analogy.

The Barber Analogy

Who shaves the barber?

Let me tell you a story...

Once upon a time there was a town with strict laws on shaving. Everyone was required by law to shave daily. Those who didn't feel like shaving themselves went to the town barbershop. The barber who owned the shop had been legally appointed “the man who shaves all and only those who don’t shave themselves”. This was all well and good, until the barber was arrested for being unshaven. You might think the barber could have just shaven himself, but the law said that the barber could only shave those who don’t shave themselves. And if he didn't shave himself, he was supposed to be shaved by the barber. But he is the barber, and once again, the barber was not supposed to shave men who shave themselves! When the judge realized that it was impossible for the barber to follow the law, he ruled that the law be revised to resolve the contradiction and that the barber be released from jail.

The set of all sets which do not contain themselves is analogous to the barber who only shaves men who do not shave themselves. If the barber shaves himself, he is no longer a person who is allowed to be shaved by the barber; if the set of all sets which do not contain themselves contains itself, it is no longer allowed to contain itself. If the barber does not shave himself, he should be shaved by the barber; if the set does not contain itself, it should be contained in itself. This is Russell’s Antimony. Just as the law is impossible for the barber to follow, the set of all sets which do not contain themselves is a logical impossibility. See the image below for a visual presentation of the contradiction.

---

It must either contain itself or not contain itself, and since both possibilities yield contradictions, this set is a logical impossibility.

A little History

Russell was none too pleased about discovering his paradox.

The year was 1901. Just when the world of mathematics had dealt with one set of paradoxes and foundational crises regarding limits in calculus, a new batch had emerged from set theory. Like many of his peers at the time, young philosopher and mathematician Bertrand Russell was hard at work trying to construct a firm logical foundation for all of mathematics. While working on the first of his books in the area, the Principles of Mathematics, Russell came upon the idea of a set of all sets which do not include themselves. He soon realized that when you consider whether this, in his words, "very peculiar class" includes itself, "each alternative leads to its opposite and there is a contradiction".

Russell's Antinomy came to be the most famous paradox in set theory. The concept of a set, or class as Russell called it, was crucial for the program of deriving the foundation of mathematics from logic. Russell's discovery of a paradox stemming from the accepted conception of a set was like a crack in this foundation. It prompted a refinement of the concept of a set and much later work in logic, set theory, and the philosophy of the foundations of mathematics.

For more on the implications of Russell's Antinomy, see this section.

A More Mathematical Explanation

[Click to view A More Mathematical Explanation]

Some Basic Notation

Before describing Russell’s Antinomy mathematically, we need to get acqua [...]

[Click to hide A More Mathematical Explanation]

Some Basic Notation

Before describing Russell’s Antinomy mathematically, we need to get acquainted with some basic set theory notation.

Membership Relation

The fundamental concept of set theory is that of inclusion, or membership, of an object in a set. The symbol ∈ denotes the membership relation between an object and a set. To say that the set A contains the element a, or equivalently that a is in A, we write

$a \in A$

To say that Bertrand Russell was a person using set theory notation, where Russell is represented r and the set of all people P, we write

$r \in P$

We can use a similar notation to indicate that something is not included in a set. For example, to say that Bertrand Russell was not a fish, where the set of all fish is F, we write

$r \notin F$

List Notation

Sets are often represented as lists of elements separated by commas and contained in brackets. For example, a set A containing only the elements a and b is written

$A = \{ a,b \}$

A set Y consisting of the numbers 1, 2, 3, and 4 looks like

$Y = \{ 1,2,3,4 \}$

Representing a set with a list like this can be tedious if the set is especially large. Some sets have infinitely many elements, and can't be written this way at all. In cases like these, set-builder notation is usually used.

Set-builder Notation

Set-builder notation describes a set by stating the properties that its elements must satisfy. This allows us to represent sets of any size without trouble. For example, while the set of all people P would take quite a long time to write out as a list, we can represent it in set-builder notation with

$P = \{ x:x \text{ is a person} \}$

This formula would be read "P is the set of all x such that x is a person".

The set Y we defined earlier as a list of the numbers 1, 2, 3, and 4 could also be written in set-builder notation. Where the set of all integers is $\mathbb{Z}$,

$Y = \{ n \in \mathbb{Z}:0<n<5 \}$

Which would be read "Y is the set of all integers n such that n is greater than 0 and less than 5".

Russell's Antinomy

If S is some set, then Russell's set of all sets which do not contain themselves, which we will call R, is represented

$R = \{ S:S \notin S \}$

Which means that saying

$S \in R$

is equivalent to saying

$S \notin S$

or formally

$S \in R \Leftrightarrow S \notin S$

Where the symbol $\Leftrightarrow$ is read "if and only if".

As discussed earlier, the paradox arises when we consider whether R includes itself. We can represent this question of self-inclusion formally by substituting the set R for the variable set S in the expression above. This gives us

$R \in R \Leftrightarrow R \notin R$

which is a contradiction.

Why It's Interesting

hello

The Implications of the Paradox

Russell's Antinomy was like a crack in the logical foundation of mathematics.

In so-called naïve set theory prior to the discovery of Russell’s Antinomy, a set was simply a collection of objects with some common property. It didn’t matter what the property was or what the objects were. Mathematically, this definition was embodied by the Comprehension Axiom of set theory. This axiom essentially says that any propositional function P(x) can be used to determine a set. So for any statement of a property P, there exists a set whose elements are all the things x which satisfy the property. We will return to this axiom of naïve set theory later when discussing the resolution of the paradox. For now, the takeaway is that the generality of the classical defintion of a set is what makes a set of all sets which do not contain themselves an acceptable notion, and thus makes Russell’s Antinomy possible.

When Russell discovered the paradox, Gottlob Frege was working on his Grundgesetze der Arithmetik, which attempted to establish a foundation for mathematics using symbolic logic. Unfortunately, much of Frege’s work relied on the conception of a set which leads to Russell’s Antinomy. Russell wrote to Frege after discovering his paradox, just when the second volume of Frege’s Grundgesetze was going to press. Realizing the significance of the paradox, Frege added a note to the end of his book saying

“A scientist can hardly meet with anything more undesirable than to have the foundations give way just as the work is finished. I was put in this position by a letter from Mr. Bertrand Russell when the work was nearly through the press.”

It wasn't just Frege's work that was jeopardized by Russell's Antinomy. As mentioned earlier, the entire enterprise of shoring up mathematics on a logical foundation, including Russell's own work, needed set theory to have any hope of succeeding. And set theory wasn't going to be up to the task until Russell's paradox had been resolved.

The Resolution of the Paradox

This was no easy task. Various resolutions have been developed over the years, most focused on restricting the principles governing what qualifies as a set, like the Comprehension Axiom, so that a set of all sets which do not contain themselves is not an acceptable notion in the first place.

The Theory of Types

Russell's own response to the paradox was his theory of types, which can be illustrated with a continuation of the barber story told earlier...

After the trial of the barber, the town leaders met to resolve the confusion created by their shaving law. After much debate, they agreed on a new shaving law establishing a caste system in the town. Each and every townsperson thenceforth belonged to a caste, and was only allowed to be shaven by someone belonging to a lower caste. The barber, for example, ended up in caste 3, and while his business was restricted to only shaving people in higher castes like 4, 5, and 6, he no longer had to worry about whether or not he could shave himself since he was shaven by members of castes 1 and 2. The law was quite controversial, since it meant that nobody was allowed to shave themselves anymore. They instead had to pay to be shaven by members of a lower caste. The members of caste 1 were especially unhappy. There was no lower caste to shave them, and as a result they became quite scruffy.

As before, the people in the story are like sets, and shaving someone is like being contained in a set. Russell's theory of types does away with the Comprehension Axiom and imposes a hierarchy on sets, such that sets can only contain objects of lower types, just like the caste system for shaving imposed on the townspeople. The equivalent of caste 1 in the story are objects called individuals in the theory of types. Sets containing only individuals are like members of caste 2 who can only be shaven by members of caste 1. Sets of sets, or families of sets, are analogous to members of caste 3, and so on. Just as the caste system abolishes self-shaving and with it the barber's paradox, Russell's theory of types makes it so that self-inclusion and Russell's antimony can't occur in the first place.

Connection to Principia Mathematica

Russell and Whitehead's Principia was so exact that it took them until page 362 to prove 1 + 1 = 2. As you can see, the language used is more symbolic logic than English.

Russell's theory of types served as the vehicle for his groundbreaking work formalizing the foundations of mathematics. The theory was first discussed in Russell's original Principles of Mathematics published in 1903, but wasn't fully formed for about five years after that. It was eventually laid out by the monumental Principia Mathematica he co-authored with Alfred North Whitehead. The Principia was the product of years of work seeking to succeed where Frege had failed and establish a foundation of symbolic logic for all of mathematics. It presented a system of axioms and rules of reasoning from which all of mathematics was to be formulated and proved.

While the Principia was certainly a milestone in mathematics, it is essentially an unfinished work and many would even say a lost cause. The hierarchy that the theory of types imposes has been criticized for being too ad hoc to eliminate Russell's paradox successfully. And even if the Principia does do away with the paradox, it has other problems which make it fall short of the immense ambitions of its authors.

File:Kurt gödel.jpg

Kurt Gödel

In 1931, the 25-year-old mathematician Kurt Gödel proved two theorems, known as Gödel's Incompleteness Theorems, that dealt a crushing blow to the mission of the Principia Mathematica. The first of these theorems states that if the system laid out by the Principia is consistent, it must necessarily be incomplete. Incomplete means that there is a true statement in the language of the system (symbolic logic) that can neither be proven nor disproven using the system. Any such statement is said to be Undecidable within the system. The second theorem states that the consistency of the system used by the Principia cannot be established within the system. If you could prove the system was consistent using the rules of the system, it would in fact be an indication that the system is inconsistent.

So even if Russell's Antinomy and all other paradoxes could be eradicated from Principia, it would still not describe all the truths in number theory. Furthermore, the Principia could never prove itself to be free of paradoxes. The foundations of mathematics could never be completed.

Other Resolutions of Russell's Antinomy

The theory of types is not the only possible resolution of the paradox. Various alternative set theories, most modifying or excluding the Comprehension Axiom, have been developed to deal with Russell's Antinomy. Among them are Gödel-Bernays set theory, Zermelo-Fraenkel set theory, and Quine's New Foundations. Although Russell's theory of types is still used in areas of computer science and some philosophical investigations, it is no longer considered to be the best mathematical formulation of set theory. Today a version of Zermelo-Fraenkel theory is generally used.

Zermelo-Fraenkel Theory

Zermelo-Fraenkel theory, or ZF, resolves the paradox in a way not dissimilar to that used by Russell. Instead of the “top down” approach to sets embodied by the Comprehension Axiom, where any property is sufficient to define a set, ZF adopts a “bottom up” approach, where only those sets exist that can be explicitly constructed from already-constructed sets, starting with individual elements and following carefully constrained operations. This ZF conception of a set is said to be iterative, since new sets are built up from old sets.

In ZF, the Comprehension Axiom is restricted so that instead of being able to define a set of all things satisfying some property, we can only define a set of all things from an existing set which satisfy the property. This new axiom is known as the Restricted Comprehension Axiom or the Separation Axiom.

With the Separation Axiom, we can’t form a set of all sets which do not contain themselves, only a set of all sets from some preexisting set which do not contain themselves. Without a set of all sets which do not contain themselves, the contradiction discovered by Russell cannot be proven and Russell’s Antinomy doesn’t exist.

Although one axiom of ZF called the Axiom of Choice was initially highly controversial, today ZF is the generally accepted form of set theory. It too is subject to the constraints proven by Gödel's Incompleteness Theorems, and thus cannot provide the complete and consistent foundation for all of mathematics that Russell and his peers sought, but set theory remains a vital underlying branch of mathematics.

Self-Reference

Self-reference can get pretty loopy.

Self-reference lies at the heart of many paradoxes, Russell's Antinomy among them. Another famous example is the liar paradox, arising from the self-referential statement "This sentence is not true", or "I am lying". In the context of set theory, self-reference isn't about truth of statements but membership of sets. From this perspective, the set of all sets which do not contain themselves is like the set theory version of the liar sentence.

Russell recognized the role of self-reference in generating his paradox, concluding that "whatever involves all members of a collection must not itself be a member of the collection". In other words, self-reference had to be banished from the realm of set theory, a goal which Russell accomplished with his theory of types in the Principia. As Douglas Hofstadter puts it, "Principia Mathematica was a mammoth exercise in exorcising strange loops from logic, set theory, and number theory".

An example of the "infinite hallway" effect.

We can visualize self-reference, or "strange loopiness" in Hofstadter's lingo, using pictorial self-containment. A picture is said to be self-referential if it contains a copy of itself in miniature, which then must contain another even smaller copy, which itself contains another, ad infinitum. We can see this "infinite hallway" effect in the animation on the left of a self-referential picture of a room being constructed step by step. We also see this visual consequence of self-reference in this page's main image illustrating Russell's Antinomy. When we visualize a self-containing set with a blob containing a smaller copy of itself, that copy must include a smaller copy, and that copy a smaller copy, and so on. Unfortunately this is hard to draw beyond two or three copies.

As a side note, not all self-referential things are paradoxical and not all paradoxes are self-referential. For example, this page is self-referential, because of sentences like this, and is about a paradox, but I wouldn't go so far as to say it is paradoxical.

Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.

Related Links

Additional Resources

• For a good story about the life of Bertrand Russell and the search for the foundations of mathematics, I'd suggest reading the graphic novel Logicomix.

• If you're interested in self-reference, you should definitely look into Douglas Hofstadter's book I am a Strange Loop.

• For more about paradoxes exhibiting self-reference, check out the Stanford Encyclopedia of Philosophy's page about self-reference.

• For more on resolutions for Russell's paradox besides the theory of types, look at the third section of this page.

References

---

If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.