Countable Infinity
“Countable infinity is 'an infinity you can number'; the reals are a larger infinity that cannot even be numbered.”
The formula
|ℕ| = |ℤ| = |ℚ| = ℵ₀ < |ℝ|How to read it: The naturals, integers, and rationals can all be numbered 1,2,3,… so they share the same size ℵ₀ of infinity, but the reals are a larger infinity
- ℵ₀
- — Aleph-null — the smallest infinity, the size of 'countable' infinity
- ℕ
- — The set of natural numbers — the benchmark for countable infinity
- ℝ
- — The set of real numbers — an uncountable (larger) infinity
The hook
You might think all infinities are equally infinite — they are not. There is countable infinity and uncountable infinity: infinities of different sizes exist.
In plain words
If the elements of an infinite set can be numbered 1,2,3,… with none left out, it is 'countably infinite'. The naturals, integers, and rationals all qualify. Yet the reals cannot be numbered that way even in principle — they are a larger infinity.
The intuition
Two infinities are 'the same size' if they can be paired up with none left over (a one-to-one correspondence). Picture Hilbert's Hotel — it has infinitely many rooms, all full, yet when a new guest arrives you move every guest to the next room (n→n+1), freeing room 1. A 'full infinity' still has room! If such a pairing exists, they are the same infinity.
How it's built
Even the even numbers alone match the naturals in size: n↔2n pairs them perfectly (a part equal to the whole — the paradox of infinity). The integers too can be lined up 0,1,−1,2,−2,… and numbered. Even the rationals can be counted by sweeping a table diagonally. The reals, by contrast, are proven uncountable by Cantor's 'diagonal argument'.
Example
Suppose you list every real number — 0.a₁a₂a₃…, 0.b₁b₂b₃…, … Now build a new number by changing each diagonal digit (the 1st digit of the 1st number, the 2nd of the 2nd, …) to something different. This number differs from every listed number in at least one place, so it is not on the list — no listing can hold all the reals. Hence |ℝ| > ℵ₀.
Common mistake
A common error is 'infinity + 1 = infinity, so all infinities are equal'. Adding does not enlarge it, but an infinity of a 'different order' like the reals can never be paired one-to-one with the naturals. Infinity has a genuine hierarchy.
Where it's used
Which problems an algorithm can solve (computability), the fact that most real numbers are 'unnameable', that 'almost every' number is irrational in probability, the infinite hierarchies of logic — a cornerstone of modern math and computer science.
Where it came from
In 1874 Georg Cantor proved 'infinity comes in sizes', founding set theory. Treated as heresy in his day, he was defended by Hilbert's line: 'No one shall expel us from the paradise Cantor created.'
Prerequisites
Quick check
Which of the following is an 'uncountable' (larger) infinite set?
- all integers
- all even numbers
- all rationals
- all real numbers✓
Practice
Hilbert's Hotel has infinitely many rooms and all are full. When one new guest arrives, how must the guests move to make room?
Answer: 3
- Move each guest from room n to room n+1
- This empties room 1 for the new guest
- Even a full infinity can make room
Takeaway: Countable infinity makes new room by 'shifting everyone by one' — the paradox of infinity.
In the one-to-one correspondence n ↔ 2n between naturals and even numbers, what is the partner of n=7?
Answer: 14
- The rule is n ↔ 2n
- 7 ↔ 2·7 = 14
Takeaway: A subset (evens) is the same size as the whole (naturals) — possible only because it is infinite.
Is the set of all rationals a 'countable' infinity?
Answer: 0
- Arrange fractions in a table and sweep diagonally in a zigzag to number them 1,2,3,…
- Skip duplicates (reducible fractions) and none is left out
- So the rationals are countable, of size ℵ₀
Takeaway: The rationals look dense, yet can still be numbered — the same size as the naturals.
Explain in your notebook why Cantor's diagonal argument proves the reals are uncountable.
Answer: undefined
- Assume you have listed every real number (make a complete list)
- Construct a new real by changing each diagonal digit to a different value
- This number differs from the nth listed number in the nth place, so it matches none → it is not on the list
- Contradiction → no listing can hold all the reals (uncountable)
Takeaway: Diagonal argument: assume a 'complete list' and you can always build a missing number → |ℝ| > ℵ₀.