6:13 PM

Last time we looked at infinite sets which seem like they should be smaller than the natural numbers, and concluded that they are actually the same size. Since size is a weird concept applied to infinite sets, it might be better to say that they have the same cardinality instead. This time, we're going to look at some sets which seem like they might be bigger than the natural numbers.

The first candidate is the integers, but I'm not going to waste time with them because I have bigger targets in mind. I'll just point out that the sequence 0, 1, -1, 2, -2, … gives a one-to-one, onto mapping onto the natural numbers, and move on. I could give a formal proof, but I want to look at a more interesting problem instead.

Take the set of all ordered pairs of natural numbers. This includes all pairs of the form (p, q), where p and q are both any natural number. At first glance, this set is way bigger than the natural numbers. The integers looked twice as big as the natural numbers, but turn out to be the same size, but ordered pairs look infinitely bigger. Pick a number n. Then take all of the ordered pairs (n, q), where q is any natural number. We now have a mapping that maps an infinite number of ordered pairs to each natural numbers, so surely this is enough to show that there are infinitely more ordered pairs than natural numbers, right?

Wrong. If we picture the ordered pairs as a grid of points, the points on the left edge of the grid is pairs of the form (1, q), for all natural numbers q, and the bottom edge is pairs of the form (p, 1), for all natural numbers p. The grid extends infinitely far to the right and up, and every pair (p, q) is represented by one point in the grid. The mapping suggested above can be represented by a series of vertical lines, each of which is infinitely long. There are also infinitely many lines, but the end result is that every point on the grid is on one of the lines.

Instead of vertical lines, draw diagonal lines on the grid. Each line starts on the point (n, 1) and continues across the grid to the point (1, n). Each line therefore passes through all of the points of the form (p, q), where p+q=n+1. (If you can't visualize this, draw it on a piece of paper and it should be clear.) Therefore, every point (p, q) is on one of these lines, and there are an infinite number of lines, but now the number of points on each line is finite. That means that we can start with the first line, which only goes through the point (1, 1), and start counting them off. The first line goes through the point (1, 1), the second goes through (2, 1) and (1, 2), the third through (3, 1), (2, 2), and (1, 3), and so on. We have a sequence that will hit every point on the grid, or every ordered pair. We can run it in both directions, so given an ordered pair, we can find which natural number it corresponds to, and given a natural number, we can find the ordered pair it matches. If we wanted to do it formally, we could work out the exact formulas, but I'm comfortable skipping the details here.

We just showed that a set which has one mapping to the natural numbers which maps an infinite number of points to each number also has a different mapping which maps exactly one point to each number. If your head is exploding right now, that's normal. This makes no sense. I know that I had to see this multiple times before I felt like I really understood what's going on here. If you want to play around with the cardinality of countable sets, the Hilbert hotel can give you practice mixing and matching infinite sets.

I'll give you some time to make sense of this. Next time, I'll look at a generalization of what we did here with ordered pairs.

3 comments