Cardinality and the Infinite

The study of cardinality is the study of the “size” of sets. While counting finite sets is intuitive, the transition to infinite sets reveals a landscape of varying magnitudes that defies simple intuition. Through the work of Georg Cantor in the late 19th century, we learned that infinity is not a single value, but a hierarchy of transfinite numbers.

Defining Cardinality via Bijections

In the absence of a counting process ($1,2,3,\dots$), we compare sets using mappings. Two sets $A$ and $B$ have the same Cardinality, denoted $|A|=|B|$, if and only if there exists a Bijection $f:A\to B$.

This definition leads to surprising conclusions for infinite sets ($|A|=|B|$ can hold even if $A⊊B$):

• The set of natural numbers $\mathbb{N}$ has the same cardinality as the set of even numbers $2\mathbb{N}$ (via the mapping $n\mapsto 2n$).
• $\mathbb{N}$ has the same cardinality as the set of integers $\mathbb{Z}$.
• $\mathbb{N}$ has the same cardinality as the set of rational numbers $\mathbb{Q}$.

Countable Infinity (${\aleph }_0$)

A set is Countably Infinite if it has the same cardinality as $\mathbb{N}$. We use the Hebrew letter Aleph to denote these sizes, with $|\mathbb{N}|={\aleph }_0$ (Aleph-null).

The fact that $\mathbb{Q}$ is countable is proven using Cantor’s Pairing Function or a zigzag traversal of a 2D grid of fractions. It shows that even though $\mathbb{Q}$ is dense (between any two rationals, there is another rational), it is no “larger” than the discrete natural numbers.

Uncountability and Cantor’s Diagonal Argument

Cantor’s most famous result was proving that the set of real numbers $\mathbb{R}$ is Uncountable ($|\mathbb{R}|>{\aleph }_0$).

The Diagonal Argument:

1. Assume the interval $(0,1)$ is countable. List the numbers in decimal form: $r_1=0.d_{11}{d}_{12}{d}_{13}\dots$ $r_2=0.d_{21}{d}_{22}{d}_{23}\dots$ …
2. Construct a new number $x=0.x_1{x}_2{x}_3\dots$ where $x_i\ne d_{ii}$ (specifically, let $x_i=4$ if $d_{ii}\ne 4$, else $x_i=5$).
3. The number $x$ differs from every $r_n$ in the $n$-th decimal place.
4. Therefore, $x$ is not in the list, contradicting the assumption that the list was complete.

The cardinality of $\mathbb{R}$ is often called the Continuum, denoted $c$ or $2^{{\aleph }_0}$.

Cantor’s Theorem and the Hierarchy of Infinites

Cantor’s Theorem states that for any set $A$, the cardinality of its Power Set $\mathcal{P}(A)$ is strictly greater than the cardinality of $A$: $|A|<|\mathcal{P}(A)|$ This allows us to construct an endless sequence of increasing infinities: ${\aleph }_0<2^{{\aleph }_0}<2^{2^{{\aleph }_0}}<\dots$ There is no “largest” infinity.

Cardinal Arithmetic

Arithmetic with cardinals follows different rules than finite arithmetic:

• Addition: ${\aleph }_0+n={\aleph }_0$ and ${\aleph }_0+{\aleph }_0={\aleph }_0$.
• Multiplication: ${\aleph }_0\times {\aleph }_0={\aleph }_0$.
• Exponentiation: $2^{{\aleph }_0}$ is the size of the set of all subsets of $\mathbb{N}$, which is equal to $c$.

The Continuum Hypothesis (CH)

Cantor conjectured that there is no cardinality between the size of the integers and the size of the reals. That is, is ${\aleph }_1=2^{{\aleph }_0}$?

In 1963, Paul Cohen proved that the Continuum Hypothesis is Independent of ZFC set theory. You can neither prove it nor disprove it using the standard axioms. This realization changed the face of mathematical logic, suggesting that there are different “universes” of set theory where CH is true and others where it is false.

Conceptual Note: Hilbert’s Grand Hotel

The paradoxes of infinite cardinality are often illustrated by Hilbert’s Hotel, where a full hotel can accommodate $n$ new guests, or even an infinite number of new guests, by simply shifting the current guests from room $k$ to room $k+n$ or room $2k$. While physically impossible, this is a mathematically rigorous characteristic of any set with cardinality ${\aleph }_0$.

Computational Representation of Infinity

In symbolic logic and computer science, we distinguish between sets that are Recursively Enumerable (where we can write a program to list all elements) and those that are not. The natural numbers are enumerable, but the set of all possible computer programs (a subset of ${\Sigma }^{\ast }$) is countable, while the set of all possible real-number functions is uncountable. This fundamental limit means that there are vastly more “problems” than there are “solutions” (algorithms).

/**
 * While we cannot represent an infinite set physically, 
 * we can represent a "Generator" for a countably infinite set.
 */
function* naturalNumbers() {
    let n = 0;
    while (true) {
        yield n++;
    }
}

// In contrast, there is no 'generator' that can yield all 
// Real numbers in a sequence, even with infinite time.

By understanding cardinality, we see that mathematics is not just a tool for finite counting, but a way to categorize the infinite itself. We move from the discrete world of integers to the dense world of rationals, and finally to the continuous world of reals and beyond.