Cardinality

For other uses, see Cardinality (disambiguation).

Error creating thumbnail:

A one-to-one correspondence between a set of apples and a set of oranges shows they have the same cardinality.

In mathematics, cardinality is an inherent property of sets, roughly meaning the number of individual objects they contain, which may be infinite. The concept is understood through one-to-one correspondences between sets. That is, if their objects can be paired such that each object has a pair, and no object is paired more than once.

Two sets are said to be equinumerous or have the same cardinality if there exists a one-to-one correspondence between them. Otherwise, under the axiom of choice, one of the two sets must be equinumerous with a strict subset of the other and is said to be strictly smaller than it; the other set is strictly larger. Using this concept, it is possible to show there are different sizes of infinity.

A set is countably infinite if it can be placed in one-to-one correspondence with the set of natural numbers Template:Tmath. For example, the set of even numbers Template:Tmath and the set of rational numbers are countable. Uncountable sets are those strictly larger than the set of natural numbers. The set of all real numbers and the powerset of the set of natural numbers are proven to be uncountable by so-called diagonal arguments. Cantor's theorem generalizes these arguments to show there is an infinite hierarchy of infinities.

For finite sets, cardinality recovers the usual concept of size as "number of elements." However, it is more often difficult to ascribe "sizes" to infinite sets. A system of cardinal numbers can be developed to extend the role of natural numbers in answering "how many". Most commonly, the Aleph numbers Template:Tmath are used, since their definition naturally extends the process of counting, and it can be shown that every infinite set has cardinality equivalent to some Aleph.

The set of natural numbers has cardinality Template:Tmath. The question of whether the real numbers have cardinality Template:Tmath is known as the continuum hypothesis, which has been shown to be both unprovable and undisprovable in standard set theories such as Zermelo–Fraenkel set theory. Alternative set theories and additional axioms give rise to different properties and have often strange or unintuitive consequences. However, every theory of cardinality using standard logical foundations of mathematics admits Skolem's paradox.

The basic concepts of cardinality go back as early as the 6th century BCE, and there are several close encounters with it throughout history, however, the results were generally dismissed as paradoxical. It is considered to have been first introduced formally to mathematics by Georg Cantor at the turn of the 20th century. Cantor's theory of cardinality was then formalized, popularized, and explored by many influential mathematicians of the time, and has since become a fundamental concept of mathematics.

Basics

Definition

Cardinality is an inherent property of sets which defines their size, roughly meaning the number of individual objects they contain. Fundamentally however, it is different from the concepts of number or counting as the cardinalities of two sets can be compared without referring to their number of elements, or defining number at all. For example, in the image above, a set of apples is compared to a set of oranges such that every fruit is used exactly once which shows these two sets have the same cardinality, even if one doesn't know how many of each there are. Thus, cardinality is measured by putting sets in one-to-one correspondence. If it is possible, the sets are said to have the same cardinality, and if not, one set is said to be strictly larger or strictly smaller than the other.

Sets and functions

	not surjective	surjective
not injective	Total function general function	File:Surjection.svg surjective only
injective	File:Injection.svg injective only	Error creating thumbnail: bijective

The basic concepts of cardinality are developed in terms of sets and functions, which are somewhat more abstract than their counterparts outside of mathematics. Informally, a set can be understood as any collection of objects, usually represented with curly braces. For example, Template:Tmath specifies a set, called Template:Tmath, which contains the numbers 1, 2, and 3. The symbol Template:Tmath represents set membership, for example Template:Tmath says "1 is a member of the set Template:Tmath" which is true by the definition of Template:Tmath above. Here Template:Tmath is finite, but that is not a requirement in general. The only requirement for a set is that it is well-defined. That is, for any object, Template:Tmath, one can determine whether Template:Tmath belongs to that set Template:Tmath, or Template:Tmath does not belong to that set Template:Tmath. One example of an infinite set is the set of all natural numbers Template:Tmath.

A function, or correspondence, maps members of one set to the members of another, often represented with an arrow diagram. For example, the adjacent table depicts several functions which map sets of natural numbers to sets of letters. If a function does not map two members to the same place, it is called injective. If a function covers every member in the output set, it is called surjective. If a function is both injective and surjective, it is called bijective or a one-to-one correspondence. Functions are not limited to those one can draw an arrow diagram for, so long as the function is well-defined. That is, for each possible input, one can determine the output. For example, one may define a function on the natural numbers by multiplying by two: Template:TmathTemplate:TmathTemplate:Tmath Template:Tmath

Etymology and related terms

The term cardinality originates from the post-classical Latin cardo ("to hinge"), which referred to something central or pivotal, both literally and metaphorically. This passed into medieval Latin and then into English, where cardinal came to describe things considered to be, in some sense, fundamental, such as, cardinal sins, cardinal directions, and (in linguistics) 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 German mathematician Georg Cantor in the late 19th century, who 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. Around 1930, the terms cardinality and cardinal number were adopted from the grammatical sense, and later translations would use these terms.

Comparing sets

Equinumerosity

"Equipollent" redirects here. Not to be confused with Equipollent (geometry).

File:Aplicación 2 inyectiva sobreyectiva04.svg

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.

An intuitive relationship between two sets having the "same size" is that their objects can be paired one-to-one. That is, if each object in one set can be assigned a dedicated "pair" in the other, and no object from either set left unpaired, it seems reasonable to say there are the same number of objects in each set. A one-to-one pairing between two sets defines a bijective function between them by mapping each object to its pair. Similarly, a bijection between two sets defines a pairing of their elements by pairing each object with the one it maps to. Therefore, these notions of "pairing" and "bijection" are, at least intuitively, equivalent. Thus, the following definition is given:

Two sets are said to have the same cardinality or be equinumerous if their members can be paired one-to-one. That is, if there exists a function between them which is bijective. This is often written as Template:Tmath, or Template:Tmath. Alternatively, these sets may be said to be equivalent, similar, equipotent, or equipollent. For example, the set Template:Tmath of even numbers has the same cardinality as the set Template:Tmath of natural numbers, since the function Template:Tmath is a bijection from Template:Tmath to Template:Tmath.

The property for finite sets that "the whole is greater than the part" is no longer true for infinite sets, and the existence of surjections or injections that don't work does not prove that there is no bijection. For example, the function Template:Tmath from Template:Tmath to Template:Tmath, defined by multiplying by 4, Template:Tmath, is injective, but not surjective (since 2, for instance, is not mapped to). Further, the function Template:Tmath from Template:Tmath to Template:Tmath, defined by rounding down to the nearest even number, Template:Tmath (cf. floor function), is surjective, but not injective, (since 0 and 1 for instance both map to 0). Neither Template:Tmath nor Template:Tmath can challenge Template:Tmath, which was established by the existence of Template:Tmath.

Equivalence

File:Example for a composition of two functions.svg

The composition of two functions applies one function to the output of another: Template:Tmath.

A fundamental result in developing a theory of cardinality is that equinumerosity forms an equivalence relation—that is, a relation satisfying the same three basic properties as equality: reflexivity, symmetry, and transitivity.

Reflexivity, the property that every set has the same cardinality as itself Template:Tmath, follows from the identity function: for any set Template:Tmath, the function that maps each element to itself is a bijection from Template:Tmath to Template:Tmath. Symmetry, the property that, if Template:Tmath has the same cardinality as Template:Tmath Template:Tmath, then Template:Tmath has the same cardinality as Template:Tmath Template:Tmath, holds because any bijection Template:Tmath has an inverse function Template:Tmath, which is also bijective. Transitivity, the property that if Template:Tmath and Template:Tmath have the same cardinality Template:Tmath, and Template:Tmath and Template:Tmath have the same cardinality Template:Tmath then so do Template:Tmath and Template:Tmath Template:Tmath, follows from the composition of functions: given bijections Template:Tmath and Template:Tmath, their composition Template:Tmath is a bijection from Template:Tmath to Template:Tmath (see image).

Since equinumerosity satisfies all three properties, it is an equivalence relation. This means that it groups sets into equivalence classes—groups of sets that are all equinumerous with one another—where each group defines a possible size of a set. This motivates the notion of cardinal numbers, which are representatives that stand for the "size" of each group, developed in the section below.

Inequality

File:Square to circle bijection.webm

Given the two injections between a circle and a square above, the Schröder–Bernstein theorem constructs the following bijection.

A set Template:Tmath is not larger than a set Template:Tmath if it can be mapped into Template:Tmath without overlap. That is, the cardinality of Template:Tmath is less than or equal to the cardinality of Template:Tmath if there is an injective function from Template:Tmath to Template:Tmath. This is written Template:Tmath, Template:Tmath and eventually Template:Tmath, and read as "Template:Tmath is not greater than Template:Tmath," or "Template:Tmath is dominated by Template:Tmath." If Template:Tmath, but there is no injection from Template:Tmath to Template:Tmath, then Template:Tmath is said to be strictly smaller than Template:Tmath, written without the underline as Template:Tmath or Template:Tmath. For example, if Template:Tmath has four elements and Template:Tmath has five, then the following are true Template:Tmath, Template:Tmath, and Template:Tmath.

The basic properties of an inequality are reflexivity (for any Template:Tmath, Template:Tmath), transitivity (if Template:Tmath and Template:Tmath, then Template:Tmath) and antisymmetry (if Template:Tmath and Template:Tmath, then Template:Tmath). Cardinal inequality Template:Tmath as defined above is reflexive since the identity function is injective, and is transitive by function composition. Antisymmetry—the fact that, given injections in both directions, then one can find a bijection—is non-trivial, and is the content of the so-called Schröder–Bernstein theorem. One such proof can be summarized as follows, with the help of the adjacent illustration:

Given injections in both directions (Template:Tmath, and Template:Tmath), take set Template:Tmath and "color" each point blue. Then take the image of set Template:Tmath on Template:Tmath after the injection—that is, the set of points that the injection projects on to—and color those red. Then take the image of Template:Tmath on this image of Template:Tmath, and color those points blue again. By recursively alternating the images of these sets, one obtains a "coloring" of the original set (see illustration). For each point, it either stops at some finite step—and thus is definitively colored blue or red—or continues switching indefinitely. Of the points that are definitively colored blue, map these points onto the next recursive image (i.e. by applying Template:Tmath then Template:Tmath), leaving all other points in place. The resulting set is exactly the image of Template:Tmath. Taking this transformation, followed by the inverse of Template:Tmath, gives a bijection from Template:Tmath to Template:Tmath.

A further property of cardinal inequality is totality, which says that any two sets are comparable. That is, for any Template:Tmath and Template:Tmath, either Template:Tmath or Template:Tmath. A full proof of which requires concepts introduced later, however the argument can be briefly summarized as follows. Every well-ordered set is isomorphic to a unique ordinal number, called the order type of the set. By the well-ordering theorem, every set can be well-ordered. Then, by comparing their order types, one can show that Template:Tmath or Template:Tmath. This fact is equivalent to the axiom of choice.

Countability

Countable sets

A set is called countable if it is finite or has a bijection with the set of natural numbers Template:Tmath, in which case it is called countably infinite. 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 (cf. § Pre-Cantorian set theory). However, several other examples have historically been considered surprising or initially unintuitive since the rise of set theory.

File:Diagonal argument.svg

File:Straight counter-clockwise spiral path in square grid.png

Two images of a visual depiction of a function from Template:Tmath to Template:Tmath. On the left, a version for the positive rational numbers. On the right, a spiral for all pairs of integers Template:Tmath for each fraction Template:Tmath.

The rational numbers Template:Tmath are those which can be expressed as the quotient or fraction Template:Tmath 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, 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 Template:Tmath gets mapped to by all the fractions Template:Tmath, as the grid method treats these all as distinct ordered pairs. So this function shows Template:Tmath not Template:Tmath. This can be corrected by "skipping over" these numbers in the grid, using the Schröder–Bernstein theorem, or by designing a function which does this naturally, for example using the Calkin–Wilf tree.

File:Algebraicszoom.png

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 Template:Tmath is a solution to Template:Tmath, and the rational number Template:Tmath is the solution to Template:Tmath. 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 transcendental 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 by ordering the polynomials lexicographically (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.

Hilbert's hotel

File:Hilbert's Hotel.png

Visual representation of Hilbert's hotel. Each guest goes to the room with a number that is double their room number, leaving the odd-numbered rooms vacant.

Hilbert's paradox of the Grand Hotel is a popular 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, one for each natural number, 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 3 to room 4, and in general, room n to room n+1. Then every guest still has a room, but room 1 is open for the new guest.

Then, the scenario continues by imagining an infinitely long 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 further 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.

Uncountable sets

Further information: § Cardinality of the continuum

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 Template:Tmath, which can be understood as the set of all numbers on the number line. One method of proving that the reals are uncountable is called Cantor's diagonal argument, credited to Cantor for his 1891 proof, though his method 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 Template:Tmath). Then, take the decimal representation of each real number, for example, Template:Tmath with a leading zero followed by any sequence of digits. The number 1 is included in this set since 1 = 0.999... Considering these real numbers in a column, it is always possible to 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. The new number must also have a unique decimal representation, that is, it cannot end in repeating nines or repeating zeros. For example, if the digit isn't 2, make the digit of the new number 2, and if it was 2, make it 3. 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.

Error creating thumbnail:

Template:Tmath does not have the same cardinality as its power set Template:Tmath: For every function f from Template:Tmath to Template:Tmath, the set Template:Tmath disagrees with every set in the range of Template:Tmath, hence Template:Tmath cannot be surjective. The picture shows an example Template:Tmath and the corresponding Template:Tmath; red: Template:Tmath, blue: Template:Tmath.

Another classical example of an uncountable set, established using a related reasoning, is the power set of the natural numbers, denoted Template:Tmath. This is the set of all subsets of Template:Tmath, including the empty set and Template:Tmath itself. The method is much closer to Cantor's original diagonal argument. Again, assume by contradiction that there exists a one-to-one correspondence Template:Tmath between Template:Tmath and Template:Tmath, so that every subset of Template:Tmath is assigned to some natural number. These subsets are then placed in a column, in the order defined by Template:Tmath (see image). Now, one may define a subset Template:Tmath of Template:Tmath which is not in the list by taking the negation of the "diagonal" of this column as follows:

If Template:Tmath, then Template:Tmath, that is, if 1 is in the first subset of the list, then 1 is not in the subset Template:Tmath. Further, if Template:Tmath, then Template:Tmath, that is if the number 2 is not in the second subset of the column, then 2 is in the subset Template:Tmath. Then in general, for each natural number Template:Tmath, Template:Tmath if and only if Template:Tmath, meaning Template:Tmath is put in the subset Template:Tmath only if the nth subset in the column does not contain the number Template:Tmath. Then, for each natural number Template:Tmath, Template:Tmath, meaning, Template:Tmath is not the nth subset in the list, for any number Template:Tmath, and so it cannot appear anywhere in the list defined by Template:Tmath. Since Template:Tmath was chosen arbitrarily, this shows that every function from Template:Tmath to Template:Tmath must be missing at least one element, therefore no such bijection can exist, and so Template:Tmath must be not be countable.

These two sets, Template:Tmath and Template:Tmath can be shown to have the same cardinality (by, for example, assigning each subset to a decimal expansion) called the cardinality of the continuum.

Cantor's theorem generalizes the second theorem above, showing that every set is strictly smaller than its powerset. In broad strokes, the proof goes as follows: Given a set Template:Tmath, assume by contradiction that there is a bijection Template:Tmath from Template:Tmath to Template:Tmath. Then, the subset Template:Tmath given by taking the negation of the "diagonal", formally, Template:Tmath, cannot be in the list. Therefore, every function is missing at least one element, and so Template:Tmath. Further, since Template:Tmath is itself a set, the argument can be repeated to show Template:Tmath. Taking Template:Tmath, this shows that Template:Tmath is even larger than Template:Tmath, which was already shown to be uncountable. Repeating this argument shows that there are infinitely many "sizes" of infinity.

Cardinal numbers

In the above sections, "the cardinality of a set" was described relationally. In other words, one set could be compared to another, intuitively comparing their "size". Cardinal numbers are a means of measuring this "size" more explicitly. For finite sets, this is simply the natural number found by counting the elements. This number is called the cardinal number of that set, or simply the cardinality of that set. The cardinal number of a set Template:Tmath is generally denoted by Template:Tmath, with a vertical bar on each side, though it may also be denoted by Template:Tmath, Template:Tmath, or Template:Tmath.

For infinite sets, "cardinal number" is somewhat more difficult to define formally. Cardinal numbers are not usually thought of in terms of their formal definition, but immaterially in terms of their arithmetic/algebraic properties. The assumption that there is some cardinal function Template:Tmath which satisfies Template:Tmath, sometimes called the axiom of cardinality or Hume's principle, is sufficient for deriving most properties of cardinal numbers.

Commonly in mathematics, if a relation satisfies the properties of an equivalence relation, the objects used to materialize this relation are equivalence classes, which groups all the objects equivalent to one another. These called the Frege–Russell cardinal numbers. However, this would mean that cardinal numbers are too large to form sets (apart from the cardinal number Template:Tmath whose only element is the empty set), since, for example, the cardinal number Template:Tmath would be the set of all sets with one element, then Template:Tmath, and would therefore contain itself, violating regularity. Thus, due to John von Neumann, it is more common to assign representatives of these classes.

Finite cardinals

Main articles: Finite set and Combinatorial principles

Error creating thumbnail:

A bijective function, Template:Tmath from the set X = {1,2,3,4} to the set Y demonstrates that Y has cardinality 4.

Given a basic sense of natural numbers, a set is said to have cardinality Template:Tmath if it can be put in one-to-one correspondence with the set Template:Tmath, analogous to counting its elements. For example, the set Template:Tmath has a natural correspondence with the set Template:Tmath, and therefore is said to have cardinality 4. Other terminologies include "Its cardinality is 4" or "Its cardinal number is 4". In formal contexts, the natural numbers can be understood as some construction of objects satisfying the Peano axioms—a list of properties, such that any system satisfying these properties is, in a certain sense, just like the natural numbers.

Showing that such a correspondence exists is not always trivial. Combinatorics is the area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. The notion cardinality of finite sets is closely tied to many basic combinatorial principles, and provides a set-theoretic foundation to recover them. It can be shown by induction on the possible sizes of sets that finite cardinality corresponds uniquely with natural numbers (cf. Finite set § Uniqueness of cardinality). This is related to several other concepts, verifying Hume's principle and the basis of bijective proofs, and is equivalent to a certain formulation of the pigeonhole principle, that a finite set cannot be put in one to one correspondence with a proper subset of itself.

The addition principle asserts that given disjoint sets Template:Tmath and Template:Tmath, Template:Tmath, intuitively meaning that the sum of the parts is equal to the whole. The multiplication principle asserts that given two sets Template:Tmath and Template:Tmath, Template:Tmath, intuitively meaning that there are Template:Tmath ways to pair objects from these sets. Both of these can be proven by a bijective proof, together with induction. The more general result is the inclusion–exclusion principle, which defines how to count the number of elements in overlapping sets.

Naturally, a set is defined to be finite if it is empty or can be put in correspondence with the set Template:Tmath, for some natural number Template:Tmath. However, there exist other definitions of "finite" which don't rely on a definition of "number." For example, a set is called Dedekind-finite if it cannot be put in one-to-one correspondence with a proper subset of itself, though this definition requires the axiom of choice.

Aleph numbers

File:Aleph0.svg

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 represent the sizes of infinite sets, denoted with an aleph Template:Tmath, the first letter of the Hebrew alphabet. The first aleph number is Template:Tmath, called "aleph-nought", "aleph-zero", or "aleph-null", which represents the cardinality of the set of all natural numbers: Template:Tmath. Then, Template:Tmath represents the next largest cardinality, then Template:Tmath, and so on. 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 Template:Tmath, and 3 comes after both, denoted Template:Tmath. Then, one defines a new number, Template:Tmath, which comes after every natural number, denoted Template:Tmath. Further Template:Tmath, and so on. More formally, these ordinal numbers can be defined as follows:

Template:Tmath, the empty set, Template:Tmath, Template:Tmath, Template:Tmath, and so on. Then one can define Template:Tmath, for example, Template:Tmath, therefore Template:Tmath. Defining Template:Tmath gives Template:Tmath the desired property of being the smallest ordinal greater than all finite ordinal numbers. Further, Template:Tmath, and so on.

Since Template:Tmath by the natural correspondence, one may define Template:Tmath as the set of all finite ordinals. That is, Template:Tmath. Then, Template:Tmath is the set of all countable ordinals (all ordinals Template:Tmath with cardinality Template:Tmath), the first uncountable ordinal. Since a set cannot contain itself, Template:Tmath must have a strictly larger cardinality: Template:Tmath. Furthermore, Template:Tmath is the set of all ordinals with cardinality less than or equal to Template:Tmath, and in general the successor cardinal Template:Tmathis the set of all ordinals with cardinality up to Template:Tmath. Put another way for infinite cardinals, Template:Tmath is the number of possible well-orderings on Template:Tmath up to order isomorphism. Proving that such a set always exists is known as Hartogs' theorem, wherein the smallest ordinal not less than or equal to than a set Template:Tmath is called the Hartogs number of Template:Tmath. Then, Template:Tmath for a limit ordinal Template:Tmath is the union of all lesser alephs.

The importance of ordinal numbers here is to generalize the notion of counting to infinite sets. When counting, one implicitly assigns an order to their set of objects, but no matter what order one assigns the final result of the count is always the same, which demonstrates the connection between cardinal and ordinal numbers. Further, by the well-ordering theorem, there cannot exist any set with cardinality between Template:Tmath and Template:Tmath, and every infinite set has some cardinality corresponding uniquely to some aleph Template:Tmath, for some ordinal Template:Tmath. This allows one to use a constructive definition of the cardinality function, by assigning each set to its equinumerous aleph.

Cardinal arithmetic

Error creating thumbnail:

The addition of the objects from the two disjoint sets is an instance of Template:Tmath.

Basic arithmetic can be done on cardinal numbers in a very natural way, by extending the theorems for finite combinatorial principles above. The intuitive principle that is Template:Tmath and Template:Tmath are disjoint then addition of these sets is simply taking their union, written as Template:Tmath. Thus if Template:Tmath and Template:Tmath are infinite, cardinal addition is defined as Template:Tmath where Template:Tmath denotes disjoint union. Similarly, the multiplication of two sets is intuitively the number of ways to pair their elements (as in the multiplication principle), therefore cardinal multiplication is defined as Template:Tmath, where Template:Tmath denotes the Cartesian product. These definitions can be shown to satisfy the basic properties of standard arithmetic:

• Associativity: Template:Tmath, and Template:Tmath
• Commutativity: Template:Tmath, and Template:Tmath
• Distributivity: Template:Tmath

Although a lot of properties of finite arithmetic hold for infinite arithmetic, as above and in the table below, strict inequalities (such as Kőnig's theorem) are rare. For example, in finite arithmetic, for any nonzero number Template:Tmath, Template:Tmath. However, since both the set of even numbers Template:Tmath and set of odd numbers Template:Tmath have cardinality Template:Tmath, it shows Template:Tmath thus Template:Tmath. In fact, for any infinite cardinal, Template:Tmath. In this way, infinite cardinal addition and multiplication are considered to be remarkably well-behaved (at least under the Axiom of Choice).

Cardinal exponentiation Template:Tmath is defined via set exponentiation, the set of all functions Template:Tmath, that is, Template:Tmath which naturally extends the role of "repeated multiplication" to infinite sets. For finite sets this can be shown to coincide with standard natural number exponentiation, but includes as a corollary that zero to the power of zero is one Template:Tmath since there is exactly one function from the empty set to itself: the empty function. A combinatorial argument can be used to show Template:Tmath, by considering the indicator function of each subset. In general, cardinal exponentiation is not as well-behaved as addition and multiplication. For example, even though it can be proven that the expression Template:Tmathdoes indeed correspond to some aleph, it is unprovable from standard set theories which aleph it corresponds to.

Basic results

Exponentiation	Inequality and Monotonicity	Identity elements	Absorption laws (for infinite A,B)
Template:Tmath	Template:Tmath implies Template:Tmath	Template:Tmath	Template:Tmath
Template:Tmath	Template:Tmath implies Template:Tmath	Template:Tmath	Template:Tmath
Template:Tmath	Template:Tmath implies Template:Tmath	Template:Tmath	Template:Tmath (annihilator)
Template:Tmath	Template:Tmath and Template:Tmath implies Template:Tmath		Template:Tmath

Set of all cardinal numbers

ת

The Hebrew letter Tav, denoting the proper class of all cardinal numbers

The set of all cardinal numbers refers to a hypothetical set which contains all cardinal numbers. Such a set cannot exist, which has been considered paradoxical, and related to the Burali-Forti paradox. Using the definition of cardinal numbers as representatives of their cardinalities. It begins by assuming there is some set Template:Tmath. Then, if there is some largest cardinal Template:Tmath, then the powerset Template:Tmath is strictly greater, and thus not in Template:Tmath. Conversely, if there is no largest element, then the union Template:Tmath contains the elements of all elements of Template:Tmath, and is therefore greater than or equal to each element. Since there is no largest element in Template:Tmath, for any element Template:Tmath, there is another element Template:Tmath such that Template:Tmath and Template:Tmath. Thus, for any Template:Tmath, Template:Tmath, and so Template:Tmath. Thus, the collection of all cardinal numbers is too large to form a set, and is a proper class. Georg Cantor denoted the collection of all cardinal numbers ת‎ (tav, the last letter of the Hebrew alphabet), and considered it to be an "inconsistent multiplicity".

Cardinality of the continuum

Main articles: Cardinality of the continuum and Continuum hypothesis

Error creating thumbnail:

The number line, containing all points in its continuum

The real numbers Template:Tmath formalize the intuitive notion of the continuum: the unbroken, gapless set of points on the number line. There are numerous ways to construct and analyze the continuum in set theory, for example, sets of Cauchy sequences of rational numbers, or Dedekind cuts. However, a somewhat informal definition as the set of infinite sequences of digits, e.g. Template:Tmath, with the usual arithmetic and order is a popular and sufficient choice for basic arguments involving the continuum. The cardinality of this set, denoted "Template:Tmath" (a lowercase fraktur script "c"), turns out to be remarkably stable under various transformations.

File:Cantor set binary tree.svg

First five iterations approaching the Cantor set

For example, all intervals on the real line e.g. Template:Tmath, and Template:Tmath, have the same cardinality as the entire set Template:Tmath. First, Template:Tmath is a bijection from Template:Tmath to Template:Tmath. The fact that two intervals of unequal length can be mapped one-to-one has been known, even if considered paradoxical, for thousands of years (cf. § Ancient history). Further, the tangent function is a bijection from the interval Template:Tmath to the whole real line. A more surprising example is the Cantor set, which is defined as follows: take the interval Template:Tmath and remove the middle third Template:Tmath, then remove the middle third of each of the two remaining segments, and continue removing middle thirds (see image). The Cantor set is the collection of points that survive this process. The remaining points are exactly those whose decimal expansion can be written in ternary without a 1. Reinterpreting these decimal expansions as binary (e.g. by replacing the 2s with 1s) gives a bijection between the Cantor set and the interval Template:Tmath. The Cantor set has a measure or "length" of zero, and yet is still equinumerous to the whole real line.

File:Peanocurve.svg

Three iterations of a Peano curve construction, whose limit is a space-filling curve

In the other direction, into higher dimensions, one can find a bijective map between a one-dimensional line and a two-dimensional square. Given a point in the unit square in Template:Tmath (two-dimensional space) Template:Tmath, one can interleave their digits to get the unique number Template:Tmath in the unit interval Template:Tmath. Space-filling curves offer a more visual proof, giving a continuous map from the unit interval onto the unit square. Classical examples include the Peano curve and Hilbert curve. Although these maps are not bijective, they are indeed sufficient to show Template:Tmath with the converse being immediate. Both of these methods can be reused at each dimension to show that Template:Tmath and thus Template:Tmath for any dimension Template:Tmath. Further, the infinite cartesian product Template:Tmath can also be shown to be equinumerous to Template:Tmath by cardinal arithmetic: Template:Tmath. Thus, the real numbers, all finite-dimensional real spaces, and the countable cartesian product have the same cardinality.

As shown in § Uncountable sets, the set of real numbers is strictly larger than the set of natural numbers. Specifically, Template:Tmath. The Continuum Hypothesis (CH) asserts that the real numbers have the next largest cardinality after the natural numbers, that is Template:Tmath. As shown by Gödel and Cohen, 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, meaning it produces no contradictions. The Generalized Continuum Hypothesis (GCH) extends this to all infinite cardinals, stating that Template:Tmath for every ordinal Template:Tmath. Research on CH and GCH continues independent of ZFC, especially in descriptive set theory and through the exploration of large cardinal axioms. Without GHC, the cardinality of Template:Tmath cannot be written in terms of specific alephs. The Beth numbers ( Template:Tmath, the second letter of the Hebrew alphabet) provide a concise notation for powersets of the real numbers starting from Template:Tmath, then Template:Tmath, and Template:Tmath, and in general Template:Tmath and Template:Tmath if Template:Tmath is a limit ordinal.

Alternative and additional axioms

Around the turn of the 20th century, set theory turned to an axiomatic approach to avoid rampant foundational issues related to its naive study (cf. § Axiomatic set theory). The most common axiomatic set theory used today is Zermelo–Fraenkel set theory (ZFC). In this system, the relevant axioms include: the Axiom of Infinity, stating roughly "there is an infinite set", specifically, a set with cardinality of the natural numbers Template:Tmath; the Axiom of power set, which says that, for any set Template:Tmath, the powerset Template:Tmath also exists; and the Axiom of Choice, explained below. ZFC has been criticized both for being too strong, and too weak. Similarly, there are many "natural extensions" of ZFC studied by set theorists. Thus, there exist many alternative systems of axioms each of which has implications to the standard theory of cardinality discussed above.

Without the axiom of choice

File:Axiome du choix.svg

For any infinite collection of "jars of marbles," the axiom of choice allows one to choose exactly one marble from each jar.

The Axiom of Choice (AC) is a fundamental principle in the foundations of mathematics which has seen much controversy in its history. Informally, it states that given any collection of non-empty sets, it is possible to construct a new set by choosing one element from each set, even if the collection is infinite. The controversy over AC had mostly to do with the nature of how it chose these elements. Whereas most axioms seem to describe what sets are or allow one to construct explicit sets, AC does not tell you which set you have constructed, just that such a choice function exists, leaving the constructed set implicit. It is hardly controversial to modern mathematicians, however, because of its unique historical controversy it is often given special treatment not given to other axioms that basic proofs which use it ought to call it out.

The Axiom of Choice is very closely related to the nature of cardinality. AC imposes a strict structure on what cardinality can be and what it means to compare to sets. Assuming AC is false, cardinality has a much more intricate structure and resists the kind of linear order AC offers. For example, cardinal inequality does not treat injection and surjection equivalently. Specifically, there exists sets, such that there is a surjection from Template:Tmath onto Template:Tmath, but no injection from Template:Tmath into Template:Tmath, thus injection is a strictly stronger notion. Similarly, although cardinal inequality maintains a partial order, there exist incomparable sets under cardinal inequality, that is, the law of trichotomy fails to hold, and there are sets such that none of Template:Tmath, Template:Tmath, Template:Tmath hold. Both of these (trichotomy and that surjection implies injection) are equivalent to AC.

Because trichotomy does not hold and the aleph sequence has a natural well-order, there exist sets whose cardinality does not correspond to any aleph. As such, the cardinality function Template:Tmath becomes somewhat more difficult to define. In fact, a cardinality function that maps each set to a unique "representative" of that cardinality—i.e. satisfying Hume's principle, and idempotence (Template:Tmath or Template:Tmath)—is impossible without AC. Set theories without AC address this by adopting the so-called Frege–Russell–Scott definition, introduced by Dana Scott, reminiscent of the Frege–Russell cardinal numbers. Under this definition, one considers the "Set of all sets" equinumerous with Template:Tmath, but applies Scott's trick to regularize these classes. Specifically, it reduces this class to only those sets of minimal rank; that is, those sets which appear earliest in the von Neumann hierarchy. Since the von Neumann hierarchy is well-ordered, there is a least rank, and since these sets all share that rank, their collection is bounded in the hierarchy and thus constitutes a set rather than a proper class.

Cardinal arithmetic is much more involved, losing many of its simplest identities. The identity Template:Tmath requires a well-defined notion of "max" which requires all sets to be comparable, and therefore does not hold. Similarly, the statement that Template:Tmath for every infinite cardinal Template:Tmath, and even the statement that the arbitrary product of non-zero cardinal numbers always non-zero—called the Multiplicative axiom by Bertrand Russell—are both equivalent to AC. Further, although the Generalized Continuum Hypothesis (GCH, that Template:Tmath for every Template:Tmath) is independent of ZFC, it can be shown ZF+GCH is sufficient to derive AC, and therefore, if AC is false, it follows that GCH does not hold.

Proper classes

Some set theories include classes, which are collections of sets, which allows theories to discuss any collection of sets without running into issues self-reference (e.g. the set of all sets that don't contain themselves.). A class is called a proper class when, at least intuitively, it is "too large" to form a set. For example, the Universe of all sets, the class of all cardinal numbers, and the class of all ordinal numbers are proper classes. Such set theories include Von Neumann–Bernays–Gödel set theory (NBG), and Morse–Kelley set theory (MK). Cantor originally called the size of these "too large" sets "Absolute infinite", separating it from the transfinite. The former he characterized by its "inconsistency", causing paradoxes, and associated the concept with God.

Proper classes can, in a sense, be assigned cardinalities. The first to formally distinguish between sets and classes was John von Neumann, who formalized the notion of "too large to form sets". More accurately, he defined a class to be "too big" (a proper class) if and only if it was equinumerous with the whole Universe of sets (cf. Axiom of limitation of size; used as an axiom in MK set theory, and derivable as a theorem in NBG). Thus, all proper classes have the same "size". The axiom has several implications, mostly relating to the limitation of size principles of early set theory. It implies the axiom of specification, the axiom of replacement, the axiom of union, and the axiom of global choice.

Large cardinals

File:Large Cardinals.jpg

Large cardinal hierarchy, ordered from bottom to top in terms of strength

Large cardinal axioms assert the existence of cardinal numbers which, as the name suggests, are very large—so large that they cannot be proven to exist within ZFC. For example, an inaccessible cardinal is, roughly, a cardinal that cannot be approached from below using basic set-theoretic operations such as unions, limits, and powersets (more formally, a regular, limit cardinal greater than Template:Tmath). Large cardinals are understood in terms of the Von Neumann hierarchy, denoted Template:Tmath (for some ordinal Template:Tmath), which can be understood as the sets that can be obtained from the empty set, followed by recursively applying the powerset Template:Tmath times. Specifically, Template:Tmath, Template:Tmath and Template:Tmath for a limit ordinal Template:Tmath.

There exist many known properties defining large cardinals, which come seemingly in a linear hierarchy, in terms of consistency strength. As an analogy, in ZFC without the Axiom of Infinity can only prove the existence of finite sets. Therefore Template:Tmath, whose existence is provable in usual ZFC, can serve as a model of ZFC–Infinity, and thus if ZFC is consistent, ZFC–Infinity is consistent. Analogously, ZFC+"There exists an inaccessible cardinal" implies the consistency of ZFC, since if Template:Tmath is inaccessible, Template:Tmath can serve as a model of ZFC (cf. Grothendieck universe). Stronger and stronger large cardinal axioms assert the existence of larger and larger cardinals, each of which proves the consistency—or inconsistency—of the weaker systems.

Large cardinals are at the forefront of set-theoretic research for both practical and philosophical reasons. In a practical sense, it is often the case that unproven or unprovable conjectures can be settled by sufficiently strong large cardinal axioms. For example, the existence of a measurable cardinal is inconsistent with Gödel's constructibility axiom. Similarly, the existence of a Reinhardt cardinal is inconsistent with the axiom of choice, which makes it a much more controversial large cardinal axiom. In a philosophical sense, according to a platonic view among set-theorists such as W. Hugh Woodin, these axioms simply extend the system to include sets that are "supposed" to be considered. That is, there is some fundamental universe of sets, which these axioms grant further access to. For this reason, large cardinal axioms are generally given preference compared to other possible axioms of set theory. This view is controversial among a competing philosophy, sometimes called pluralism, which posits that set theory should be understood as a multiverse of set theories, but no "absolute" or "true" model.

Determinacy

File:Banach-Tarski Paradox.svg

Illustration of the Banach–Tarski paradox, which arises in ZFC, but is impossible in ZF+AD

The Axiom of Determinacy (AD) asserts that certain kinds of mathematical games on the natural numbers are determined; that is, one player will always have a guaranteed winning strategy. The first serious study of the consequences of AD started during the 1960s in descriptive set theory—which, roughly, studies the definable sets of the real numbers—after it was noticed that it leads to very nice regulatory properties of the real numbers. However, it was shown that this axiom is inconsistent with AC and thus was never taken as a fundamental axiom of set theory.

AD is closely related to the cardinality of the real numbers, giving it a structure very different than under AC. Under AD, the real numbers cannot be well-ordered, meaning Template:Tmath does not correspond to any aleph. Despite this, AD imposes a rigid structure on the real numbers, known as the perfect set property, implying that every set of real numbers is either countable, or has cardinality of exactly Template:Tmath, equal to the whole real line. Similarly, it also implies that all sets of real numbers are Lebesgue measurable, eliminating the existence of sets whose size is non-zero, but cannot be assigned a length. Existence of such non-measurable sets allows the Banach–Tarski paradox, demonstrating that one can cut one sphere into finitely many pieces, smoothly rearrange them, and end with two solid spheres, which becomes impossible under AD.

On the other hand, due to the restrictions on what sets can exist, it implies that one can partition the real numbers into strictly more groups than there are real numbers. Specifically, one can find an injection to show that Template:Tmath (equivalence classes of reals, such that Template:Tmath iff Template:Tmath). However, if an injection Template:Tmath existed. then the image Template:Tmath would be a set, which cannot be assigned a measure, contradicting AD. So no such injection could exist, and thus Template:Tmath.

However, its relationship with large cardinals and the continuum hypothesis is still of heavy interest among set theorists such as Donald A. Martin, John R. Steel, and W. Hugh Woodin, at least in part because AD is equiconsistent with the large cardinal axiom that there exists infinitely many Woodin cardinals.

Skolem's paradox

Main article: Skolem's paradox

File:Lowenheim-skolem.svg

Illustration of the Löwenheim–Skolem theorem, where Template:Tmath and Template:Tmath are models of set theory, and Template:Tmath 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 in the language, such that the axioms of the theory are satisfied within this structure. In first-order logic, the Löwenheim–Skolem theorem states that if a theory has an infinite model, then it also has models of every other infinite cardinality. Applied to set theory, it asserts that Zermelo–Fraenkel set theory, which proves the existence of uncountable sets such as Template:Tmath, nevertheless has a countable model. Thus, Skolem's paradox was posed as follows: how can it be that there exists a domain of set theory which only contains countably many objects, but is capable of satisfying the statement "there exists a set with uncountably many elements"?

Skolem's paradox does not only apply to ZFC, but any first-order set theory, if it is consistent, has a model which is countable. A mathematical explanation of the paradox, showing that it is not a true contradiction in mathematics, was first given in 1922 by Thoralf Skolem, who asserted it as a reason against founding mathematics on first order logic. He explained that the countability or uncountability of a set is not absolute, but relative to the model in which the cardinality is measured. This is because, for example, if the set Template:Tmath is countable in a model of set theory then there is a bijection Template:Tmath. But a submodel containing Template:Tmath which excludes all such functions would thus contain no bijection between Template:Tmath and Template:Tmath, and therefore Template:Tmath would be uncountable. In second-order and higher-order logics, the Löwenheim–Skolem theorem does not hold. This is due to the fact that second-order logic quantifies over all subsets of the domain. 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.

History

Ancient history

File:AristotlesWheelLabeledDiagram.svg

Diagram of Aristotle's wheel as described in Mechanica

From the 6th century BCE, the writings of Greek philosophers, such as Anaximander, discuss infinite sets or objects, however, it was generally viewed as paradoxical and imperfect (cf. Zeno's paradoxes). Aristotle distinguished between the notions of actual 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", 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, roughly, the continuum). 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

File:Galileo Galilei (1564-1642) RMG BHC2700.tiff

File:Bernard Bolzano.jpg

Portrait of Galileo Galilei, c. 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 presents a seeming paradox in infinite sequences of numbers. It goes as follows: for each perfect square Template:Tmath 1, 4, 9, 16, and so on, there is a unique square root Template:Tmath 1, 2, 3, 4, and so on. Therefore, there are as many perfect squares as there are square roots. However, every number is a square root, since it can be squared, but not every number is a perfect square. Moreover, the proportion of perfect squares as one passes larger values diminishes, and is eventually smaller than any given fraction. Galileo 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.

In A Treatise of Human Nature (1739), David Hume is quoted for saying "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.

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, presented an early formulation of what would later be recognized as one-to-one correspondence between infinite sets. He discussed examples such as the pairing between the intervals Template:Tmath and Template:Tmath by the relation Template:Tmath, and revisited Galileo's paradox. However, he too resisted saying that these sets were, in that sense, the same size. 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.

Early set theory

Georg Cantor

refer to caption

Georg Cantor,     c. 1870

The concept of cardinality 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 together with ordinal numbers, which he viewed as abstractions of sets. For a given set Template:Tmath, he wrote Template:Tmath to mean the abstraction of that set from its elements, while maintaining their order, and cardinal numbers were a double abstraction, written Template:Tmath. Specifically, his definition was "the general concept which, with the aid of our intelligence, results from a set when we abstract from the nature of its various elements and from the order of their being given." This definition was considered to be imprecise, unclear, and purely psychological, and it would be some time before the concept was put on more rigorous footing. 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. This led to the formulation of the Continuum Hypothesis: whether Template:Tmath. Cantor was unable to resolve CH and left it as an open problem.

Other contributors

Parallel to Cantor’s development, Richard Dedekind independently formulated many advanced theorems of set theory, and helped establish set-theoretic foundations of algebra and arithmetic. Dedekind's The Nature and Meaning of Numbers (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 Template:Tmath have the same cardinality, in 1890, Giuseppe Peano introduced the Peano curve, which was a more visual proof that the unit interval Template:Tmath has the same cardinality as the unit square on Template:Tmath. This created a new area of mathematical analysis studying what is now called space-filling curves. In 1894, attempting to formalize Cantor's "cardinal number", Peano introduced "definition by abstraction": if one can define an equivalence relation, then one may define "that property" which an equivalence class describes. However, this was received harshly by Russell for not considering that this property may not be unique.

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 accepting Cantor's and Frege’s intuitions of cardinality. This definition of cardinal numbers is now referred to as the Frege–Russell definition. This definition was eventually superseded by the convention established by John von Neumann in 1928 which uses representatives to define cardinal numbers.

At the Paris conference of the International Congress of Mathematicians in 1900, David Hilbert, one of the most influential mathematicians of the time, gave a speech wherein he presented ten unsolved problems (of a total of 23, later published, now called Hilbert's problems). Of these, he placed "Cantor's problem" (now called the Continuum Hypothesis) as the first on the list. This list of problems would prove to be very influential in 20th century mathematics, and attracted a lot of attention from other mathematicians toward Cantor's theory of cardinality.

Axiomatic set theory

File:Hausdorff 1913-1921.jpg

Error creating thumbnail:

Felix Hausdorff 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 foundation through which infinite cardinals could be systematically studied while avoiding the paradoxes of naive set theory.

Ignoring possible foundational issues, during the early 1900s, Felix Hausdorff would begin studying "exorbitant numbers": roughly, very large cardinal numbers, or what are now called inaccessible cardinals. This work would be continued and popularized by several other influential set theorists such as Paul Mahlo—who introduced Mahlo cardinals—as well as Wacław Sierpiński, and Alfred Tarski. Their work would eventually be known collectively as the study of large cardinals.

In 1940, Kurt Gödel showed that the Continuum Hypothesis (CH) cannot be disproved from the axioms of ZFC by showing that both CH and AC hold in his constructible universe: an inner model of ZFC. The existence of a model of ZFC in which additional axioms hold shows that the additional axioms are (relatively) consistent with ZFC. 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. Cohen was awarded the Fields Medal in 1966 for his proof.

See also

• Cardinal and Ordinal Numbers
• Fuzzy set § Scalar cardinality
• Infinitary combinatorics
• Multiplicity (mathematics)
• Natural density
• Numerosity (mathematics)
• Subcountability

References

Primary sources

• Bolzano, Bernard (1950) [1851]. Přihonský, František (ed.). Paradoxes Of The Infinite. Translated by Steele, Donald A. London: Routledge and Kegan Paul.
• Cantor, Georg (1984) [1872–1884]. "Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen". Über unendliche, lineare Punktmannigfaltigkeiten: Arbeiten zur Mengenlehre aus den Jahren 1872–1884. Teubner-Archiv zur Mathematik (in German). Vienna: Springer. 2. doi:10.1007/978-3-7091-9516-1_2. ISBN 978-3-7091-9516-1. Retrieved 2025-05-24.
• Cantor, Georg (1883). "Ueber unendliche, lineare Punktmannichfaltigkeiten". Mathematische Annalen (in German). 21 (4): 545–591. doi:10.1007/BF01446819. ISSN 1432-1807.
• Cantor, Georg (1891). "Ueber eine elementare Frage der Mannigfaltigkeitslehre". Jahresbericht der Deutschen Mathematiker-Vereinigung. 1: 75–78.
• Cantor, Georg (1895). "Beiträge zur Begründung der transfiniten Mengenlehre". Mathematische Annalen (in German). 46 (4). doi:10.1007/BF02124929. ISSN 1432-1807.
• Cantor, Georg (1932) [1932]. Zermelo, Ernst (ed.). Gesammelte Abhandlungen. Berlin: Springer. doi:10.1007/978-3-662-00274-2. ISBN 978-3-662-00254-4.
• Cohen, P. J. (1963). "The Independence of the Continuum Hypothesis". Proceedings of the National Academy of Sciences of the United States of America. 50 (6): 1143–1148. Bibcode:1963PNAS...50.1143C. doi:10.1073/pnas.50.6.1143. ISSN 0027-8424. PMC 221287. PMID 16578557.
• Cohen, Paul J. (1964). "The Independence of the Continuum Hypothesis, II". Proceedings of the National Academy of Sciences of the United States of America. 51 (1): 105–110. Bibcode:1964PNAS...51..105C. doi:10.1073/pnas.51.1.105. JSTOR 72252. PMC 300611. PMID 16591132.
• Dedekind, Richard (1961) [1888]. Was sind und was sollen die Zahlen? (in German). Vieweg+Teubner Verlag Wiesbaden. doi:10.1007/978-3-663-02788-1.
• Ewald, William B., ed. (1996). From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics. 2. Oxford University Press. ISBN 0-19-850536-1.
• Gödel, Kurt (1938). "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis". Proceedings of the National Academy of Sciences. 24 (12): 556–557. Bibcode:1938PNAS...24..556G. doi:10.1073/pnas.24.12.556. PMC 1077160. PMID 16577857.
• Frege, Gottlob (1884). "IV. Der Begriff der Anzahl § 63. Die Möglichkeit der eindeutigen Zuordnung als solches. Logisches Bedenken, dass die Gleichheit für diesen Fall besonders erklärt wird". Die Grundlagen der Arithmetik – via Project Gutenberg. §63. Ein solches Mittel nennt schon Hume: »Wenn zwei Zahlen so combinirt werden, dass die eine immer eine Einheit hat, die jeder Einheit der andern entspricht, so geben wir sie als gleich an.«
• Galilei, Galileo (1914) [1638]. Dialogues Concerning Two New Sciences (PDF). Translated by Crew, Henry; De Salvio, Alfonso. New York: The Macmillan Company.
• Hartogs, Friedrich M. (1915). Felix Klein; Walther von Dyck; David Hilbert; Otto Blumenthal (eds.). "Über das Problem der Wohlordnung". Mathematische Annalen. Leipzig: B. G. Teubner. 76 (4). doi:10.1007/bf01458215. ISSN 0025-5831. S2CID 121598654.
• Hume, David (1739). "Part III. Of Knowledge and Probability: Sect. I. Of Knowledge". A Treatise of Human Nature – via Project Gutenberg.
• Langford, C. H. (1926). "Analytic Completeness of Sets of Postulates". Proceedings of the London Mathematical Society. 25 (1). doi:10.1112/plms/s2-25.1.115 – via Oxford Academic.
• Lévy, Azriel (1969), Bulloff, Jack J.; Holyoke, Thomas C.; Hahn, Samuel W. (eds.), "The Definability of Cardinal Numbers", Foundations of Mathematics, Berlin, Heidelberg: Springer, pp. 15–38, doi:10.1007/978-3-642-86745-3_3, ISBN 978-3-642-86747-7, archived from the original on 2023-03-11
• Peano, G. (1890). "Sur une courbe, qui remplit toute une aire plane". Mathematische Annalen (in French). 36 (1): 157–160. doi:10.1007/BF01199438. ISSN 1432-1807. Archived from the original on 2018-07-22. Alt URL
• Pincus, David (1974). "Cardinal representatives". Israel Journal of Mathematics. 18 (4): 321–344. doi:10.1007/BF02760841. ISSN 0021-2172.
•  Russell, Bertrand (2010) [1903]. The Principles of Mathematics. London: Routledge. ISBN 978-0-203-86476-0.
• Russell, B. (1907). "On Some Difficulties in the Theory of Transfinite Numbers and Order Types". Proceedings of the London Mathematical Society. s2-4 (1): 29–53. doi:10.1112/plms/s2-4.1.29. ISSN 1460-244X.
• Russell, Bertrand; Whitehead, Alfred North (1925) [1910]. Principia Mathematica. I (2nd ed.). London: Cambridge University Press. LCCN 25015133.
• Russell, Bertrand; Whitehead, Alfred North (1973) [1927]. Principia Mathematica (PDF). II (2nd ed.). London: Cambridge University Press. ISBN 0-521-06791-X. LCCN 25015133.
• Skolem, Thoralf (1962). Abstract Set Theory. University of Notre Dame Press.
• Steiner, Jacob (1867). Vorlesungen über synthetische Geometrie / 1 Die Theorie der Kegelschnitte in elementarer Form. Ghent University. Leipzig: Teubner.

Secondary and tertiary sources

• Abbott, Stephen (2015). Understanding Analysis. Undergraduate Texts in Mathematics (2nd ed.). New York: Springer Science+Business Media. doi:10.1007/978-1-4939-2712-8. ISBN 978-1-4939-2711-1. ISSN 0172-6056. LCCN 2015937969.
• Aigner, Martin; Ziegler, Günter M. (2018). Proofs from THE BOOK (6th ed.). Berlin: Springer-Verlag. doi:10.1007/978-3-662-57265-8. ISBN 978-3-662-57264-1. LCCN 2018940433. Alt URL
• 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.
• Bays, Timothy (2025). "Skolem's Paradox". In Zalta, Edward N.; Nodelman, Uri (eds.). The Stanford Encyclopedia of Philosophy (Spring 2025 ed.). Metaphysics Research Lab, Stanford University. Retrieved 2025-04-13.
• Bell, John L. (2021). "The Axiom of Choice". In Zalta, Edward N. (ed.). The Stanford Encyclopedia of Philosophy (Winter 2021 ed.). Metaphysics Research Lab, Stanford University. Retrieved 2026-05-02.
• Boolos, George (1996). Hart, W. D. (ed.). The Philosophy of Mathematics. New York: Oxford University Press. ISBN 978-0-19-875119-9. LCCN 95-49208.
• Bourbaki, Nicholas (1968). Theory of Sets. Éléments de mathématique. Paris: Éditions Hermann. LCCN 68-25177.
• Brualdi, Richard A. (2004) [1977]. Introductory combinatorics (4th ed.). Upper Saddle River: Pearson Education. ISBN 0-13-100119-1. LCCN 2004044455.
• Clegg, Brian (2003). A Brief History of Infinity. London: Constable & Robinson. ISBN 978-1-84119-650-3.
• Cohen, Paul Joseph (2008) [1966]. Set theory and the continuum hypothesis. Mineola, New York City: Dover Publications. ISBN 978-0-486-46921-8.
• Darling, David (2008). "Aristotle's Wheel". Universal Book of Mathematics. Hoboken: Wiley & Sons. ISBN 978-0-470-30788-5.
• Dasgupta, Abhijit (2013). Set Theory: With an Introduction to Real Point Sets. New York: Birkhäuser. doi:10.1007/978-1-4614-8854-5. ISBN 978-1-4614-8854-5. LCCN 2013949160.
• Demopoulos, William (1997). Frege's Philosophy of Mathematics. Cambridge: Harvard University Press. ISBN 978-0-674-31943-1. LCCN 94-34381.
• Drabkin, Israel E. (1950). "Aristotle's Wheel: Notes on the History of a Paradox". Osiris. 9. doi:10.1086/368528. JSTOR 301848. S2CID 144387607.
• Enderton, Herbert (1977). Elements of Set Theory. New York: Academic Press. ISBN 0-12-238440-7. LCCN 76-27438.
• Farlow, Stanley J. (2014). Paradoxes in Mathematics. Mineola: Dover Publications. ISBN 978-0-486-49716-7.
• Felgner, Ulrich (2023). Philosophy of Mathematics in Antiquity and in Modern Times. Science Networks. Historical Studies. Cham: Birkhäuser. doi:10.1007/978-3-031-27304-9. ISBN 978-3-031-27304-9. ISSN 2296-6080.
• Ferreirós, José (2007). Labyrinth of Thought: A History of Set Theory and Its Role in Modern Mathematics. 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. Alt URL
• Gamov, George (1947). One Two Three... Infinity. Viking Press. LCCN 62-24541. Archived on 2016-01-06
• Gugenheimer, Heinrich Walter (1963). Differential Geometry. Courier Dover Publications. Archived from the original on 2019-07-18.
• Hashisaki, Joseph; Peterson, John (1963). Theory of Arithmetic. New York: John Wiley & Sons. LCCN 63-11445.
• 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. Alt URL
• Hazewinkel, Michiel (2013) [1998]. Encyclopaedia of Mathematics: C An updated and annotated translation of the Soviet 'Mathematical Encyclopaedia'. 2. Dordrecht: Kluwer Academic Publishers. p. 24. doi:10.1007/978-94-009-6000-8. ISBN 978-94-009-6000-8. LCCN 87-26437.
• Heller, Michael; Woodin, W. Hugh (2011). Infinity: New Research Frontiers. New York: Cambridge University Press. ISBN 978-1-107-00387-3. LCCN 2010049374.
• 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.
• Jech, Thomas (2008) [1973]. The Axiom of Choice. Dover Books on Mathematics. Dover Publications. ISBN 9780486466248. ISSN 2693-051X. LCCN 73-15535.
• Jech, Thomas (2003) [1997]. Set Theory. Springer Monographs in Mathematics (3rd ed.). Berlin: Springer-Verlag. doi:10.1007/3-540-44761-X. ISBN 978-3-540-44085-7. ISSN 1439-7382.
• Joseph, George Gheverghese (2010). The Crest of the Peacock: Non-European Roots of Mathematics (3rd ed.). Princeton, New Jersey: Princeton University Press. ISBN 978-0-691-13526-7. Archived from the original on 2024-08-05. Alt URL
• Kanamori, Akihiro (2003) [1994]. The Higher Infinite: Large Cardinals in Set Theory from Their Beginnings. Springer Monographs in Mathematics (2nd ed.). Berlin: Springer-Verlag. doi:10.1007/978-3-540-88867-3. ISBN 978-3-540-88866-6. ISSN 1439-7382. LCCN 2008940025.
• Kleene, Stephen Cole (1952). Introduction To Metamathematics. New York: D. Van Nostrand Company.
• 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. Alt URL
• Koellner, Peter (2011). "Independence and Large Cardinals". In Zalta, Edward N. (ed.). The Stanford Encyclopedia of Philosophy (Summer 2011 ed.). Metaphysics Research Lab, Stanford University. Retrieved 2025-07-08.
• Koellner, Peter (2014). "Large Cardinals and Determinacy". In Zalta, Edward N. (ed.). The Stanford Encyclopedia of Philosophy (Spring 2014 ed.). Metaphysics Research Lab, Stanford University. Retrieved 2025-07-08.
• 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.
• Mayberry, John P. (2011). Foundations of Mathematics in the Theory of Sets. Encyclopedia of Mathematics and its Applications. Cambridge University Press. doi:10.1017/CBO9781139087124. ISBN 978-0-521-17271-4. ISSN 0953-4806.
• Moschovakis, Yiannis N. (1994). Notes on Set Theory. Undergraduate Texts in Mathematics. New York: Springer-Verlag. ISBN 978-0-387-94180-6. LCCN 93-35825.
• O'Connor, John J.; Robertson, Edmund F. (2000). "MacTutor – Jaina mathematics". MacTutor History of Mathematics Archive. Retrieved 2025-06-09 – via University of St Andrews, Scotland.
• Pickover, Clifford A. (2014). "Aristotle's Wheel Paradox". The Math Book: 250 Milestones in the History of Mathematics. New York: Barnes & Noble. ISBN 978-1-4351-4803-1.
• Pinter, Charles C. (2014) [1971]. A Book of Set Theory. Dover Books on Mathematics. Mineola: Dover Publications. ISBN 978-0-486-79549-2. ISSN 2693-051X. LCCN 2013024319. Archived from the original on 2024-08-04. Alt URL
• Potter, Michael (2004). Set Theory and its Philosophy: A Critical Introduction. Clarendon Press. ISBN 978-0-19-155643-2.
• Reck, Erich (2023). "Dedekind's Contributions to the Foundations of Mathematics". In Zalta, Edward N.; Nodelman, Uri (eds.). The Stanford Encyclopedia of Philosophy (Winter 2023 ed.). Metaphysics Research Lab, Stanford University. Retrieved 2025-07-11.
• Schumacher, Carol (1996). Chapter Zero: Fundamental Notions of Abstract Mathematics. Reading: Addison-Wesley. ISBN 9780201826531. LCCN 95-22675.
• Stewart, Ian (1995) [1981]. Concepts of modern mathematics. Dover Books on Mathematics. New York: Dover Publications. ISBN 9780486284248. ISSN 2693-051X. LCCN 94-39733. [URL]
• Stoll, Robert R. (1963). Set Theory and Logic. San Francisco: W. H. Freeman. LCCN 63-8995.
• Suppes, Patrick (1972) [1960]. Axiomatic Set Theory. Dover Books on Mathematics. New York: Dover Publications. ISBN 0-486-61630-4. ISSN 2693-051X. LCCN 72-86226. Archived from the original on 2014-08-06. Alt URL
• 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. Alt URL
• 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.
• Taylor, Alan D.; Wagon, Stan (2019). "A Paradox Arising from the Elimination of a Paradox". The American Mathematical Monthly. 126 (4): 306–318. doi:10.1080/00029890.2019.1559416. ISSN 0002-9890. JSTOR 48661905.
• van Dalen, Dirk; Ebbinghaus, Heinz-Dieter (Jun 2000). "Zermelo and the Skolem Paradox". The Bulletin of Symbolic Logic. 6 (2): 145–161. CiteSeerX 10.1.1.137.3354. doi:10.2307/421203. hdl:1874/27769. JSTOR 421203. S2CID 8530810.