HOME

TheInfoList



OR:

This article contains a discussion of paradoxes of set theory. As with most mathematical
paradox A paradox is a logically self-contradictory statement or a statement that runs contrary to one's expectation. It is a statement that, despite apparently valid reasoning from true premises, leads to a seemingly self-contradictory or a logically u ...
es, they generally reveal surprising and counter-intuitive mathematical results, rather than actual logical contradictions within modern
axiomatic set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concer ...
.


Basics


Cardinal numbers

Set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concer ...
as conceived by
Georg Cantor Georg Ferdinand Ludwig Philipp Cantor ( , ;  – January 6, 1918) was a German mathematician. He played a pivotal role in the creation of set theory, which has become a fundamental theory in mathematics. Cantor established the importance o ...
assumes the existence of infinite sets. As this assumption cannot be proved from first principles it has been introduced into
axiomatic set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concer ...
by the
axiom of infinity In axiomatic set theory and the branches of mathematics and philosophy that use it, the axiom of infinity is one of the axioms of Zermelo–Fraenkel set theory. It guarantees the existence of at least one infinite set, namely a set containing th ...
, 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 number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s, and also all the
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ratio ...
s, i.e., the fractions. These sets have in common the
cardinal number In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. Th ...
, 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 In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
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 In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relatio ...
, and the cardinal numbers are the
equivalence class In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
es.


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 In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
guarantees that every set can be
well-ordered In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-o ...
, 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 In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the least ...
. 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,  = , ω,  =  \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 In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
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 In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relatio ...
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
subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...
s of a set ''S'' (all possible choices of its elements), we obtain the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is p ...
''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 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 In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable. Properties The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only set th ...
to give an unambiguous meaning to phrases such as "the set of all natural numbers is infinite". Just as for
finite sets In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. T ...
, 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 Galileo di Vincenzo Bonaiuti de' Galilei (15 February 1564 – 8 January 1642) was an Italian astronomer, physicist and engineer, sometimes described as a polymath. Commonly referred to as Galileo, his name was pronounced (, ). He was ...
and
Bernard Bolzano Bernard Bolzano (, ; ; ; born Bernardus Placidus Johann Gonzal Nepomuk Bolzano; 5 October 1781 – 18 December 1848) was a Bohemian mathematician, logician, philosopher, theologian and Catholic priest of Italian extraction, also known for his li ...
, 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 ''n''2, and likewise the other way around. * The answer is no, because the squares are a
proper subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...
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 In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
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 Hilbert's paradox of the Grand Hotel (colloquial: Infinite Hotel Paradox or Hilbert's Hotel) is a thought experiment which illustrates a counterintuitive property of infinite sets. It is demonstrated that a fully occupied hotel with infinitely ...
for more on paradoxes of enumeration.


''Je le vois, mais je ne crois pas''

"I see it but I don't believe," Cantor wrote to
Richard Dedekind Julius Wilhelm Richard Dedekind (6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to number theory, abstract algebra (particularly ring theory), and the axiomatic foundations of arithmetic. His ...
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 In set theory, the cardinality of the continuum is the cardinality or "size" of the set of real numbers \mathbb R, sometimes called the continuum. It is an infinite cardinal number and is denoted by \mathfrak c (lowercase fraktur "c") or , \mathb ...
. This demonstrates that the "size" of sets as defined by cardinality alone is not the only useful way of comparing sets.
Measure theory In mathematics, the concept of a measure is a generalization and formalization of geometrical measures (length, area, volume) and other common notions, such as mass and probability of events. These seemingly distinct concepts have many simi ...
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. F. Q. Gouvêa
"Was Cantor Surprised?"
''
American Mathematical Monthly ''The American Mathematical Monthly'' is a mathematical journal founded by Benjamin Finkel in 1894. It is published ten times each year by Taylor & Francis for the Mathematical Association of America. The ''American Mathematical Monthly'' is an e ...
'', 118, March 2011, 198–209.
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 Ernst Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logician and mathematician, whose work has major implications for the foundations of mathematics. He is known for his role in developing Zermelo–Fraenkel axiomatic se ...
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 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 The Banach–Tarski paradox is a theorem in set-theoretic geometry, which states the following: Given a solid ball in three-dimensional space, there exists a decomposition of the ball into a finite number of disjoint subsets, which can then be p ...
, 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 number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal ...
s) 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 Tristram may refer to: Literature * the title character of ''The Life and Opinions of Tristram Shandy, Gentleman'', a novel by Laurence Sterne * the title character of ''Tristram of Lyonesse'', an epic poem by Algernon Charles Swinburne *"Tristra ...
, the hero of a novel by
Laurence Sterne Laurence Sterne (24 November 1713 – 18 March 1768), was an Anglo-Irish novelist and Anglican cleric who wrote the novels ''The Life and Opinions of Tristram Shandy, Gentleman'' and '' A Sentimental Journey Through France and Italy'', published ...
, 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 10''n'' - 9 to 10''n'' 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 In mathematical logic, Russell's paradox (also known as Russell's antinomy) is a set-theoretic paradox discovered by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains a ...
. 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 system A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system. A for ...
s actually propose to be talking about.


Early paradoxes: the set of all sets

In 1897 the Italian mathematician
Cesare Burali-Forti Cesare Burali-Forti (13 August 1861 – 21 January 1931) was an Italian mathematician, after whom the Burali-Forti paradox is named. Biography Burali-Forti was born in Arezzo, and was an assistant of Giuseppe Peano in Turin from 1894 to 189 ...
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 David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician, one of the most influential mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many a ...
and
Richard Dedekind Julius Wilhelm Richard Dedekind (6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to number theory, abstract algebra (particularly ring theory), and the axiomatic foundations of arithmetic. His ...
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 Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ar ...
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 . 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 The barber paradox is a puzzle derived from Russell's paradox. It was used by Bertrand Russell as an illustration of the paradox, though he attributes it to an unnamed person who suggested it to him.''The Philosophy of Logical Atomism'', reprin ...
, states: The male barber who shaves all and only men who do not 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 The Grelling–Nelson paradox is an antinomy, or a semantic self-referential paradox, concerning the applicability to itself of the word "heterological", meaning "inapplicable to itself". It was formulated in 1908 by Kurt Grelling and Leonard Nel ...
, 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 Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics. Unlike axiomatic set theories, which are defined using formal logic, naive set theory is defined informally, in natural language. It des ...
. 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 \varphi(a,x) in the language of set theory which holds exactly when a is a code for a finite proposition about a set, x is a set, and a holds for x. This result is known as
Tarski's indefinability theorem Tarski's undefinability theorem, stated and proved by Alfred Tarski in 1933, is an important limitative result in mathematical logic, the foundations of mathematics, and in formal semantics. Informally, the theorem states that ''arithmetical truth ...
; 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 ''n''th decimal of the ''n''th real number defined by the set ''E''; we form a number ''N'' having zero for the integral part and ''p'' + 1 for the ''n''th 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 ''n''th number by the ''n''th 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 Leopold Löwenheim �le:o:pɔl̩d ˈlø:vɛnhaɪm(26 June 1878 in Krefeld – 5 May 1957 in Berlin) was a German mathematician doing work in mathematical logic. The Nazi regime forced him to retire because under the Nuremberg Laws he was conside ...
(1915) the Norwegian logician
Thoralf Skolem Thoralf Albert Skolem (; 23 May 1887 – 23 March 1963) was a Norwegian mathematician who worked in mathematical logic and set theory. Life Although Skolem's father was a primary school teacher, most of his extended family were farmers. Skolem ...
showed in 1922 that every consistent theory of
first-order predicate calculus First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
, such as set theory, has an at most countable model. However,
Cantor's theorem In mathematical set theory, Cantor's theorem is a fundamental result which states that, for any set A, the set of all subsets of A, the power set of A, has a strictly greater cardinality than A itself. For finite sets, Cantor's theorem can b ...
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).


See also

*
Proof of impossibility In mathematics, a proof of impossibility is a proof that demonstrates that a particular problem cannot be solved as described in the claim, or that a particular set of problems cannot be solved in general. Such a case is also known as a negative p ...
* Berry paradox


Notes


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: ''Grundzüge 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 Alfred North Whitehead (15 February 1861 – 30 December 1947) was an English mathematician and philosopher. He is best known as the defining figure of the philosophical school known as process philosophy, which today has found applicat ...
, 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.


External links


Principia Mathematica
by
Timothy Gowers Sir William Timothy Gowers, (; born 20 November 1963) is a British mathematician. He is Professeur titulaire of the Combinatorics chair at the Collège de France, and director of research at the University of Cambridge and Fellow of Trinity ...
* * {{Mathematical logic
Set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concer ...
Set theory