Paradoxes of set theory
This article contains a discussion of paradoxes of set theory. As with most mathematical paradoxes, they generally reveal surprising and counter-intuitive mathematical results, rather than actual logical contradictions within modern axiomatic set theory.
Basics
Cardinal numbers
as conceived by Georg Cantor assumes the existence of infinite sets. As this assumption cannot be proved from first principles it has been introduced into axiomatic set theory by the axiom of infinity, which asserts the existence of the set N of natural numbers. Every infinite set which can be enumerated by natural numbers is the same size as N, and is said to be countable. Examples of countably infinite sets are the natural numbers, the even numbers, the prime numbers, and also all the rational numbers, i.e., the fractions. These sets have in common the cardinal number |N| = , a number greater than every natural number.Cardinal numbers can be defined as follows. Define two sets to have the same size by: there exists a bijection between the two sets. Then a cardinal number is, by definition, a class consisting of all sets of the same size. To have the same size is an equivalence relation, and the cardinal numbers are the equivalence classes.
Ordinal numbers
Besides the cardinality, which describes the size of a set, ordered sets also form a subject of set theory. The axiom of choice guarantees that every set can be well-ordered, which means that a total order can be imposed on its elements such that every nonempty subset has a first element with respect to that order. The order of a well-ordered set is described by an ordinal number. For instance, 3 is the ordinal number of the set with the usual order 0 < 1 < 2; and ω is the ordinal number of the set of all natural numbers ordered the usual way. Neglecting the order, we are left with the cardinal number |N| = |ω| = .Ordinal numbers can be defined with the same method used for cardinal numbers. Define two well-ordered sets to have the same order type by: there exists a bijection between the two sets respecting the order: smaller elements are mapped to smaller elements. Then an ordinal number is, by definition, a class consisting of all well-ordered sets of the same order type. To have the same order type is an equivalence relation on the class of well-ordered sets, and the ordinal numbers are the equivalence classes.
Two sets of the same order type have the same cardinality. The converse is not true in general for infinite sets: it is possible to impose different well-orderings on the set of natural numbers that give rise to different ordinal numbers.
There is a natural ordering on the ordinals, which is itself a well-ordering. Given any ordinal α, one can consider the set of all ordinals less than α. This set turns out to have ordinal number α. This observation is used for a different way of introducing the ordinals, in which an ordinal is equated with the set of all smaller ordinals. This form of ordinal number is thus a canonical representative of the earlier form of equivalence class.
Power sets
All subsets of a set S form the power set P. Georg Cantor proved that the power set is always larger than the set, i.e., |P| > |S|. A special case of Cantor's theorem is that the set of all real numbers R cannot be enumerated by natural numbers, that is, R is uncountable: |R| > |N|.Paradoxes of the infinite sets
Instead of relying on ambiguous descriptions such as "that which cannot be enlarged" or "increasing without bound", set theory provides definitions for the term infinite set to give an unambiguous meaning to phrases such as "the set of all natural numbers is infinite". Just as for finite sets, the theory makes further definitions which allow us to consistently compare two infinite sets as regards whether one set is "larger than", "smaller than", or "the same size as" the other. But not every intuition regarding the size of finite sets applies to the size of infinite sets, leading to various apparently paradoxical results regarding enumeration, size, measure and order.Paradoxes of enumeration
Before set theory was introduced, the notion of the size of a set had been problematic. It had been discussed by Galileo Galilei and Bernard Bolzano, among others. Are there as many natural numbers as squares of natural numbers when measured by the method of enumeration?- The answer is yes, because for every natural number n there is a square number n2, and likewise the other way around.
- The answer is no, because the squares are a proper subset of the naturals: every square is a natural number but there are natural numbers, like 2, which are not squares of natural numbers.
Hilbert's paradox of the Grand Hotel illustrates more paradoxes of enumeration.
''Je le vois, mais je ne crois pas''
"I see it but I don't believe," Cantor wrote to Richard Dedekind after proving that the set of points of a square has the same cardinality as that of the points on just an edge of the square: the cardinality of the continuum.This demonstrates that the "size" of sets as defined by cardinality alone is not the only useful way of comparing sets. Measure theory provides a more nuanced theory of size that conforms to our intuition that length and area are incompatible measures of size.
The evidence strongly suggests that Cantor was quite confident in the result itself and that his comment to Dedekind refers instead to his then-still-lingering concerns about the validity of his proof of it. Nevertheless, Cantor's remark would also serve nicely to express the surprise that so many mathematicians after him have experienced on first encountering a result that is so counter-intuitive.
Paradoxes of well-ordering
In 1904 Ernst Zermelo proved by means of the axiom of choice that every set can be well-ordered. In 1963 Paul J. Cohen showed that in Zermelo–Fraenkel set theory without the axiom of choice it is not possible to prove the existence of a well-ordering of the real numbers.However, the ability to well order any set allows certain constructions to be performed that have been called paradoxical. One example is the Banach–Tarski paradox, a theorem widely considered to be nonintuitive. It states that it is possible to decompose a ball of a fixed radius into a finite number of pieces and then move and reassemble those pieces by ordinary translations and rotations to obtain two copies from the one original copy. The construction of these pieces requires the axiom of choice; the pieces are not simple regions of the ball, but complicated subsets.
Paradoxes of the Supertask
In set theory, an infinite set is not considered to be created by some mathematical process such as "adding one element" that is then carried out "an infinite number of times". Instead, a particular infinite set is said to already exist, "by fiat", as an assumption or an axiom. Given this infinite set, other infinite sets are then proven to exist as well, as a logical consequence. But it is still a natural philosophical question to contemplate some physical action that actually completes after an infinite number of discrete steps; and the interpretation of this question using set theory gives rise to the paradoxes of the supertask.The diary of Tristram Shandy
, the hero of a novel by Laurence Sterne, writes his autobiography so conscientiously that it takes him one year to lay down the events of one day. If he is mortal he can never terminate; but if he lived forever then no part of his diary would remain unwritten, for to each day of his life a year devoted to that day's description would correspond.The Ross-Littlewood paradox
An increased version of this type of paradox shifts the infinitely remote finish to a finite time. Fill a huge reservoir with balls enumerated by numbers 1 to 10 and take off ball number 1. Then add the balls enumerated by numbers 11 to 20 and take off number 2. Continue to add balls enumerated by numbers 10n - 9 to 10n and to remove ball number n for all natural numbers n = 3, 4, 5,.... Let the first transaction last half an hour, let the second transaction last quarter an hour, and so on, so that all transactions are finished after one hour. Obviously the set of balls in the reservoir increases without bound. Nevertheless, after one hour the reservoir is empty because for every ball the time of removal is known.The paradox is further increased by the significance of the removal sequence. If the balls are not removed in the sequence 1, 2, 3,... but in the sequence 1, 11, 21,... after one hour infinitely many balls populate the reservoir, although the same amount of material as before has been moved.