The Strangest Paradoxes in Set Theory
The Paradox of Enumeration
The paradox of enumeration is one of the basic problems of sets, first encountered prior to the development of modern set theory. It is related to the cardinality, or quantity of elements, of certain infinite sets, where attempts to determine whether two sets have the same cardinality lead to a paradox.
For example, consider the set of non-negative integers: 0, 1, 2, 3, and so on. Does this set have the same cardinality as the set of square numbers (numbers you can get by multiplying an integer by itself)? Let’s call these sets A and B respectively.
On one hand, you can pair each number in set A with its square in set B, which suggests that the cardinalities are the same. But on the other hand, every element contained in B is contained in A, and A contains elements that B doesn’t. So B is a proper subset of A. This suggests that A has a greater cardinality than B.
This issue can be resolved using a formal definition of cardinality in set theory. Two sets have the same cardinality if each element in one set can be matched in a one-to-one correspondence with an element in the other set, with no elements left over. Such a correspondence is known as a bijection between the sets. Under this definition, sets A and B have the same cardinality.
This modern notion of cardinality was developed by German-Russian mathematician Georg Cantor in the 1870s as part of his work on the creation of modern set theory. The sets in this particular case are called countably infinite, as they both have the same cardinality as the set of natural numbers. This cardinality is called ℵ₀ (aleph-null).
Cardinality of the Continuum
The set of real numbers, sometimes referred to as the continuum, has a greater cardinality than the set of natural numbers. This cardinality is denoted by a lowercase Fraktur c.
In particular, consider the power set of the natural numbers, meaning the set containing all possible subsets of the natural numbers. The cardinality of this power set, 2^ℵ₀, is equal to the cardinality of the continuum.
However, a seemingly counterintuitive result arises when considering the cardinality of the set of all possible pairs of real numbers. This set can be visualized as the set of all possible points in the coordinate plane. In order to find the cardinality of this set, we might first try seeing if it can be put in a bijection with the set of real numbers.
Given a decimal representation of a real number, the nth digit after the decimal point can be called digit number n. The digit in the ones place is digit number zero, and digits to the left are numbered with descending negative numbers. Now, for a given pair of real numbers (x, y), write out the digits of each one and then interlace these digits to create a new number a. The nth digit in x becomes the 2nth digit in a, and the mth digit in y becomes the (2m + 1)th digit in a. This will always result in a valid real number a. Indeed, this process is also fully reversible and can be used backward to convert any real number a into a pair of real numbers (x, y).
Thus a bijection exists between the set of real numbers and the set of pairs of real numbers, so the two sets have the same cardinality. In other words, there are equally as many numbers on the number line as there are points on the entire coordinate plane.
This result can also be proven with cardinal arithmetic, which comes down to demonstrating that c² = c. Since c = 2^ℵ₀, we get c² = (2^ℵ₀)² = 2^(2·ℵ₀). And 2 · ℵ₀ is just ℵ₀, so 2^(2·ℵ₀) = 2^ℵ₀ = c.
Russell’s Paradox
Russell’s Paradox was posited by English mathematician and logician Bertrand Russell in 1901, though it was actually first independently discovered by German mathematician Ernst Zermelo, who did not publish his work.
The paradox is as follows. If a set contains all sets that do not contain themselves, then does that set contain itself? If the answer is no, then the set does not contain itself, but that means it has to be included in itself, which is a contradiction. But if the answer is yes, then the set does contain itself, so it shouldn’t be included, which is also a contradiction.
Russell’s Paradox presented major problems for set theory around the beginning of the 20th century. Up to that point, the common conception of a set was as a collection of objects of some sort, with absolutely no restrictions on what those objects might be. However, Russell’s Paradox showed that this framework led to logical paradoxes. This was problematic for mathematicians, as much of math was built upon set theory.
Mathematicians at the time had to come up with consistent ground rules, or axioms, regarding what a set might be or contain. This led to the development of axiomatic set theory, as opposed to the naive set theory of the past. An axiomatization of set theory was put forward by Zermelo in 1908 in order to keep track of the assumptions made in his proof of the well-ordering theorem. In the process, this set of axioms resolved the paradoxes created by naive set theory.
In the 1920s, further work was done by Abraham Fraenkel, Thoralf Skolem, and Zermelo, which yielded an axiomatic set theory known as ZFC. To this day, mathematicians generally use ZFC as the canonical axiomatic set theory.
König’s Paradox
König’s paradox was published in 1905 by Hungarian mathematician Julius König. It can be stated like this: there are a countably infinite number of finitely long sequences of words. Of those word sequences, some of them are definitions of certain real numbers, so the number of finitely long real number definitions is also countably infinite. This means that the set of real numbers that can be finitely defined is countably infinite, forming a subset of the set of real numbers.
If the real numbers are well-ordered, there must be a first real number that cannot be finitely defined. But this statement counts as a finite definition of that real number, so it is self-contradictory.
Though this paradox can arise in naive set theory, it is resolved if one uses the rules of axiomatic set theory. In particular, it is true that a statement about a set can be represented as a set itself, which relies on a system known as Gödel numbers. However, the language of set theory simply does not allow for the definition of true statements in arithmetic using the tools of arithmetic itself. This is known as Tarski’s undefinability theorem, proven in 1933 by Polish-American mathematician Alfred Tarski.
König’s paradox is related to Berry’s paradox, which is another paradox related to the concept of defining numbers. Berry’s paradox arises from the phrase “the smallest positive integer not definable in under 60 letters.” This phrase would seem to define a certain positive integer, but that would make that number definable in under 60 letters, leading to a contradiction.
Richard’s Paradox
Richard’s paradox, created by French mathematician Jules Richard in 1905, is based on an alternate version of Cantor’s diagonal argument, which Cantor used to show that the real numbers have a greater cardinality than the natural numbers.
Similarly to König’s paradox, Richard’s paradox considers the set of all finite definitions of real numbers. Imagine arranging all of these definitions in increasing order of length, then ordering each group of definitions of a certain length in alphabetical order. Based on this ordered sequence of definitions, the corresponding real numbers can also be placed in a sequence.
Using this sequence, a new real number R can be constructed. The integer part of R is zero. Then look at the first decimal place of the first real number in the sequence. If the digit is 1, then append the digit 2 to R; otherwise, append the digit 1. Repeat this process using the nth digit of the nth real number in the sequence for the entire sequence, and you will end up with a new real number not on the list, similar to Cantor’s diagonal argument.
But the preceding statements make up a finite definition of a real number, meaning that real number should be on the list. So this is a contradiction. This paradox, like König’s, can be averted by axiomatic set theory. In order for this paradox to occur, one must be able to tell whether a given description applies to a set based on the rules of set theory itself. However, this type of self-reference isn’t actually allowed in axiomatic set theory. In essence, we simply disallow ourselves from doing the thing that causes the paradox in the first place, which is required in order for set theory to be consistent.
Skolem’s Paradox
Skolem’s paradox is a veridical paradox, a true yet seemingly absurd statement, regarding consistent axiomatizations of set theory. It was first discussed by Norwegian mathematician Thoralf Skolem in 1922.
It states that such axiomatizations may have a countable model, yet can be used to construct a sentence stating the existence of uncountable sets. This seems counterintuitive, as a countable model must contain only countable sets.
This paradox is based on two theorems. The first is Cantor’s theorem, proven by Georg Cantor, which states that the power set of a set must have a strictly greater cardinality than the original set. The second is the Löwenheim-Skolem theorem, stating that axioms satisfiable by an infinite structure are also satisfiable by a countable structure. Here, a “structure” consists of a set along with a collection of operations and relations applying to that set. This theorem was proven by Skolem and German mathematician Leopold Löwenheim.
Skolem noted that these two theorems seem to go against each other, even though this isn’t actually the case. The situation can be resolved by noting that for a particular model, the term “set” can only ever refer to a set that already exists within that model. In order for a set to be considered countable within a given model, that model must contain a suitable bijection, with this bijection being a set itself.
Skolem wrote that the notion of a countable set should be considered relative, as a set that is countable in one model may not necessarily be countable in another. His overall writings on this subject were intended as a critique of the idea of using set theory as a foundation for mathematics, as he was surprised when mathematicians of his time began to give serious consideration to the idea. However, his attempts were unsuccessful. Today, set theory is a widely regarded basis for mathematical logic, and Skolem’s paradox is primarily perceived as a simple quirk of, rather than a serious flaw with, set theory.
Further Reading
- Cantor’s Theorem on MathWorld
- Russell’s Paradox at Stanford Encyclopedia of Philosophy
- Zermelo-Fraenkel Set Theory on MathWorld
- The Löwenheim-Skolem Theorem at Stanford Encyclopedia of Philosophy
- Tarski’s Undefinability Theorem on MathWorld
Leave a Reply