Cardinality and infinity

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 ⁠\(\{1,2,3,4,\cdots\}\)⁠. For example, the set of even numbers ⁠\(\{2,4,6,\cdots\}\)⁠ 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 ⁠\(\aleph_0, \aleph_1, \aleph_2, ... \aleph_\omega, \aleph_{\omega+1}...\)⁠ 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 ⁠\(\aleph_0\)⁠. The question of whether the real numbers have cardinality ⁠\(\aleph_1\)⁠ 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.

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 does not know how many of each there are. Thus, cardinality is measured by putting sets in so-called one-to-one correspondence: each object in one set can be assigned a dedicated "pair" in the other, and no object from either set left unpaired. 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.

The basic concepts of cardinality are developed in terms of sets and functions, which are 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, ⁠\(S = \{1,2,3\}\)⁠ specifies a set, called ⁠\(S\)⁠, which contains the numbers 1, 2, and 3. The symbol ⁠\(\in\)⁠ represents set membership, for example ⁠\(1 \in S\)⁠ says "1 is a member of the set ⁠\(S\)⁠" which is true by the definition of ⁠\(S\)⁠ above. Here ⁠\(S\)⁠ 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, ⁠\(x\)⁠, one can determine whether ⁠\(x\)⁠ belongs to that set ⁠\((x \in S)\)⁠, or ⁠\(x\)⁠ does not belong to that set ⁠\((x \notin S)\)⁠. One example of an infinite set is the set of all natural numbers ⁠\(\{ 1,2,3,\cdots \}\)⁠.

A function, or correspondence, maps each member of one set to a unique member 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, the output is defined. For example, one may define a function ⁠\(f\)⁠ on the natural numbers by multiplying by two: ⁠\(f(1) = 2, \;\)⁠⁠\(f(2) = 4, \;\)⁠⁠\(f(3) = 6, \dots \,\)⁠ ⁠\(f(n) = 2n \dots\)⁠

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.

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, 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 ⁠\(A \sim B\)⁠, or ⁠\(A \approx B\)⁠. Alternatively, these sets may be said to be equivalent, similar, equipotent, or equipollent. For example, the set ⁠\(E = \{0, 2, 4, 6, \text{...}\}\)⁠ of even numbers has the same cardinality as the set ⁠\(\N = \{0, 1, 2, 3, \text{...}\}\)⁠ of natural numbers, since the function ⁠\(f(n) = 2n\)⁠ is a bijection from ⁠\(\N\)⁠ to ⁠\(E\)⁠.

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 do not work does not prove that there is no bijection. For example, the function ⁠\(g\)⁠ from ⁠\(\N\)⁠ to ⁠\(E\)⁠, defined by multiplying by 4, ⁠\(g(n) = 4n\)⁠, is injective, but not surjective (since 2, for instance, is not mapped to). Further, the function ⁠\(h\)⁠ from ⁠\(\N\)⁠ to ⁠\(E\)⁠, defined by rounding down to the nearest even number, ⁠\(h(n) = 2 \operatorname{floor}(n/2)\)⁠ (cf. floor function), is surjective, but not injective, (since 0 and 1 for instance both map to 0). Neither ⁠\(g\)⁠ nor ⁠\(h\)⁠ can challenge ⁠\(E \sim \N\)⁠, which was established by the existence of ⁠\(f\)⁠.

A set ⁠\(A\)⁠ is not larger than a set ⁠\(B\)⁠ if it can be mapped into ⁠\(B\)⁠ without overlap. That is, the cardinality of ⁠\(A\)⁠ is less than or equal to the cardinality of ⁠\(B\)⁠ if there is an injective function from ⁠\(A\)⁠ to ⁠\(B\)⁠, or equivalently, if there is a surjection from ⁠\(B\)⁠ to ⁠\(A\)⁠ (or ⁠\(A\)⁠ is empty). This is written ⁠\(A \preceq B\)⁠, or ⁠\(A \lesssim B\)⁠. and read as "⁠\(A\)⁠ is not greater than ⁠\(B\)⁠," or "⁠\(A\)⁠ is dominated by ⁠\(B\)⁠." If ⁠\(A \preceq B\)⁠, but there is no injection from ⁠\(B\)⁠ to ⁠\(A\)⁠, then ⁠\(A\)⁠ is said to be strictly smaller than ⁠\(B\)⁠, written without the underline as ⁠\(A \prec B\)⁠. For example, if ⁠\(A\)⁠ has four elements and ⁠\(B\)⁠ has five, then the following are true ⁠\(A \preceq A\)⁠, ⁠\(A \preceq B\)⁠, and ⁠\(A \prec B\)⁠.

The basic properties of an inequality are reflexivity (for any ⁠\(a\)⁠, ⁠\(a \leq a\)⁠), transitivity (if ⁠\(a \leq b\)⁠ and ⁠\(b \leq c\)⁠, then ⁠\(a \leq c\)⁠) and antisymmetry (if ⁠\(a \leq b\)⁠ and ⁠\(b \leq a\)⁠, then ⁠\(a = b\)⁠). Cardinal inequality ⁠\((\preceq)\)⁠ 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 (⁠\(f: A \to B\)⁠, and ⁠\(g: B \to A\)⁠), take set ⁠\(A\)⁠ and "color" each point blue. Then take the image of set ⁠\(B\)⁠ on ⁠\(A\)⁠ after the injection, that is, the set of points that the injection projects on to, and color those red. Then take the image of ⁠\(A\)⁠ on this image of ⁠\(B\)⁠, 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 in ⁠\(A\)⁠ that are definitively colored blue, map them into the next recursive image (i.e. by applying ⁠\(f\)⁠ then ⁠\(g\)⁠), leaving all other points in place. This transforms the set ⁠\(A\)⁠ into exactly the image of ⁠\(B\)⁠. Taking this transformation, followed by the inverse of ⁠\(g\)⁠, gives a bijection from ⁠\(A\)⁠ to ⁠\(B\)⁠ (since ⁠\(g\)⁠ is injective and surjective on its image, its inverse is bijective).

A further property of cardinal inequality is totality, which says that any two sets are comparable. That is, for any ⁠\(a\)⁠ and ⁠\(b\)⁠, either ⁠\(a \leq b\)⁠ or ⁠\(b \leq a\)⁠. 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 ⁠\(A \preceq B\)⁠ or ⁠\(B \preceq A\)⁠. This fact is equivalent to the axiom of choice.

A set is called countable if it is finite or has a bijection with the set of natural numbers ⁠\((\N)\)⁠, 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.

The rational numbers ⁠\((\Q)\)⁠ are those which can be expressed as the quotient or fraction ⁠\(\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, 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 over-cover the rationals, since, for example, the fractions ⁠\(\textstyle\frac{2}{4},\, \frac{3}{6}, \, \frac{4}{8}, \, \dots\)⁠ all get mapped to ⁠\(\textstyle\frac{1}{2}\)⁠, as the grid method treats these all as distinct ordered pairs. So this function shows ⁠\(\vert \Q \vert \leq \vert \N \vert\)⁠ not ⁠\(\vert \Q \vert = \vert \N \vert\)⁠. 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.

A number is called algebraic if it is a solution of some polynomial equation with integer coefficients. For example, the square root of two ⁠\(\sqrt2\)⁠ is a solution to ⁠\(x^2 - 2 = 0\)⁠, and the rational number ⁠\(p/q\)⁠ is the solution to ⁠\(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 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 subsection), 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.

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 ⁠\((\R)\)⁠, 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 ⁠\([0,1]\)⁠). Then, take the decimal representation of each real number, for example, ⁠\(0.5772...\)⁠ 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 list, 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 list, the second digit is different from the second number in the list, 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 is not 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.

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

These two sets, ⁠\(\R\)⁠ and ⁠\(\mathcal{P}(\N)\)⁠ can be shown to have the same cardinality (by, for example, assigning each subset to a decimal expansion) called the cardinality of the continuum.

Condensed: the full section is in Wikipedia.

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 ⁠\(A\)⁠ is generally denoted by ⁠\(\vert A \vert\)⁠, with a vertical bar on each side, though it may also be denoted by ⁠\(A\)⁠, ⁠\(\operatorname{card}(A)\)⁠, or ⁠\(\#A\)⁠.

For infinite sets, "cardinal number" is somewhat more difficult to define formally. However, 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 cardinality function ⁠\(A \mapsto \vert A \vert\)⁠ which satisfies ⁠\(A \sim B \iff \vert A \vert = \vert B \vert\)⁠ (in prose, "two sets are equinumerous exactly when they map to the same cardinal number"), 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, each of which group objects equivalent to one another. These equivalence classes are called the Frege-Russell cardinal numbers. However, these equivalence classes are too large to form sets (apart from the cardinal number ⁠\(\bold 0\)⁠ whose only element is the empty set), since, for example, the cardinal number ⁠\(\bold 1\)⁠ would be the set of all sets with one element, then ⁠\(\{ \bold 1 \} \in \bold 1\)⁠, and would therefore contain itself, violating regularity. Thus, due to John von Neumann, it is more common to assign representatives of these classes.

Given a basic sense of natural numbers, a set is said to have cardinality ⁠\(n\)⁠ if it can be put in one-to-one correspondence with the set ⁠\(\{1,\,2,\, \dots, \, n \}\)⁠, analogous to counting its elements. For example, the set ⁠\(S = \{ A,B,C,D \}\)⁠ has a natural correspondence with the set ⁠\(\{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". 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 ⁠\(A\)⁠ and ⁠\(B\)⁠, ⁠\(\vert A \cup B\vert = \vert A \vert + \vert B \vert\)⁠, intuitively meaning that the sum of the parts is equal to the whole. The multiplication principle asserts that given two sets ⁠\(A\)⁠ and ⁠\(B\)⁠, ⁠\(\vert A \times B\vert = \vert A \vert \cdot \vert B \vert\)⁠, intuitively meaning that there are ⁠\(\vert A \vert \cdot \vert B \vert\)⁠ 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 ⁠\(\{1,\,2,\, \dots, \, n\}\)⁠, for some natural number ⁠\(n\)⁠. However, there exist other definitions of "finite" which do not 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 to be equivalent to the original definition.

The aleph numbers are a sequence of cardinal numbers that represent the sizes of infinite sets, denoted with an aleph ⁠\(\aleph\)⁠, the first letter of the Hebrew alphabet. The first aleph number is ⁠\(\aleph_0\)⁠, called "aleph-nought", "aleph-zero", or "aleph-null", which represents the cardinality of the set of all natural numbers: ⁠\(\aleph_0 = \vert \N \vert = \vert\{0,1,2,3,\cdots\}\vert\)⁠. Then, ⁠\(\aleph_1\)⁠ represents the next largest cardinality, then ⁠\(\aleph_2\)⁠, 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 ⁠\(1 < 2\)⁠, and 3 comes after both, denoted ⁠\(1 < 2 < 3\)⁠. Then, one defines a new number, ⁠\(\omega\)⁠, which comes after every natural number, denoted ⁠\(1 < 2 < 3 < \cdots < \omega\)⁠. Further ⁠\(\omega < \omega+1< \dots < \omega+\omega=\omega\cdot 2\)⁠, and so on. More formally, these ordinal numbers can be defined as follows:

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

Since ⁠\(\omega \sim \N\)⁠ by the natural correspondence, one may define ⁠\(\aleph_0\)⁠ as the set of all finite ordinals. That is, ⁠\(\aleph_0 := \omega\)⁠. Then, ⁠\(\aleph_1\)⁠ is the set of all countable ordinals (all ordinals ⁠\(\alpha\)⁠ with cardinality ⁠\(\vert \alpha \vert \leq \aleph_0\)⁠), the first uncountable ordinal. Since a set cannot contain itself, ⁠\(\aleph_1\)⁠ must have a strictly larger cardinality: ⁠\(\aleph_0 < \aleph_1\)⁠. Furthermore, ⁠\(\aleph_2\)⁠ is the set of all ordinals with cardinality less than or equal to ⁠\(\aleph_1\)⁠, and in general the successor cardinal ⁠\(\kappa^+\)⁠is the set of all ordinals with cardinality up to ⁠\(\kappa\)⁠. Put another way for infinite cardinals, ⁠\(\kappa^+\)⁠ is the number of possible well-orderings on ⁠\(\kappa\)⁠ up to order isomorphism. Proving that such a set always exists is known as Hartogs' theorem, wherein the smallest ordinal not less or equal to than a set ⁠\(\kappa\)⁠ is called the Hartogs number of ⁠\(\kappa\)⁠. Then, ⁠\(\aleph_\lambda\)⁠ for a limit ordinal ⁠\(\lambda\)⁠ 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 ⁠\(\aleph_0\)⁠ and ⁠\(\aleph_1\)⁠, and every infinite set has some cardinality corresponding uniquely to some aleph ⁠\(\aleph_\alpha\)⁠, for some ordinal ⁠\(\alpha\)⁠. This allows one to use a constructive definition of the cardinality function, by assigning each set to its equinumerous aleph.

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 if ⁠\(A\)⁠ and ⁠\(B\)⁠ are disjoint then addition of these sets is simply taking their union, written as ⁠\(\vert A \cup B\vert = \vert A \vert + \vert B \vert\)⁠. Thus if ⁠\(A\)⁠ and ⁠\(B\)⁠ are infinite, cardinal addition is defined as ⁠\(\vert A \vert + \vert B \vert := \vert A \sqcup B\vert\)⁠ where ⁠\(\sqcup\)⁠ 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 ⁠\(\vert A \vert \cdot \vert B \vert := \vert A \times B\vert\)⁠, where ⁠\(\times\)⁠ denotes the Cartesian product. These definitions can be shown to satisfy the basic properties of standard arithmetic:

• Associativity: ⁠\(\vert A \vert + \vert B \sqcup C\vert = \vert A \sqcup B\vert + \vert C \vert\)⁠, and ⁠\(\vert A \vert \cdot \vert B \times C \vert = \vert A \times B \vert \cdot \vert C \vert\)⁠
• Commutativity: ⁠\(\vert A \vert + \vert B \vert = \vert B \vert + \vert A \vert\)⁠, and ⁠\(\vert A \vert \cdot \vert B \vert = \vert B \vert \cdot \vert A \vert\)⁠
• Distributivity: ⁠\(\vert A \vert \cdot \vert B \sqcup C\vert = \vert A \times B\vert + \vert A \times C\vert\)⁠

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 ⁠\(n\)⁠, ⁠\(n+n > n\)⁠. However, since both the set of even numbers ⁠\((E)\)⁠ and set of odd numbers ⁠\((F)\)⁠ have cardinality ⁠\(\aleph_0\)⁠, it shows ⁠\(\vert E \sqcup F \vert = \vert \N \vert\)⁠ thus ⁠\(\aleph_0 + \aleph_0 = \aleph_0\)⁠. In fact, for any infinite cardinal, ⁠\(\kappa+\kappa=\kappa\cdot\kappa=\kappa\)⁠. In this way, infinite cardinal addition and multiplication are considered to be remarkably well-behaved (at least under the Axiom of Choice).

Cardinal exponentiation ⁠\(\vert A \vert^{\vert B \vert}\)⁠ is defined via set exponentiation, the set of all functions ⁠\(f:B \mapsto A\)⁠, that is, ⁠\(\vert A \vert^{\vert B \vert} := \vert A^B\vert\)⁠ 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 ⁠\((0^0 = 1)\)⁠ since there is exactly one function from the empty set to itself: the empty function. A combinatorial argument can be used to show ⁠\(2^{\vert A \vert} = \vert\mathcal{P}(A)\vert\)⁠, 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 ⁠\(2^{\aleph_0}\)⁠does indeed correspond to some aleph, it is unprovable from standard set theories which aleph it corresponds to.

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 ⁠\(S := \{ X \, \vert X \text{ is a cardinal number}\}\)⁠. Then, if there is some largest cardinal ⁠\(\kappa \in S\)⁠, then the powerset ⁠\(2^\kappa\)⁠ is strictly greater, and thus not in ⁠\(S\)⁠. Conversely, if there is no largest element, then the union ⁠\(\bigcup S\)⁠ contains the elements of all elements of ⁠\(S\)⁠, and is therefore greater than or equal to each element. Since there is no largest element in ⁠\(S\)⁠, for any element ⁠\(x \in S\)⁠, there is another element ⁠\(y \in S\)⁠ such that ⁠\(\vert x \vert < \vert y \vert\)⁠ and ⁠\(\vert y \vert \leq \Bigl\vert \bigcup S \Bigr\vert\)⁠. Thus, for any ⁠\(x \in S\)⁠, ⁠\(\vert x \vert < \Bigl\vert \bigcup S \Bigr \vert\)⁠, and so ⁠\(\Bigl\vert \bigcup S \Bigr\vert \notin S\)⁠. 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".

The real numbers ⁠\((\R)\)⁠ 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. ⁠\(0.1234...\)⁠, with the usual arithmetic and order is a popular and sufficient choice for basic arguments involving the continuum. The cardinality of this set, denoted "⁠\(\mathfrak c\)⁠" (a lowercase fraktur script "c"), turns out to be remarkably stable under various transformations.

For example, all intervals on the real line e.g. ⁠\([0,1]\)⁠, and ⁠\([0,2]\)⁠, have the same cardinality as the entire set ⁠\(\R\)⁠. First, ⁠\(f(x) = 2x\)⁠ is a bijection from ⁠\([0,1]\)⁠ to ⁠\([0,2]\)⁠. 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 ⁠\(\textstyle\left( \frac{-\pi}{2} \, , \frac{\pi}{2} \right)\)⁠ to the whole real line. A more surprising example is the Cantor set, which is defined as follows: take the interval ⁠\([0,1]\)⁠ and remove the middle third ⁠\(\textstyle( \frac{1}{3}, \frac{2}{3} )\)⁠, 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 ⁠\([0,1]\)⁠. The Cantor set has a measure or "length" of zero, and yet is still equinumerous to the whole real line.

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 ⁠\(\R^2\)⁠ (two-dimensional space) ⁠\(\textstyle(0.a_1 a_2 a_3... \, , 0.b_1 b_2 b_3...)\)⁠, one can interleave their digits to get the unique number ⁠\(\textstyle0.a_1 b_1 a_2 b_2...\)⁠ in the unit interval ⁠\([0,1]\)⁠. 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 ⁠\(\vert \R^2 \vert \leq \vert \R \vert\)⁠ with the converse being immediate. Both of these methods can be reused at each dimension to show that ⁠\(\vert \R^n \vert = \vert \R^{n+1}\vert\)⁠ and thus ⁠\(\vert \R \vert = \vert \R^n\vert\)⁠ for any dimension ⁠\(n \geq 1\)⁠. Further, the infinite cartesian product ⁠\(\R^\infty\)⁠ can also be shown to be equinumerous to ⁠\(\R\)⁠ by cardinal arithmetic: ⁠\(\textstyle \vert \R^\infty\vert = \vert \R \vert^{\aleph_0} = (2^{\aleph_0} )^{\aleph_0} = 2^{(\aleph_0 \cdot \aleph_0)} = 2^{\aleph_0} = \vert \R \vert\)⁠. Thus, the real numbers, all finite-dimensional real spaces, and the countable cartesian product have the same cardinality.

Condensed: the full section is in Wikipedia.