7:31 AM

Friday Random Ten!

1. Kraftwerk - Neon Lights
2. Tori Amos - Curtain Call
3. Netherlands Bach Collegium - Johann Sebastian Bach: Cantata #133, "Ich Freue Mich In Dir"
4. David Bowie - The Loneliest Guy
5. Freiburg Baroque Orchestra Soloists - Johann Sebastian Bach: Cantata #157, "Ich Lasse Dich Nicht, Du Segnest Mich Denn"
6. Jaap Ter Linden - Johann Sebastian Bach: Cello Suite #1, BWV 1007, Praeludium
7. Netherlands Bach Collegium - Johann Sebastian Bach: Cantata #58, "Kann Es Die Wlet Nicht Lassen"
8. Ludwig van Beethoven: Scottish Songs WoO 156, "Auld Lang Syne"
9. Klára Würtz - Wolfgang Amadeus Mozart: Piano Sonata No. 2, K. 280, Presto
10. London Symphony Orchestra & Chorus - Ludwig van Beethoven: Mass In C, Op. 86, Sanctus

0 comments

8:00 PM

Suppose we have a metric space. That is, we have some set X, and we have a distance function d(p,q) defining the distance between any two points p and q in X. The distance function obeys the three rules we covered last time, so distances are positive real numbers between any two distinct points and 0 from every point to itself, the distances are symmetric, and distances obey the triangle inequality.

I'm going to talk in abstract terms, but it's helpful to think in terms of a concrete example, so generally think in terms of a 2-D plane with real number coordinates and the distance measured as the straight line distance between two points. There will be cases where we have to work with other metric spaces, but this should provide a good baseline in general.

Look at a particular point in the metric space (or the plane). Call it p. It is naturally surrounded by other points. We can think of the other points as near p if the distance from the other point to p is less than some positive number r. What qualifies as "near" depends on context, so the size of r varies based on the circumstances. Take the set of all points with distance less than r from point p, or the set of points that are near to p. This set is called the neighborhood of p, with radius r. p is in the neighborhood of itself.

On the plane with straight line distances, the neighborhood of p is the interior of the circle of radius r around p, but not the circle itself. In three dimensions, the neighborhood is the interior of a sphere. For the sake of comparison, on the natural number line, if r>1, the neighborhood is just a bunch of individual points, and if r≤1, the neighborhood is only p itself.

Now, given our space X, choose a subset of that space and call it E. Consider some point in E, which we will again call p. Look at the neighborhoods of p. These are subsets of X, the space itself, and the size of the neighborhoods varies with different values of r. If any neighborhood of p is also entirely a subset of E, then p is an interior point of E.

Look at the plane. E is some crazy shape on the plane. If it's possible to draw a circle of any radius around p such that every point inside the circle is inside E, then p is an interior point of E. For example, if E is a square, so every point in X has the coordinates (x,y) and E is the set of all points with 0≤x≤1; and 0 ≤y≤1, then, say, (3/4,8/9) is an interior point of E, but (0,1/2) is not.

But let's define E, instead, as all the points in the same square, on the real plane, but only if the point has rational coordinates. Then E looks the same, but we know it has lots of holes, and in fact any circle around any point in E must include some holes. Therefore, no point in E is an interior point of E.

On the other hand, if our space was defined as the points with rational coordinates, then that same definition of E would have interior points. Holes in X can't be in the neighborhood of p. The point is just that whether a particular point is an interior point of a set depends on both the set and the space that contains it.

Any set E such that every point in the set is an interior point of the set is an open set. Our original example, the set of points in the real plane such that 0≤x≤1 and 0≤y≤1 for real values of x and y, is not open, because points can be on the edge of the set. If we redefine E to not include the edges, so 0<x<1 and 0<y<1, then E is open. Any given point can be close to the edge of the set, but there are always points which are closer to the edge, and we can always draw a circle around any point in the set so that every point in the circle is also in the set.

It's easy to show by thinking about what neighborhoods and open sets look like that every neighborhood is an open set. Pick a point p and draw a circle around it. Pick some point in the circle, and you can always draw a smaller circle around that point which remains entirely within the larger circle. The visualization on the real plane is easy, and it's not much more effort to use the triangle inequality to show it's true for any metric space.

0 comments

6:09 PM

Following infinite sets, the next topic covered in the textbook is topology. The course notes skip straight over topology and move on to sequences. Comparing the two, it looks like the course notes limit discussion of sequences to Euclidean spaces, while the textbook discusses sequences in metric spaces in general. Since the coverage of the topic is more general, the book needs to develop more of a theoretical framework.

My attitude is that as long as it's in the book, I might as well take a look. There are some caveats for my posts here. I'm less familiar with topology than I am with previous topics, so I'm more dependent on the book for making sense of the material. Also, on previous topics, I was able to compare the notes and the book, so I got two shots at understanding, and now I only have one.

The book's presentation of this material is very dense. It could be that the book expects this is review and is covering it quickly. Or it may consider this background to the later material, so while it may be new to the reader, the book doesn't want to spend more time on it than necessary. Or the book could always be this dense, and I just haven't noticed until now.

In any event, the presentation of the material in the book isn't very friendly to comprehension. It starts with a full page of definitions of terms, and then starts cranking through theorems expecting an understanding of those terms. My goal is to restructure the material, giving more of a chance to work with each concept before moving on to the next. This may make things more comprehensible. Or it may make things a giant mess.

The first topic is actually a bit of review. I've already mentioned metric spaces, but now I'm going to take another look. A metric space is a set of points with a distance function defined between pairs of points. Given any two points in the space, the distance function gives us a real number which specifies the distance between them. In order to qualify as a metric space, the distance function must have three properties.

1. For any two points p and q, d(p,q)≥0. Furthermore, d(p,q)=0 if and only if p=q. The distance from any point to itself is always 0. The distance from any point to any other point is always a real number greater than 0.
2. For any two points p and q, d(p,q)=d(q,p). Living outside of Boston, I'm well aware that driving directions from one place to another can be radically different depending which way you're going. One way streets make a mess of trip planning, and sometimes the route to a destination is significantly shorter than the route back. In a metric space, the distance is always the same, regardless of which direction you are traveling in.
3. For any three points p, q, and r, d(p,q)≤d(p,r)+d(q,r). (The triangle inequality) I was about to say that the distance function doesn't care which path you take, as long as the distance is the same, but that's not completely accurate. d(p,q) is the direct distance between p and q. If you start from p, go to some other point r, and then proceed to q, the combined distance of that trip is always equal to or greater than the direct distance. You can't take a shortcut by deliberately going through another point. (Boston geography is looking less and less like a metric space all the time.)

This definition means that sets with the distance functions we expect to work are metric spaces. In particular, for the set of real numbers, the distance function d(p,q)=|p−q| defines a metric space. For ordered pairs of real numbers, or higher dimensional Euclidean spaces, the distance as measured as the length of a vector between the two points defines a valid metric space.

However, different distance functions for the same set of points can also define a valid metric space. For example, one metric space with more relevance to New York than to Boston uses taxicab geometry to find distances on the 2-d plane. First you have to travel right or left, then you can travel up or down. In formulas, if p=(p₁,p₂) and q=(q₁,q₂), the taxicab distance is d(p,q)=|p₁−q₁| + |p₂−q₂|.

Also, different sets of points with the same distance function are distinct metric spaces. I expect that comparing the space of rational numbers to the space of real numbers, both with d(p,q)=|p−q|, will help clarify some of the properties of metric spaces.

2 comments

8:45 PM

We've shown that the natural numbers, integers, and rational numbers, along with a bunch of other things, all have the same cardinality. There's one set of numbers that we conspicuously haven't looked at: the real numbers. I don't want to show a formal proof about the cardinality of the reals today, but I expect to in the future. Instead, I want to do some informal thinking about the topic without necessarily coming to any conclusions.

This approach is in keeping with the lecture notes, which defers to the textbook, and the textbook, which implies that we could construct a proof based on indicator sets and Cantor diagonalization, but pushes off a full proof to a later topic, where it will use a different approach.

So, let's start with the obvious. By definition, the rational numbers are a subset of the real numbers. The rational numbers have holes (the standard example being √2) and the real numbers are defined as the set of numbers which fills those holes. This implies that the set of real numbers could be larger than the set of rational numbers. However, we know that the natural numbers are a subset of the rational numbers, and yet the set of rational numbers and the set of natural numbers are the same size. By now, we have enough experience with infinite sets to not trust our first intuitions.

The real numbers can be constructed from sets of rational numbers. Each set is called a Dedekind cut, and each set corresponds to a particular real number. I haven't discussed Dedekind cuts previously, but as we become more comfortable with infinite sets it may make sense to look at them in detail. The important thing for our purposes is that each set consists of all the rational numbers less than a particular real number. Note that this is strictly less than, so that the set which corresponds to the real number 1/2 includes all rational numbers less than 1/2. It does not include 1/2 even though 1/2 is a rational number.

My first thought was that, well then, every set has a greatest member, and so really, there should be a one-to-one relationship from each real number to the greatest member of that set. As usual, this thinking is completely wrong. In an earlier post, I looked at the proof that there is always a rational number between any two real numbers. The signficance here is that for each set, if you claim a particular number as the greatest rational number in that set, you can always find a rational number between that number and the real number the set corresponds to. The number you have found is in the set and is greater than the supposed greatest number, so the only conclusion is that each set has no greatest member. (Every number in the set for 1/2 is less than 1/2, but there is no greatest rational number less than 1/2.)

So we can't establish a relationship between the greatest member of each set and the corresponding real number, which is just as well, because if we could, the sets wouldn't be very good for filling the holes in the rational numbers anyway.

What else can we do with these sets? Well, talking about sets of rational numbers reminds me of power sets, which we just used to prove that uncountable infinite sets exist. A power set is the collection of all possible subsets of a set, and Dedekind cuts are subsets of the rational numbers. Unfortunately, Dedekind cuts do not include all possible subsets of the rational numbers, so the power set of the rational numbers is not equal to the set of all Dedekind cuts.

You can kick around some other power sets, like the power set of all natural numbers, but I don't see an obvious way to map a power set to the set of all Dedekind cuts. (I'm open to the possibility that there's a non-obvious way. After all, I don't think that the diagonalization that shows that ordered pairs of natural numbers are countable is obvious. But if there is a non-obvious way, I don't know what it is.)

You could argue that maybe you don't need all of the subsets of the rational numbers. Maybe Cantor's diagonalization would work on just the Dedekind cuts. This might be worth exploring, but in order for it to work, the set generated by the anti-g function would have to be a Dedekind cut. Unless you can prove that any set generated by any potential ordering must be a Dedekind cut, I don't think it works. If the set generated by anti-g isn't a Dedekind cut, there's no problem. The set was designed to not be in the list of all Dedekind cuts, it's not a Dedekind cut, and it's not on the list.

If it's not clear, I'm just throwing out ideas here. If I'm missing anything, feel free to jump in and leave a comment.

There is one statement we have to work with, which you can develop if you're interested. This comes from the textbook. Consider the output from the indicator functions of subsets of the natural numbers. Compare this to binary representations of real numbers.

I'm stopping there. I'm not drawing any conclusions, just exploring ways of thinking about the question. Next time I'm moving on to new and different topics.

4 comments

8:33 PM

The goal is to construct an uncountable set, that is, an infinite set that does not have a one-to-one, onto mapping from the natural numbers. Our first tool toward this goal is the power set. A power set is the set of all possible subsets of a given set. It's clear that the cardinality of a power set of a finite set is larger than the cardinality of the finite set. Given our experience with countable sets, whether the cardinality of a power set of a countable set could believably be the same as the cardinality of the countable set is unclear.

Our second tool is indicator functions. Here's the idea. Start with a set Ω. For the sake of example, let's say that Ω has three members, and Ω={a,b,c}. Now take some subset of Ω, call it A. Again, for example, let's say that A={b}. Now, we are going to build a function, called I_A, which indicates whether each member of Ω is in A. Pick any point in Ω and call it ω. If ω is in A, then I_A(ω)=1. If ω is not in A, then I_A(ω)=0. In our example, I_A(a)=0, I_A(b)=1, and I_A(c)=0. Of course, if we were looking at a different subset of Ω, we would get different values for the function.

I_A is called an indicator function, because for each point in Ω, it indicates whether that point is in A. I_A is a particular mapping from the set Ω to the set {0,1}. We can easily imagine the set of all possible mappings from Ω to the set {0,1}, and give the set of mappings the notation {0,1}^Ω. We can generalize this notation and say that if f is a potential function mapping from the set X to the set Y, then the set of all possible functions from X to Y is written Y^X and is called set exponentiation.

Looking specifically at {0,1}^Ω, we can see that this set of functions is directly related to ℘(Ω), the power set of Ω. Take a particular function f which is a member of {0,1}^Ω. Now, for that function, take the set in Ω of all values ω such that f(ω)=1. Reusing terminology from previously, find the preimage of {1} in Ω. Every subset of Ω, which is a member of ℘(Ω), has a corresponding function f in {0,1}^Ω, and vice versa. Each function f in {0,1}^Ω is an indicator function, I_A, for some subset A of Ω.

Now we're ready to prove that the power set of the natural numbers is not countable. We are going to use the fact that ℘(ℕ) has a one-to-one correspondence with {0,1}^ℕ, and show that {0,1}^ℕ is not countable. And, following Cantor's diagonalization proof, we're going to do it by contradiction.

Assume that there exists a one-to-one, onto function that maps from ℕ to {0,1}^ℕ. For every natural number n in ℕ, there is a corresponding function f_n in {0,1}^ℕ. We aren't trying to specify the function, just asserting that it exists. Now, f_n has the natural numbers as its domain. So n is in the domain of f_n, and f_n(n) is valid, and must have the value of either 0 or 1. This is true for every n in the natural numbers, so we can construct a new function g, such that g(n)=f_n(n).

If we were to construct a table, with values of f_n corresponding to rows and values of n corresponding to columns, we could look up f_a(b) by looking up the value, either 0 or 1, in row a and column b of the table. The function g gets its values by running down the diagonal of the table. Importantly, g has as its domain the natural numbers, and has as its range the values {0,1}, so g is itself a member of {0,1}^ℕ.

Now for the twist. Let's generate an anti-g. The rule is simple. If for some value n, g(n)=1, then anti-g(n)=0. If g(n)=0, then anti-g(n)=1. Anti-g is also a member of {0,1}^ℕ, since its domain is again the natural numbers, and its range is {0,1}. Therefore, anti-g must also be in our table of functions. And here is the contradiction. For all n, anti-g(n)≠g(n). But g(n)=f_n(n) for all n, so anti-g(n)≠f_n(n) for all n. But since anti-g is in {0,1}^ℕ, and there is a one-to-one, onto mapping from ℕ to {0,1}^ℕ, there must be some x such that f_x(n)=anti-g(n) for all n.

We have shown that f_n(n)≠anti-g(n) for all n. Therefore, there is no x such that f_x(n)=anti-g(n) for all n, because f_x(x) can never equal anti-g(x). The only conclusion is that it is not possible to construct a one-to-one, onto mapping from ℕ to {0,1}^ℕ, and therefore that the cardinality of ℘(ℕ) is greater than the cardinality of ℕ. ℘(ℕ) is not countable.

A couple of points: This argument works for any set. The table was a useful visual reference, but we did not depend on its existence for the proof. For any set Ω, we can define {0,1}^Ω. Then our proposed mapping from Ω to {0,1}^Ω has a function f_ω for any point ω in Ω, and anti-g(ω)≠f_ω(ω) for all ω. (Okay, there were a lot of symbols in that last sentence. But there are a lot of symbols in this whole post. I apologize if your eyes are glazing over.)

In particular, this means that ℘(℘(ℕ)) has greater cardinality than ℘(ℕ), and so forth. So we need notation to represent differing cardinalities of different infinite sets. The cardinality of ℕ, the natural numbers, is ℵ₀. (This is the cardinality of the integers, the rational numbers, ordered pairs of natural numbers, etc., of course.) The cardinality of the power set of the natural numbers, ℘(ℕ), is ℵ₁. The cardinality of ℘(℘(ℕ)) is ℵ₂. And so on. Note that the subscripts are whole numbers. I don't know if ℵ_∞, or maybe ℵ_ℵ0, is a meaningful concept, or what it would mean. That's outside the scope of what I'm currently studying.

My second point: over the weekend, I raised the question of the size of an infinite dimensional coordinate space of natural numbers. Borrowing the current notation, what's the cardinality of a natural ℵ₀-space? Well, 0 isn't a natural number, but {0,1}^ℕ is obviously the same size as {1,2}^ℕ. Take some function f(n) in {1,2}^ℕ. Then in the infinite tuple (x₁, x₂,…,x_i,…), set x_i=f(i) for every i. It's clear that every function corresponds to a point in the infinite dimensional space, so since this subset of the space is uncountable, the space as a whole is uncountable. The follow up question is whether the space is the same size as ℘(ℕ), or if it is in fact larger. Proving it one way or the other isn't obvious off the top of my head, so I'll have to give it more thought.

0 comments

10:06 PM

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 (n₁,n₂,n₃). Then we can say that the set of all points of the form (n₁,n₂,n₃), where n₁, n₂, and n₃ 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 (n₁,n₂,n₃,n₄). 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 (n₁,n₂,…,n_i,…,n_k), where the set of values for i is the set of natural numbers ≤ k and there is one coordinate n_i 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 (n₁,n₂,…,n_k,n_k+1). Now, look at all the points in X for which n_k+1=1. This is a subset of points of X, all with the form (n₁,n₂,…,n_k,1). Call this subset X₁. Now, there is an obvious one-to-one correspondence between this subset and all of the points in the natural k-space. If (n₁,n₂,…,n_k,1) is a point in X₁ for particular values for each of the n_i, then (n₁,n₂,…,n_k) 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, X₁ is countable.

Now things are easy. For every natural number i, X_i is a subset of X where every point is of the form (n₁,n₂,…,n_k,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 (n₁,n₂,…,n_i,…) 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)=n_i 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…

1 comments