Countable and uncountable sets, part 1

While writing the paradox series, and thinking about set theory for the item on Russell’s Paradox, I decided to do some related entries, considering things that seem contradictory but aren’t. This one is on the cardinality of sets, and, in particular, about countable and uncountable sets.

[Let me start by saying that this will be a simplified explanation, making a number of unstated assumptions (such as assuming the axiom of choice, as is standard in modern set theory). If one is rigorous, this stuff can get way more complicated than I’ll ever want to get into here; PhD theses, and, indeed, whole careers are often based on rigorous coverage of this. We’re not going there.]

I think we all understand that there are finite sets, and infinite ones. A finite set has... well, a finite number of elements — the set of all U.S. presidents, the set of bones in the human body, the set of all films that have won “Best Picture” Academy Awards, the set of all people in the world. Or the set of all natural numbers less than or equal to 5: { 1, 2, 3, 4, 5 }.

An infinite set has an infinite number of elements. We have a vague idea what that means, but it’s harder to write that down, isn’t it? Examples are easy, though: the set of all natural numbers, for example: { 1, 2, 3, 4, 5, 6, ... }, with no bound. The set of all integers — positive and negative natural numbers, and zero. The set of all rational numbers — the integers and all the fractions. The set of all real numbers — the rationals, plus the irrational numbers, numbers such as √2, √3, and π.

There are other sets in the real world that we think of as infinite, but are we sure they are? The set all of grains of sand in the world; the set of all stars in the universe; the set of all atoms in the universe, come to that. But in mathematics, an infinite set is more precise. It doesn’t refer to something bigger than we can imagine, but really something that no number, however vastly, immensely large, can describe.

To get a less vague meaning of “infinite”, we’ll go back to the finite sets and talk about countability and cardinality. Clearly, one aspect of any finite set is that there’s a natural number (or zero, for the empty set) that tells us how many elements are in the set. For the set of all U.S. presidents, it’s 43 (soon to be 44). For the set of all natural numbers less than or equal to 5, it’s 5. For the set of all people in the world, we don’t know the number... but it’s clear to us that there is one, and it’s quite large.

We call that number the cardinal number of a set, and every finite set has a cardinal number that’s a non-negative integer. And we can define an infinite set as a set that does not have an integral cardinal number. It seems intuitive, then, that the sets of natural numbers, integers, rationals and reals are all infinite.

Going back to finite sets, we also understand that we can count the elements of any finite set. George Washington is “1”, John Adams is “2”, ..., Abraham Lincoln is “16”, ..., Woodrow Wilson is “28”, ..., and George Bush is “43”. We hope Barack Obama will be “44”. And the counting stops. Similarly, for bones, films, and people, we can assign a natural number to each element, starting at 1 and increasing by 1 for each element, and we call that “counting” (and here’s where the axiom of choice comes in).

More formally, what we’re really doing when we count is creating a one-to-one correspondence between the elements of the set and the subset of natural numbers less than or equal to the cardinal number of the set (we’ll ignore, for the presidents, the fact that Grover Cleveland appears twice; think of him as having a not-so-evil twin).

But why do we have to stop? For an infinite set, T, suppose we can create a one-to-one correspondence between T and the entire set of natural numbers, unbounded. Have we not “counted” the set T, in some sense? Granted, our counting never stops — it’s an infinite set, after all — but if we can prove that every element of T has a natural number associated with it, we can say that we can count the elements.

Definition: For any set, S, if a one-to-one correspondence exists between S and a subset of the natural numbers, we say that S is countable. If no such mapping exists, we say that S is uncountable.

Clearly, all finite sets are countable, so all uncountable sets are infinite. Let’s play with some countable sets for a bit. First, another definition: the cardinal number of the natural numbers is a thing we call (said “aleph-null”, using the Hebrew letter aleph).

The set of natural numbers is countable, of course, by definition — each number maps to itself, and there’s our one-to-one correspondence. What about the set of even natural numbers? Our intuition certainly tells us that there are fewer of those — half as many, because all evens are also natural numbers, but half the natural numbers are not even. How well does our intuition serve us when we look at one-to-one correspondences?

We can define the function f(n) := 2n, for all natural numbers n. It’s pretty easy to see that f defines a one-to-one correspondence between the naturals and the evens: for every natural number n there’s a well defined and unique value of 2n, and that value is even; for every even number k, there’s a well defined and unique natural number n such that 2n = k. So the set of even natural numbers is countable: its cardinal number is .

It’s also not hard to show a mapping from the naturals to the whole numbers (naturals and zero): f(n) := n - 1, giving us the counter-intuitive concept that we can add an element (zero) to the set, and not increase the cardinal number. Such is the mystique of infinite sets. In fact, we can also easily map the whole numbers (and, therefore, the natural numbers) to the integers (positive and negative), with a simple alternation:

f(n) :=
    if n = 0, then 0
    if n is even, then n/2
    if n is odd, then - (n+1)/2

We won’t go into the proof that this is a one-to-one correspondence, but it is, and it’s easy to prove.

And there’s another apparent paradox: that we can, as it seems, halve or double the number of elements in our countably infinite set, and not change the cardinal number, the “size” of the set. It’s still .

This goes along with the popular notion that when you do arithmetic on “infinity”, you don’t change anything: infinity plus one equals infinity; infinity times two equals infinity. In mathematics that’s not quite right, though, and next time we’ll look more at countable sets, uncountable sets, and infinite cardinal numbers.