Cardinality

In mathematics, cardinality is the measure of the "number of elements" of a set, a concept that extends the intuitive idea of counting to infinite collections. Two sets have the same cardinality if there exists a bijective function (a one‑to‑one correspondence) between their elements. The cardinality of a set \( A \) is commonly denoted \( |A| \), \( \operatorname{card}(A) \), or \( \# A \). Cardinality is a fundamental notion in set theory and forms the basis for the study of infinite numbers, cardinal arithmetic, and the hierarchy of infinities.

Definition and basic properties

A set \( A \) is said to have the same cardinality as a set \( B \), written \( A \sim B \), if there exists a bijection from \( A \) to \( B \). This relation is an equivalence relation on the class of all sets. The cardinal number (or simply cardinal) of a set \( A \) can be defined as its equivalence class under this relation, though in formal set theories such as Zermelo–Fraenkel with the Axiom of Choice (ZFC), cardinals are usually identified with certain von Neumann ordinal numbers (initial ordinals).

The order relation between cardinals is defined by \( |A| \le |B| \) if and only if there is an injective function from \( A \) to \( B \). The Cantor–Bernstein–Schröder theorem guarantees that if \( |A| \le |B| \) and \( |B| \le |A| \), then \( |A| = |B| \). Under the Axiom of Choice, the cardinals are totally ordered.

History

The notion of cardinality was introduced by Georg Cantor in the 1870s as part of his development of set theory. Cantor observed that infinite sets can be put into bijective correspondence with proper subsets of themselves, a property he used to define infinite sets. He showed that not all infinite sets have the same size: the set of real numbers is strictly larger than the set of natural numbers. This discovery led to the development of transfinite numbers and the modern theory of cardinal and ordinal numbers. Cantor’s work provoked foundational debates but ultimately became a cornerstone of mathematics.

Cardinal numbers

In ZFC, a cardinal number is an ordinal \( \kappa \) that is not equipotent with any smaller ordinal. Such ordinals are called initial ordinals. For finite sets, the cardinal number is simply the natural number that names the size of the set. For infinite sets, the cardinal numbers are traditionally denoted by the aleph numbers (\( \aleph_0, \aleph_1, \aleph_2, \dots \)) introduced by Cantor.

The Axiom of Choice ensures that every set can be well‑ordered and thus is equipotent to some initial ordinal, so every set has a cardinal number. Without the Axiom of Choice, a larger class of cardinalities exists, often studied via Scott’s trick or by other means that do not rely on well‑ordering.

Finite sets

A set is finite if its cardinality is a natural number, i.e., if it is either empty or can be put into bijection with a set of the form \( \{0, 1, \dots, n-1\} \) for some \( n \in \mathbb{N} \). Finite cardinal arithmetic coincides with ordinary arithmetic on natural numbers. The empty set has cardinality 0, and for disjoint finite sets \( A \) and \( B \), \( |A \cup B| = |A| + |B| \). The cardinality of the Cartesian product of two finite sets is \( |A \times B| = |A| \cdot |B| \).

Infinite sets and aleph numbers

An infinite set is a set that is not finite. The smallest infinite cardinal is \( \aleph_0 \) (aleph‑null), the cardinality of the natural numbers \( \mathbb{N} \). Any set with cardinality \( \aleph_0 \) is called countably infinite. The next larger cardinal is \( \aleph_1 \), followed by \( \aleph_2 \), and so on. The sequence of alephs is indexed by the ordinal numbers.

Countable sets

A set is countable if its cardinality is less than or equal to \( \aleph_0 \); it is countably infinite if it is countable and infinite, i.e., \( |A| = \aleph_0 \). Examples of countably infinite sets include the integers \( \mathbb{Z} \), the rational numbers \( \mathbb{Q} \), and the set of all finite sequences from a countable alphabet. A classic proof shows that \( \mathbb{Q} \) is countable by enumerating fractions in a diagonal grid.

Uncountable sets and the continuum

A set is uncountable if its cardinality is strictly greater than \( \aleph_0 \). The most familiar uncountable set is the set of real numbers \( \mathbb{R} \), whose cardinality is denoted by \( \mathfrak{c} \) (the continuum). Cantor’s diagonal argument demonstrates that \( \mathfrak{c} > \aleph_0 \). The cardinality of the power set of \( \mathbb{N} \) is also \( \mathfrak{c} \), and in general the cardinality of the power set of a set of size \( \kappa \) is \( 2^{\kappa} \). The relationship \( 2^{\aleph_0} = \mathfrak{c} \) is a starting point for the continuum problem.

Cardinal arithmetic

Cardinal numbers can be added, multiplied, and exponentiated, extending ordinary arithmetic on natural numbers but with different behaviors for infinite cardinals.

Addition and multiplication

For cardinals \( \kappa \) and \( \lambda \), the sum \( \kappa + \lambda \) is defined as the cardinality of the disjoint union of sets with those cardinalities. The product \( \kappa \cdot \lambda \) is the cardinality of the Cartesian product. For infinite cardinals, these operations are trivial under the Axiom of Choice: if \( \kappa \) and \( \lambda \) are infinite and at least one is nonzero, then
\[
\kappa + \lambda = \kappa \cdot \lambda = \max(\kappa, \lambda).
\]
Without the Axiom of Choice, addition and multiplication may not be so well‑behaved, and infinite Dedekind‑finite sets can exhibit different properties.

Exponentiation and Cantor’s theorem

Cardinal exponentiation \( \kappa^{\lambda} \) is defined as the cardinality of the set of all functions from a set of size \( \lambda \) to a set of size \( \kappa \). Cantor’s theorem states that for any cardinal \( \kappa \), the power set cardinal \( 2^{\kappa} \) is strictly larger than \( \kappa \), i.e., \( 2^{\kappa} > \kappa \). This yields a never‑ending hierarchy of infinite cardinals. For example, \( 2^{\aleph_0} = \mathfrak{c} \), and \( 2^{\mathfrak{c}} \) is larger still.

The continuum hypothesis and generalized continuum hypothesis

The continuum hypothesis (CH) asserts that there is no cardinal strictly between \( \aleph_0 \) and \( \mathfrak{c} \), i.e., \( 2^{\aleph_0} = \aleph_1 \). The generalized continuum hypothesis (GCH) states that for every infinite cardinal \( \kappa \), \( 2^{\kappa} = \kappa^+ \), where \( \kappa^+ \) is the smallest cardinal larger than \( \kappa \). Both statements are independent of ZFC: they cannot be proved or disproved from the standard axioms, as shown by Kurt Gödel (consistency) and Paul Cohen (independence via forcing). The continuum hypothesis remains a central topic in set theory and the philosophy of mathematics.

Large cardinals and further notions

Beyond the alephs, set theorists study large cardinals—cardinals that cannot be proved to exist within ZFC but whose existence implies strong consistency properties. Examples include inaccessible cardinals, measurable cardinals, and Woodin cardinals. These notions often involve elementary embeddings or ultrafilters and are connected to the search for new axioms of set theory.

In contexts without the Axiom of Choice, cardinality becomes more nuanced: sets may be incomparable in size, and the concept of cardinality is sometimes replaced by studies of equivalence classes under bijection without a canonical least representative.

Cardinality in other areas

Cardinality extends beyond pure set theory. In model theory, the cardinality of a structure refers to the size of its underlying set, and the Löwenheim–Skolem theorems reveal limitations on the sizes of models of first‑order theories. In topology and analysis, cardinality arguments are used to distinguish sizes of bases, determine separability, or construct pathological objects via transfinite induction. In computer science, cardinality (often finite) is used in database theory, combinatorics, and algorithm analysis, while the concept of infinite cardinalities appears in the theory of computability and formal languages.