How do you compare the sizes of two infinite sets, when you can't finish counting either?
Set theory's answer is beautifully simple: two sets have the same size exactly when
there is a
bijection
between them — a perfect pairing with nothing left over. A set is called countable
if it can be paired up with the natural numbers \mathbb{N} = \{1, 2, 3, \dots\}
— equivalently, if you can arrange all its elements into a single list
x_1, x_2, x_3, \dots that eventually reaches every one of them. (Finite
sets count as countable too; the interesting case is countably infinite.)
The integers are countable
The integers \mathbb{Z} look like they should be "twice the size" of
\mathbb{N} — they run off to infinity in both directions. Yet
they are the same size, because you can list them all without missing any: start at
0 and zig-zag outward,
0,\ 1,\ -1,\ 2,\ -2,\ 3,\ -3,\ \dots
Every integer appears at a definite position, so this is a bijection
\mathbb{N} \to \mathbb{Z}. The code prints it out — position
n and the integer sitting there:
// A bijection N -> Z: position n maps to an integer, hitting every one exactly once.
function integerAt(n: number): number {
return n % 2 === 0 ? n / 2 : -(n - 1) / 2; // 1->0, 2->1, 3->-1, 4->2, 5->-2, ...
}
for (let n = 1; n <= 11; n++) {
console.log("position " + n + ": " + integerAt(n));
}
console.log("...every integer eventually appears, so Z is countable.");
The trick is that "same size" doesn't mean "you can finish counting" — you never finish. It means
there is a systematic rule that reaches each element at some finite position.
Even the rationals are countable
Here is the real shock. The rationals \mathbb{Q} are
dense — between any two of them lie infinitely many more — so surely there are
"more" rationals than integers? No. Lay the positive fractions out in a grid, with numerator across
and denominator down, and sweep through it along diagonals:
\tfrac{1}{1}, \tfrac{2}{1}, \tfrac{1}{2}, \tfrac{3}{1}, \tfrac{2}{2}, \tfrac{1}{3},
\dots (skipping repeats). Every fraction sits on some diagonal, so it is reached at a
finite step — a listing of all of \mathbb{Q}. The rationals are countable.
- A set is countable if it can be listed x_1, x_2, x_3, \dots
— put in bijection with \mathbb{N} (finite sets included).
- \mathbb{Z} and \mathbb{Q} are both
countable — the same size as \mathbb{N}.
- A countable union of countable sets is countable, and a subset of a countable
set is countable.
This is the smallest size of infinity, written \aleph_0 ("aleph-null").
You might now suspect every infinite set is countable — but the real numbers will shatter
that: they are
uncountable, a strictly
bigger infinity.
A hotel has infinitely many rooms, numbered 1, 2, 3, \dots, and every
one is full. A new guest arrives. No problem: ask the guest in room n to
shuffle to room n+1, freeing room 1. A
coachload of infinitely many new guests? Move everyone from n
to 2n, freeing all the odd rooms. A countable infinity has room for more
countable infinities — exactly the "same size" trickery that makes
\mathbb{N}, \mathbb{Z} and \mathbb{Q} all the
same size.
-
Countable includes finite. "Countable" means finite or countably
infinite. If you specifically mean the infinite case, say "countably infinite".
-
Countable does not mean "you can count to the end" — you never can. It means a
listing exists that reaches every element at some finite position. And crucially, not
every infinite set is countable: \mathbb{R} is not.