Cardinality: Difference between revisions

For other uses, see Cardinality (disambiguation).

A bijection, comparing a set of apples to a set of oranges, showing they have the same cardinality.

In mathematics, the cardinality of a finite set is the number of its elements, and is therefore a measure of size of the set. Since the discovery by Georg Cantor, in the late 19th century, of different sizes of infinite sets, the term cardinality was coined for generalizing to infinite sets the concept of the number of elements.

More precisely, two sets have the same cardinality if there exists a one-to-one correspondence between them. In the case of finite sets, the common operation of counting consists of establishing a one-to-one correspondence between a given set and the set of the ⁠$n$⁠ first natural numbers, for some natural number ⁠$n$⁠. In this case, ⁠$n$⁠ is the cardinality of the set.

A set is infinite if the counting operation never finishes, that is, if its cardinality is not a natural number. The basic example of an infinite set is the set of all natural numbers.

The great discovery of Cantor is that infinite sets of apparently different size may have the same cardinality, and, nevertheless, there are infinitely many different cardinalities. For example, the even numbers, the prime numbers and the polynomials whose coefficients are rational number have the same cardinality as the natural numbers. The set of the real numbers has a greater cardinality than the natural numbers, and has the same cardinality as the interval ⁠$[0,1]$⁠ and as every Euclidean space of any dimension. For every set, its power set (the set of all its subsets) has a greater cardinality.

Cardinalities are represented with cardinal numbers, which are specific sets of a given cardinality, which have been chosen once for all. Some infinite cardinalities have been given a specific name, such as ⁠$\aleph _{0}$⁠ for the cardinality of the natural numbers and ⁠${\mathfrak {c}}$⁠, the cardinality of the continuum, for the cardinality of the real numbers.

Basics

Finite cardinalities

Given a finite set, its cardinality is what is commonly called its number of elements.

The standard way to compute this number of elements is by counting, that is, by labelling the set elements by the first natural numbers, with no gap and no repetition. Mathematically, counting amounts to construct a bijective function from the first natural numbers to the set to be counted.

The number of elements of a finite set is the largest natural number reached by counting its elements. So, a set ⁠$S$⁠ has ⁠$n$⁠ elements if there is a bijective function from the set $\{1,2,\ldots ,n\}$ to ⁠$S$⁠. One says that the cardinality of ⁠$S$⁠ is ⁠$n$⁠. If the counting process never finishes, one has an infinite set.

A proof by induction is needed for proving that the result of counting does not depend on the order in which the elements are counted. This is expressed by the fact that, if ⁠$m<n$⁠ there is no injective function, and thus no bijective function, from $\{1,2,\ldots ,n\}$ to $\{1,2,\ldots ,m\}.$ A variant of this property is often referred to as the pigeonhole principle.

The latter poperty is equivalent with the fact that , if ⁠$m<n$⁠ there is no surjective function from $\{1,2,\ldots ,m\}$ to $\{1,2,\ldots ,n\}.$ This means that for finite sets, the fifth Euclid's common notion applies, which states that "the whole is greater than the part". This principle is not valid for infinite sets, and this is presumably the main reason for which most mathematicians were reluctant to study infinite sets, before the 20th century (see Galileo's paradox).

General case

Cardinalities, like natural numbers, are difficult to define formally, and this is by their basic properties that there are best introduced. Therefore, in this section, the cardinality of a set is not defined as a value, but only the comparison between cardinalities (equality and greater than) is defined and studied. (This is to compare with the natural numbers for which operations and ordering are defined a long time before any proper definition of the concept.)

The cardinality of a finite set ⁠$S$⁠ is a natural number, the numbers of its elements, which is commonly denoted |S| or ⁠$\#S$⁠. These notations are also used for infinite sets, although $\operatorname {card} (S)$ seems more common in the infinite case.

Equinumerosity

Two sets have the same cardinality or are equinumerous if there exists a bijection or one-to-one correspondence between them. For example, the integers and the even integers have the same cardinality, since multiplication and division by 2 provide bijection between them.

The equinumerosity of two sets ⁠$A$⁠ and ⁠$B$⁠ is denoted

$\operatorname {card} (A)=\operatorname {card} (B).$

For any three sets ⁠$A$⁠, ⁠$B$⁠, and ⁠$C$⁠, one has

• ⁠$\operatorname {card} (A)=\operatorname {card} (A)\qquad$⁠ (reflexitivity),
• ⁠$\operatorname {card} (A)=\operatorname {card} (B)\implies \operatorname {card} (B)=\operatorname {card} (A)\qquad$⁠ (symmetry),
• ⁠$\operatorname {card} (A)=\operatorname {card} (B)$⁠ and ⁠$\operatorname {card} (B)=\operatorname {card} (C)\implies \operatorname {card} (A)=\operatorname {card} (C)\qquad$⁠ (transitivity).

This results immediately from the fact that the identity function, the inverse function of a bijective function, and the composition of two bijective functions are all bijective. This means that equinumerosity is an equivalence relation on the subsets of a given set.

See below for various examples.

Partial order

One says that the cardinality of a set ⁠$A$⁠ is less than or equal to the cardinality of ⁠$B$⁠, denoted

$\operatorname {card} (A)\leq \operatorname {card} (B),$

if there is an injective function from ⁠$A$⁠ to ⁠$B$⁠.

This defines a partial order on cardinalities, since one has

• ⁠$\operatorname {card} (A)\leq \operatorname {card} (A)$⁠,
• ⁠$\operatorname {card} (A)\leq \operatorname {card} (B)$⁠ and ⁠$\operatorname {card} (B)\leq \operatorname {card} (C)$⁠ imply ⁠$\operatorname {card} (A)\leq \operatorname {card} (C)$⁠
• ⁠$\operatorname {card} (A)\leq \operatorname {card} (B)$⁠ and ⁠$\operatorname {card} (B)\leq \operatorname {card} (A)$⁠ inly ⁠$\operatorname {card} (A)\operatorname {card} (A)$⁠.

The two first assertions result from the fact that the identity function and the composition of two injective functions are injective. The third assertion results from Schröder–Bernstein theorem, which asserts that, given an injection from ⁠$A$⁠ into ⁠$B$⁠ and an injection from ⁠$B$⁠ into ⁠$A$⁠, one can construct a bijection between ⁠$A$⁠ and ⁠$B$⁠.

If the axiom of choice is assumed, as it is commonly the case in modern mathematics, this partial order is a total order and a well-order.

Without the axiom of choice, one cannot prove that cadinalities are totally ordered. In particular, without the axiom of choice, there may exist Dedekind finite sets that are infinite; for such a set ⁠$F$⁠, one has neither ⁠$\operatorname {card} (F)\leq \operatorname {card} (\mathbb {N} )$⁠ nor ⁠$\operatorname {card} (\mathbb {N} )\leq \operatorname {card} (F)$⁠.

Countable sets

Main article: Countable set

As suggested by the name, a countable set is a set that can be exhausted by counting its elements, possibly with an endless counting. Such a counting process defines an injective function from the set to the natual numbers.

So, a countable set is a set ⁠$S$⁠ such that ⁠$\operatorname {card} (S)\leq \operatorname {card} (\mathbb {N} )$⁠. Thus, a countable set is either a finite set or a countably infinite set, that is a set such that ⁠$\operatorname {card} (S)=\operatorname {card} (\mathbb {N} )$⁠.

Every subset of a countable set is countable.

Illustration of the proof that the sequences of two natural numbers form a countable set, and that the same is true for the subset of irreducible fractions (in black)

Many sets that seem to be much larger that the natural numbers are neverthess countable. This is the case, in particular, of the set of all finite sequences of natural numbers. This can be proven by ordering these sequences as follows. Two sequences are first compared by the sums of their elements; when the sum of the members of two sequences are equal, the two sequences are compared by using a lexicographical order or any other total order. Since there is a finite number of sequences with a given sum, the order so defined provides a bijection between the the set of all finite sequences of natural numbers and the natural numbers.

It follows that countable sets include all sets whose all elements can be unambiguously encoded with sequences of natural numbers. This includes many algebraic structures such the integers (⁠$\mathbb {Z}$⁠), the rational numbers (⁠$\mathbb {Q}$⁠), the polynomials with rational coefficients (⁠$\mathbb {Q} [X_{1},\ldots ,X_{n}]]$⁠) and algebraic numbers, which are all countably infinite sets.

The set of all algorithms is also countably infinite, and it results that the same is true for the set of computable numbers. Similarly, the set of the theorems of a mathematical theory is also countable.

Nevertheless, there are infinite sets that are not countable; see the next section.

Uncountable sets

Main article: Uncountable set

There are sets that are not countable. They are said to be uncountable. That is, a uncountable set is an infinite set with a cardinality strictly larger than that of the set of the natural numbers.

Cardinality of the continuum

Main article: Cardinality of the continuum

The first prof of the existence of uncountable sets was given by Georg Cantor in 1891, who proved that the interval ⁠$(0,1)$⁠ of the real line is uncountable.

In a second proof, he used what is now called Cantor's diagonal argument to prove that a function from the natural numbers to the interval ⁠$I=(0,1)$⁠ cannot be surjective, and is therefore not a bijection. Indeed, if ⁠$f:\mathbb {N} \to I$⁠ is such a function, one can define a number of the interval that is not of the form ⁠$f(n)$⁠. Such a number is obtained with a number ⁠$X$⁠ such that, for every ⁠$k$⁠, the ⁠$k$⁠th decimal digit of ⁠$X$⁠ differs from the ⁠$k$⁠th digit of ⁠$f(k)$⁠ and differs also from ⁠$0$⁠ anf ⁠$1$⁠ (the latter condition for avoiding numbers that have two decimal representations). The term "diagonal argument" refers to the fact that, one can write an (infinite) matrix such the ⁠$(i,j)$⁠ entry is the ⁠$j$⁠th digit of ⁠$f(i)$⁠, and, then, the digits of ⁠$X$⁠ are obtained by changing the digits of the diagonal of the matrix. Then, this number ⁠$X$⁠ will be different from each of the numbers in the list by at least one digit, and therefore must not be in the list. This shows that the real numbers cannot be put into a one-to-one correspondence with the naturals, and thus must be strictly larger.

One has $$\operatorname {card} (\mathbb {R} )=\operatorname {card} (I),$$ since the function ⁠$x\mapsto \tan(x\pi -\pi /2)$⁠ is a bijection between these two sets.

This cardinality is called the cardinality of the continuum and commonly denoted as ⁠${\mathfrak {c}}$⁠ ("the continuum" is a old name for the real line).

Space-filling curves show that every finite dimensional real vector space has the cardinality of the continuum, as well as almost all spaces considered in geometry and analysis. So, almost all uncountable sets that are encountered in mathematics have the cardinality of the continuum.

Powersets

There are many other cardinalities than those described above. The most common method for defining sets with larger cardinalities is with powersets.

The powerset ${\mathcal {P}}(S)$ of a set ⁠$S$⁠ is the set of all subsets of ⁠$S$⁠. It often identified with the set of all functions of ⁠$S$⁠ to ⁠$\{0,1\}$⁠, through the one-to-one correspondence associating to such a function the subset where it takes the value ⁠$1$⁠.

Proof with the diagonal argument that $\operatorname {card} ({\mathcal {P}}(\mathbb {N} )>\operatorname {card} (\mathbb {N} )\colon$ The set $T=\{n\in N:n\notin f(n)\}$ formed by removing the red digits cannot occur an any row.

The cardinality of ${\mathcal {P}}(\mathbb {N} )$ is the cardinality of the continuum. This can be proven by considering the sequence of the digits of the binary representation of a real number in the interval ⁠$(0,1)$⁠ as a function from ⁠$\mathbb {N}$⁠ to ⁠$\{0,1\}$⁠.

More generally, Cantor's theorem asserts that for every set ⁠$S$⁠, one has $$\operatorname {card} ({\mathcal {P}}(S))>\operatorname {card} (S).$$

This can be proved with a variant of Cantor's diagonal agument: one has ${\textstyle \operatorname {card} ({\mathcal {P}}(S))\geq \operatorname {card} (S),}$ since the map ⁠$x\mapsto \{x\}$⁠ is an injective function from ⁠$S$⁠ to ⁠${\mathcal {P}}(S)$⁠. So, it suffices to prove that there is no bijection between ⁠$S$⁠ and ⁠${\mathcal {P}}(S)$⁠, and, in particular, that a function from ⁠$S$⁠ to ⁠${\mathcal {P}}(S)$⁠ cannot be surjective.

So, let ⁠$f$⁠ be a function from ⁠$S$⁠ to ⁠${\mathcal {P}}(S)$⁠. The subset $T=\{x\in S:x\notin f(x)\}\in {\mathcal {P}}(S)$ cannot be in the image of ⁠$f$⁠, since if one would have $T=f(x)$ then either $x\in f(x)$ or $x\in f(x),$ but not both. The definition of ⁠$T$⁠ implies that if one is in any of the two cases, one is also in the other case, a contradiction that proves that ⁠$f$⁠ is not surjective.

A transfinite induction using powerset construction and starting from the natural numbers allows giving values, called beth numbers, to some cardinalities. These beth numbers are uniquely defined sets defined by:

• $\beth _{0}=\mathbb {N}$
• $\beth _{1}={\mathcal {P}}(\mathbb {N} )={\mathfrak {c}}$
• $\beth _{\alpha +1}={\mathcal {P}}(\beth _{\alpha })\quad$ for every ordinal $\alpha$
• $\beth _{\lambda }=\bigcup _{\alpha <\lambda }\beth _{\alpha }\quad$ for every limit ordinal $\lambda$

Unless if the generalized continuum hypothesis is assumed, not all cardinalities can be represented by beth numbers.

Continuum hypothesis

Main article: Continuum hypothesis

The continuum hypothesis is the assertion that there is no set ⁠$S$⁠ such that ⁠$\operatorname {card} (\mathbb {N} )<\operatorname {card} (S)<\operatorname {card} (\mathbb {R} )$⁠. With the axiom of choice, the continuum hypothesis implies that the cardinal of the continuum is the least uncountable cardinal.

The proof of the continuum hypothesis was the first of the Hilbert's problems, stated in 1900.

In the framework of Zermelo–Fraenkel set theory (ZF), Paul Cohen proved in 1963, that the continuum hypothesis is independent from the other axioms of set theory, with or without the axiom of choice. More precicely, if ZF is consistent (that is, not self contradictory), then both ZF with ths continuum hypothesis and ZF with the negation of the continuum hypothesis are consistent, and they remain consistent if either the axiom of choice or its negation are added to the theory.

Cardinal numbers

Main articles: Cardinal number and Aleph number

In the preceding sections, the "cardinality" of a set was defined relationally. That is, the cardinalities of two sets can be compared, but the cardinality of a specific set was not defined as a mathematical object.

The first tentatives for defining cardinalities were to define them as equivalence classes for the relation "having the same cardinality". Unfortunately, this does not work beause these equivalence classes are not sets. So, the approach that has been eventually chosen is to define once for all specific sets, called cardinal numbers or aleph numbers, such that every set is equinumerous with exactly one cardinal number.

The definition of cardinal numbers involves a transfinite induction and uses ordinal numbers, which are well ordered sets such that every well-ordered set is order isomorphic to exactly one ordinal number.

The axiom of choice states that every set can be well ordered. This implies that, without the axiom of choice, there may be cardinalities that do not correspond to a cardinal number.

Formally, the infinite cardinal mumbers, also called aleph numbers because they are denoted with the Hebrew letter aleph, are defined as follows:

• $\aleph _{0}=\mathbb {N} \quad$ ($\mathbb {N}$ is the least infinite ordinal)
• For every ordinal $\alpha ,$ one defines $\aleph _{\alpha +1}$ as the least ordinal $\beta$ such that $\operatorname {card} (\beta )>\operatorname {card} (\aleph _{\alpha })$
• For every limit ordinal $\lambda ,$ one define $\aleph _{\lambda }$ as the least ordinal $\mu$ such that $\operatorname {card} (\mu )>\operatorname {card} (\aleph _{\alpha })$ for all $\alpha <\lambda$

If one starts the transfinite induction with the empty set ⁠$\emptyset$⁠ instead of ⁠$\mathbb {N}$⁠, the first cardinal numbers become the von Neumann natural numbers.

History

Etymology

In English, the term cardinality originates from the post-classical Latin cardinalis, meaning "principal" or "chief", which derives from cardo, a noun meaning "hinge". In Latin, cardo referred to something central or pivotal, both literally and metaphorically. This concept of centrality passed into medieval Latin and then into English, where cardinal came to describe things considered to be, in some sense, fundamental, such as cardinal virtues, cardinal sins, cardinal directions, and (in the grammatical sense) cardinal numbers. The last of which referred to numbers used for counting (e.g., one, two, three), as opposed to ordinal numbers, which express order (e.g., first, second, third), and nominal numbers used for labeling without meaning (e.g., jersey numbers and serial numbers).

In mathematics, the notion of cardinality was first introduced by Georg Cantor in the late 19th century, wherein he used the used the term Mächtigkeit, which may be translated as "magnitude" or "power", though Cantor credited the term to a work by Jakob Steiner on projective geometry. The terms cardinality and cardinal number were eventually adopted from the grammatical sense, and later translations would use these terms.

Prehistory

Further information: Tally marks § Early history, and History of ancient numeral systems

A crude sense of cardinality, an awareness that groups of things or events compare with other groups by containing more, fewer, or the same number of instances, is observed in a variety of present-day animal species, suggesting an origin millions of years ago. Human expression of cardinality is seen as early as 40000 years ago, with equating the size of a group with a group of recorded notches, or a representative collection of other things, such as sticks and shells. The abstraction of cardinality as a number is evident by 3000 BCE, in Sumerian mathematics and the manipulation of numbers without reference to a specific group of things or events.

Ancient history

Diagram of Aristotle's wheel as described in Mechanica.

From the 6th century BCE, the writings of Greek philosophers, such as Anaximander, show hints of comparing infinite sets or shapes. While the Greeks considered notions of infinity, they viewed it as paradoxical and imperfect (cf. Zeno's paradoxes), often associating good and evil with finite and infinite. Aristotle distinguished between the notions of actual infinity and potential infinity, arguing that Greek mathematicians understood the difference, and that they "do not need the [actual] infinite and do not use it." The greek notion of number (αριθμός, arithmos) was used exclusively for a definite number of definite objects (i.e. finite numbers). This would be codified in Euclid's Elements, where the fifth common notion states "The whole is greater than the part", often called the Euclidean principle. This principle would be the dominating philosophy in mathematics until the 19th century.

Around the 4th century BCE, Jaina mathematics would be the first to discuss different sizes of infinity. They defined three major classes of number: enumerable (finite numbers), unenumerable (asamkhyata, roughly, countably infinite), and infinite (ananta). Then they had five classes of infinite numbers: infinite in one direction, infinite in both directions, infinite in area, infinite everywhere, and infinite perpetually.

One of the earliest explicit uses of a one-to-one correspondence is recorded in Aristotle's Mechanics (c. 350 BCE), known as Aristotle's wheel paradox. The paradox can be briefly described as follows: A wheel is depicted as two concentric circles. The larger, outer circle is tangent to a horizontal line (e.g. a road that it rolls on), while the smaller, inner circle is rigidly affixed to the larger. Assuming the larger circle rolls along the line without slipping (or skidding) for one full revolution, the distances moved by both circles are the same: the circumference of the larger circle. Further, the lines traced by the bottom-most point of each is the same length. Since the smaller wheel does not skip any points, and no point on the smaller wheel is used more than once, there is a one-to-one correspondence between the two circles.

Pre-Cantorian set theory

Portrait of Galileo Galilei, circa 1640 (left). Portrait of Bernard Bolzano 1781–1848 (right).

Galileo Galilei presented what was later coined Galileo's paradox in his book Two New Sciences (1638), where he attempts to show that infinite quantities cannot be called greater or less than one another. He presents the paradox roughly as follows: a square number is one which is the product of another number with itself, such as 4 and 9, which are the squares of 2 and 3, respectively. Then the square root of a square number is that multiplicand. He then notes that there are as many square numbers as there are square roots, since every square has its own root and every root its own square, while no square has more than one root and no root more than one square. But there are as many square roots as there are numbers, since every number is the square root of some square. He denied that this was fundamentally contradictory, however, he concluded that this meant we could not compare the sizes of infinite sets, missing the opportunity to discover cardinality.

Bernard Bolzano's Paradoxes of the Infinite (Paradoxien des Unendlichen, 1851) is often considered the first systematic attempt to introduce the concept of sets into mathematical analysis. In this work, Bolzano defended the notion of actual infinity, examined various properties of infinite collections, including an early formulation of what would later be recognized as one-to-one correspondence between infinite sets, and proposed to base mathematics on a notion similar to sets. He discussed examples such as the pairing between the intervals $[0,5]$ and $[0,12]$ by the relation $5y=12x.$ Bolzano also revisited and extended Galileo's paradox. However, he too resisted saying that these sets were, in that sense, the same size. Thus, while Paradoxes of the Infinite anticipated several ideas central to later set theory, the work had little influence on contemporary mathematics, in part due to its posthumous publication and limited circulation.

Other, more minor contributions include David Hume in A Treatise of Human Nature (1739), who said "When two numbers are so combined, as that the one has always a unit answering to every unit of the other, we pronounce them equal", now called Hume's principle, which was used extensively by Gottlob Frege later during the rise of set theory. Jakob Steiner, whom Georg Cantor credits the original term, Mächtigkeit, for cardinality (1867). Peter Gustav Lejeune Dirichlet is commonly credited for being the first to explicitly formulate the pigeonhole principle in 1834, though it was used at least two centuries earlier by Jean Leurechon in 1624.

Early set theory

Georg Cantor

Georg Cantor,     c. 1870

The concept of cardinality, as a formal measure of the size of a set, emerged nearly fully formed in the work of Georg Cantor during the 1870s and 1880s, in the context of mathematical analysis. In a series of papers beginning with On a Property of the Collection of All Real Algebraic Numbers (1874), Cantor introduced the idea of comparing the sizes of infinite sets, through the notion of one-to-one correspondence. He showed that the set of real numbers was, in this sense, strictly larger than the set of natural numbers using a nested intervals argument. This result was later refined into the more widely known diagonal argument of 1891, published in Über eine elementare Frage der Mannigfaltigkeitslehre, where he also proved the more general result (now called Cantor's Theorem) that the power set of any set is strictly larger than the set itself.

Cantor introduced the notion cardinal numbers in terms of ordinal numbers. He viewed cardinal numbers as an abstraction of sets, introduced the notations, where, for a given set ${\textstyle M}$, the order type of that set was written ${\textstyle {\overline {M}}}$, and the cardinal number was ${\textstyle M}$, a double abstraction. He also introduced the Aleph sequence for infinite cardinal numbers. These notations appeared in correspondence and were formalized in his later writings, particularly the series Beiträge zur Begründung der transfiniten Mengenlehre (1895–1897). In these works, Cantor developed an arithmetic of cardinal numbers, defining addition, multiplication, and exponentiation of cardinal numbers based on set-theoretic constructions. This led to the formulation of the Continuum Hypothesis (CH), the proposition that no set has cardinality strictly between $\aleph _{0}$ and the cardinality of the continuum, that is $|\mathbb {R} |=\aleph _{1}$. Cantor was unable to resolve CH and left it as an open problem.

Other contributors

Parallel to Cantor’s development, Richard Dedekind independently formulated a definition of infinite set as one that can be placed in bijection with a proper subset of itself, which was shown to be equivalent with Cantor’s definition of cardinality (given the axiom of choice). Dedekind’s Was sind und was sollen die Zahlen? (1888) emphasized structural properties over extensional definitions, and supported the bijective formulation of size and number. Dedekind was in correspondence with Cantor during the development of set theory; he supplied Cantor with a proof of the countability of the algebraic numbers, and gave feedback and modifications on Cantor's proofs before publishing.

After Cantor's 1883 proof that all finite-dimensional spaces $(\mathbb {R} ^{n})$ have the same cardinality, in 1890, Giuseppe Peano introduced the Peano curve, which was a more visual proof that the unit interval $[0,1]$ has the same cardinality as the unit square on $\mathbb {R} ^{2}.$ This created a new area of mathematical analysis studying what is now called space-filling curves.

German logician Gottlob Frege attempted to ground the concepts of number and arithmetic in logic using Cantor's theory of cardinality and Hume's principle in Die Grundlagen der Arithmetik (1884) and the subsequent Grundgesetze der Arithmetik (1893, 1903). Frege defined cardinal numbers as equivalence classes of sets under equinumerosity. However, Frege's approach to set theory was later shown to be flawed. His approach was eventually reformalized by Bertrand Russell and Alfred Whitehead in Principia Mathematica (1910–1913, vol. II) using a theory of types. Though Russell initially had difficulties understanding Cantor's and Frege’s intuitions of cardinality. This definition of cardinal numbers is now referred to as the Frege-Russell definition.

Axiomatic set theory

Ernst Zermelo and Kurt Gödel

In 1908, Ernst Zermelo proposed the first axiomatization of set theory, now called Zermelo set theory, primarily to support his earlier (1904) proof of the Well-ordering theorem, which showed that all cardinal numbers could be represented as Alephs, though the proof required a controversial principle now known as the Axiom of Choice (AC). Zermelo's system would later be extended by Abraham Fraenkel and Thoralf Skolem in the 1920s to create the standard foundation of set theory, called Zermelo–Fraenkel set theory (ZFC, "C" for the Axiom of Choice). ZFC provided a rigorous, albeit non-categorical, foundation through which infinite cardinals could be systematically studied while avoiding the paradoxes of naive set theory.

In 1940, Kurt Gödel showed that CH cannot be disproved from ZF set theory (ZFC without Choice), even if the axiom of choice is adopted, i.e. from ZFC. Gödel's proof shows that both CH and AC hold in the constructible universe, an inner model of ZF set theory, assuming only the axioms of ZF. The existence of an inner model of ZF in which additional axioms hold shows that the additional axioms are (relatively) consistent with ZF, provided ZF itself is consistent. In 1963, Paul Cohen showed that CH cannot be proven from the ZFC axioms, which showed that CH was independent from ZFC. To prove his result, Cohen developed the method of forcing, which has become a standard tool in set theory. Essentially, this method begins with a model of ZFC in which CH holds and constructs another model which contains more sets than the original in a way that CH does not hold in the new model. Cohen was awarded the Fields Medal in 1966 for his proof.

Paradoxes

During the rise of set theory, several paradoxes (see: Paradoxes of set theory). These can be divided into two kinds: real paradoxes and apparent paradoxes. Apparent paradoxes are those which follow a series of reasonable steps and arrive at a conclusion which seems impossible or incorrect according to one's intuition, but aren't necessarily logically impossible. Two historical examples have been given, Galileo's Paradox and Aristotle's Wheel, in § History. Real paradoxes are those which, through reasonable steps, prove a logical contradiction. The real paradoxes here apply to naive set theory or otherwise informal statements, and have been resolved by restating the problem in terms of a formalized set theory, such as Zermelo–Fraenkel set theory.

Apparent paradoxes

Hilbert's hotel

Main article: Hilbert's paradox of the Grand Hotel

Visual representation of Hilbert's hotel

Hilbert's Hotel is a thought experiment devised by the German mathematician David Hilbert to illustrate a counterintuitive property of countably infinite sets, allowing them to have the same cardinality as a proper subset of themselves. The scenario begins by imagining a hotel with an infinite number of rooms, all of which are occupied. But then a new guest walks in asking for a room. The hotel accommodates by moving the occupant of room 1 to room 2, the occupant of room 2 to room 3, room three to room 4, and in general, room n to room n+1. Then every guest still has a room, but room 1 opens up for the new guest.

Then, the scenario continues by imagining an infinite bus of new guests seeking a room. The hotel accommodates by moving the person in room 1 to room 2, room 2 to room 4, and in general, room n to room 2n. Thus, all the even-numbered rooms are occupied, but all the odd-numbered rooms are vacant, leaving room for the infinite bus of new guests. The scenario continues by assuming an infinite number of these infinite buses arrive at the hotel, and showing that the hotel is still able to accommodate. Finally, an infinite bus which has a seat for every real number arrives, and the hotel is no longer able to accommodate.

Skolem's paradox

Main article: Skolem's paradox

Illustration of the Löwenheim–Skolem theorem, where ${\mathcal {M}}$ and ${\mathcal {N}}$ are models of set theory, and $\kappa$ is an arbitrary infinite cardinal number.

In model theory, a model corresponds to a specific interpretation of a formal language or theory. It consists of a domain (a set of objects) and an interpretation of the symbols and formulas in the language, such that the axioms of the theory are satisfied within this structure. The Löwenheim–Skolem theorem shows that any model of set theory in first-order logic, if it is consistent, has an equivalent model which is countable. This appears contradictory, because Georg Cantor proved that there exist sets which are not countable. Thus the seeming contradiction is that a model that is itself countable, and which therefore contains only countable sets, satisfies the first-order sentence that intuitively states "there are uncountable sets".

A mathematical explanation of the paradox, showing that it is not a true contradiction in mathematics, was first given in 1922 by Thoralf Skolem. He explained that the countability of a set is not absolute, but relative to the model in which the cardinality is measured. Skolem's work was harshly received by Ernst Zermelo, who argued against the limitations of first-order logic and Skolem's notion of "relativity", but the result quickly came to be accepted by the mathematical community.

Real paradoxes

Cantor's paradox

Main article: Cantor's paradox

Cantor's theorem state's that, for any set $A,$ possibly infinite, its powerset ${\mathcal {P}}(A)$ has a strictly greater cardinality. For example, this means there is no bijection from $\mathbb {N}$ to ${\mathcal {P}}(\mathbb {N} )\sim \mathbb {R} .$ Cantor's paradox is a paradox in naive set theory, which shows that there cannot exist a "set of all sets" or "universe set". It starts by assuming there is some set of all sets, $U:=\{x\;|\;x\,{\text{ is a set}}\},$ then it must be that $U$ is strictly smaller than ${\mathcal {P}}(U),$ thus $|U|\leq |{\mathcal {P}}(U)|.$ But since $U$ contains all sets, we must have that ${\mathcal {P}}(U)\subseteq U,$ and thus $|{\mathcal {P}}(U)|\leq |U|.$ Therefore $|{\mathcal {P}}(U)|=|U|,$ contradicting Cantor's theorem. This was one of the original paradoxes that added to the need for a formalized set theory to avoid these paradoxes. This paradox is usually resolved in formal set theories by disallowing unrestricted comprehension and the existence of a universe set.

Set of all cardinal numbers

Similar to Cantor's paradox, the paradox of the set of all cardinal numbers is a result due to unrestricted comprehension. It often uses the definition of cardinal numbers as ordinal numbers for representatives. It is related to the Burali-Forti paradox. It begins by assuming there is some set $S:=\{X\,|X{\text{ is a cardinal number}}\}.$ Then, if there is some largest element $\aleph \in S,$ then the powerset ${\mathcal {P}}(\aleph )$ is strictly greater, and thus not in $S.$ Conversly, if there is no largest element, then the union $\bigcup S$ contains the elements of all elements of $S,$ and is therefore greater than or equal to each element. Since there is no largest element in $S,$ for any element $x\in S,$ there is another element $y\in S$ such that $|x|<|y|$ and $|y|\leq {\Bigl |}\bigcup S{\Bigr |}.$ Thus, for any $x\in S,$ $|x|<{\Bigl |}\bigcup S{\Bigr |},$ and so ${\Bigl |}\bigcup S{\Bigr |}\notin S.$

See also

• Cardinal function
• Inaccessible cardinal
• Infinitary combinatorics
• Large cardinal
  • List of large cardinal properties
• Numerosity (mathematics)
• Regular cardinal
• Scott's trick
• The Higher Infinite
• Von Neumann universe
• Zero sharp

References

Bibliography

• Anellis, Irving M.; et al. (AMS-IMS-SIAM Joint Summer Research Conference) (1984). Axiomatic Set Theory. Contemporary Mathematics. Providence: American Mathematical Society. ISBN 0-8218-5026-1. LCCN 84-18457.
• Bourbaki, Nicholas (1968). Theory of Sets. Éléments de mathématique. Paris: Éditions Hermann. LCCN 68-25177.
• Enderton, Herbert (1977). Elements of Set Theory. New York: Academic Press. ISBN 0-12-238440-7. LCCN 76-27438.
• Ferreirós, José (2007). Labyrinth of Thought. Science Networks - Historical Studies (2nd ed.). Basel: Birkhäuser. doi:10.1007/978-3-7643-8350-3. ISBN 978-3-7643-8349-7. LCCN 2007931860. Archived from the original on 2019-07-09.
• Halmos, Paul R. (1998) [1974]. Naive Set Theory. Undergraduate Texts in Mathematics. New York: Springer Science+Business Media. doi:10.1007/978-1-4757-1645-0. ISBN 978-0-387-90092-6. ISSN 0172-6056. Archived from the original on 2023-01-12.
• Hrbáček, Karel; Jech, Thomas (2017) [1999]. Introduction to Set Theory (3rd, Revised and Expanded ed.). New York: CRC Press. doi:10.1201/9781315274096. ISBN 978-0-82477915-3. LCCN 99-15458.
• Kleene, Stephen Cole (1967). Mathematical Logic. New York: John Wiley & Sons. ISBN 0-471-49033-4. LCCN 66-26747.
• Krivine, Jean-Louis (1971). Introduction to Axiomatic Set Theory. Synthese Library. New York: D. Reidel Publishing Company. doi:10.1007/978-94-010-3144-8. ISBN 9780391001794. ISSN 0166-6991. LCCN 71-146965. Archived from the original on 2014-08-06.
• Kuratowski, Kazimierz (1968). Set Theory. Amsterdam: North Holland Publishing. LCCN 67-21972.
• Lévy, Azriel (1979). Basic Set Theory. Perspectives in Mathematical Logic. Berlin: Springer-Verlag. ISBN 3-540-08417-7. LCCN 78-1917.
• Russell, Bertrand; Whitehead, Alfred North (1973) [1927]. Principia Mathematica (PDF). Vol. II (2nd ed.). London: Cambridge University Press. ISBN 0-521-06791-X.
• Stoll, Robert R. (1963). Set Theory and Logic. San Francisco: W. H. Freeman. ISBN 7167 0416-1. LCCN 63-8995. {{cite book}}: ISBN / Date incompatibility (help)
• Suppes, Patrick (1972) [1960]. Axiomatic Set Theory. Dover Books on Mathematics. New York: Dover. ISBN 0-486-61630-4. LCCN 72-86226. Archived from the original on 2014-08-06.
• Takeuti, Gaisi; Zaring, Wilson M (1982). Introduction to Axiomatic Set Theory. Graduate Texts in Mathematics (2nd ed.). New York: Springer-Verlag. doi:10.1007/978-1-4613-8168-6. ISBN 0-387-90683-5. ISSN 0072-5285. LCCN 81-8838. Archived from the original on 2014-08-06.
• Tao, Terence (2022). Analysis I. Texts and Readings in Mathematics (4th ed.). Singapore: Springer Science+Business Media. doi:10.1007/978-3-662-00274-2. ISBN 978-981-19-7261-4. ISSN 2366-8717.