Paradoxes of Set Theory

From the paradise, that Cantor created for us, no one can expel us" - declared the great mathematician David Hilbert (1862−1943) regarding the set theory of Georg Cantor (1845−1918). Such was the feeling of delight from the new "toy" among the mathematicians of that time. Set theory was born in 1873 when Cantor introduced the concept of a set and established that the real numbers are uncountable. Initially, the new theory helped solve a number of problems. However, very soon a series of contradictions were revealed in it.

The best-known paradoxes of set theory are

Russell's paradox
Cantor's paradox
Burali-Forti paradox
Richard's paradox

Consider these paradoxes in more detail.

Russell's Paradox

The Russell's paradox has been discovered in \(1901\) by the British philosopher and mathematician Bertrand Russell \(\left( {1872 - 1970} \right).\) It was also independently found in \(1899\) by the German mathematician Ernst Zermelo \(\left( {1871 - 1953} \right),\) but he did not publish the paradox.

The Russell's paradox deals with the set of all sets which are not members of themselves. For example, the set of all stars in the universe is not a star itself. Let's denote such a set of all sets by \(R.\)

Suppose that \(R\) is not a member of itself. Then by definition of \(R\) it must contain itself, that is, \(R\) must be a member of itself.
Suppose now that \(R\) is a member of itself. Then by definition of \(R\) it must not belong to itself, that is, \(R\) must not be a member of itself.

In both cases we have a contradiction. This contradiction is just Russell's paradox.

This paradox arises in Cantor's naive set theory which is based on predicate logic. Its formal (simplified) derivation can be obtained as follows:

Within naive set theory, the statement

\[\exists y\,\forall x\left( {x \in y \Leftrightarrow P\left( x \right)} \right)\]

is true for any predicate or property \({P\left( x \right)}.\) This means that for any predicate \({P\left( x \right)},\) there exists a set \(y\) whose elements \(x\) satisfy the predicate.

Let \({P\left( x \right)}\) be defined by the formula \(x \not\in x.\) In this case, the predicate \({P\left( x \right)}\) means that a set \(x\) does not contain itself, that is, it defines the above set \(R.\) Replacing \(y\) with \(R,\) we rewrite the logical statement in the form

\[\exists R\,\forall x\left( {x \in R \Leftrightarrow x \notin x} \right).\]

This is valid for any set \(x\) including \(x = R.\) As a result, we get a symbolic expression of Russell's paradox:

\[{R \in R \Leftrightarrow R \not\in R}.\]

There is no error in Russell's paradox: it does prove the inconsistency of naive set theory. One of the ways to get rid of the contradiction is to limit the conditions under which sets are formed. The idea is to exclude too large sets like the Russell set \(R\) and other contradictory sets. This approach was implemented in axiomatic set theory known as \(ZFC.\)

Cantor's Paradox

Cantor's paradox has been discovered by Cantor's himself in \(1899.\)

German mathematician Georg Cantor — Fig.2 Georg Cantor (1845-1918)

Recall Cantor's theorem which states that, for any set \(A,\) its power set \(\mathcal{P}\left( A \right)\) has a strictly greater cardinality than \(A:\)

\[\left| {\mathcal{P}\left( A \right)} \right| \gt \left| A \right|.\]

We denote the set of all sets by \(U.\) Since \(U\) contains all sets, it must also contain all elements of \(\mathcal{P}\left( U \right).\) Therefore, the power set \(\mathcal{P}\left( U \right)\) is a subset of \(U,\) so the cardinality of \(\mathcal{P}\left( U \right)\) is less than or equal to the cardinality of \(U.\) This, however, immediately contradicts Cantor's theorem.

Cantor's paradox demonstrates that the assumption of the existence of a set of all sets leads to a contradiction. Hence, the theory that allows such sets is inconsistent.

Burali-Forti Paradox

This paradox is named after the Italian mathematician Cesare Burali-Forti \(\left( {1861 - 1931} \right)\) who was an assistant of Giuseppe Peano \(\left( {1858 - 1932} \right).\)

Burali-Forti paradox appeared in \(1897.\) It deals with ordinal numbers and arises in the following way:

According to von Neumann's construction, an ordinal number \(\alpha\) is defined as the well-ordered set of all smaller ordinals:

\[\alpha = \left\{ {\beta \mid \beta \lt \alpha } \right\},\]

where the relation \(\lt\) implies set membership, that is, \(\beta \lt \alpha \text{ if } \beta \in \alpha .\)

Let \(\Omega\) be the set of all ordinal numbers arranged by the relation \(\lt.\) The set \(\Omega\) is well-ordered, so it has its own ordinal number \(\gamma.\)

The ordinal \(\gamma\) must be greater than any ordinal number in \(\Omega.\) However, this contradicts the fact that \(\Omega\) contains all ordinal numbers.

This contradiction shows that there is no set of all ordinals!

Richard's Paradox

This paradox was first described in \(1905\) by the French mathematician Jules Antoine Richard \(\left( {1862 - 1956} \right).\) It is related to the concept of definability and Cantor's diagonal argument.

Let's take a natural language, say, English or French (Richard was French). Certain expressions of this language can describe real numbers. For example,

The Pi number can be described as "the ratio of the circumference of a circle to its diameter.
The number \(3.25\) can be described as "the real number the integer part of which is \(3\) and the decimal part is \(0.25.\)

We arrange all phrases describing real numbers in lexicographic order. As a result, we get an infinite list in which each phrase is mapped to a real number: \(r_1, r_2, r_3, \ldots\)

Now we apply diagonalization over decimal expansions and construct a new real number \(r\) which is not in this list. Let the integer part of \(R\) be equal to \(0.\) Then we use the following rule: the \(n\text{th}\) decimal place of \(r\) is \(1\) if the \(n\text{th}\) decimal place of \(r_n\) is not \(1.\) Respectively, the \(n\text{th}\) decimal place of \(r\) is \(2\) if the \(n\text{th}\) decimal place of \(r_n\) is \(1.\)

The number \(r\) must be among the numbers \(r_n\) since we have described it using the same language. However, after applying the diagonalization, it is not in the list of phrases! This is the contradiction!

We have considered here only some of the most famous paradoxes. In fact, their list is much wider. For instance, one can mention such paradoxes as the Banach-Tarski paradox, König's paradox, Skolem's paradox, Berry paradox, and others.

In response to set theoretical paradoxes, mathematicians developed axiomatic set theories, which, through various axioms, define what can and cannot be sets. The most common version of the axiomatic set theory is Zermelo-Fraenkel set theory with the Axiom of Choice \(\left({ZFC}\right).\)