wherein is detailed Matt's experiences as he tries to figure out what to do with his life. Right now, that means lots of thinking about math.

Wednesday, March 07, 2012

Last time, we showed that if you have a countable collection of sets, and each set has a countable number of members, the union of all the sets is countable. Now I'm going to use this fact to show that the set of all rational numbers is countable. There are multiple ways you could approach this, but I'm going to do it in two steps. This is both to get a little more experience working with infinite sets, and also to reinforce the counterintuitive nature of infinity.

First, I will show that all rational numbers strictly greater than zero and less than or equal to one are countable. By definition, any rational number can be written in the form p/q, where p and q are both integers and q≠0. If we restrict q to the natural numbers (the same as the positive integers) and we restrict p to the natural numbers less than or equal to q, then we have the set of all rational numbers greater than zero and less than or equal to one. Note that we have lots of duplication. This set includes both 1/1 and 2/2, and they are of course the same number. That won't be a problem. The important thing is that we aren't missing any rational numbers in that range.

Now, we are going to divide this set of rational numbers into subsets. The rule is simple. Subset q gets all all the numbers with q as a denominator. So subset 1 consists only of the number 1/1, subset 2 includes 1/2 and 2/2, and so on. There are two important facts here. 1. Every rational number greater than 0 and less than or equal to 1 is in one of these sets. 2. Each set is finite, and the total number of sets is countable.

This means we can use the theorem established last time to immediately state that the union of all the subsets is countable. Since the union is equal to the set of all the rational numbers greater than 0 and less than or equal to 1, that set is countable.

If we want to, we can look at the map in more detail. This is just like running up the diagonals in the ordered pairs of natural numbers, but there are a lot of holes. 1/1 maps to 1. 1/2 maps to 2. 2/1 would map to 3, but 2/1 isn't in our set, so nothing maps to 3. 1/3 maps to 4. 2/2 would map to 5, but again, 2/2 = 1/1, and since 1/1 is already in our set, we will map nothing to 5. And so on. Ultimately, we are mapping this infinite set of rational numbers to a subset of the natural numbers. But since any infinite subset of the natural numbers is countable, and this mapping is one-to-one, we can conclude that this set of rational numbers is countable.

We've shown that this set of rational numbers is countable. But what about the set of all the rational numbers? Well, there are countably many rational numbers greater than 0 and less than or equal to 1, but there is exactly 1 natural number in that range. So the rational numbers have a pretty big head start over the natural numbers.

There are, of course, countably many rational numbers greater than 1 and less than or equal to 2, but when we take the union of the set between 0 and 1 and the set between 1 and 2, we get the set greater than 0 but less than or equal to 2, which is countable, since the union of countable sets is countable. So we haven't actually gained anything.

Meanwhile, the set of natural numbers less than or equal to 2 now has 2 members. It's still a long way off, but maybe it's a little closer? Not really. The difference in cardinality between any finite set and a countable set is essentially the same. One finite set might be larger than another finite set, but they're still both a whole different class than a countable set.

But we know where this is going. A union of a countable collection of sets, each with a countable number of members, is countable. Therefore, the set of all rational numbers is countable. Meanwhile, the union of a countable collection of sets, even if each set contains only one member, is also countable. So if we extend this exercise out to there, the natural numbers are a countable set assembled from a countable number of sets of one member each.

As we are constructing the rational numbers as unions of sets, there are many apparent opportunities for the rationals to show that they are a larger set than the natural numbers, but it never works out. I'm going to run this in the opposite direction for the moment, and point out that this implies than any countable set can be subdivided into countably many disjoint subsets, each of which is countable. (The fact that the subsets are disjoint means that each member of the original set appears in only one subset.) So you can blow your mind by packing down some giant, but countable, set into some smaller countable set. You can also blow your mind by splintering a countable set into countable slivers of sets, and each sliver can be the same size as the original set.

By now you may be wondering if, indeed, any infinite sets are not countable. That's an excellent question, which we will consider next time.

FAQ

What does "rolls a hoover" mean, anyway?

"Roll a hoover" was coined by Christopher Locke, aka RageBoy (not worksafe). He enumerated some Hooverian Principles, but that might not be too helpful. My interpretation is that rolling a hoover means doing something that you know is stupid without any clear sense of what the outcome will be, just to see what will happen. In my case, I quit my job in an uncertain economy to try to start a business. I'm still not sure how that will work out.