Paradoxes

Basics

Cardinal numbers

Set theory 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 (cardinality) 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| = \aleph_0 (aleph-nought), 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 (a one-to-one
correspondence between the elements). 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 {0, 1, 2} 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| = |?| =  \aleph_0.

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

By forming all subsets of a set S (all possible choices of its elements), we
obtain the power set P(S). Georg Cantor proved that the power set is always
larger than the set, i.e., |P(S)| > |S|. A special case of Cantor's theorem
proves that the set of all real numbers R cannot be enumerated by natural
numbers. R is uncountable: |R| > |N|.


Paradoxes of the infinite set

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.

By defining the notion of the size of a set in terms of its cardinality, the
issue can be settled. Since there is a bijection between the two sets
involved, this follows in fact directly from the definition of the cardinality
of a set.

See Hilbert's paradox of the Grand Hotel for more on paradoxes of enumeration.

Je le vois, mais je ne crois pas

"I see it but I can't believe it", 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 a side 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.


Paradoxes of well-ordering

In 1904 Ernst Zermelo proved by means of the axiom of choice (which was
introduced for this reason) that every set can be well-ordered. In 1963
Paul J. Cohen showed that using the axiom of choice is essential to
well-ordering the real numbers; no weaker assumption suffices.

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 (with no scaling) 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 (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 should define an ordinal number ? which does not belong to the set.
On the other hand, ? must belong to the set of all ordinal numbers.
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

Konig's paradox

In 1905, the Hungarian mathematician Julius Konig 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
Godel numbers, there is no formula \phi(a,x) in the language of set theory
which holds exactly when a is a code for a finite description of a set and
this description is a true description of the set 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 Konig'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 Lowenheim and Skolem
Also called Skolem's paradox

Based upon work of the German mathematician Leopold Lowenheim (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).[edit] )(see also Berry paradox)

References

    * G. Cantor: Gesammelte Abhandlungen mathematischen und philosophischen
      Inhalts, E. Zermelo (Ed.), Olms, Hildesheim 1966.
    * H. Meschkowski, W. Nilson: Georg Cantor - Briefe, Springer, Berlin 1991.
    * A. Fraenkel: Einleitung in die Mengenlehre, Springer, Berlin 1923.
    * A.A. Fraenkel, A. Levy: Abstract Set Theory, North Holland,
      Amsterdam 1976.
    * F. Hausdorff: Grundzuge der Mengenlehre, Chelsea, New York 1965.
    * B. Russell: The principles of mathematics I, Cambridge 1903.
    * B. Russell: On some difficulties in the theory of transfinite numbers
         and order types, Proc. London Math. Soc. (2) 4 (1907) 29-53.
    * P.J. Cohen: Set Theory and the Continuum Hypothesis, Benjamin, New
      York 1966.
    * S. Wagon: The Banach-Tarski-Paradox, Cambridge University Press,
      Cambridge 1985.
    * A.N. Whitehead, B. Russell: Principia Mathematica I, Cambridge Univ.
      Press, Cambridge 1910, p. 64.
    * E. Zermelo: Neuer Beweis fü'r die Mö'glichkeit einer
      Wohlordnung, Math. Ann. 65 (1908) p. 107-128.