# 3.6.2: Counting to infinity

So far, we have only discussed finite sets. N, the set of natural numbers {0, 1, 2, 3, . . . }, is an example of an infinite set. There is no one-to-one correspondence between N and any of the finite sets Nn. Another example of an infinite set is the set of even natural numbers,E = {0,2,4,6,8,...}. There is a natural sense in which the sets N and E have the same number of elements. That is, there is a one-to-one correspondence between them. The function f : N → E defined by f(n) = 2n is bijective. We will say that N and E have the same cardinality, even though that cardinality is not a finite number. Note that E is a proper subset of N. That is, N has a proper subset that has the same cardinality as N.

We will see that not all infinite sets have the same cardinality. When it comes to infinite sets, intuition is not always a good guide. Most people seem to be torn between two conflicting ideas. On the one hand, they think, it seems that a proper subset of a set should have fewer elements than the set itself. On the other hand, it seems that any two infinite sets should have the same number of elements. Neither of these is true, at least if we define having the same number of elements in terms of one-to-one correspondence.

A set A is said to be countably infinite if there is a one-to-one correspondence between N and A. A set is said to be countable if it is either finite or countably infinite. An infinite set that is not countably infinite is said to be uncountable. If X is an uncountable set, then there is no one-to-one correspondence between N and X.

The idea of ‘countable infinity’ is that even though a countably infinite set cannot be counted in a finite time, we can imagine counting all the elements of A, one-by-one, in an infinite process. A bijective function f : N → A provides such an infinite listing:( f (0), f (1), f (2), f (3), . . . ). Since f is onto, this infinite list includes all the elements ofA. In fact, making such a list effectively shows that A is countably infinite, since the list amounts to a bijective function from N to A. For an uncountable set, it is impossible to make a list, even an infinite list, that contains all the elements of the set.

Before you start believing in uncountable sets, you should ask for an example. In Chapter 3, we worked with the infinite sets Z (the integers), Q (the rationals), R (the reals), and R ∖ Q (the irrationals). Intuitively, these are all ‘bigger’ than N, but as we have already mentioned, intuition is a poor guide when it comes to infinite sets. Are any of Z, Q, R, and R ∖ Q in fact uncountable?

It turns out that both Z and Q are only countably infinite. The proof that Z is count- able is left as an exercise; we will show here that the set of non-negative rational numbers is countable. (The fact that Q itself is countable follows easily from this.) The reason is that it’s possible to make an infinite list containing all the non-negative rational numbers. Start the list with all the non-negative rational numbers n/m such that n + m = 1. There is only one such number, namely 0/1. Next come numbers with n + m = 2. They are0/2 and 1/1, but we leave out 0/2 since it’s just another way of writing 0/1, which is already in the list. Now, we add the numbers with n + m = 3, namely 0/3, 1/2, and2/1. Again, we leave out 0/3, since it’s equal to a number already in the list. Next come numbers with n + m = 4. Leaving out 0/4 and 2/2 since they are already in the list, we add 1/3 and 3/1 to the list. We continue in this way, adding numbers with n + m = 5, then numbers with n + m = 6, and so on. The list looks like

$$\left(\frac{0}{1}, \frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{1}, \frac{1}{4}, \frac{2}{3}, \frac{4}{2}, \frac{4}{5}, \frac{1}{5}, \frac{5}{1}, \frac{1}{6}, \frac{2}{5}, \ldots\right)$$

This process can be continued indefinitely, and every non-negative rational number will eventually show up in the list. So we get a complete, infinite list of non-negative rational numbers. This shows that the set of non-negative rational numbers is in fact countable.