## Talking Forever

David Corfield of The n-Category Café and Alexandre Borovik of Mathematics Under the Microscope have opened up ~~an infinite dialogue~~ A Dialogue on Infinity. And they’ve chosen an *excellent* WordPress theme for it!

## My solution to the XKCD Puzzle

So here’s how I’ve been thinking about that XKCD puzzle. My approach is essentially an exercise in the techniques covered in John Baez’ Quantum Gravity seminar for 2003-2004.

Basically, we consider each possible path from the source — which we’ll assume is at the origin of our lattice — to the target — which will be at lattice coordinates — as a series circuit, and the collection of all possible paths is a giant parallel circuit. If a given path has length it passes through resistors, and so its total resistance is . Thus we need to form the sum over all paths

and take the reciprocal of this sum. So we’ve got a combinatorial problem: how many lattice paths have length and go from the origin to ? Let’s call this number and build the “exponential generating function”

We choose the exponential generating function here rather than the ordinary generating function because of a manipulation we want to do later that looks nicer for exponential generating functions. We’ll go from to our desired sum a little later.

For now, let’s consider a simpler generating function. Consider the number of paths on a one-dimensional lattice with length that start at and end at . First off, if we have no paths that work. Similarly, if is not divisible by we won’t have any good paths. But when , there are generally many different paths. How do we get our hands on one? Choose steps to take left and the other to take right, and we’ll end up steps to the right. So we set to get the exponential generating function

where is a Bessel function of the first kind.

Now a path in the two-dimensional lattice is really a mixture of two one-dimensional paths. That is, we break our steps up into chunks of and steps, respectively, put a one-dimensional path on the chunk ending at , and put a one-dimensional path on the chunk ending at . And it turns out that generating functions are perfect for handling this!

This tells us how to find the number of paths of length that end at — it’s just the th derivative of this power series, evaluated at . That is

Now let’s consider the ordinary generating function for :

Here the coefficient of is the number of paths of length (and thus with resistance ) from the origin to . What we want to calculate is the sum . To get at this, we’ll divide our power series by and then integrate with respect to . This will give the series , which we can then evaluate at . Notice that we never have any paths of length zero unless we’re counting up the reciprocal resistance from the origin to itself, which should definitely be infinite anyway, so dividing by isn’t really a problem.

Now I admit there’s one glaring problem here: I don’t know offhand how to go from an exponential generating function to an ordinary generating function, much less how to integrate what we get from doing that to this product of Bessel functions.

Any thoughts?

*[UPDATE]:* I was just working on some numerics and there’s a problem here somewhere. The coefficients are off, but by a (sort of) predictable amount. I don’t really have time to fix this now, so I’ll come back with more later.

*[UPDATE]:* Okay, I see what’s wrong now. I’m adjusting what I said above.

*[UPDATE]:* Someone pointed out to me that after all of this I need to do a renormalization just like for the path integrals in quantum field theory. That is, in the above I need to restrict to paths that never hit the same edge twice, which is a harder combinatorial problem than I expected.

Still, it’s nifty to see the Bessel functions…

## Metric Spaces and continuity of real-valued functions

Now that we’ve got the real numbers which correspond to our usual notion of magnitudes like distances, let’s refine our concept of a uniform space to take into account this idea of distance.

A metric space is a set equipped with a notion of “distance” in the set. That is, we have a set and a function , which assigns a real number to every pair of points in . This function will satisfy the following axioms:

- For all , .
- For all , if and only if .
- For all , .
- For all , .

The first says that distances are all nonnegative real numbers. The second says that any point is distance from itself, and *only* from itself. The third says that the distance between two points doesn’t depend on the order in which we take the points. The last is called the triangle inequality, because if we think of the points as the vertices of a triangle then it’s shorter to go from to along the leg connecting those two than to take the detour to .

Notice that these properties line up with those of absolute values. That is, the function defined by will be a distance function on .

Now any metric space is actually a uniform space. We define an entourage for each positive real number . This consists of all the pairs with . Since each of these will contain the diagonal. The intersection is the entourage corresponding to the smaller of and . Each is its own reflection by the symmetry of the distance function. And the triangle inequality gives our half-size entourages — if and then .

For the real numbers themselves we should verify that we get back the same uniform structure as we did before. Remember that the uniform structure we got from completing the uniform structure on the rational numbers had an entourage for each positive , with . Each one of these shows up in the entourages for the metric structure, by considering as a positive real number, but does every basic entourage from the metric structure show up as an entourage in the complete uniform structure? It does! The Archimedean property tells us that for any positive we can find a positive rational number . Then , and so is an entourage in the completion of the uniform structure on the rationals.

Let’s look at the neighborhood structure we get from the entourages of the metric structure. A subset is a neighborhood of if and only if it contains for some . That is, it must contain the “open ball” of all such that .

In this means that we have a neighborhood base for each point consisting of the intervals . Thus a subset of will be open if and only if it contains such a symmetric neighborhood of each of its points, and this will happen if and only if is the union of a collection of open intervals. Then we can take the intervals as a base for our topology.

As a final *coup de grâce*, let’s write down explicitly the condition that a function be a continuous map. We have a neighborhood base of our topology, and we know we only need to check the neighborhood definition of continuity on a neighborhood base.

So, a function will be continuous at if and only if for each neighborhood there is a neighborhood with . Translating this all into our explicit language for the real numbers and restricting to neighborhood bases says that a function is continuous at if and only if for each there is a so that implies . And we’re back to the old definition of continuity from calculus 1! Then, as usual, we say that is continuous if the above condition holds for all .

What about uniform continuity. We can again translate the statements to our special case and check them on the basic entourages. A function will be uniformly continuous if for every there is a so that for all , implies that .

Notice particularly the difference between uniform continuity and continuity. Continuity says that (for all ) (for all there exists a ) such that ( implies ). Uniform continuity says that (for all there exists a ) such that (for all ) ( implies ). The quantifier for shows up *after* the quantifier for in the latter definition. That is, for a uniformly continuous function we can pick the *uniformly* to apply to all points , while for a merely continuous function we may have to use a different for each point . At first it doesn’t seem to be that big a deal, which always causes a certain amount of confusion in an advanced calculus (undergraduate real analysis) class, but it turns out that being able to choose the same at every point makes a lot of nice things work out that don’t otherwise hold.

*[UPDATE]:* I’m feeling a little silly that I didn’t mention this before, but the last two definitions immediately port over to *any* function between metric spaces and by just using the local definitions of “distance” in place of that for . A function is continuous if for all and there is a so that implies . Similarly, is uniformly continuous if for all there is a so that for all implies .

## Archimedean Fields

Whether we use Dedekind cuts or Cauchy sequences to construct the ordered field of real numbers (and it doesn’t matter which), we are taking the ordered field of rational numbers and enlarging it to be “complete” in some sense or another. But we also aren’t making it *too* much bigger. The universality property we got from completing the uniform structure already gives evidence of that, but there’s another property which we can show is true of , and which shows that the real numbers aren’t too unwieldy.

In *The Sand Reckoner*, the ancient Greek mathematician Archimedes once set about the problem of should the number of grains of sand in existence to be finite. He does this by determining a (very weak) upper bound: the number of grains of sand it would take to fill up the entire universe, as he understood the latter term. He writes:

There are some … who think that the number of the sand is infinite in multitude; and I mean by the sand not only that which exists about Syracuse and the rest of Sicily but also that which is found in every region whether inhabited or uninhabited. Again there are some who, without regarding it as infinite, yet think that no number has been named which is great enough to exceed its multitude. And it is clear that they who hold this view, if they imagined a mass made up of sand in other respects as large as the mass of the earth filled up to a height equal to that of the highest of the mountains, would be many times further still from recognizing that any number could be expressed which exceeded the multitude of the sand so taken. But I will try to show you by means of geometrical proofs, which you will be able to follow, that, of the numbers named by me … some exceed not only the number of the mass of sand equal in magnitude to the earth filled up in the way described, but also that of a mass equal in magnitude to the universe

The deep fact here is a fundamental realization about numbers: the set of natural numbers has no upper bound in the real number system. That is, no matter how huge a real number we pick there’s always a natural number bigger than it. Equivalently, given any positive real number — even as small as the volume of a grain of sand — and another positive real number — even as large as the volume of (the ancient Greek conception of) the universe — there’s some natural number so that . When this happens in a given ordered field we say that the field is “Archimedean”.

So let’s show that is Archimedean. If there were positive real numbers and so that for all natural numbers , then would be an upper bound for the set of . Then Dedekind completeness gives us a least upper bound , and we can just take to be this least upper bound. Now , and also , and so . That is, is another upper bound for the set of multiples of . But since was chosen to be positive we see that , contradicting the assumption that was the least such upper bound. So such a pair of real numbers can’t exist.

In particular, we can take a positive real number and consider the set of natural numbers which are larger than it. Since the natural numbers are well-ordered, there is a least such number, and it can’t be because we assume . Subtracting one from this number will then give the largest natural number that is still below in the real number order, and we denote this number by . We can thus write any positive number uniquely as the sum of a natural number and some remainder with .

It turns out that the real numbers are actually the *largest* Archimedean field. That is, if is any ordered field satisfying the Archimedean property, there will be an monomorphism of ordered fields , making (the image of) a subfield of . I won’t prove this here, but I will note one thing about the meaning of this result: the Archimedean property essentially limits the size of an ordered field. That is, an ordered field can’t get too big without breaking this property. Dually, an ordered field can’t get too small without breaking Dedekind completeness or uniform completeness. Completeness pulls the field one way, while the Archimedean property pulls the other way, and the two reach a sort of equilibrium in the real numbers, living both at the top of one world and the bottom of the other.

## Cuts and Sequences are Equivalent

Sorry to not get this posted until so late, but the end of the semester has been a bit hectic.

We’ve used Dedekind cuts to “complete” the order on the rational numbers — to make sure that every nonempty set of numbers with an upper bound has a least upper bound. We’ve also used Cauchy sequences to “complete” the uniform structure on the rational numbers — to make sure that every Cauchy sequence converges. But do we actually get the same thing in each case?

If we take a real number represented by a Cauchy sequence it’s easy to come up with a cut. Given a rational number we use the constant sequence and compare it to . If is eventually nonnegative then is less than , and should go into the left set . On the other hand, if it’s eventually nonpositive then is greater than and should go into the right set . It’s straightforward to show that this function from to the set of cuts preserves the order.

Now let’s start with the cut and write down a Cauchy sequence. Pick some and , and construct the sequence as follows. First write down and . Now set . This value will either be in or it won’t. If it is, replace by , and otherwise replace by . Then define as the midpoint between our two left and right points, and again replace either the left or the right point. Keep going, and we see that all future numbers in the sequence are closer to each other than the current and are to each other. And these two always keep moving closer and closer to each other, halving their distance at each step. So the sequence has to be Cauchy. If we picked a different and to start with, we’d get an equivalent sequence. I’ll leave this to you to show.

Notice here that the points in the sequence that lie in are moving steadily upwards towards the cut, and those in are moving steadily downwards towards it. Eventually, the sequence will rise above any point in and fall below any point in , and so if we take this sequence and build a cut from it we will get back the exact same cut we started with. Also, if we build a cut from a Cauchy sequence, and then a sequence from it, we get back an equivalent sequence. Thus we have set up a bijection between the set of cuts and the set of equivalence classes of Cauchy sequences, and we’ve already seen that it preserves the order structure.

Now let’s look at the map from sequences to cuts and verify that it preserves addition and multiplication of positive numbers. This will make the map into an isomorphism of ordered fields, and so both constructions are describing essentially the same thing. So if we have Cauchy sequences and , which give right sets and of rational numbers, then what’s the right set of the sequence ? It’s the set of rational numbers so that is eventually nonnegative. But any such can be broken up as , where and are both eventually nonnegative. That is, is the set of sums of elements of and , and so addition is preserved. The proof for multiplication is essentially the same.

So both methods of extending the real numbers give us essentially the same ordered field, which is thus both complete as a uniform space and Dedekind complete.

## Dedekind Completion

There’s another sense in which the rational numbers are lacking and the real numbers fix them up. This one is completely about the order structure on , and will lead to another construction of the real numbers.

Okay, so what’s wrong with the rational numbers now? In any partial order we can consider least upper or greatest lower bounds. That is, given a nonempty set of rational numbers the least upper bound or “supremum” is a rational number so that for all — it’s an upper bound — and if is any upper bound then . Similarly the “infimum” is the greatest lower bound — a lower bound that’s greater than all the other lower bounds.

There’s just one problem: there might not be a supremum of a given set. Even if the set is bounded above, there may be no *least* upper bound. For instance, the set of all rational numbers so that is bounded above, since is an example of an upper bound, and is another. But no matter what upper bound we have in hand, we can always find a lower number which is still an upper bound for this set. In fact, the upper bound *should* be , but this isn’t a rational number!

Now we define an ordered field to be “Dedekind complete” if every nonempty set with an upper bound has a least upper bound . Considering the set consisting of the negatives of elements of , every nonempty set with a lower bound will have a least lower bound. The flaw in the rational numbers is that they are not Dedekind complete.

So, in order to complete them, we will use the method of “Dedekind cuts”. Given a nonempty set with any upper bounds at all, the collection of all the upper bounds forms another set , and any element of gives a lower bound for . We then have the collection of all lower bounds of , which we call . Every rational number will be in either or . Given a rational number if there is an with then is a lower bound for , and is thus in . If not, then is an upper bound for and is thus in . However, one number may be in both and . If has a rational supremum then it is in both and . There can be no more overlap.

So we’ve come up with a way of cutting the rational numbers into a pair of sets — the “left set” and “right set” of the “cut” — with for every and . We define a new total order on the set of cuts by if . Every rational number corresponds to one of the cuts which contains a one-point overlap at that rational number, and clearly this inclusion preserves the order on the rational numbers.

Now if I take any nonempty collection of cuts with an upper bound (in the order on the set of cuts) we can take the union of all the and the intersection of all the to get a new cut. The left set contains all the , and it’s contained in any other left set which contains them, so it’s the least upper bound. Thus the collection of cuts is now Dedekind complete.

We can also add field structures to this completion of an ordered field. For this purpose, it will be useful to denote a generic element of by , and assume runs over all elements of wherever it appears. For instance, given cuts and , we define their sum to be . The negative of a cut will be . The product of two positive cuts and will have as its right set the collection of all products , and its left set defined to make this a cut. Finally, the reciprocal of a positive cut will have the set as its right set, and its left set defined to make this a cut.

This suffices to define all the field operations on the set of cuts, and if we start with we get another model of . I’ll leave verification of the field axioms as an exercise, and come back to prove that the method of cuts and the method of Cauchy sequences are equivalent. Once you play with cuts for a while, you may understand why I came at the real numbers with Cauchy sequences first. The cut approach seems to have a certain simplicity, and it’s less ontologically demanding since we’re only ever talking about pairs of subsets of the rational numbers rather than gigantic equivalence classes of sequences. But in the end I always find cuts to be extremely difficult to work with. Luckily, once we’ve shown them to be equivalent to Cauchy sequences it will establish that the real numbers we’ve been talking about are Dedekind complete, and we can put the messiness of this definition behind us.

## The Order on the Real Numbers

We’ve defined the real numbers as a topological field by completing the rational numbers as a uniform space, and then extending the field operations to the new points by continuity. Now we extend the order on the rational numbers to make into an ordered field.

First off, we can simplify our work greatly by recognizing that we just need to determine the subset of positive real numbers — those with . Then we can say if . Now, each real number is represented by a Cauchy sequence of rational numbers, and so we say if has a representative sequence with each point .

What we need to check is that the positive numbers are closed under both addition and multiplication. But clearly if we pick and to be nonnegative Cauchy sequences representing and , respectively, then is represented by and is represented by , and these will be nonnegative since is an ordered field.

Now for each , , so . Also, if and , then and , so , and so . These show that defines a preorder on , since it is reflexive and transitive. Further, if and then and , so and thus . This shows that is a partial order. Clearly this order is total because any real number either has a nonnegative representative or it doesn’t.

One thing is a little hazy here. We asserted that if a number and its negative are both greater than or equal to zero, then it must be zero itself. Why is this? Well if is a nonnegative Cauchy sequence representing then represents . Now can we find a nonnegative Cauchy sequence equivalent to ? The lowest rational number that can be is, of course, zero, and so . But for and to be equivalent we must have for each positive rational an so that for . But this just says that converges to !

So is an ordered field, so what does this tell us? First off, we get an absolute value just like we did for the rationals. Secondly, we’ll get a uniform structure as we do for any ordered group. This uniform topology has a subbase consisting of all the half-infinite intervals and for all real . But this is also a subbase for the metric we got from completing the rationals, and so the two topologies coincide!

One more very important thing holds for all ordered fields. As a field is a kind of a ring with unit, and like any ring with unit there is a unique ring homomorphism . Now since in any ordered field, we have , and , and so on, to show that no nonzero integer can become zero under this map. Since we have an injective homomorphism of rings, the universal property of the field of fractions gives us a unique field homomorphism extending the ring homomorphism from the integers.

Now if is complete in the uniform structure defined by its order, this homomorphism will be uniformly complete. Therefore by the universal property of uniform completions, we will find a unique extension . That is, given any (uniformly) complete ordered field there is a unique uniformly continuous homomorphism of fields from the real numbers to the field in question. Thus is the universal such field, which characterizes it uniquely up to isomorphism!

So we can unambiguously speak of “the” real numbers, even if we use a different method of constructing them, or even no method at all. We can work out the rest of the theory of real numbers from these properties (though for the first few we might fall back on our construction) just as we could work out the theory of natural numbers from the Peano axioms.

## The Topological Field of Real Numbers

We’ve defined the topological space we call the real number line as the completion of the rational numbers as a uniform space. But we want to be able to do things like arithmetic on it. That is, we want to put the structure of a field on this set. And because we’ve also got the structure of a topological space, we want the field operations to be continuous maps. Then we’ll have a topological field, or a “field object” (analogous to a group object) in the category of topological spaces.

Not only do we want the field operations to be continuous, we want them to agree with those on the rational numbers. And since is dense in (and similarly is dense in ), we will get unique continuous maps to extend our field operations. In fact the uniqueness is the easy part, due to the following general property of dense subsets.

Consider a topological space with a dense subset . Then every point has a sequence with . Now if and are two continuous functions which agree for every point in , then they agree for all points in . Indeed, picking a sequence in converging to we have

.

So if we can show the existence of a continuous extension of, say, addition of rational numbers to all real numbers, then the extension is unique. In fact, the continuity will be enough to tell us what the extension *should* look like. Let’s take real numbers and , and sequences of rational numbers and converging to and , respectively. We should have

but how do we know that the limit on the right exists? Well if we can show that the sequence is a Cauchy sequence of rational numbers, then it must converge because is complete.

Given a rational number we must show that there exists a natural number so that for all . But we know that there’s a number so that for , and a number so that for . Then we can choose to be the larger of and and find

So the sequence of sums is Cauchy, and thus converges.

What if we chose different sequences and converging to and ? Then we get another Cauchy sequence of rational numbers. To show that addition of real numbers is well-defined, we need to show that it’s equivalent to the sequence . So given a rational number does there exist an so that for all ? This is almost exactly the same as the above argument that each sequence is Cauchy! As such, I’ll leave it to you.

So we’ve got a continuous function taking two real numbers and giving back another one, and which agrees with addition of rational numbers. Does it define an Abelian group? The uniqueness property for functions defined on dense subspaces will come to our rescue! We can write down two functions from to defined by and . Since agrees with addition on rational numbers, and since triples of rational numbers are dense in the set of triples of real numbers, these two functions agree on a dense subset of their domains, and so must be equal. If we take the from as the additive identity we can also verify that it acts as an identity real number addition. We can also find the negative of a real number by negating each term of a Cauchy sequence converging to , and verify that this behaves as an additive inverse, and we can show this addition to be commutative, all using the same techniques as above. From here we’ll just write for the sum of real numbers and .

What about the multiplication? Again, we’ll want to choose rational sequences and converging to and , and define our function by

so it will be continuous and agree with rational number multiplication. Now we must show that for every rational number there is an so that for all . This will be a bit clearer if we start by noting that for each rational there is an so that for all . In particular, for sufficiently large we have , so the sequence is bounded above by some . Similarly, given we can pick so that for and get an upper bound for all . Then choosing to be the larger of and we will have

for . Now given a rational we can (with a little work) find and so that the expression on the right will be less than , and so the sequence is Cauchy, as desired.

Then, as for addition, it turns out that a similar proof will show that this definition doesn’t depend on the choice of sequences converging to and , so we get a multiplication. Again, we can use the density of the rational numbers to show that it’s associative and commutative, that serves as its unit, and that multiplication distributes over addition. We’ll just write for the product of real numbers and from here on.

To show that is a field we need a multiplicative inverse for each nonzero real number. That is, for each Cauchy sequence of rational numbers that doesn’t converge to , we would like to consider the sequence , but some of the might equal zero and thus throw us off. However, there can only be a finite number of zeroes in the sequence or else would be an accumulation point of the sequence and it would either converge to or fail to be Cauchy. So we can just change each of those to some nonzero rational number without breaking the Cauchy property or changing the real number it converges to. Then another argument similar to that for multiplication shows that this defines a function from the nonzero reals to themselves which acts as a multiplicative inverse.

## Another Carnival

The Secret Blogging Seminar is hosting the latest installment of the Carnival of Mathematics. They seem to have done a fair job of collecting links, with more (and more varied) entries than I remember seeing before. Enjoy.

## Miscellany

Well, yesterday was given over to exam-writing, so today I’ll pick up a few scraps I mentioned in passing on Thursday.

First of all, the rational numbers are countable. To be explicit, in case I haven’t been before, this means that there is an injective function from the set of rational numbers to the set of natural numbers. Really, I’ll just handle the positive rationals, but it’s straightforward how to include the negatives as well. To every positive rational number we can get a pair of natural numbers — the numerator and the denominator. Then we can send the pair to the number , which is a bijection between the set of all pairs of natural numbers and all natural numbers. Clearly they contain the natural numbers, so the set of rational numbers is countably infinite.

Now, equivalence relations. Given any relation on a set we can build it up into an equivalence relation. First throw in the diagonal to make it reflexive. Then throw in all the points for to make it symmetric. For transitivity, we can similarly start throwing elements into the relation until this condition is satisfied.

But that’s all sort of ugly. Here’s a more elegant way of doing it: given any relation , consider all the relations on that contain — . Some of these will be equivalence relations. In particular, the whole product is an equivalence relation, so there is at least one such. It’s simple to verify that the intersection of any family of equivalence relations on is again an equivalence relation, so we can take the intersection of *all* equivalence relations on containing to get the smallest such relation. Notice, by the way, how this is similar to generating a topology from a subbase, or to taking the closure of a subset in a topological space.

Finally, absolute values. In any totally ordered group we have the positive “cone” of all elements with . and the negative “cone” of all elements with . In the latter case, we can multiply both sides by the inverse of to get in the positive cone. Notice that the identity is in both cones, but the reflection described leaves it fixed. So for every element in we get a well-defined element called its absolute value. Of course, we often assume that is abelian and write this all additively instead of multiplicatively.

This function has a number of nice properties. First of all, is always in . Secondly, is the identity in if and only if itself is the identity. Thirdly, . And finally, if is abelian we have the “triangle inequality” .

Okay, does that catch us up?