Sign in Subscribe

Cardinality: Counting the Uncountable

Cardinality: Counting the Uncountable
Cardinality: Counting the Uncountable | Ideasthesia

Some infinities are bigger than others.

That sounds like nonsense — infinity is infinity, right? But Georg Cantor proved otherwise. The integers and the reals are both infinite, but the reals are a larger infinity. You can't pair them one-to-one. There are fundamentally more real numbers than integers.

Cardinality measures the size of sets — even infinite ones.

That's the unlock. Two sets have the same cardinality if you can match their elements one-to-one. For finite sets, cardinality is just the count. But for infinite sets, this matching criterion reveals that infinities come in different sizes. Some infinite sets are countable (like ℕ). Others are uncountable (like ℝ). Cantor showed us how to tell the difference.

Cardinality for Finite Sets

|{a, b, c}| = 3 |{1, 2, 3, 4, 5}| = 5 |∅| = 0

For finite sets, cardinality is the number of elements. Simple.

Comparing Infinite Sets

How do you compare two infinite sets? You can't count to infinity.

Cantor's insight: two sets have the same cardinality if there exists a bijection (one-to-one correspondence) between them.

A bijection pairs every element of A with exactly one element of B, and vice versa. If such a pairing exists, the sets are "the same size."

The Natural Numbers and Even Numbers

Is the set of even positive integers smaller than ℕ⁺ = {1, 2, 3, ...}?

Intuition says yes — evens are a "half" of naturals.

But consider this pairing:

  • 1 ↔ 2
  • 2 ↔ 4
  • 3 ↔ 6
  • n ↔ 2n

Every natural pairs with exactly one even. Every even pairs with exactly one natural. A perfect bijection.

So |{even positive integers}| = |ℕ⁺|.

The even numbers, despite being a proper subset, have the same cardinality as the naturals.

Countable Infinity: ℵ₀

A set is countably infinite if it has the same cardinality as ℕ.

This cardinality is called ℵ₀ (aleph-null).

Countable sets: you can list them as a sequence (1st, 2nd, 3rd, ...).

Examples:

  • ℕ (naturals)
  • ℤ (integers) — list as 0, 1, -1, 2, -2, 3, -3, ...
  • ℚ (rationals) — Cantor's diagonal argument shows they're listable

All these have cardinality ℵ₀.

The Rationals Are Countable

Surprising: there seem to be "more" rationals than integers. Between any two integers, infinitely many rationals.

But you can list them. Arrange all positive rationals in a grid:

1/1  1/2  1/3  1/4  ...
2/1  2/2  2/3  2/4  ...
3/1  3/2  3/3  3/4  ...
...

Then traverse diagonally (skipping repeats like 2/2 = 1/1):

1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, ...

Every positive rational appears exactly once. Add negatives and zero: still countable.

|ℚ| = ℵ₀.

The Reals Are Uncountable

Now for the bombshell: the real numbers cannot be listed.

Cantor's Diagonal Argument:

Suppose you could list all reals between 0 and 1:

  • r₁ = 0.d₁₁d₁₂d₁₃d₁₄...
  • r₂ = 0.d₂₁d₂₂d₂₃d₂₄...
  • r₃ = 0.d₃₁d₃₂d₃₃d₃₄...
  • ...

Construct a new number s:

  • The 1st digit of s differs from d₁₁
  • The 2nd digit of s differs from d₂₂
  • The 3rd digit of s differs from d₃₃
  • ...

Then s differs from r₁ in the 1st digit, from r₂ in the 2nd digit, etc.

So s is not in the list. But s is a real between 0 and 1.

Contradiction. No complete list exists. ∎

The Continuum

|ℝ| is called the cardinality of the continuum, often written 𝔠 or 2^ℵ₀.

2^ℵ₀ > ℵ₀

The reals are a strictly larger infinity than the naturals.

Power Sets and Cardinality

Cantor also proved: for any set A, |𝒫(A)| > |A|.

The power set (set of all subsets) is always strictly larger than the original set.

For finite sets: |𝒫({1,2,3})| = 2³ = 8 > 3.

For infinite sets: |𝒫(ℕ)| = 2^ℵ₀ = 𝔠 > ℵ₀.

This is why |ℝ| = 2^ℵ₀. The reals have the same cardinality as 𝒫(ℕ).

The Hierarchy of Infinities

ℵ₀ < 2^ℵ₀ < 2^(2^ℵ₀) < ...

Each power set creates a larger infinity. There's no largest infinity.

The subscripts ℵ₀, ℵ₁, ℵ₂, ... form an endless sequence of infinite cardinals.

The Continuum Hypothesis

Is there an infinity between ℵ₀ and 2^ℵ₀?

The Continuum Hypothesis (CH) says no: 2^ℵ₀ = ℵ₁.

Gödel (1940) and Cohen (1963) proved CH is independent of standard set theory. It can't be proved or disproved from the usual axioms.

This is a strange situation: a precise mathematical question with no definite answer.

Comparing Cardinal Numbers

For cardinals, we can compare sizes:

  • ℵ₀ < 𝔠 (countable < continuum)
  • |ℕ| = |ℤ| = |ℚ| = ℵ₀
  • |ℝ| = |𝒫(ℕ)| = 𝔠
  • |ℝ| = |ℝ²| = |ℝⁿ| = 𝔠 (the plane has the same cardinality as the line!)

The last one is counterintuitive. Cantor himself said, "I see it, but I don't believe it."

Sets with Cardinality 𝔠

All these have the same cardinality as ℝ:

  • Any interval (0, 1) or [0, 1] or (-∞, ∞)
  • ℝ² (the plane)
  • ℝⁿ (n-dimensional space)
  • 𝒫(ℕ)
  • The set of all functions from ℕ to {0, 1}
  • The Cantor set

Infinity behaves strangely.

The Core Insight

Cardinality extends counting to infinity, revealing that infinities have sizes.

Countable infinity (ℵ₀) is the smallest infinite cardinal — the size of ℕ. Uncountable infinities (like 𝔠) are strictly larger.

Cantor's diagonal argument is the key technique: to show a set is uncountable, assume a complete list exists and construct an element not on the list.

The universe of infinite sets has structure. Not all infinities are equal.

Part 10 of the Set Theory series.

Previous: Number Sets: Natural Integers Rational Real Complex Next: Functions as Sets: The Set-Theoretic Definition

Comments ()