The Cardinality of Sets: Navigating Infinite Sizes

Everyone with telekinetic powers, raise my hand — Emo Phillips

The Cardinality of Sets: Navigating Infinite Sizes

When we deal with finite sets, counting elements is trivial. But how do we measure the “size” of a set when its elements stretch on forever? In the late 19th century, Georg Cantor revolutionized mathematics by demonstrating that we shouldn’t count elements to compare sets; instead, we should pair them up.

Definition: The empty set $\emptyset$ is finite and has cardinality $\vert{}\emptyset\vert{} = 0$. A non-empty set $S$ is called finite and has cardinality $\vert{}S\vert{} = n \in \mathbb{N}$ if and only if there exists a perfect bijection from $S$ to the set $\{1, 2, \dots, n\}$.

If $X$ and $Y$ are finite sets, the existence of a bijection means they have the exact same number of elements.

• A function $f: X \to Y$ can only be injective if $\vert{}Y\vert{} \ge \vert{}X\vert{}$. There are enough unique targets in the codomain for every element in the domain.
• A function $f: X \to Y$ can only be surjective if $\vert{}Y\vert{} \le \vert{}X\vert{}$. There are enough elements in the domain to hit every single target in the codomain.
• Therefore, if a function is bijective (both injective and surjective), it forces $\vert{}Y\vert{} = \vert{}X\vert{}$.

We extend this exact logic to infinite sets. Two sets $X$ and $Y$ have the same cardinality if and only if there exists a bijection between them.

For any sets $A, B,$ and $C$, the rules of bijections give us an equivalence relation for cardinalities:

• Reflexive: $\vert{}A\vert{} = \vert{}A\vert{}$. The identity function $\text{id}_A(x) = x$ is a bijection.
• Symmetric: If $\vert{}A\vert{} = \vert{}B\vert{}$, then $\vert{}B\vert{} = \vert{}A\vert{}$. If $f: A \to B$ is a bijection, its inverse $f^{-1}: B \to A$ is also a bijection.
• Transitive: If $\vert{}A\vert{} = \vert{}B\vert{}$ and $\vert{}B\vert{} = \vert{}C\vert{}$, then $\vert{}A\vert{} = \vert{}C\vert{}$. If $f$ and $g$ are bijections, their composition $g \circ f$ is also a bijection.

Cantor’s Theorem: The Hierarchy of Infinities

Is $\mathbb{R}$ the largest infinity? No. In fact, there is no largest infinity. For any set, you can always create a strictly larger set by taking its Power Set.

Theorem (Cantor’s Theorem): Let $A$ be a set, and $\mathcal{P(A)}$ be its power set. Then $\vert{}A\vert{} < \vert{}\mathcal{P}(A)\vert{}$. Recall that for any set $A$, the power set of $A$, written $\mathbb{P(A)}$, is the collection of all subsets of $A$.

Proof:

First, we can easily define an injective function $f: A \to \mathcal{P}(A)$ by mapping every element to a subset containing only itself: $f(a) = \{a\}$. Because an injection exists, we know $\vert{}A\vert{} \le \vert{}\mathcal{P}(A)\vert{}$.

To prove it is strictly less, we must prove no bijection exists.

For the sake of contradiction, assume a bijection $f: A \to \mathcal{P}(A)$ does exist. This means every element $a \in A$ pairs perfectly with a specific subset of $A$.

Let us construct a very specific subset of $A$, called $D$: $D = \{a \in A \mid a \notin f(a)\}$. Notice: The proof does not require $D$ to be nonempty. The empty set is still a member of the power set.

This set $D$ contains all elements that are not inside the subset they map to.

Because $D$ is a subset of $A$, $D \in \mathcal{P}(A)$. Because $f$ is a bijection, there must be some specific element $y \in A$ that perfectly maps to $D$, meaning $f(y) = D$.

Now, we ask the fatal logical question: Is $y$ an element of $D$?

• If $y \in D$, then by the definition of our set $D$, $y \notin f(y)$. But since $f(y) = D$, this means $y \notin D$. This is a contradiction ($\bot$).
• If $y \notin D$, then $y \notin f(y)$. But by the definition of our set $D$, any element not in its own mapped subset must be included in $D$. So $y \in D$. This is also a contradiction ($\bot$). Since both cases lead to impossible paradoxes, the bijection $f$ cannot exist. Therefore, $\vert{}A\vert{} < \vert{}\mathcal{P}(A)\vert{}$. $\blacksquare$

The Cardinality of Countable Infinity ($\aleph_0$)

We denote the cardinality of the natural numbers $\mathbb{N}$ by the Hebrew letter Aleph-null ($\aleph_0$).

Definition: Let $A$ be an arbitrary set. $A$ is said to be countably infinite if $\vert{}A\vert{} = \vert{}\mathbb{N}\vert{}$, meaning there exists a bijection $f: \mathbb{N} \to A$.

If a set is countably infinite, the bijection allows us to systematically arrange its elements into an infinite, discrete list: $a_1, a_2, a_3, \dots$ where every element will eventually be reached.

The Paradox of Proper Subsets

In the finite world, if you remove an element from a set, the set gets smaller. In the infinite world, this intuition completely collapses.

A defining characteristic of an infinite set is that a proper subset can have the exact same cardinality as the whole set.

For example, the integers ($\mathbb{Z}$) contain more numbers than the natural numbers ($\mathbb{N}$)? Intuitively, $\mathbb{Z}$ contains all positive numbers, negative numbers, and zero, making it roughly “twice as large.” Yet, mathematically, they are exactly the same size.

Theorem: $\vert{}\mathbb{N}\vert{} = \vert{}\mathbb{Z}\vert{} = \aleph_0$.

Proof: We can establish a bijection by alternating between positive and negative numbers. We map: $1 \leftrightarrow 0, \quad 2 \leftrightarrow 1, \quad 3 \leftrightarrow -1, \quad 4 \leftrightarrow 2, \quad 5 \leftrightarrow -2 \dots$

We can write this as a precise piecewise function $f: \mathbb{N} \to \mathbb{Z}$:

$f(n) = \begin{cases} \frac{n}{2}, & \text{if } n \text{ is even} \\ \frac{1-n}{2}, & \text{if } n \text{ is odd} \end{cases}$

This function is a flawless bijection. No integer is skipped, and no integer is hit twice.

The rationals $\mathbb{Q}$ are countable, even though there are infinitely many of them, $|\mathbb Q|=\aleph_0$.

At first this seems impossible because between any two integers there are infinitely many fractions. For example, between $0$ and $1$ alone we already have $ \dots, \frac12,\ \frac13,\ \frac14,\ \frac15,\dots$ so it feels as though there should be “more” rationals than naturals.

The surprising fact is that infinite sets can have proper subsets of the same size. Just as $|\mathbb N| = |2\mathbb N|$, we also have $|\mathbb N| = |\mathbb Q|$ (Figure 1a).

The “string” analogy expresses the existence of a bijection $\mathbb N \longleftrightarrow \mathbb Q$.

Imagine every rational number attached to a tangled string. If you pull the string straight, the rationals line up in a sequence: $q_0,\ q_1,\ q_2,\ q_3,\ \dots$ where every rational appears exactly once.

Then you can define $n \mapsto q_n$. This gives a bijection with $\mathbb N.$

The hard part is showing that such a listing exists. A common construction is to arrange all positive rationals in a grid: $\begin{array}{ccccc} 1/1 & 1/2 & 1/3 & 1/4 & \cdots\\ 2/1 & 2/2 & 2/3 & 2/4 & \cdots\\ 3/1 & 3/2 & 3/3 & 3/4 & \cdots\\ 4/1 & 4/2 & 4/3 & 4/4 & \cdots\\ \vdots & \vdots & \vdots & \vdots \end{array}$

Every positive rational appears somewhere as $\frac{m}{n}$. Now traverse the grid diagonally: $1/1, \quad 1/2,\,2/1, \quad 3/1,\,2/2,\,1/3, \quad \dots$ and skip duplicates such as $2/2 = 1/1,\qquad 2/4 = 1/2.$

This produces an infinite list containing every positive rational exactly once. Then, insert $0$ and alternate positive and negative rationals: $0, \frac11, -\frac11, \frac12, -\frac12, \frac21, -\frac21, \dots$ giving a sequence of all rational numbers.

Notice how different this is from Cantor’s theorem:

• $\mathbb N$ and $\mathbb Q$ are both countably infinite: $|\mathbb N|=|\mathbb Q|=\aleph_0.$
• The real numbers are strictly larger: $|\mathbb N|<|\mathbb R|.$ In fact, $|\mathbb R| = |\mathcal P(\mathbb N)|.$

So despite the rationals being dense on the number line, they are still only “the first size” of infinity, whereas the reals form a strictly larger infinity. This is one of the most surprising consequences of Cantor’s theory of cardinality.

Continuous Bijections: Geometry of the Real Line

Bijections aren’t just for discrete numbers; they apply to continuous geometry as well.

1. Any two closed intervals have the same cardinality. For any real numbers $a < b$, $\vert{}[0, 1]\vert{} = \vert{}[a, b]\vert{}$.
   We can prove this with a linear scaling function $f: [0, 1] \to [a, b]$ defined by $f(x) = (b - a)x + a$ (Figure 1.e).
   This function stretches the interval length by $(b-a)$ and shifts it by $a$. It is a perfect bijection.

2. A finite segment has the same cardinality as the infinite Real Line. $\vert{}(-\frac{\pi}{2}, \frac{\pi}{2})\vert{} = \vert{}\mathbb{R}\vert{}$ (Figure 1.f).
   We prove this using trigonometry. The function $f: (-\frac{\pi}{2}, \frac{\pi}{2}) \to \mathbb{R}$ defined by: $f(x) = \tan(x)$ is strictly increasing (hence injective) and spans from $-\infty$ to $\infty$ between its vertical asymptotes (hence surjective).

3. A geometric projection mapping $(0, \infty) \to (0, 1)$.

Let’s build a bijection geometrically. Imagine the interval $(0, \infty)$ lying on the positive x-axis, and the interval $(0, 1)$ lying on the positive y-axis.

Place an observer at the point $P(-1, 1)$. If the observer looks at any point $x$ on the positive x-axis, their line of sight must perfectly cross the y-axis at some unique point $y \in (0,1)$.

Let’s find the formula for this intersection. The line passes through $P(-1, 1)$ and $X(x, 0)$.

The slope is $m = \frac{0 - 1}{x - (-1)} = \frac{-1}{x+1}$. The equation of the line is $Y - 0 = \frac{-1}{x+1}(X - x)$.

The y-intercept (where $X = 0$) gives our mapping function: $f(x) = \frac{x}{x+1}$

Proof of Bijection:

• Injective: Assume $f(x_1) = f(x_2)$. Then, $\frac{x_1}{x_1+1} = \frac{x_2}{x_2+1}$.
  Cross-multiply: $x_1(x_2+1) = x_2(x_1+1) \implies x_1x_2 + x_1 = x_1x_2 + x_2 \implies x_1 = x_2$.
• Surjective: Take any $y \in (0, 1)$. Set $y = \frac{x}{x+1}$.
  Solving for $x$ yields $x = \frac{y}{1-y}$. Since $y \in (0,1)$, both the numerator and denominator are positive, guaranteeing $x > 0$. Thus, $x \in (0, \infty)$. $\blacksquare$

 

Operations on Countable Sets

Definition. Let $A$ be an arbitrary set. Then, $A$ is said to be countably infinite if $|\mathbb N| = \lvert A\rvert$, that is, if there exists a bijection $f: \mathbb N \to A$. $A$ is said to be uncountable if $A$ is infinite and $|\mathbb N| \ne \lvert A\rvert$, that is, if there exists no bijection $f: \mathbb N \to A$.

If $A$ is countably infinite, there exists a bijection $f: \mathbb N \to A$. It allows us to list the elements of $A$ as an infinite list $f(1), f(2), f(3), \dots$, i.e., the set elements can be arranged in an infinite list $a_1, a_2, a_3, \dots$.

Can we combine infinite sets and keep them countable? The short answer is yes.

Theorem: If $A$ and $B$ are both countably infinite, then their Union ($A \cup B$) and their Cartesian Product ($A \times B$) are also countably infinite.

Proof:

1. The Union: Because $A$ and $B$ are countable, we can write them as lists: $A = \{a_1, a_2, \dots\}$ and $B = \{b_1, b_2, \dots\}$. We can shuffle them into a single alternating list: $A \cup B = \{a_1, b_1, a_2, b_2, a_3, b_3, \dots\}$.
   If the sets overlap, we simply skip elements we have already listed to maintain injectivity.
   Because we can arrange the union into a discrete, indexed sequence, it is countable.

2. The Cartesian Product: This requires Cantor’s Pairing Function. Imagine plotting $A \times B$ on a 2D grid, where the coordinates are $(a_i, b_j)$. We cannot count row by row (because row 1 goes on infinitely, and we would never reach row 2). Instead, we weave through the grid diagonally!

$$(a_1, b_1) \to (a_1, b_2) \to (a_2, b_1) \to (a_3, b_1) \to (a_2, b_2) \to (a_1, b_3) \dots$$

This zig-zag path straightens the 2D infinite grid out into a single 1D string, ensuring every ordered pair is eventually reached. Thus, $A \times B$ is countable.

Extending to $n$ Dimensions

By mathematical induction, we can prove that given $n$ countably infinite sets $A_1, A_2, \dots, A_n$, their Cartesian product $\prod_{i=1}^n A_i$ is also countably infinite.

Proof by Induction:

• Base Case ($n=2$): We just proved that $A_1 \times A_2$ is countably infinite using Cantor’s Pairing Function.
• Inductive Step: Assume the theorem holds for $n=k$. This means the Cartesian product of $k$ sets, $P_k = (A_1 \times A_2 \times \dots \times A_k)$, is countably infinite. We must prove it holds for $n=k+1$.

Consider the product of $k+1$ sets. We can define a natural bijection $f$ that groups the first $k$ dimensions together:

$f(x_1, x_2, \dots, x_{k+1}) = ((x_1, \dots, x_k), x_{k+1})$. This function flawlessly maps the $(k+1)$-dimensional product to the 2-dimensional product $P_k \times A_{k+1}$.

By our inductive hypothesis, $P_k$ is countably infinite. We are given that $A_{k+1}$ is countably infinite.

Since the Cartesian product of two countably infinite sets is countably infinite (Base Case), the set $P_k \times A_{k+1}$ is countable. Because our bijection links them, the product of $k+1$ sets is countably infinite. $\blacksquare$