Countable sets

Countability is a sort of equivalent of size for sets, because with infinite sets we can’t work with the number of elements, since the number of elements is, surprisingly, … infinite. The size of a set is also called its cardinality.

The size of an infinite set

Finding the size of a finite set is easy: we count the elements. So the set M = {a, b, c, d, e} has size 5, and we write |M| = 5.

With infinite sets the situation is a good deal harder. How could we compare the sizes of infinite sets? Is it even possible, or are all infinite sets “equally big”?

As an example, take the set of positive integers and the set of even positive integers. So we have the sets ℤ⁺ = {1, 2, 3, 4, 5, 6, …} and S = {2, 4, 6, …}. It is tempting to say that the set of positive integers is bigger than the set of even numbers, because the positive integers contain all the even numbers and some extra elements as well – the odd numbers.

So we could write S ⊊ ℤ⁺, meaning that S is a proper subset of ℤ⁺. And we could say that if S ⊊ ℤ⁺, then the set ℤ⁺ is bigger – it surely contains more elements than S.

One reason why we can’t measure sets by the subset relation is that sets can have different sizes even though neither set is a subset of the other. We can show this even with finite sets: A = {1, 3, 4, 9} and B = {b, u, r, z, m}. We have |A| = 4 and |B| = 5. The set B is bigger than A, yet A ⊆ B does not hold. With infinite sets we can see this with the even and odd numbers. Neither set is a subset of the other.

So the subset relation is not a good candidate for deciding whether one set is bigger than another.

Bijections

Let’s try a different approach. We have two sets, A and B. We can say that they have the same size if there is a bijection (one-to-one correspondence) between them. What does that mean? We take an element from the set A and an element from the set B and form the pair (a, b). We remove those elements from the sets and carry on. If we manage to “empty” both sets, we have found a bijection.

An example with finite sets: A = {a, b, c} and B = {1, 2, 3}. The first pair could be (a, 1), the next (b, 2) and finally (c, 3). We have used up all the elements of both sets, so we have found a bijection. Note that this is not the only bijection. This is a valid solution too: (a, 3), (b, 1), (c, 2).

With infinite sets it gets a bit more interesting. Let’s try the odd and even positive integers. Intuitively we feel there should be the same number of each. Let’s try. We take the first odd number and map it to the first even number: (1, 2). Then the second odd number and the second even number: (3, 4). And so on. This gives us the pairs (1, 2), (3, 4), (5, 6), (7, 8), … We could write that every odd number l is mapped to the even number l + 1, and every even number s is the image of the odd number s − 1. So for every odd number and every even number there is a pair that contains it. The sets of odd and even numbers are therefore the same size.

Even numbers vs. positive integers

Now let’s try the same method and compare the set of positive integers with the set of even numbers. So we have the sets ℤ⁺ = {1, 2, 3, 4, 5, 6, …} and S = {2, 4, 6, …}. Intuitively we expect the set of positive integers to be bigger.

But let’s try to find a bijection. We can say that every positive integer n is mapped to its double, 2n. This gives the pairs (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), … For every positive integer n we have the pair (n, 2n), and for every even number s we have the pair (s/2, s). We have found a bijection, so the set of even numbers and the set of positive integers are the same size – they have the same cardinality.

This may seem confusing, because the positive integers surely contain more elements than the even numbers. They contain all the even numbers and all the odd numbers as well. But we can find a bijection, so the two sets are the same size.

Comparison with the positive integers

The positive integers actually give the smallest size of an infinite set. Whether another set has the same size as the positive integers can often be found out quite easily – we just need to find a bijection with the positive integers, which in practice means that we only need to be able to number the elements of our set M, that is, put them in order.

So if we can arrange the elements of a set so that we can say which is first, which is second, third, fourth, tenth and so on, then the set is the same size as ℤ⁺. We then call such a set countable.

It is easy to see that the even and odd positive integers are countable, because we can say which is the first, second, third and so on even or odd number. What about the even integers? That is, the set S = {…, −4, −2, 0, 2, 4, …}. Can we put them in order? We can: we take the same ordering as before and straight after each positive even number we write its negative: S = {0, 2, −2, 4, −4, 6, −6, …}. We can do the same, for example, for the integers.

The size of the rational numbers

A more interesting example is the rational numbers, the fractions. Can we put them in order? We can, but it gets a bit harder. We build a table with infinitely many rows and columns. Each cell holds a fraction. In the nth column and mth row we put the fraction n/m. So in the 1st column and 2nd row we have $\frac{1}{2}$, and in the third column and fourth row we have 3/4.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

How do we now put these numbers in order and number them? We can’t number them row by row or column by column, because we would be swallowed up by that one row or column straight away. Instead we take the numbers along the diagonals: (first diagonal:) 1/1, (second diagonal:) 2/1, 1/2, (third diagonal:) 3/1, 2/2, 1/3, (fourth diagonal:) 4/1, 3/2, 2/3, 1/4, … There are still plenty of repeated fractions, but that doesn’t matter. What does matter is that there are no negative numbers. That is easy to fix: whenever we write a fraction, we put its negative straight after it. And then we are only missing zero at the very start. And that’s it – we have all the rational numbers in a list.

Overall we get the list: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

The size of the real numbers

Are the real numbers the same size as the positive integers? The decision will be harder still than for the rational numbers. We will use a proof by contradiction. Suppose that the real numbers are countable and that there is a bijection with the positive integers. That is, suppose they can be put in order. And let’s say that the following list is that ordering:

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

The table shows the first seven real numbers in our ordering. The ordering can of course be arbitrary – the numbers needn’t be sorted by size.

By our assumption, all the real numbers are listed in this infinite table. (The table is again infinite; only the first seven entries are shown here.) Now we will try to find or construct a real number that is not in this table. If we find such a number, it contradicts the claim that the table contains all the real numbers, and we can conclude that the set of real numbers is not countable.

We construct the number that isn’t in the table like this:

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

We start by writing 0,… This is how our new real number will begin. In the first decimal place we put a digit that is not the first digit of the first real number in our ordering (it is highlighted with a box in the table). That digit is 3, so we choose, say, 1 and we get the number 0.1…

We continue. In the second place we put a digit that is not the second digit of the second real number. That one is 9, so let’s say 2. We get the number 0.12… In the third place we put a digit that differs from the third digit of the third real number. That one is 3, so we choose, for instance, 7. We get 0, 127…

And so on and so on. In the nth position of the new number there is always a digit that differs from the digit in the nth position of the nth number in our ordering.

What does this give us? It gives us a number that differs from every number in our ordering in at least one digit. Take the latest temporary result: 0.127… This number certainly differs from the first number in our ordering in at least the first digit – because we built it that way. It differs from the second number in at least the second digit. From the third in the third digit. In general, the new number differs from the number in the nth place of the ordering in at least the digit in the nth position.

So the newly constructed number can’t be found in the table, which was supposed to represent a bijection between the positive integers and the real numbers. The real numbers are therefore bigger than the positive integers. The real numbers are not countable; they are uncountable.

More sources

• Are there more odd or even numbers?