Cardinality

For other uses, see Cardinality (disambiguation).

In mathematics, the cardinality of a set is the number of its elements. The cardinality of a set may also be called its size, when no confusion with other notions of size is possible.^[a] Beginning in the late 19th century, this concept of size was generalized to infinite sets, allowing one to distinguish between different types of infinity and to perform arithmetic on them. Nowadays, infinite sets are encountered in almost all parts of mathematics, even those that may seem to be unrelated. Familiar examples are provided by most number systems and algebraic structures (natural numbers, rational numbers, real numbers, vector spaces, etc.), as well as in geometry, by lines, line segments and curves, which are considered as the sets of their points.

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

There are two approaches to describing cardinality: one which uses cardinal numbers and another which compares sets directly using functions between them, either bijections or injections. The former states the size as a number; the latter compares their relative size and led to the discovery of different sizes of infinity.^[1] For example, the sets ${\displaystyle A=\{1,2,3\}}$ and ${\displaystyle B=\{2,4,6\}}$ are the same size as they each contain 3 elements (the first approach) and there is a bijection between them (the second approach).

Introduction

Notation and terminology

The cardinality, or cardinal number, of a set ${\displaystyle A}$ is generally denoted by ${\displaystyle |A|,}$ with a vertical bar on each side.^[2] (This is the same notation as for absolute value; the meaning depends on context.) The notation ${\displaystyle |A|=|B|}$ means that the two sets ⁠${\displaystyle A}$⁠ and ⁠${\displaystyle B}$⁠ have the same cardinality. The cardinal number of a set ${\displaystyle A}$ may also be denoted by ${\displaystyle n(A),}$ ${\displaystyle A}$, ${\displaystyle \operatorname {card} (A),}$ ${\displaystyle \#A,}$ etc. It is conventional to recognize three kinds of cardinality:

• Any set X with cardinality less than that of the natural numbers, or | X | < | N |, is said to be a finite set.
• Any set X that has the same cardinality as the set of the natural numbers, or | X | = | N | = ${\displaystyle \aleph _{0},}$ is said to be a countably infinite set.^[3]
• Any set X with cardinality greater than that of the natural numbers, or | X | > | N |, for example | R | = ${\displaystyle {\mathfrak {c}}}$ > | N |, is said to be uncountable.

Examples and properties

• If X = {a, b, c} and Y = {apples, oranges, peaches}, where a, b, and c are distinct, then | X | = | Y | because { (a, apples), (b, oranges), (c, peaches)} is a bijection between the sets X and Y. The cardinality of each of X and Y is 3.
• If | X | ≤ | Y |, then there exists Z such that | X | = | Z | and Z ⊆ Y.
• If | X | ≤ | Y | and | Y | ≤ | X |, then | X | = | Y |. This holds even for infinite cardinals, and is known as Cantor–Bernstein–Schroeder theorem.
• Sets with cardinality of the continuum include the set of all real numbers, the set of all irrational numbers and the interval ${\displaystyle [0,1].}$

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.^[4][5] The last of which referred to numbers used for counting (e.g., one, two, three),^[6] as opposed to ordinal numbers, which express order (e.g., first, second, third),^[7] and nominal numbers used for labeling without meaning (e.g., jersey numbers and serial numbers).^[8]

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.^[9][10][11] The terms cardinality and cardinal number were eventually adopted from the grammatical sense, and later translations would use these terms.^[12][13] Similarly, the terms for countable and uncountable sets come from countable and uncountable nouns.^{[citation needed]}

History

Prehistory

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.^[14] 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.^[15] 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.^[16]

Ancient History

Diagram of Aristotle's wheel as described in Mechanica.

From the 6th century BCE, the writings of Greek philosophers show hints of the cardinality of infinite sets. While they considered the notion of infinity as an endless series of actions, such as adding 1 to a number repeatedly, they did not consider the size of an infinite set of numbers to be a thing.^[17] The ancient Greek notion of infinity also considered the division of things into parts repeated without limit. In Euclid's Elements, commensurability was described as the ability to compare the length of two line segments, a and b, as a ratio, as long as there were a third segment, no matter how small, that could be laid end-to-end a whole number of times into both a and b. But with the discovery of irrational numbers, it was seen that even the infinite set of all rational numbers was not enough to describe the length of every possible line segment.^[18]

One of the earliest explicit uses of a one-to-one correspondence is recorded in Aristotle's Mechanics (c. 350 BC), 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.^[19] 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, however, concluded that this meant we could not compare the sizes of infinite sets, missing the opportunity to discover cardinality.^[20]

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 ${\displaystyle [0,5]}$ and ${\displaystyle [0,12]}$ by the relation ${\displaystyle 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.^[21][22][23]

Other, more minor contributions incude 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",^[24] now caled Hume's principle, which was used extensively by Gottlob Frege later during the rise of set theory.^[25] Jakob Steiner, whom Georg Cantor credits the original term, Mächtigkeit, for cardinality (1867).^[9][10][11] Peter Gustav Lejeune Dirichlet is commonly credited for being the first to explicitly formulate the pigeonhole principle in 1834,^[26] though it was used at least two centuries earlier by Jean Leurechon in 1624.^[27]

Early Set theory

To better understand infinite sets, a notion of cardinality was formulated c. 1880 by Georg Cantor, the originator of set theory. He examined the process of equating two sets with a bijection, a one-to-one correspondence between the elements of two sets. In 1891, with the publication of his diagonal argument, he demonstrated that there are sets of numbers that cannot be placed in one-to-one correspondence with the set of natural numbers, i.e., there are "uncountable sets" that contain more elements than there are in the infinite set of natural numbers.^[28]

Comparing sets

A one-to-one correspondence from N, the set of all non-negative integers, to the set E of non-negative even numbers. Although E is a proper subset of N, both sets have the same cardinality.

While the cardinality of a finite set is simply its number of elements, extending that notion to infinite sets usually starts with defining comparison of sizes of arbitrary sets (some of which are possibly infinite).

Equinumerosity

Main article: Equinumerosity

Two sets have the same cardinality if there exists a one-to-one correspondence between the elements of ⁠${\displaystyle A}$⁠ and those ⁠${\displaystyle B}$⁠ (that is, a bijection from ⁠${\displaystyle A}$⁠ to ⁠${\displaystyle B}$⁠).^[3] Such sets are said to be equipotent, equipollent, or equinumerous. For example, the set ${\displaystyle E=\{0,2,4,6,{\text{...}}\}}$ of non-negative even numbers has the same cardinality as the set ${\displaystyle \mathbb {N} =\{0,1,2,3,{\text{...}}\}}$ of natural numbers, since the function ${\displaystyle f(n)=2n}$ is a bijection from ⁠${\displaystyle \mathbb {N} }$⁠ to ⁠${\displaystyle E}$⁠ (see picture).

For finite sets ⁠${\displaystyle A}$⁠ and ⁠${\displaystyle B}$⁠, if some bijection exists from ⁠${\displaystyle A}$⁠ to ⁠${\displaystyle B}$⁠, then each injective or surjective function from ⁠${\displaystyle A}$⁠ to ⁠${\displaystyle B}$⁠ is a bijection. This is no longer true for infinite ⁠${\displaystyle A}$⁠ and ⁠${\displaystyle B}$⁠. For example, the function ⁠${\displaystyle g}$⁠ from ⁠${\displaystyle \mathbb {N} }$⁠ to ⁠${\displaystyle E}$⁠, defined by ${\displaystyle g(n)=4n}$ is injective, but not surjective since 2, for instance, is not mapped to, and ⁠${\displaystyle h}$⁠ from ⁠${\displaystyle \mathbb {N} }$⁠ to ⁠${\displaystyle E}$⁠, defined by ${\displaystyle h(n)=2\operatorname {floor} (n/2)}$ (see: floor function) is surjective, but not injective, since 0 and 1 for instance both map to 0. Neither ⁠${\displaystyle g}$⁠ nor ⁠${\displaystyle h}$⁠ can challenge ${\displaystyle |E|=|\mathbb {N} |,}$ which was established by the existence of ⁠${\displaystyle f}$⁠.

Equivalence

Example for a composition of two functions.

A fundamental result often used for cadinality is that of an equivalence relation. A binary relation is an equvalence relation if it satisfies the three basic properties of equality: reflexivity, symmetry, and transitivity. A relation ${\displaystyle R}$ is reflexive if, for any ${\displaystyle a,}$ ${\displaystyle aRa}$ (read: ${\displaystyle a}$ is ${\displaystyle R}$-related to ${\displaystyle a}$); symmetric if, for any ${\displaystyle a}$ and ${\displaystyle b,}$ if ${\displaystyle aRb,}$ then ${\displaystyle bRa}$ (read: if ${\displaystyle a}$ is related to ${\displaystyle b,}$ then ${\displaystyle b}$ is related to ${\displaystyle a}$); and transitive if, for any ${\displaystyle a,}$ ${\displaystyle b,}$ and ${\displaystyle c,}$ if ${\displaystyle aRb}$ and ${\displaystyle bRc,}$ then ${\displaystyle aRc.}$

Given any set ${\displaystyle A,}$ there is a bijection from ${\displaystyle A}$ to itself by the identity function, therefore cardinality is reflexive. Given any sets ${\displaystyle A}$ and ${\displaystyle B,}$ such that there is a bijection ${\displaystyle f}$ from ${\displaystyle A}$ to ${\displaystyle B,}$ then there is an inverse function ${\displaystyle f^{-1}}$ from ${\displaystyle B}$ to ${\displaystyle A,}$ which is also bijective, therefore cardinality is symmetric. Finally, given any sets ${\displaystyle A,}$ ${\displaystyle B,}$ and ${\displaystyle C}$ such that there is a bijection ${\displaystyle f}$ from ${\displaystyle A}$ to ${\displaystyle B,}$ and ${\displaystyle g}$ from ${\displaystyle B}$ to ${\displaystyle C,}$ then their composition ${\displaystyle g\circ f}$ (read: ${\displaystyle g}$ after ${\displaystyle f}$) is a bijection from ${\displaystyle A}$ to ${\displaystyle C,}$ and so cardinality is transitive. Thus, cardinality forms an equivalence relation. This means that cardinality partitions sets into equivalence classes, and one may assign a representative to denote this class. This motivates the notion of a cardinal number.

Somewhat more formally, a relation must be a certain set of ordered pairs. Since there is no set of all sets in standard set theory (see: § Cantor's paradox), cardinality is not a relation in the usual sense, but a predicate or a relation over classes.

Inequality

A set ${\displaystyle A}$ is not larger than a set ${\displaystyle B}$ if it can be mapped into ${\displaystyle B}$ without overlap. That is, the cardinality of ${\displaystyle A}$ is less than or equal to the cardinality of ${\displaystyle B}$ if there is an injective function from ${\displaystyle A}$ to ${\displaystyle B}$. This is written ${\displaystyle A\preceq B,}$ or ${\displaystyle |A|\leq |B|.}$ If ${\displaystyle A\preceq B,}$ but there is no injection from ${\displaystyle B}$ to ${\displaystyle A,}$ then ${\displaystyle A}$ is said to be strictly smaller than ${\displaystyle B,}$ written without the underline as ${\displaystyle A\prec B}$ or ${\displaystyle |A|<|B|.}$ For example, if ${\displaystyle A}$ has four elements and ${\displaystyle B}$ has five, then the following are true ${\displaystyle A\preceq A,}$ ${\displaystyle A\preceq B,}$ and ${\displaystyle A\prec B.}$

For example, the set ⁠${\displaystyle \mathbb {N} }$⁠ of all natural numbers has cardinality strictly less than its power set ⁠${\displaystyle {\mathcal {P}}(\mathbb {N} )}$⁠, because ${\displaystyle g(n)=\{n\}}$ is an injective function from ⁠${\displaystyle \mathbb {N} }$⁠ to ⁠${\displaystyle {\mathcal {P}}(\mathbb {N} )}$⁠, and it can be shown that no function from ⁠${\displaystyle \mathbb {N} }$⁠ to ⁠${\displaystyle {\mathcal {P}}(\mathbb {N} )}$⁠ can be bijective (see picture). By a similar argument, ⁠${\displaystyle \mathbb {N} }$⁠ has cardinality strictly less than the cardinality of the set ⁠${\displaystyle \mathbb {R} }$⁠ of all real numbers. For proofs, see Cantor's diagonal argument or Cantor's first uncountability proof.

If ${\displaystyle |A|\leq |B|}$ and ${\displaystyle |B|\leq |A|,}$ then ${\displaystyle |A|=|B|}$ (a fact known as the Schröder–Bernstein theorem). The axiom of choice is equivalent to the statement that ${\displaystyle |A|\leq |B|}$ or ${\displaystyle |B|\leq |A|}$ for every ⁠${\displaystyle A}$⁠ and ⁠${\displaystyle B}$⁠.^[29][30]

Countable sets

Main article: Countable set

A set is called countable if it is finite or has a bijection with the set of natural numbers ${\displaystyle (\mathbb {N} ),}$ in which case it is called countably infinte. The term denumerable is also sometimes used for countably infinite sets. For example, the set of all even natural numbers is countable, and therefore has the same cardinality as the whole set of natural numbers, even though it is a proper subset. Similarly, the set of square numbers is countable, which was considered paradoxical for hundreds of years before modern set theory (see: § Pre-Cantorian Set theory). However, several other examples have historically been considered suprising or initially unintuitive since the rise of set theory.

Two images of a visual depiction of a function from ${\displaystyle \mathbb {N} }$ to ${\displaystyle \mathbb {Q} .}$ On the left, a version for the positive rational numbers. On the right, a spiral for all pairs of integers ${\displaystyle p/q.}$

The rational numbers ${\displaystyle (\mathbb {Q} )}$ are those which can be expressed as the quotient or fraction ⁠${\displaystyle {\tfrac {p}{q}}}$⁠ of two integers. The rational numbers can be shown to be countable by considering the set of fractions as the set of all ordered pairs of integers, denoted ${\displaystyle \mathbb {Z} \times \mathbb {Z} ,}$ which can be visualized as the set of all integer points on a grid. Then, an intuitive function can be described by drawing a line in a repeating pattern, or spiral, which eventually goes through each point in the grid. For example, going through each diagonal on the grid for positive fractions, or through a lattice spiral for all integer pairs. These technically over cover the rationals, since, for example, the rational number ${\textstyle {\frac {1}{2}}}$ gets mapped to by all the fractions ${\textstyle {\frac {2}{4}},\,{\frac {3}{6}},\,{\frac {4}{8}},\,\dots ,}$ as the grid method treats these all as disticnt ordered pairs. So this function shows ${\displaystyle |\mathbb {Q} |\leq |\mathbb {N} |}$ not ${\displaystyle |\mathbb {Q} |=|\mathbb {N} |.}$ This can be corrected by "skipping over" these numbers in the grid, or by designing a function which does this naturally, but these menthods are usually more complicated.

Algebraic numbers on the complex plane, colored by degree

A number is called algebraic if it is a solution of some polynomial equation (with integer coefficients). For example, the square root of two ${\displaystyle {\sqrt {2}}}$ is a solution to ${\displaystyle x^{2}-2=0,}$ and the rational number ${\displaystyle p/q}$ is the solution to ${\displaystyle qx-p=0.}$ Conversely, a number which cannot be the root of any polynomial is called transcendental. Two examples include Euler's number (e) and pi (π). In general, proving a number is trancendental is considered to be very difficult, and only a few classes of transcendental numbers are known. However, it can be shown that the set of algebraic numbers is countable (for example, see Cantor's first set theory article § The proofs). Since the set of algebraic numbers is countable while the real numbers are uncountable (shown in the following section), the transcendental numbers must form the vast majority of real numbers, even though they are individually much harder to identify. That is to say, almost all real numbers are transcendental.

Uncountable sets

Main article: Uncountable set

N does not have the same cardinality as its power set P(N): For every function f from N to P(N), the set T = {n∈N: n∉f(n)} disagrees with every set in the range of f, hence f cannot be surjective. The picture shows an example f and the corresponding T; red: n∈f(n)\T, blue:n∈T\f(n).

A set is called uncountable if it is not countable. That is, it is infinite and strictly larger than the set of natural numbers. The usual first example of this is the set of real numbers, which can be understood as the set of all numbers on the number line. The method for the proof is called Cantor's diagonal argument, credited to Cantor for his 1891 proof,^[31] though his differs from the more common presentation.

It begins by assuming, by contradiction, that there is some one-to-one mapping between the natural numbers and the set of real numbers between 0 and 1 (the interval ${\displaystyle [0,1]}$). Then, take the decimal expansions of each real number, which looks like ${\displaystyle 0.d_{1}d_{2}d_{3}...}$ Considering these real numbers in a column, create a new number such that the first digit of the new number is different from that of the first number in the column, the second digit is different from the second number in the column and so on. For example, if the digit isn't a 7, make the digit of the new number a 7, and if it was a seven, make it a 3 (The reason for 3 and 7 is to avoid issues related to 0.999...).^[32] Then, this new number 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.^[33]

Cardinal numbers

Main article: Cardinal number

In the above section, "cardinality" of a set was defined relationally. In other words, it was not defined as a specific object itself. However, such an object can be defined as follows.

Finite sets

Main article: Finite set

A bijective function, f: X → Y, from set X to set Y demonstrates that the sets have the same cardinality, in this case equal to the cardinal number 4.

Given a basic sense of natural numbers, a set is said to have cardinality ${\displaystyle n}$ if it can be put in one-to-one correspondence with the set ${\displaystyle \{1,\,2,\,\dots ,\,n\}.}$ For example, the set ${\displaystyle S=\{A,B,C,D\}}$ has a natural correspondence with the set ${\displaystyle \{1,2,3,4\},}$ and therefore is said to have cardinality 4. Other terminologies include "Its cardinality is 4" or "Its cardinal number is 4". While this definition uses a basic sense of natural numbers, it may be that cardinality is used to define the natural numbers, in which case, a simple construction of objects satisfying the Peano axioms can be used as a substitute. Most commonly, the Von Neumann ordinals.

Showing that such a correspondence exists is not always trivial, which is the subject matter of combinatorics.

Uniqueness

An intuitive property of finite sets is that, for example, if a set has cardinality 4, then it does not also have cardinality 5. Intuitively meaning that a set cannot have both exaclty 4 elements and exactly 5 elements. However, it is not so obviously proven. The following proof is adapted from Analysis I by Terence Tao.^[34]

Intuitive depiction of the function ${\displaystyle g}$ in the lemma, for the case ${\displaystyle |X|=7.}$

Lemma: If a set ${\displaystyle X}$ has cardinality ${\displaystyle n\geq 1,}$ and ${\displaystyle x_{0}\in X,}$ then the set ${\displaystyle X-\{x_{0}\}}$ (i.e. ${\displaystyle X}$ with the element ${\displaystyle x_{0}}$ removed) has cardinality ${\displaystyle n-1.}$

Proof: Given ${\displaystyle X}$ as above, since ${\displaystyle X}$ has cardinality ${\displaystyle n,}$ there is a bijection ${\displaystyle f}$ from ${\displaystyle X}$ to ${\displaystyle \{1,\,2,\,\dots ,\,n\}.}$ Then, since ${\displaystyle x_{0}\in X,}$ there must be some number ${\displaystyle f(x_{0})}$ in ${\displaystyle \{1,\,2,\,\dots ,\,n\}.}$ We need to find a bijection from ${\displaystyle X-\{x_{0}\}}$ to ${\displaystyle \{1,\dots n-1\}}$ (which may be empty). Define a function ${\displaystyle g}$ such that ${\displaystyle g(x)=f(x)}$ if ${\displaystyle f(x)<f(x_{0}),}$ and ${\displaystyle g(x)=f(x)-1}$ if ${\displaystyle f(x)>f(x_{0}).}$ Then ${\displaystyle g}$ is a bijection from ${\displaystyle X-\{x_{0}\}}$ to ${\displaystyle \{1,\dots n-1\}.}$

Theorem: If a set ${\displaystyle X}$ has cardinality ${\displaystyle n,}$ then it cannot have any other cardinality. That is, ${\displaystyle X}$ cannot also have cardinality ${\displaystyle m\neq n.}$

Proof: If ${\displaystyle X}$ is empty (has cardinality 0), then there cannot exist a bijection from ${\displaystyle X}$ to any nonempty set ${\displaystyle Y,}$ since nothing mapped to ${\displaystyle y_{0}\in Y.}$ Assume, by induction that the result has been proven up to some cardinality ${\displaystyle n.}$ If ${\displaystyle X,}$ has cardinality ${\displaystyle n+1,}$ assume it also has cardinality ${\displaystyle m.}$ We want to show that ${\displaystyle m=n+1.}$ By the lemma above, ${\displaystyle X-\{x_{0}\}}$ must have cardinality ${\displaystyle n}$ and ${\displaystyle m-1.}$ Since, by induction, cardinality is unique for sets with cardinality ${\displaystyle n,}$ it must be that ${\displaystyle m-1=n,}$ and thus ${\displaystyle m=n+1.}$

Aleph numbers

Main article: Aleph number

Aleph-nought, aleph-zero, or aleph-null: the smallest infinite cardinal number, and the cardinal number of the set of natural numbers.

The aleph numbers are a sequence of cardinal numbers that denote the size of infinite sets, denoted with an aleph ${\displaystyle \aleph ,}$ the first letter of the Hebrew alphabet. The first aleph number is ${\displaystyle \aleph _{0},}$ called "aleph-nought", "aleph-zero", or "aleph-null", which represents the cardinality of the set of all natural numbers: ${\displaystyle \aleph _{0}=|\mathbb {N} |=|\{0,1,2,3,\cdots \}|.}$ Then, ${\displaystyle \aleph _{1}}$ represents the next largest cardinality. The most common way this is formalized in set theory is through Von Neumann ordinals, known as Von Neumann cardinal assignment.

Ordinal numbers generalize the notion of order to infinite sets. For example, 2 comes after 1, denoted ${\displaystyle 1<2,}$ and 3 comes after both, denote ${\displaystyle 1<2<3.}$ Then, one define a new number, ${\displaystyle \omega ,}$ which comes after every natural number, denoted ${\displaystyle 1<2<3<\cdots <\omega .}$ Further ${\displaystyle \omega <\omega +1,}$ and so on. More formally, these ordinal numbers can be defined as follows:

${\displaystyle 0:=\{\},}$ the empty set, ${\displaystyle 1:=\{0\},}$ ${\displaystyle 2:=\{0,1\},}$ ${\displaystyle 3:=\{0,1,2\},}$ and so on. Then one can define ${\displaystyle m<n{\text{, if }}\,m\in n,}$ for examlpe, ${\displaystyle 2\in \{0,1,2\}=3,}$ therefore ${\displaystyle 2<3.}$ Further, defining ${\displaystyle \omega$ :=\{0,1,2,3,\cdots \}} (a limit ordinal) gives ${\displaystyle \omega }$ the desired property of being the smallest ordinal greater than all finite ordinal numbers.

Since ${\displaystyle \omega \sim \mathbb {N} }$ by the natural correspondence, one may define ${\displaystyle \aleph _{0}}$ as the set of all finite ordinals. That is, ${\displaystyle \aleph _{0}:=\omega .}$ Then, ${\displaystyle \aleph _{1}}$ is the set of all countable ordinals (all ordinals ${\displaystyle \kappa }$ with cardinality ${\displaystyle |\kappa |\leq \aleph _{0}}$), the first uncountable ordinal. Since a set cannot contain itself, ${\displaystyle \aleph _{1}}$ must have a strictly larger cardinality: ${\displaystyle \aleph _{0}<\aleph _{1}.}$ Furthermore, ${\displaystyle \aleph _{2}}$ is the set of all ordinals with cardinality ${\displaystyle \aleph _{1},}$ and so on. By the well-ordering theorem, there cannot exist any set with cardinality between ${\displaystyle \aleph _{0}}$ and ${\displaystyle \aleph _{1},}$ and every infinite set has some cardinality corresponding to some aleph ${\displaystyle \aleph _{\alpha },}$ for some ordinal ${\displaystyle \alpha .}$

Cardinality of the continuum

Main article: Cardinality of the continuum

The number line, containing all points in its continuum.

The cardinality of the real numbers is denoted by "${\displaystyle {\mathfrak {c}}}$" (a lowercase fraktur script "c"), and is also referred to as the cardinality of the continuum. Cantor showed, using the diagonal argument, that ${\displaystyle {\mathfrak {c}}>\aleph _{0}.}$ We can show that ${\displaystyle {\mathfrak {c}}=2^{\aleph _{0}},}$ this also being the cardinality of the set of all subsets of the natural numbers.

The continuum hypothesis says that ${\displaystyle \aleph _{1}=2^{\aleph _{0}},}$ i.e. ${\displaystyle 2^{\aleph _{0}}}$ is the smallest cardinal number bigger than ${\displaystyle \aleph _{0},}$ i.e. there is no set whose cardinality is strictly between that of the integers and that of the real numbers. The continuum hypothesis is independent of ZFC, a standard axiomatization of set theory; that is, it is impossible to prove the continuum hypothesis or its negation from ZFC—provided that ZFC is consistent.^[35][36][37]

One of Cantor's most important results was that the cardinality of the continuum (${\displaystyle {\mathfrak {c}}}$) is greater than that of the natural numbers (${\displaystyle \aleph _{0}}$); that is, there are more real numbers R than natural numbers N. Namely, Cantor showed that ${\displaystyle {\mathfrak {c}}=2^{\aleph _{0}}=\beth _{1}}$ (see Beth one) satisfies:

${\displaystyle 2^{\aleph _{0}}>\aleph _{0}}$

(see Cantor's diagonal argument or Cantor's first uncountability proof).

The continuum hypothesis states that there is no cardinal number between the cardinality of the reals and the cardinality of the natural numbers, that is,

${\displaystyle 2^{\aleph _{0}}=\aleph _{1}}$

However, this hypothesis can neither be proved nor disproved within the widely accepted ZFC axiomatic set theory, if ZFC is consistent.

The first of these results is apparent by considering, for instance, the tangent function, which provides a one-to-one correspondence between the interval (−½π, ½π) and R.

The second result was first demonstrated by Cantor in 1878, but it became more apparent in 1890, when Giuseppe Peano introduced the space-filling curves, curved lines that twist and turn enough to fill the whole of any square, or cube, or hypercube, or finite-dimensional space. These curves are not a direct proof that a line has the same number of points as a finite-dimensional space, but they can be used to obtain such a proof.

Cantor also showed that sets with cardinality strictly greater than ${\displaystyle {\mathfrak {c}}}$ exist (see his generalized diagonal argument and theorem). They include, for instance:

• the set of all subsets of R, i.e., the power set of R, written P(R) or 2^R
• the set R^R of all functions from R to R

Both have cardinality

${\displaystyle 2^{\mathfrak {c}}=\beth _{2}>{\mathfrak {c}}}$

(see Beth two).

The cardinal equalities ${\displaystyle {\mathfrak {c}}^{2}={\mathfrak {c}},}$ ${\displaystyle {\mathfrak {c}}^{\aleph _{0}}={\mathfrak {c}},}$ and ${\displaystyle {\mathfrak {c}}^{\mathfrak {c}}=2^{\mathfrak {c}}}$ can be demonstrated using cardinal arithmetic:

${\displaystyle {\mathfrak {c}}^{2}=\left(2^{\aleph _{0}}\right)^{2}=2^{2\cdot {\aleph _{0}}}=2^{\aleph _{0}}={\mathfrak {c}},}$

${\displaystyle {\mathfrak {c}}^{\aleph _{0}}=\left(2^{\aleph _{0}}\right)^{\aleph _{0}}=2^{{\aleph _{0}}\cdot {\aleph _{0}}}=2^{\aleph _{0}}={\mathfrak {c}},}$

${\displaystyle {\mathfrak {c}}^{\mathfrak {c}}=\left(2^{\aleph _{0}}\right)^{\mathfrak {c}}=2^{{\mathfrak {c}}\cdot \aleph _{0}}=2^{\mathfrak {c}}.}$

Paradoxes

During the rise of set theory came along 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 arive 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 infinite sets (assuming the axiom of choice), 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.^[38]

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 busses arrives 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.^[38]

Skolem's paradox

Main article: Skolem's paradox

Illustration of the Löwenheim–Skolem theorem, where ${\displaystyle {\mathcal {M}}}$ and ${\displaystyle {\mathcal {N}}}$ are models of set theory, and ${\displaystyle \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".^[39]

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.^[40][39]

Real paradoxes

Cantor's paradox

Main article: Cantor's paradox

Cantor's theorem state's that, for any set ${\displaystyle A,}$ possibly infinite, its powerset ${\displaystyle {\mathcal {P}}(A)}$ has a strictly greater cardinality. For example, this means there is no bijection from ${\displaystyle \mathbb {N} }$ to ${\displaystyle {\mathcal {P}}(\mathbb {N} )\sim \mathbb {R} .}$ Cantor's paradox is a paradox in naive set theory, which proves there is not "set of all sets" or "universe set". It starts by assuming there is some set of all sets, ${\displaystyle U:=\{x\;|\;x\,{\text{ is a set}}\},}$ then it must be that ${\displaystyle U}$ is strictly smaller than ${\displaystyle {\mathcal {P}}(U),}$ thus ${\displaystyle |U|\leq |{\mathcal {P}}(U)|.}$ But since ${\displaystyle U}$ contains all sets, we must have that ${\displaystyle {\mathcal {P}}(U)\subseteq U,}$ and thus ${\displaystyle |{\mathcal {P}}(U)|\leq |U|.}$ Therefore ${\displaystyle |{\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 ${\displaystyle S:=\{X\,|X{\text{ is a cardinal number}}\}.}$ Then, if there is some largest element ${\displaystyle \aleph \in S,}$ then the powerset ${\displaystyle {\mathcal {P}}(\aleph )}$ is strictly greater, and thus not in ${\displaystyle S.}$ Conversly, if there is no largest element, then the union ${\displaystyle \bigcup S}$ contains the elements of all elements of ${\displaystyle S,}$ and is therefore greater than or equal to each element. Since there is no largest element in ${\displaystyle S,}$ for any element ${\displaystyle x\in S,}$ there is another element ${\displaystyle y\in S}$ such that ${\displaystyle |x|<|y|}$ and ${\displaystyle |y|\leq {\Bigl |}\bigcup S{\Bigr |}.}$ Thus, for any ${\displaystyle x\in S,}$ ${\displaystyle |x|<{\Bigl |}\bigcup S{\Bigr |},}$ and so ${\displaystyle {\Bigl |}\bigcup S{\Bigr |}\notin S.}$

Union and intersection

Main article: Inclusion-exclusion principle

If A and B are disjoint sets, then

${\displaystyle \left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert B\right\vert .}$

From this, one can show that in general, the cardinalities of unions and intersections are related by the following equation:^[41]

${\displaystyle \left\vert C\cup D\right\vert +\left\vert C\cap D\right\vert =\left\vert C\right\vert +\left\vert D\right\vert .}$

See also

• Aleph number
• Beth number
• Cantor's paradox
• Cantor's theorem
• Countable set
• Counting
• Ordinality
• Pigeonhole principle