Sets that are Elements of Themselves: Verboten

Russell’s Paradox.

Can a set be an element of itself? A simple example will provide an answer to this question.

Let us define a set to be small if it has less than 100 elements. There are clearly an enormous number of small sets. For example,

The set of continents.
The set of Platonic solids.
The set of Books of the Bible.
The set of colours in the rainbow.

Let us collect all the small sets in one place:

$\displaystyle \mathcal{S} := \{ X : X\mbox{\ is a small set\ }\}$

It is clear that ${\mathcal{S}}$ has numerous members, so it is not a small set. That is, ${\mathcal{S}\notin\mathcal{S}}$ .

We define a set to be large if it is not small. Thus, a large set has at least 100 elements. There is clearly an abundance of large sets. Let us collect all the large sets in one place:

$\displaystyle \mathcal{L} := \{ X : X\mbox{\ is a large set\ }\}$

Clearly, ${\mathcal{L}}$ is vast: it satisfies the requirement to be a large set. Thus, ${\mathcal{L}}$ is a member of itself: ${\mathcal{L}\in\mathcal{L}}$ .

So, we see that an arbitrarily chosen set ${X}$ may or may not be an element of itself. Let us collect together all the sets that are not elements of themselves:

$\displaystyle \mathfrak{L} := \{ X : X \notin X \} \,.$

The question posed by Bertrand Russell was “Is ${\mathfrak{L}}$ a member of itself?”

If ${\mathfrak{L}\notin\mathfrak{L}}$ , then it satisfies the condition for membership of ${\mathfrak{L}}$ , so ${\mathfrak{L}\in\mathfrak{L}}$ .
If ${\mathfrak{L}\in\mathfrak{L}}$ , then it fails to satisfy the condition for membership, so ${\mathfrak{L}\notin\mathfrak{L}}$ .

In either case, there is an unavoidable contradiction.

This is the paradox announced by Russell in 1903. In fact, it had been discovered in 1899 by the German mathematician Ernst Zermelo.

Gottlob Frege

According to Wikipedia, the German logician Gottlob Frege is widely considered to be the greatest logician since Aristotle, and one of the most profound philosophers of mathematics ever. In 1903, As Vol. 2 of Frege’s work Grundgesetze der Arithmetik (Basic Laws of Arithmetic) was about to go to press, Russell wrote to him pointing out that the paradox followed from Frege’s Basic Law V, thereby fatally undermining Frege’s work.

This had to have caused great distress, but Frege was stoical in his reaction, and included a remarkably honest comment in his book:

“Hardly anything more unfortunate can befall a scientific writer than to have one of the foundations of his edifice shaken after the work is finished. This was the position I was placed in by a letter of Mr Bertrand Russell, just when the printing of this volume was nearing its completion.”

The Remedy

The paradox had serious consequences for the foundations of mathematics. In symbolic logic, the definition of “implication” is that a proposition, ${P}$ , implies another, ${Q}$ , if either ${Q}$ is true or ${P}$ is false (or both):

$\displaystyle [P \implies Q] \equiv [\lnot P \lor Q ]$

Thus, any proposition ${Q}$ whatsoever can be said to follow from a proposition ${P}$ that is false; see, for example, Kuratowski (1961). Therefore, a contradiction such as Russell’s paradox is disastrous for the axiomatic basis of set theory: if any formula can be proven true, the distinction between truth and falsity is destroyed.

In 1908, Zermelo proposed an axiomatization of set theory that avoided the problematic paradoxes. Modifications to this axiomatic theory, formulated around 1920, resulted in the axiomatic system called ZFC (for Zermelo-Fraenkel and Axiom of Choice). In this system, sets are prohibited from being elements of themselves. Such entities form “proper classes”, which are not sets.

In Zermelo-Fraenkel set theory, the collection ${\mathcal{S}}$ of small sets defined above is a set, but the collection ${\mathcal{L}}$ of large sets is not. ZFC remains the most popular axiomatic set theory today, although there are reasons to favour an alternative scheme formulated by von Neumann, Bernays and Gödel, the NBG system.

Sources

${\bullet}$ Kuratowski, Kazimierz, 1961: Introduction to Set Theory and Topology. Pergamon Press.

ThatsMaths