4.8 Cardinality

Definition of cardinality

Cardinality is how we measure the "size" of a set. For finite sets, this is straightforward: just count the elements. For infinite sets, things get much more interesting, because cardinality gives us a way to show that some infinities are genuinely larger than others.

Sets and cardinality

The cardinality of a set $A$ is written $|A|$ and represents the number of elements it contains. For finite sets, this is simple:

• $|\{1, 2, 3\}| = 3$
• $|\emptyset| = 0$
• $|\{a, b\}| = 2$

For infinite sets, you can't just "count up" to a final number, so we need more sophisticated tools to compare sizes. That's where one-to-one correspondence comes in.

Finite vs. infinite sets

A finite set has some specific number of elements. You could, in principle, list them all and stop. An infinite set never runs out of elements; no matter how many you've listed, there are always more.

The more surprising distinction comes within infinite sets. Not all infinities are the same size. Infinite sets split into two categories:

• Countably infinite: can be matched up with the natural numbers
• Uncountably infinite: too large to be matched with the natural numbers

Comparing set sizes

The central question of cardinality theory is: how do you compare the sizes of two sets, especially when both are infinite? You can't just count and compare totals. Instead, you try to build a perfect pairing between them.

One-to-one correspondence

A one-to-one correspondence (also called a bijection) is a pairing between two sets where every element in each set gets exactly one partner in the other set, with no elements left over on either side.

If you can construct such a pairing between sets $A$ and $B$, then $|A| = |B|$, regardless of whether the sets are finite or infinite.

Bijective functions

A bijection is a function that is both:

• Injective (one-to-one): no two inputs map to the same output
• Surjective (onto): every element in the target set gets hit by some input

If a bijection $f: A \to B$ exists, the two sets have the same cardinality. This is the formal tool behind one-to-one correspondence.

Equipotent sets

Two sets are equipotent (written $A \sim B$) when a bijection exists between them. This means they have the same cardinality.

A classic example: the set of even natural numbers is equipotent to the set of all natural numbers. The function $f(n) = 2n$ pairs every natural number with a unique even number, leaving nothing unpaired. This feels strange since the evens are a subset of the naturals, but that's exactly the kind of counterintuitive result that makes infinite cardinality interesting.

Countable sets

A set is countable if it's either finite or can be put into one-to-one correspondence with the natural numbers. Countably infinite sets represent the smallest type of infinity, and their cardinality is denoted $\aleph_0$ (aleph-null).

Natural numbers

The natural numbers $\mathbb{N} = \{1, 2, 3, \ldots\}$ serve as the reference set for countable infinity. Any set that can be listed in a sequence (first element, second element, third element, ...) without missing any is countably infinite. The natural numbers have a built-in ordering that makes this enumeration obvious.

Integers and rationals

Both the integers $\mathbb{Z}$ and the rational numbers $\mathbb{Q}$ are countably infinite, even though they seem "bigger" than $\mathbb{N}$.

• Integers: You can list them as $0, 1, -1, 2, -2, 3, -3, \ldots$, which defines a bijection with $\mathbb{N}$. Adding negative numbers doesn't increase the cardinality.
• Rationals: You can arrange all positive fractions in a grid (numerator along one axis, denominator along the other) and then traverse the grid diagonally, skipping duplicates. This produces a complete list, proving $|\mathbb{Q}| = \aleph_0$.

These results show that "countable infinity" is surprisingly robust. You can combine, rearrange, or extend countable sets and still end up with a countable set.

Countably infinite sets

Beyond $\mathbb{Z}$ and $\mathbb{Q}$, other important countably infinite sets include:

• The set of algebraic numbers (roots of polynomials with integer coefficients)
• The Cartesian product of finitely many countable sets
• Any subset of a countable set

A useful fact: the Cartesian product of countably many countable sets is also countable. This property is important when building more complex mathematical structures from simpler countable ones.

Uncountable sets

Uncountable sets are "too big" to be listed in any sequence. No bijection with the natural numbers is possible. This represents a genuinely larger order of infinity.

Real numbers

The real numbers $\mathbb{R}$ (every point on the number line) are uncountable. This includes all rationals and all irrationals together. The cardinality of $\mathbb{R}$ is $2^{\aleph_0}$, also called the cardinality of the continuum.

The fact that $\mathbb{R}$ is uncountable while $\mathbb{Q}$ is countable means the "extra" real numbers (the irrationals) vastly outnumber the rationals, even though rationals are dense on the number line.

Cantor's diagonal argument

Georg Cantor proved that $\mathbb{R}$ is uncountable using an elegant proof by contradiction. Here's how it works:

1. Assume you can list all real numbers between 0 and 1 in a sequence: $r_1, r_2, r_3, \ldots$
2. Write out the decimal expansion of each number.
3. Construct a new number $d$ by choosing its $n$-th decimal digit to differ from the $n$-th digit of $r_n$ (for example, if the digit is 5, make it 6; otherwise make it 5).
4. This new number $d$ is between 0 and 1, but it differs from every $r_n$ in at least one decimal place.
5. So $d$ is not on the list, contradicting the assumption that the list was complete.

Therefore, no such complete list can exist, and the reals are uncountable.

Power set theorem

Cantor's theorem states that for any set $A$, the power set $\mathcal{P}(A)$ (the set of all subsets of $A$) has strictly greater cardinality than $A$ itself:

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

This holds for finite and infinite sets alike. For a finite set with $n$ elements, $|\mathcal{P}(A)| = 2^n$. For infinite sets, this theorem generates an endless hierarchy of ever-larger infinities: $|A| < |\mathcal{P}(A)| < |\mathcal{P}(\mathcal{P}(A))| < \cdots$

Cardinal numbers

Cardinal numbers are abstract numbers that represent set sizes. For finite sets, they're just the familiar counting numbers. For infinite sets, they form a hierarchy of distinct infinities.

Aleph numbers

The aleph numbers ($\aleph_0, \aleph_1, \aleph_2, \ldots$) represent the cardinalities of well-ordered infinite sets, arranged in increasing order.

• $\aleph_0$ is the smallest infinite cardinal (the size of $\mathbb{N}$)
• $\aleph_1$ is the next infinite cardinal after $\aleph_0$
• Each $\aleph_n$ represents a distinct, strictly larger infinite cardinality

Beth numbers

The beth numbers provide an alternative way to index infinite cardinalities, defined using power sets:

• $\beth_0 = \aleph_0$ (the cardinality of $\mathbb{N}$)
• $\beth_{n+1} = 2^{\beth_n}$ (the cardinality of the power set of a set of size $\beth_n$)

So $\beth_1 = 2^{\aleph_0}$, which is the cardinality of $\mathbb{R}$. Whether $\beth_1 = \aleph_1$ is exactly the continuum hypothesis.

Continuum hypothesis

The continuum hypothesis (CH) states that there is no set whose cardinality falls strictly between $\aleph_0$ and $2^{\aleph_0}$. In other words, $\aleph_1 = 2^{\aleph_0}$.

This was the first of Hilbert's famous 23 problems. Gödel (1940) showed CH is consistent with the standard axioms of set theory (ZFC), and Cohen (1963) showed its negation is also consistent. This means CH is independent of ZFC: you can't prove it true or false from the standard axioms. It highlights a genuine limitation in what our foundational axiom systems can settle about infinite sets.

Operations on cardinals

Cardinal arithmetic extends the familiar operations of addition, multiplication, and exponentiation to infinite cardinals, but the results often defy finite intuition.

Addition and multiplication

For disjoint sets $A$ and $B$:

• Cardinal addition: $|A \cup B| = |A| + |B|$
• Cardinal multiplication: $|A \times B| = |A| \cdot |B|$

With infinite cardinals, these operations behave very differently from finite arithmetic. If at least one of $\kappa$ or $\lambda$ is infinite, then:

$\kappa + \lambda = \max(\kappa, \lambda)$

$\kappa \cdot \lambda = \max(\kappa, \lambda)$

So $\aleph_0 + \aleph_0 = \aleph_0$, and $\aleph_0 \cdot \aleph_0 = \aleph_0$. Adding or multiplying an infinite cardinal by itself doesn't make it bigger.

Exponentiation of cardinals

Cardinal exponentiation is defined as: $|B^A|$ is the cardinality of the set of all functions from $A$ to $B$.

Unlike addition and multiplication, exponentiation does produce larger cardinals. Cantor's theorem guarantees:

$2^\kappa > \kappa \text{ for any cardinal } \kappa$

This is what generates the hierarchy of infinities. Each application of the power set operation jumps to a strictly larger cardinality.

Cardinal arithmetic laws

The standard algebraic laws carry over:

• Commutativity: $\kappa + \lambda = \lambda + \kappa$ and $\kappa \cdot \lambda = \lambda \cdot \kappa$
• Associativity: $(\kappa + \lambda) + \mu = \kappa + (\lambda + \mu)$
• Distributivity: $\kappa \cdot (\lambda + \mu) = \kappa \cdot \lambda + \kappa \cdot \mu$
• Absorption: $\kappa + \lambda = \max(\kappa, \lambda)$ when at least one is infinite

The absorption law is the big difference from finite arithmetic. It means infinite cardinal addition and multiplication are dominated by the larger operand.

Ordinal vs. cardinal numbers

Ordinals and cardinals both deal with infinite sets, but they measure different things. Understanding the distinction is important for advanced set theory.

Distinction and relationship

• Ordinal numbers capture the order type of a well-ordered set. They care about the arrangement of elements.
• Cardinal numbers capture the size of a set, ignoring order entirely.

Every ordinal has an associated cardinal (its "size"), but many different ordinals can share the same cardinal. For example, $\omega$ (the first infinite ordinal) and $\omega + 1$ are different ordinals, but both correspond to the cardinal $\aleph_0$.

Ordinal arithmetic vs. cardinal arithmetic

A key difference: ordinal arithmetic is not commutative, while cardinal arithmetic is.

• Ordinal: $1 + \omega = \omega$, but $\omega + 1 \neq \omega$ (it's a distinct, larger ordinal)
• Cardinal: $\aleph_0 + \aleph_0 = \aleph_0$ (order doesn't matter)

Ordinal exponentiation also differs significantly from cardinal exponentiation. Keeping these two systems straight is essential when working with proofs involving infinite sets.

Applications of cardinality

Cardinality isn't just abstract theory. It connects to several areas of mathematics and computer science.

Set theory foundations

Cardinality is a cornerstone of axiomatic set theory (ZFC). It provides the tools to rigorously handle infinite sets, classify their sizes, and avoid the paradoxes that plagued earlier "naive" approaches to set theory.

Measure theory

Cardinality plays a role in measure theory, where the distinction between countable and uncountable sets matters directly. For instance, countable sets always have Lebesgue measure zero, while uncountable sets may or may not be measurable. These ideas underpin modern probability theory and integration.

Computational complexity

Cardinality connects to computability theory in a fundamental way. The set of all possible computer programs is countable, but the set of all functions from $\mathbb{N}$ to $\mathbb{N}$ is uncountable. This cardinality mismatch proves that most functions are not computable, which is the deeper reason behind results like the undecidability of the halting problem.

Cardinality across mathematics

Cardinality concepts appear throughout many branches of mathematics, providing structural insights in each.

Topology and cardinality

Topological properties like separability (having a countable dense subset) are defined using cardinality. The classification of topological spaces often depends on the cardinality of their bases, and dimension theory connects to how sets of different cardinalities relate to each other.

Algebra and cardinality

In algebra, cardinality helps classify structures. The dimension of a vector space can be any cardinal number, and two vector spaces over the same field are isomorphic if and only if they have the same dimension. Cardinality also appears in Galois theory when studying the size of field extensions.

Analysis and cardinality

Real analysis relies heavily on the distinction between countable and uncountable. The rationals are countable and dense, yet the irrationals (uncountable) make up "almost all" of the real line. In functional analysis, the cardinality of various function spaces determines their structural properties, such as whether a Banach space is separable.