Tristram Shandy paradox (1759)

Named after a fictional character created by English author Lawrence Sterne (1713-1768).

Shandy finds that in two years of writing he has covered two days of his autobiography and doubts whether he will ever complete the work.

However, even at that poor rate he could finish the work provided that he had an infinite amount of time in which to do so.

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 (such as the set of all natural numbers) 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

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.

Paradoxes of proof and definability

For all its usefulness in resolving questions regarding infinite sets, naive set theory has some fatal flaws. In particular, it is prey to logical paradoxes such as those exposed by Russell’s paradox. The discovery of these paradoxes revealed that not all sets which can be described in the language of naive set theory can actually be said to exist without creating a contradiction. The 20th century saw a resolution to these paradoxes in the development of the various axiomatizations of set theories such as ZFC and NBG in common use today. However, the gap between the very formalized and symbolic language of these theories and our typical informal use of mathematical language results in various paradoxical situations, as well as the philosophical question of exactly what it is that such formal systems actually propose to be talking about.

Early paradoxes: the set of all sets

In 1897 the Italian mathematician Cesare Burali-Forti discovered that there is no set containing all ordinal numbers. As every ordinal number is defined by a set of smaller ordinal numbers, the well-ordered set Ω of all ordinal numbers (if it exists) fits the definition and is itself an ordinal. On the other hand, no ordinal number can contain itself, so Ω cannot be an ordinal. Therefore, the set of all ordinal numbers cannot exist.

By the end of the 19th century Cantor was aware of the non-existence of the set of all cardinal numbers and the set of all ordinal numbers. In letters to David Hilbert and Richard Dedekind he wrote about inconsistent sets, the elements of which cannot be thought of as being all together, and he used this result to prove that every consistent set has a cardinal number.

After all this, the version of the “set of all sets” paradox conceived by Bertrand Russell in 1903 led to a serious crisis in set theory. Russell recognized that the statement x = x is true for every set, and thus the set of all sets is defined by {x | x = x}. In 1906 he constructed several paradox sets, the most famous of which is the set of all sets which do not contain themselves. Russell himself explained this abstract idea by means of some very concrete pictures. One example, known as the Barber paradox, states: The male barber who shaves all and only men who don’t shave themselves has to shave himself only if he does not shave himself.

There are close similarities between Russell’s paradox in set theory and the Grelling–Nelson paradox, which demonstrates a paradox in natural language.

Paradoxes by change of language

König’s paradox

In 1905, the Hungarian mathematician Julius König published a paradox based on the fact that there are only countably many finite definitions. If we imagine the real numbers as a well-ordered set, those real numbers which can be finitely defined form a subset. Hence in this well-order there should be a first real number that is not finitely definable. This is paradoxical, because this real number has just been finitely defined by the last sentence. This leads to a contradiction in naive set theory.

This paradox is avoided in axiomatic set theory. Although it is possible to represent a proposition about a set as a set, by a system of codes known as Gödel numbers, there is no formula {\displaystyle \varphi (a,x)} in the language of set theory which holds exactly when {\displaystyle a} is a code for a finite proposition about a set, {\displaystyle x} is a set, and {\displaystyle a} holds for {\displaystyle x}. This result is known as Tarski’s indefinability theorem; it applies to a wide class of formal systems including all commonly studied axiomatizations of set theory.

Richard’s paradox

In the same year the French mathematician Jules Richard used a variant of Cantor’s diagonal method to obtain another contradiction in naive set theory. Consider the set A of all finite agglomerations of words. The set E of all finite definitions of real numbers is a subset of A. As A is countable, so is E. Let p be the nth decimal of the nth real number defined by the set E; we form a number N having zero for the integral part and p + 1 for the nth decimal if p is not equal either to 8 or 9, and unity if p is equal to 8 or 9. This number N is not defined by the set E because it differs from any finitely defined real number, namely from the nth number by the nth digit. But N has been defined by a finite number of words in this paragraph. It should therefore be in the set E. That is a contradiction.

As with König’s paradox, this paradox cannot be formalized in axiomatic set theory because it requires the ability to tell whether a description applies to a particular set (or, equivalently, to tell whether a formula is actually the definition of a single set).

Paradox of Löwenheim and Skolem

Based upon work of the German mathematician Leopold Löwenheim (1915) the Norwegian logician Thoralf Skolem showed in 1922 that every consistent theory of first-order predicate calculus, such as set theory, has an at most countable model. However, Cantor’s theorem proves that there are uncountable sets. The root of this seeming paradox is that the countability or noncountability of a set is not always absolute, but can depend on the model in which the cardinality is measured. It is possible for a set to be uncountable in one model of set theory but countable in a larger model (because the bijections that establish countability are in the larger model but not the smaller one).