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.

Tuesday, March 06, 2012

Last time, we showed that the set of all ordered pairs of natural numbers is countable, or that it has the same cardinality as the set of natural numbers. This is true despite the fact that it appears that there should be infinitely times as many ordered pairs. (This is one reason why we don't usually consider infinity to be a number. It breaks the rules we expect for numbers.) Let's turn this into a general principle.

Start with one set of points. Assume that the points in the set are countable, so there's a one-to-one, onto mapping from the set of points to the set of natural numbers. We call the set X, we can call all the individual points x1, x2, x3, and so on. I'm not really specifying what the x's are, but since they are countable, I can use the natural numbers as indexes to specify which point I'm referring to. (I discussed indexes briefly a couple of weeks ago.) The actual x's could be the even numbers, or a different ordering of the natural numbers, or the square roots of all of the natural numbers, or ordered pairs of natural numbers, or something which isn't even number-like, as long as they are countable, whatever they are.

Next, instead of one set with a countable number of points, assume we have a countable number of sets, each with a countable number of points. Instead of X, we have Xλ, where different values of λ correspond to different sets. When specifying a point, we need to specify both which set it came from and which point in that set it is, so we can use the notation xλ, n. λ specifies the set, and n specifies the point in that set.

Now, the sets are countable. That means that the possible values of λ correspond to natural numbers. And the number of points in each set is countable, which means that the possible values for n are the natural numbers. This means that the ordered pair (λ, n) corresponds to the point xλ, n, and the ordered pairs are of natural numbers, so every point in any of the sets corresponds to an ordered pair of natural numbers. This means that the points are countable.

We have just shown that the union of a countable number of sets of a countable number of points is a countable set.

We should explore this in a little more detail. Xα is a member of the collection Xλ, where α is a member of the set of possible values for λ. We don't really have to go into the details of what the set of values for λ look like, as long as the set is countable. The point xα, k is a point in the set Xα, where k is some natural number. Then there exists a function that maps the union of all Xλ to the natural numbers. The first step is the function f(xα, k) = (α, k), which maps each point to an ordered pair. We can then map the ordered pair to a natural number using the mapping described last time.

Looking back at the ordered pairs of natural numbers from last time, the first grouping we looked at was vertical lines. For a given natural number h, take all possible natural numbers k, then the set of (h,k) lies on a vertical line. This is conceptually the same as looking at the set Xα, where α maps onto the natural number h, and all possible values of k for members in that set. By taking a set of lines that are finite length diagonals rather than infinitely long verticals, we can then traverse all of the points in all of the sets.

There has been an implied assumption here that none of the sets have the same points. In other words, if α≠β, then xα, h never equals xβ, k, for any values of α, β, h, and k. The problem is that if xα, h = xβ, k, we will hit that point twice in the process of traversing all the sets, so we will map that single point to two different natural numbers and we won't have a function at all.

This is not actually a problem. If a point exists in more than one set, we can map that point to a natural number the first time we hit it, and skip it on all future times. When we skip the point, we will also skip the natural number it would be associated with. This means that our mapping will not be onto, since there are some natural numbers we are skipping. But this is not a problem since we have shown that the cardinality of an infinite subset of the natural numbers is the same as the natural numbers.

While we're at it, some or all of the sets can be finite instead of infinite, and everything still works. When we run out of points in a set, we just skip the natural numbers that would correspond to additional points in that set, but we're still good. And as long as some of the sets are infinite, we can have a finite number of sets, and the mapping still works. (To back this claim up, we should show that the union of a countable collection of distinct sets of a finite number of points must have a countable set of points, even if every point appears in multiple sets. I'll come back to this soon, when I discuss power sets.)

However, if we have a finite number of sets, and the number of points in every set is finite, then the total number of points in the union of the sets is also finite. Eventually we'll just run out of points. There are some limits.

In conclusion, the union of a finite or countable collection of sets, each containing a finite or countable number of points, is finite or countable. This means that sets which at first glance are much bigger than the set of natural numbers are in fact the same size as the natural numbers. Next time, we will use this fact to show that the rational numbers are countable.

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.