Functions & Cardinality

Functions are the central objects of mathematics — they formalize the idea of a rule that assigns to each input exactly one output, and they provide the only rigorous way to compare the sizes of sets. The theory of cardinality, built entirely on the notion of bijection, was developed by Georg Cantor in the 1870s and 1880s, and it revealed one of the most astonishing facts in all of mathematics: there are different sizes of infinity. This topic develops the precise machinery of functions and then uses it to explore the landscape of infinite cardinal numbers, from the countable to the uncountable and beyond.

Functions as Fundamental Objects

In modern mathematics, a function $f$ from a set $A$ to a set $B$, written $f \colon A \to B$, is defined as a relation between $A$ and $B$ with the property that every element of $A$ is paired with exactly one element of $B$. More precisely, $f$ is a subset of the Cartesian product $A \times B$ such that for every $a \in A$, there exists a unique $b \in B$ with $(a, b) \in f$. We write $f(a) = b$ and call $A$ the domain of $f$, $B$ the codomain, and the set $\{f(a) : a \in A\}$ the range or image of $f$. The distinction between codomain and range is important: the codomain is the set that the function is declared to map into, while the range is the set of values it actually hits.

This set-theoretic definition, treating a function as a special kind of set of ordered pairs, was crystallized in the early twentieth century by mathematicians working to place analysis on rigorous foundations. But the intuitive concept is much older. Peter Gustav Lejeune Dirichlet, in an 1837 paper on the representation of functions by trigonometric series, gave what is often cited as the first modern definition: a function is any rule that assigns to each value of an independent variable a unique value of a dependent variable, with no requirement that the rule be given by a formula or expression. This was a radical broadening — earlier mathematicians like Euler and Fourier had thought of functions as analytic expressions, limiting the concept unnecessarily.

Three properties of functions play a decisive role in the theory of cardinality. A function $f \colon A \to B$ is an injection (or is one-to-one) if distinct elements of $A$ are mapped to distinct elements of $B$: whenever $f(a_1) = f(a_2)$, it follows that $a_1 = a_2$. It is a surjection (or is onto) if every element of $B$ is in the range of $f$: for every $b \in B$, there exists some $a \in A$ with $f(a) = b$. A function that is both injective and surjective is a bijection — it pairs elements of $A$ with elements of $B$ in a perfect one-to-one correspondence, with nothing left over on either side.

Given functions $f \colon A \to B$ and $g \colon B \to C$, their composition $g \circ f \colon A \to C$ is defined by $(g \circ f)(a) = g(f(a))$. Composition preserves injectivity and surjectivity: if both $f$ and $g$ are injective, so is $g \circ f$, and likewise for surjections. A function $f \colon A \to B$ has an inverse function $f^{-1} \colon B \to A$ if and only if $f$ is a bijection. In that case, $f^{-1}(f(a)) = a$ for all $a \in A$ and $f(f^{-1}(b)) = b$ for all $b \in B$.

One of the deepest results about injections and bijections is the Schroder-Bernstein theorem (also called the Cantor-Bernstein-Schroder theorem). It states that if there exists an injection from $A$ to $B$ and an injection from $B$ to $A$, then there exists a bijection between $A$ and $B$:

$\text{If } f \colon A \hookrightarrow B \text{ and } g \colon B \hookrightarrow A, \text{ then } |A| = |B|.$

This theorem is remarkable because it allows us to establish that two sets have the same cardinality without ever constructing an explicit bijection — we only need injections in both directions, which are often much easier to find. The proof, first given rigorously by Ernst Schroder in 1898 and independently by Felix Bernstein (then a nineteen-year-old student of Cantor) in 1897, works by partitioning $A$ into orbits under the back-and-forth iteration of $g \circ f$ and piecing together a bijection from the two injections. Cantor had stated the result earlier but without a complete proof.

Cardinality and Equinumerosity

The concept of cardinality answers the question: when do two sets have the same size? For finite sets, the answer is obvious — count the elements and compare. But for infinite sets, counting fails, and a subtler approach is needed. Cantor’s brilliant insight was to define size comparison purely in terms of functions. Two sets $A$ and $B$ are equinumerous (or equipotent), written $|A| = |B|$ or $A \approx B$, if and only if there exists a bijection $f \colon A \to B$. The cardinality of a set is, informally, the equivalence class of all sets equinumerous to it — a measure of “how many” elements it contains.

For finite sets, cardinality coincides with ordinary counting: $|\{a, b, c\}| = 3$. A set is finite if it is equinumerous with some set $\{1, 2, \ldots, n\}$ for a natural number $n$, and infinite otherwise. Richard Dedekind gave an elegant alternative characterization in 1888: a set is infinite if and only if it is equinumerous with one of its proper subsets. This is known as Dedekind-infinite, and it captures the essential strangeness of infinity — an infinite set can be put into bijection with a part of itself, something impossible for finite sets.

The first surprise of infinite cardinality is that sets which appear to be of very different sizes can turn out to be equinumerous. Consider the natural numbers $\mathbb{N} = \{0, 1, 2, 3, \ldots\}$ and the integers $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$. The integers seem “twice as large” as the naturals since they extend in both directions. Yet the function $f \colon \mathbb{N} \to \mathbb{Z}$ defined by $f(n) = n/2$ when $n$ is even and $f(n) = -(n+1)/2$ when $n$ is odd is a bijection, giving the enumeration $0, -1, 1, -2, 2, -3, 3, \ldots$ of all integers. Therefore $|\mathbb{N}| = |\mathbb{Z}|$.

Even more startling, the rational numbers $\mathbb{Q}$ — which are densely packed along the number line, with infinitely many rationals between any two distinct reals — also have the same cardinality as $\mathbb{N}$. This was one of Cantor’s earliest and most counterintuitive results. The proof will be detailed in the next section, but the punchline is already visible: for infinite sets, cardinality is not about density or geometric extent but solely about the existence of bijections.

Cardinality also supports an ordering. We write $|A| \leq |B|$ if there exists an injection from $A$ to $B$, and $|A| < |B|$ if there is an injection but no bijection. The Schroder-Bernstein theorem, discussed above, ensures that this ordering is antisymmetric: if $|A| \leq |B|$ and $|B| \leq |A|$, then $|A| = |B|$. Cantor defined cardinal arithmetic for infinite sets by extending the familiar operations: the sum $|A| + |B|$ is the cardinality of the disjoint union $A \sqcup B$, the product $|A| \cdot |B|$ is the cardinality of $A \times B$, and the exponentiation $|B|^{|A|}$ is the cardinality of the set of all functions from $A$ to $B$. For infinite cardinals, these operations behave very differently from finite arithmetic — for instance, $\aleph_0 + \aleph_0 = \aleph_0$ and $\aleph_0 \cdot \aleph_0 = \aleph_0$, where $\aleph_0$ denotes the cardinality of $\mathbb{N}$.

Countable and Uncountable Sets

A set is countably infinite if it is equinumerous with $\mathbb{N}$, and countable if it is either finite or countably infinite. A set that is not countable is uncountable. The countably infinite sets form the smallest type of infinity — they are, in a precise sense, the most manageable infinite sets, because their elements can be listed in a sequence $a_0, a_1, a_2, \ldots$ that eventually reaches every element.

The proof that $\mathbb{Q}$ is countable is a gem of Cantor’s work. Arrange all positive fractions $p/q$ (allowing duplicates) in an infinite grid where the fraction in row $p$, column $q$ is $p/q$. Now traverse this grid along successive anti-diagonals: $1/1$, then $1/2, 2/1$, then $1/3, 2/2, 3/1$, then $1/4, 2/3, 3/2, 4/1$, and so on. This zig-zag enumeration (sometimes called the Cantor pairing) visits every positive fraction exactly once (skipping duplicates like $2/2 = 1/1$ if desired). Including zero and the negative rationals by interleaving, as in the $\mathbb{Z}$ argument above, gives a bijection $\mathbb{N} \to \mathbb{Q}$. The rational numbers, despite being dense in the reals, are merely countable.

Several powerful closure properties hold for countable sets. A countable union of countable sets is countable: if $A_0, A_1, A_2, \ldots$ are each countable, then $\bigcup_{n=0}^{\infty} A_n$ is countable. The proof is an extension of the zig-zag argument — enumerate the elements of each $A_n$ as a row in an infinite grid, then traverse the grid diagonally. As a consequence, the set of algebraic numbers (roots of polynomial equations with integer coefficients) is countable, since the polynomials of degree $n$ with integer coefficients are countable for each $n$, and each such polynomial has at most $n$ roots. This result, published by Cantor in 1874, was historically significant: it showed that “most” real numbers, in the sense of cardinality, cannot be algebraic.

But the most dramatic result in this theory is negative. Not every infinite set is countable. The set of real numbers $\mathbb{R}$ is uncountable — it is strictly larger than $\mathbb{N}$. Cantor first proved this in 1874 using a topological argument based on nested intervals, and then in 1891 he gave his celebrated diagonal argument, a technique so powerful and versatile that it has been called the most important proof method in set theory. The uncountability of $\mathbb{R}$ draws a sharp line through the world of infinite sets: there are at least two fundamentally different sizes of infinity, and the infinite is not a monolith.

Cantor’s Diagonal Argument and Cardinal Bounds

Cantor’s 1891 diagonal argument is beautifully simple. Suppose, for contradiction, that the real numbers in the interval $[0,1)$ are countable. Then they can be listed as a sequence $r_0, r_1, r_2, \ldots$, where each $r_n$ has a decimal expansion $r_n = 0.d_{n,0}\, d_{n,1}\, d_{n,2}\, \ldots$ Now construct a new real number $s = 0.s_0\, s_1\, s_2\, \ldots$ by choosing each digit $s_n$ to differ from $d_{n,n}$ — the $n$-th digit of the $n$-th number on the list. For concreteness, set $s_n = 5$ if $d_{n,n} \neq 5$, and $s_n = 6$ if $d_{n,n} = 5$. The number $s$ lies in $[0,1)$ but differs from every $r_n$ in at least the $n$-th decimal place, so $s$ is not on the list. This contradicts the assumption that the list was complete. Therefore $[0,1)$ is uncountable, and since $[0,1) \subseteq \mathbb{R}$, the reals are uncountable.

The diagonal argument is far more than a one-off trick. Cantor used the same idea to prove the power set theorem: for any set $A$ (finite or infinite), the power set $\mathcal{P}(A)$ has strictly greater cardinality than $A$ itself:

$|A| < |\mathcal{P}(A)|$

The proof proceeds by contradiction. The function $a \mapsto \{a\}$ is an injection from $A$ to $\mathcal{P}(A)$, so $|A| \leq |\mathcal{P}(A)|$. Suppose for contradiction that a bijection $f \colon A \to \mathcal{P}(A)$ exists. Define the set $D = \{a \in A : a \notin f(a)\}$. Since $f$ is a surjection, $D = f(d)$ for some $d \in A$. But then: if $d \in D$, then by definition of $D$, $d \notin f(d) = D$, a contradiction; and if $d \notin D$, then $d \notin f(d)$, so by definition of $D$, $d \in D$, again a contradiction. Therefore no bijection exists and $|A| < |\mathcal{P}(A)|$.

This theorem has a staggering consequence: there is no largest cardinal number. Starting from $\mathbb{N}$ with cardinality $\aleph_0$, we can form $\mathcal{P}(\mathbb{N})$ with cardinality $2^{\aleph_0}$, then $\mathcal{P}(\mathcal{P}(\mathbb{N}))$ with cardinality $2^{2^{\aleph_0}}$, and so on without end. Each step produces a set of strictly greater cardinality. The infinite is not a single vast expanse but an endless hierarchy of ever-larger infinities.

This hierarchy is captured by the beth numbers. The beth number $\beth_0$ equals $\aleph_0$, the cardinality of $\mathbb{N}$. Each successive beth number is defined by exponentiation: $\beth_{n+1} = 2^{\beth_n}$, the cardinality of the power set of any set of cardinality $\beth_n$. Since $|\mathbb{R}| = |\mathcal{P}(\mathbb{N})| = 2^{\aleph_0} = \beth_1$, the cardinality of the continuum sits at the first step of the beth hierarchy. There is also the aleph hierarchy $\aleph_0, \aleph_1, \aleph_2, \ldots$, which enumerates all infinite cardinal numbers in order. The question of whether $\beth_1 = \aleph_1$ — that is, whether the cardinality of the continuum is the very next infinite cardinal after $\aleph_0$ — is the continuum hypothesis, formulated by Cantor in 1878. It remained one of the great open problems of mathematics until Kurt Godel (1940) and Paul Cohen (1963) showed that it is independent of the standard axioms of set theory: it can be neither proved nor disproved from ZFC. This stunning independence result, explored more fully in The Continuum Hypothesis, reveals that the universe of sets is far more open-ended than the early set theorists imagined.

The uncountability of $\mathbb{R}$, combined with the countability of the algebraic numbers, has another beautiful corollary. Since $\mathbb{R}$ is uncountable and the algebraic numbers are countable, the set of transcendental numbers — real numbers that are not roots of any polynomial with integer coefficients — must be uncountable. In fact, “almost all” real numbers are transcendental. This is a striking example of a non-constructive existence proof: Cantor showed that transcendental numbers exist in overwhelming abundance without exhibiting a single one. The explicit construction of transcendental numbers, such as Joseph Liouville’s 1851 example and the later proofs that $e$ (Hermite, 1873) and $\pi$ (Lindemann, 1882) are transcendental, required entirely different and considerably harder techniques. Cantor’s set-theoretic argument, by contrast, settles the question of existence with breathtaking economy.