Cardinality and Countability

Cardinality is the mathematical notion of the "size" of a set, extended to infinite sets in a way that turns out to distinguish different sizes of infinity. Two sets have the same cardinality if there's a one-to-one correspondence (a perfect pairing with nothing left over on either side) between their elements. A set is countably infinite if it can be put in one-to-one correspondence with the natural numbers $1, 2, 3, \dots$ — meaning you could, in principle, list its elements one at a time and eventually reach any particular one.

Surprisingly, the even numbers are countably infinite despite being "half" of the natural numbers — pair $n \leftrightarrow 2n$ and every natural number matches exactly one even number, with none left over. Even the rational numbers (all fractions) are countable, via a diagonal listing scheme. But the real numbers are uncountable: Cantor's diagonal argument shows that no matter how you attempt to list all real numbers between 0 and 1, you can always construct a new real number, differing from the $n$-th listed number in its $n$-th decimal digit, that is guaranteed not to appear anywhere on your list — proving no such complete list can exist.

Worked example. Suppose someone claims to have listed every real number between 0 and 1: $0.\overline{3}, 0.5000\ldots, 0.14159\ldots$, and so on. Build a new number by taking the 1st digit of the 1st listed number, adding 1 (wrapping 9 to 0), taking the 2nd digit of the 2nd number and adding 1, and so on down the diagonal. This new number differs from every number on the list in at least one digit — the $n$-th digit versus the $n$-th listed number — so it cannot be anywhere on the supposedly complete list, contradicting the claim.