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.

Sunday, March 11, 2012

In the comments on my post showing that ordered pairs of natural numbers are countable, someone asked if that means that k-dimensional spaces of natural numbers are countable. I responded that you could prove that they are using induction, but that I wasn't going to spend time on that. I've been thinking about it some more, and concluded that infinite sets are fun, and induction is fun, so showing that k-spaces of natural numbers are countable will be fun, so I'm going to go ahead and do it.

First of all, let's clarify the question. A natural 1-space is a set of equally spaced points on a straight line. There is a first point in the line, and then the line extends indefinitely in one direction away from that point. We can number the points, starting with the first point as number 1, and numbering each successive point with the next natural number. There's a subtle distinction here, in that the points in the natural 1-space are not actually the natural numbers, but there's a direct correspondence between the points and the natural numbers. Because of this correspondence, it is clear that the set of points in the natural 1-space is countable.

A natural 2-space is a grid of equally spaced points. There is a bottom edge and a left edge to the grid, but the grid extends indefinitely to the right and up. Every point can be written as an ordered pair of natural numbers of the form (x,y), where the point (1,1) is the bottom left corner of the grid, points of the form (x,1) all lie on the bottom edge of the grid, points of the form (1,y) lie on the left edge of the grid, and any pair (x,y) corresponds to exactly one point in the grid and every point in the grid corresponds to exactly one pair of natural numbers. Again, there is an obvious relationship between these ordered pairs and complex numbers of the form x+iy, where both x and y are natural numbers, but the set of points in the natural 2-space is a distinct concept from the set of complex numbers with natural real and imaginary parts. In particular, multiplication is defined on the complex numbers, but is not defined on the points in the 2-space. The earlier post showed that the set of ordered pairs of natural numbers is also a countable set.

A natural 3-space is a cube of equally spaced points. There is one corner, at the point (1,1,1) and the cube extends in three directions from there. I could write the points in the form (x,y,z), but instead I will write them using subscripts, as (n1,n2,n3). Then we can say that the set of all points of the form (n1,n2,n3), where n1, n2, and n3 are all natural numbers, defines a natural 3-space. (I've switched to n, rather than x, as a reminder that we're only looking at natural numbers, rather than all real numbers or some other set.) Is the set of all points in the natural 3-space countable? That's a good question.

A natural 4-space is hard to visualize, but I can still write the points in the form (n1,n2,n3,n4). I'm not sure what it looks like, but I can work with the points mathematically, and that's good enough for me. Also, the reason for using subscripts should be clear. As the number of dimensions increases, using subscripts becomes easier to work with than using separate letters. Again, we haven't yet shown whether the set of points in the natural 4-space is countable.

We can extend the definition in general to any natural k-space, where k is any natural number. Given a point in a natural k-space, we can write that point as a k-tuple of the form (n1,n2,…,ni,…,nk), where the set of values for i is the set of natural numbers ≤ k and there is one coordinate ni for each value of i. And the big question of the day is, are natural k-spaces countable, for any natural number k?

To answer this, we need to use mathematical induction. If you don't understand how induction works, it can look like voodoo. In particular, it can look like the basis of the proof is assuming what you want to prove. If that was in fact how induction works, it wouldn't be a good method of proof, but that's not what's going on. I'll take a shot at explaining it.

Induction proofs are useful when you want to show that some statement is true for all natural numbers. In our case, we want to show that the natural k-space is countable for any natural number k. In some cases, it might be easy to prove that it's true for any particular natural number, say k=100, so if all you really cared about at this moment was that particular number, you could prove it and just move on. But most of the time you would be able to prove it true for a handful of natural numbers, but you really want to know that it is true ahead of time for any natural number you might pick. You obviously can't prove it individually for every natural number, and this is where induction comes in.

Induction proofs work in two steps. The first step is to show that if the statement is true for some particular natural number n, it must be true for the natural number n+1. This is where it can look like we are assuming what we are trying to prove. However, we are not asserting that it is true for n. We are just claiming that if it is true for n, it must be true for n+1. In concrete terms, let's say that we want to know if natural 100-spaces are countable. The first step is to say that if natural 99-spaces are countable, then natural 100-spaces are countable. We haven't proved that natural 99-spaces are countable yet, so the next step is to say that if natural 98-spaces are countable, then natural 99-spaces are countable. And so on.

The second step is to show that the statement is true for n=1. This step is usually presented first in induction proofs, but I personally find that it logically comes second. First we build a chain of conditional reasoning (if it's true for n, then it must be true for n+1), then we backstop it with the proof that it is true for n=1. At that point, the whole conditional chain becomes true. There are some statements where you could construct the inductive step, that if it is true for n, it must be true for n+1, but where it is demonstrably false for n=1. At that point, your chain of conditional reasoning falls apart. None of the "if" statements hold, and you haven't proved anything.

Let me diagram out the whole inductive chain of reasoning for proving that natural 6-spaces are countable.

• Prove that if a natural k-space is countable, for any natural number k, then a natural (k+1)-space is also countable.
• If a natural 5-space is countable, a natural 6-space is countable.
• If a natural 4-space is countable, a natural 5-space is countable.
• If a natural 3-space is countable, a natural 4-space is countable.
• If a natural 2-space is countable, a natural 3-space is countable.
• If a natural 1-space is countable, a natural 2-space is countable.
• Prove that a natural 1-space is countable.
• Since a natural 1-space is countable, a natural 2-space is countable.
• Since a natural 2-space is countable, a natural 3-space is countable.
• Since a natural 3-space is countable, a natural 4-space is countable.
• Since a natural 4-space is countable, a natural 5-space is countable.
• Since a natural 5-space is countable, a natural 6-space is countable.
• And the proof is complete.

Note that there are only two steps that we have to prove. After that, the chain of logic follows automatically for any natural number k. There are also two important limitations for induction proofs. First, the logic behind them doesn't work for rational numbers or real numbers, since the inductive step states that if it's true for x, it's true for x+1. Since there is no smallest rational or real number greater than x, there's no way to step through all of the rational or real numbers. If you want to prove something is true for any rational or real number, you will have to find a different approach.

Second, you can't use induction for all integers. You need the backstop step, where you say that the statement is true for n=1. Without the backstop, you've constructed a tower of reasoning without a foundation, and the lack of support means you haven't proved anything. You don't have to start at 1, and for some proofs it is easier to start from 0 or from 2. You could start from some negative number, like −10, if you really wanted, but there is always a least number that you are starting from, and you are not saying anything about numbers less than that. For example, if you started with n=−10, you can prove that the statement is true for all integers greater than or equal to −10, but you haven't said anything about integers less than −10. If you want to prove something true for all integers, again, you have to use a different approach.

That was lots of set up, but now we're ready to prove that all natural k-spaces are countable. Doing things in the order that induction proofs are usually written, we will show that a natural k-space is countable when k=1. But that's just the natural 1-space, and as I said earlier, even though the natural 1-space is not actually the same thing as the set of natural numbers, there's an obvious one-to-one correspondence, so the natural 1-space is countable.

Now we just need to show that if a natural k-space is countable, for any natural number k, then the natural (k+1)-space is countable. To do this, we are going to rely on the proof, based on the proof that the natural 2-space is countable, that any union of a countable collection of sets, each with a countable number of points, is countable. Start by calling the set of all points in the (k+1)-space X, for convenience. We will divide X into a countable number of subsets.

Every point in X can be written in the form (n1,n2,…,nk,nk+1). Now, look at all the points in X for which nk+1=1. This is a subset of points of X, all with the form (n1,n2,…,nk,1). Call this subset X1. Now, there is an obvious one-to-one correspondence between this subset and all of the points in the natural k-space. If (n1,n2,…,nk,1) is a point in X1 for particular values for each of the ni, then (n1,n2,…,nk) is a corresponding point in the natural k-space. But our induction hypothesis is that the natural k-space is countable. If the natural k-space is countable, X1 is countable.

Now things are easy. For every natural number i, Xi is a subset of X where every point is of the form (n1,n2,…,nk,i). Every point in X is a member of one of the subsets. The collection of subsets is countable. If the natural k-space is countable, each subset is countable. If each subset is countable, and the collection of subsets is countable, then the union of the subsets, X, is countable. Therefore, if a natural k-space is countable, for any natural number k, then the natural (k+1)-space is countable.

We have shown that if a natural k-space is countable for any natural number k, then the natural (k+1)-space is countable. We have also shown that the natural 1-space is countable. This means that we get to say that by the Principle of Mathematical Induction, we have proved that every natural k-space is countable, for every natural number k.

Food for thought: k is a natural number, and therefore finite. Don't make the mistake of thinking this proves that infinite dimensional spaces of natural number coordinates are countable. What exactly would an infinite dimensional space look like? I'm not sure exactly. The coordinates of a point in this space would look like (n1,n2,…,ni,…) for every natural number i, so even writing down the coordinates for a single point in this space poses a problem. You could do it as a function, and define f(i)=ni for some function f with domain of the natural numbers, and then that function f would give you the coordinates of a single point in this space. Every point would require a different function. How many points are in this space? Are they countable? I wonder. Ponder, ponder…

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.