The Unapologetic Mathematician

Mathematics for the interested outsider

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!

December 15, 2007 Posted by | Uncategorized | 1 Comment

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 (a,b) — as a series circuit, and the collection of all possible paths is a giant parallel circuit. If a given path has length n it passes through n resistors, and so its total resistance is n. Thus we need to form the sum over all paths

\displaystyle\sum\limits_{\gamma}\frac{1}{\mathrm{length}(\gamma)}=\sum\limits_{n=0}^\infty\frac{\#\{\mathrm{length}(\gamma)=n\}}{n}

and take the reciprocal of this sum. So we’ve got a combinatorial problem: how many lattice paths \gamma have length n and go from the origin to (a,b)? Let’s call this number G_{a,b,n} and build the “exponential generating function”

\displaystyle\Gamma_{a,b}(t)=\sum\limits_{n=0}^\infty\frac{G_{a,b,n}}{n!}t^n

We choose the exponential generating function here rather than the ordinary generating function \sum G_{a,b,n}t^n because of a manipulation we want to do later that looks nicer for exponential generating functions. We’ll go from \Gamma_{a,b} to our desired sum a little later.

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

\displaystyle\Upsilon_a(t)=\sum\limits_{k=0}^\infty\frac{U_{a,2k+a}}{(2k+a)!}t^{2k+a}=\sum\limits_{k=0}^\infty\binom{2k+a}{k}\frac{1}{(2k+a)!}t^{2k+a}=i^{-a}J_a(2it)

where J_a(x) 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 n steps up into chunks of n_1 and n_2 steps, respectively, put a one-dimensional path on the n_1 chunk ending at a, and put a one-dimensional path on the n_2 chunk ending at b. And it turns out that generating functions are perfect for handling this!

\displaystyle\Gamma_{a,b}(t)=\sum\limits_{n=0}^\infty \frac{G_{a,b,n}}{n!}t^n=\sum\limits_{n=0}^\infty \left(\sum\limits_{n_1+n_2=n}\binom{n}{n_1}U_{a,n_1}U_{b,n_2}\right)\frac{t^n}{n!}=
\displaystyle\sum\limits_{n=0}^\infty\sum\limits_{n_1+n_2=n}\frac{U_{a,n_1}}{n_1!}\frac{U_{b,n_2}}{n_2!}t^{n_1+n_2}=\sum\limits_{n_1=0}^\infty\frac{U_{a,n_1}}{n_1!}t^{n_1}\sum\limits_{n_2=0}^\infty\frac{U_{b,n_2}}{n_2!}t^{n_2}=
\displaystyle\Upsilon_a(t)\Upsilon_b(t)=i^{-a-b}J_a(2it)J_b(2it)

This tells us how to find the number G_{a,b,n} of paths of length n that end at (a,b) — it’s just the nth derivative of this power series, evaluated at t=0. That is

\displaystyle G_{a,b,n}=\frac{d^n}{dt^n}\left(i^{-a-b}J_a(2it)J_b(2it)\right)

Now let’s consider the ordinary generating function for G_{a,b,n}:

\displaystyle\sum\limits_{n=0}^\infty G_{a,b,n}t^n

Here the coefficient of t^n is the number of paths of length n (and thus with resistance n) from the origin to (a,b). What we want to calculate is the sum \sum\frac{G_{a,b,n}}{n}. To get at this, we’ll divide our power series by t and then integrate with respect to t. This will give the series \sum\frac{G_{a,b,n}}{n}t^n, which we can then evaluate at t=1. 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 t 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…

December 14, 2007 Posted by | Uncategorized | 4 Comments

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 M and a function d:M\times M\rightarrow\mathbb{R}, which assigns a real number to every pair of points in M. This function will satisfy the following axioms:

  • For all x,y\in M, d(x,y)\geq0.
  • For all x,y\in M, d(x,y)=0 if and only if x=y.
  • For all x,y\in M, d(x,y)=d(y,x).
  • For all x,y,z\in M, d(x,z)\leq d(x,y)+d(y,z).

The first says that distances are all nonnegative real numbers. The second says that any point is distance {0} 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 x to z along the leg connecting those two than to take the detour to y.

Notice that these properties line up with those of absolute values. That is, the function d:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R} defined by d(x,y)=\left|x-y\right| will be a distance function on \mathbb{R}.

Now any metric space is actually a uniform space. We define an entourage E_\delta for each positive real number \delta>0. This E_\delta consists of all the pairs (x,y)\in M\times M with d(x,y)<\delta. Since d(x,x)=0 each of these will contain the diagonal. The intersection E_\delta\cap E_{\delta'} is the entourage corresponding to the smaller of \delta and \delta'. Each E_\delta is its own reflection by the symmetry of the distance function. And the triangle inequality gives our half-size entourages — if (x,y)\in E_{\frac{\delta}{2}} and (y,z)\in E_{\frac{\delta}{2}} then (x,z)\in E_\delta.

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 E_r for each positive r\in\mathbb{Q}, with E_r=\{(x,y)\in\mathbb{R}\times\mathbb{R}|\left|x-y\right|^lt;r. Each one of these shows up in the entourages for the metric structure, by considering r 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 \delta we can find a positive rational number r<\delta. Then E_r\subseteq E_\delta, and so E_\delta 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 U is a neighborhood of x if and only if it contains E_\delta\left[x\right] for some \delta>0. That is, it must contain the “open ball” of all y\in X such that \left|x-y\right|<\delta.

In \mathbb{R} this means that we have a neighborhood base for each point x consisting of the intervals (x-\delta,x+\delta)=\{y\in\mathbb{R}|\left|x-y\right|<\delta\}. Thus a subset U of \mathbb{R} 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 U is the union of a collection of open intervals. Then we can take the intervals (a,b)=\{x\in\mathbb{R}|a<x<b\} as a base for our topology.

As a final coup de grâce, let’s write down explicitly the condition that a function f:\mathbb{R}\rightarrow\mathbb{R} 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 f will be continuous at x if and only if for each neighborhood V\in\mathcal{N}(f(x)) there is a neighborhood U\in\mathcal{N}(x) with f(U)\subseteq V. Translating this all into our explicit language for the real numbers and restricting to neighborhood bases says that a function f is continuous at x if and only if for each \epsilon>0 there is a \delta>0 so that \left|x-y\right|<\delta implies \left|f(x)-f(y)\right|<\epsilon. And we’re back to the old definition of continuity from calculus 1! Then, as usual, we say that f is continuous if the above condition holds for all x\in\mathbb{R}.

What about uniform continuity. We can again translate the statements to our special case and check them on the basic entourages. A function f:\mathbb{R}\rightarrow\mathbb{R} will be uniformly continuous if for every \epsilon>0 there is a \delta>0 so that for all x,y\in\mathbb{R}, \left|x-y\right|<\delta implies that \left|f(x)-f(y)\right|<\epsilon.

Notice particularly the difference between uniform continuity and continuity. Continuity says that (for all x\in\mathbb{R}) (for all \epsilon>0 there exists a \delta>0) such that (\left|x-y\right|<\delta implies \left|f(x)-f(y)\right|<\epsilon). Uniform continuity says that (for all \epsilon>0 there exists a \delta>0) such that (for all x\in\mathbb{R}) (\left|x-y\right|<\delta implies \left|f(x)-f(y)\right|<\epsilon). The quantifier for x shows up after the quantifier for \delta in the latter definition. That is, for a uniformly continuous function we can pick the \delta uniformly to apply to all points x, while for a merely continuous function we may have to use a different \delta for each point x. 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 \delta 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 X and Y by just using the local definitions of “distance” in place of that for \mathbb{R}. A function f:X\rightarrow Y is continuous if for all x\in X and \epsilon>0 there is a \delta>0 so that d_X(x,y)<\delta implies d_Y(f(x),f(y))<\epsilon. Similarly, f is uniformly continuous if for all \epsilon>0 there is a \delta>0 so that for all x\in X d_X(x,y)<\delta implies d_Y(f(x),f(y))<\epsilon.

December 10, 2007 Posted by | Topology | 16 Comments

Archimedean Fields

Whether we use Dedekind cuts or Cauchy sequences to construct the ordered field of real numbers \mathbb{R} (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 \mathbb{R}, 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 x — even as small as the volume of a grain of sand — and another positive real number y — even as large as the volume of (the ancient Greek conception of) the universe — there’s some natural number n so that nx\geq y. When this happens in a given ordered field we say that the field is “Archimedean”.

So let’s show that \mathbb{R} is Archimedean. If there were positive real numbers x and y so that nx\leq y for all natural numbers n, then y would be an upper bound for the set of nx. Then Dedekind completeness gives us a least upper bound \sup\{nx\}, and we can just take y to be this least upper bound. Now nx\leq y, and also (n+1)x\leq y, and so nx\leq y-x. That is, y-x is another upper bound for the set of multiples of x. But since x was chosen to be positive we see that y-x<y, contradicting the assumption that y 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 x and consider the set of natural numbers n which are larger than it. Since the natural numbers are well-ordered, there is a least such number, and it can’t be {0} because we assume x>0. Subtracting one from this number will then give the largest natural number that is still below x in the real number order, and we denote this number by \lfloor x\rfloor. We can thus write any positive number uniquely as the sum \lfloor x\rfloor+r of a natural number and some remainder with 0\leq r<1.

It turns out that the real numbers are actually the largest Archimedean field. That is, if \mathbb{F} is any ordered field satisfying the Archimedean property, there will be an monomorphism of ordered fields \mathbb{F}\rightarrow\mathbb{R}, making (the image of) \mathbb{F} a subfield of \mathbb{R}. 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.

December 7, 2007 Posted by | Fundamentals, Numbers | 7 Comments

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 x represented by a Cauchy sequence x_n it’s easy to come up with a cut. Given a rational number q we use the constant sequence q_n=q and compare it to x_n. If x_n-q_n is eventually nonnegative then q is less than x$, and should go into the left set X_L. On the other hand, if it’s eventually nonpositive then q is greater than x and should go into the right set X_R. It’s straightforward to show that this function from \mathbb{R} to the set of cuts preserves the order.

Now let’s start with the cut (X_L,X_R) and write down a Cauchy sequence. Pick some x_L\in X_L and x_R\in X_R, and construct the sequence as follows. First write down x_0=x_L and x_1=x_R. Now set x_2=\frac{x_L+x_R}{2}. This value will either be in X_L or it won’t. If it is, replace x_L by x_2, and otherwise replace x_R by x_2. Then define x_3 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 x_L and x_R 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 x_L and x_R 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 X_L are moving steadily upwards towards the cut, and those in X_R are moving steadily downwards towards it. Eventually, the sequence will rise above any point in X_L and fall below any point in X_R, 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 x_n and y_n, which give right sets X_R and Y_R of rational numbers, then what’s the right set of the sequence x_n+y_n? It’s the set of rational numbers q so that x_n+y_n-q is eventually nonnegative. But any such q can be broken up as q=q_x+q_y, where x_n-q_x and y_n-q_y are both eventually nonnegative. That is, (X+Y)_R is the set of sums of elements of X_R and Y_R, 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.

December 7, 2007 Posted by | Fundamentals, Numbers | 1 Comment

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 \mathbb{Q}, 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 S the least upper bound or “supremum” \sup S is a rational number so that \sup S\geq s for all s\in S — it’s an upper bound — and if b is any upper bound then \sup S\leq b. Similarly the “infimum” \inf S 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 r so that r^2\leq 2 is bounded above, since 2 is an example of an upper bound, and \frac{3}{2} 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 \sqrt{2}, but this isn’t a rational number!

Now we define an ordered field to be “Dedekind complete” if every nonempty set S with an upper bound has a least upper bound \sup S. Considering the set consisting of the negatives of elements of S, 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 S with any upper bounds at all, the collection of all the upper bounds forms another set S', and any element of S gives a lower bound for S'. We then have the collection of all lower bounds of S', which we call S''. Every rational number will be in either S' or S''. Given a rational number r if there is an s\in S with s\geq r then r is a lower bound for S', and is thus in S''. If not, then r is an upper bound for S and is thus in S'. However, one number may be in both S' and S''. If S has a rational supremum then it is in both S' and S''. There can be no more overlap.

So we’ve come up with a way of cutting the rational numbers into a pair of sets (X_L,X_R) — the “left set” and “right set” of the “cut” X — with x_L\geq x_R for every x_L\in X_L and x_R\in x_R. We define a new total order on the set of cuts by (X_L,X_R)\leq(Y_L,Y_R) if X_L\subseteq Y_L. 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 (X^\alpha_L,X^\alpha_R) with an upper bound (in the order on the set of cuts) we can take the union of all the X^\alpha_L and the intersection of all the X^\alpha_R to get a new cut. The left set contains all the X^\alpha_L, 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 X_L by x_L, and assume x_L runs over all elements of X_L wherever it appears. For instance, given cuts (X_L,X_R) and (Y_L,Y_R), we define their sum to be (\{x_L+y_L\},\{x_R+y_R\}). The negative of a cut (X_L,X_R) will be (\{-x_R\},\{-x_L\}). The product of two positive cuts (X_L,X_R) and (Y_L,Y_R) will have as its right set the collection of all products \{x_Ry_R\}, and its left set defined to make this a cut. Finally, the reciprocal of a positive cut (X_L,X_R) will have the set \{\frac{1}{x_R}\} 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 \mathbb{Q} we get another model of \mathbb{R}. 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.

December 5, 2007 Posted by | Fundamentals, Numbers, Orders | 11 Comments

The Order on the Real Numbers

We’ve defined the real numbers \mathbb{R} as a topological field by completing the rational numbers \mathbb{Q} 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 \mathbb{R} into an ordered field.

First off, we can simplify our work greatly by recognizing that we just need to determine the subset \mathbb{R}^+ of positive real numbers — those x\in\mathbb{R} with x\geq0. Then we can say x\geq y if x-y\geq0. Now, each real number is represented by a Cauchy sequence of rational numbers, and so we say x\geq0 if x has a representative sequence x_n with each point x_n\geq 0.

What we need to check is that the positive numbers are closed under both addition and multiplication. But clearly if we pick x_n and y_n to be nonnegative Cauchy sequences representing x and y, respectively, then x+y is represented by x_n+y_n and xy is represented by x_ny_n, and these will be nonnegative since \mathbb{Q} is an ordered field.

Now for each x, x-x=0\geq0, so x\geq x. Also, if x\geq y and y\geq z, then x-y\geq0 and y-z\geq0, so x-z=(x-y)+(y-z)\geq0, and so x\geq z. These show that \geq defines a preorder on \mathbb{R}, since it is reflexive and transitive. Further, if x\geq y and y\geq x then x-y\geq0 and y-x\geq0, so x-y=0 and thus x=y. This shows that \geq 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 x_n is a nonnegative Cauchy sequence representing x then -x_n represents -x. Now can we find a nonnegative Cauchy sequence y_n equivalent to -x_n? The lowest rational number that y_n can be is, of course, zero, and so \left|y_n-(-x_n)\right|\geq x_n. But for -x_n and y_n to be equivalent we must have for each positive rational r an N so that r\geq\left|y_n-(-x_n)\right|\geq x_n for n\geq N. But this just says that x_n converges to {0}!

So \mathbb{R} is an ordered field, so what does this tell us? First off, we get an absolute value \left|x\right| 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 (x,\infty) and (-\infty,x) for all real x. 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 \mathbb{F} is a kind of a ring with unit, and like any ring with unit there is a unique ring homomorphism \mathbb{Z}\rightarrow\mathbb{F}. Now since 1gt;0 in any ordered field, we have 2=1+1>0, and 3=2+1>0, 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 \mathbb{Q}\rightarrow\mathbb{F} extending the ring homomorphism from the integers.

Now if \mathbb{F} 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 \mathbb{R}\rightarrow\mathbb{F}. 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 \mathbb{R} 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.

December 4, 2007 Posted by | Fundamentals, Numbers, Point-Set Topology, Topology | 3 Comments

The Topological Field of Real Numbers

We’ve defined the topological space we call the real number line \mathbb{R} as the completion of the rational numbers \mathbb{Q} 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 \mathbf{Top} 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 \mathbb{Q} is dense in \mathbb{R} (and similarly \mathbb{Q}\times\mathbb{Q} is dense in \mathbb{R}\times\mathbb{R}), 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 X with a dense subset D\subseteq X. Then every point x\in X has a sequence x_n\in D with \lim x_n=x. Now if f:X\rightarrow Y and g:X\rightarrow Y are two continuous functions which agree for every point in D, then they agree for all points in X. Indeed, picking a sequence in D converging to x we have
f(x)=f(\lim x_n)=\lim f(x_n)=\lim g(x_n)=g(\lim x_n)=g(x).

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 x and y, and sequences of rational numbers x_n and y_n converging to x and y, respectively. We should have
s(x,y)=s(\lim x_n,\lim y_n)=s(\lim(x_n,y_n))=\lim x_n+y_n
but how do we know that the limit on the right exists? Well if we can show that the sequence x_n+y_n is a Cauchy sequence of rational numbers, then it must converge because \mathbb{R} is complete.

Given a rational number r we must show that there exists a natural number N so that \left|(x_m+y_m)-(x_n+y_n)\right|<r for all m,n\geq N. But we know that there’s a number N_x so that \left|x_m-x_n\right|<\frac{r}{2} for m,n\geq N_x, and a number N_y so that \left|y_m-y_n\right|<\frac{r}{2} for m,n\geq N_y. Then we can choose N to be the larger of N_x and N_y and find
\left|(x_m-x_n)+(y_m-y_n)\right|\leq\left|x_m-x_n\right|+\left|y_m-y_n\right|<\frac{r}{2}+\frac{r}{2}=r
So the sequence of sums is Cauchy, and thus converges.

What if we chose different sequences x'_n and y'_n converging to x and y? Then we get another Cauchy sequence x'_n+y'_n of rational numbers. To show that addition of real numbers is well-defined, we need to show that it’s equivalent to the sequence x_n+y_n. So given a rational number r does there exist an N so that \left|(x_n+y_n)-(x'_n+y'_n)\right|<r for all n\geq N? 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 \mathbb{R}\times\mathbb{R}\times\mathbb{R} to \mathbb{R} defined by s(s(x,y),z) and s(x,s(y,z)). Since s 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 {0} from \mathbb{Q} 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 x by negating each term of a Cauchy sequence converging to x, 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 x+y for the sum of real numbers x and y.

What about the multiplication? Again, we’ll want to choose rational sequences x_n and y_n converging to x and y, and define our function by
m(x,y)=m(\lim x_n,\lim y_n)=m(\lim(x_n,y_n))=\lim x_ny_n
so it will be continuous and agree with rational number multiplication. Now we must show that for every rational number r there is an N so that \left|x_my_m-x_ny_n\right|<r for all m,n\geq N. This will be a bit clearer if we start by noting that for each rational r_x there is an N_x so that \left|x_m-x_n\right|<r_x for all m,n\geq N_x. In particular, for sufficiently large n we have \left|x_n\right|<\left|x_N\right|+r_x, so the sequence x_n is bounded above by some b_x. Similarly, given r_y we can pick N_y so that \left|y_m-y_n\right|<r_y for m,n\geq N_y and get an upper bound b_y\geq y_n for all n. Then choosing N to be the larger of N_x and N_y we will have
\left|x_my_m-x_ny_n\right|=\left|(x_m-x_n)y_m+x_n(y_m-y_n)\right|\leq r_xb_y+b_xr_y
for m,n\geq N. Now given a rational r we can (with a little work) find r_x and r_y so that the expression on the right will be less than r, 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 x and y, so we get a multiplication. Again, we can use the density of the rational numbers to show that it’s associative and commutative, that 1\in\mathbb{Q} serves as its unit, and that multiplication distributes over addition. We’ll just write xy for the product of real numbers x and y from here on.

To show that \mathbb{R} is a field we need a multiplicative inverse for each nonzero real number. That is, for each Cauchy sequence of rational numbers x_n that doesn’t converge to {0}, we would like to consider the sequence \frac{1}{x_n}, but some of the x_n might equal zero and thus throw us off. However, there can only be a finite number of zeroes in the sequence or else {0} would be an accumulation point of the sequence and it would either converge to {0} 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.

December 3, 2007 Posted by | Fundamentals, Numbers, Point-Set Topology, Topology | 13 Comments

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.

December 2, 2007 Posted by | Uncategorized | 3 Comments

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 (m,n) to the number \frac{(m+n)(m+n+1)}{2}+n, 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 R\subseteq X\times X on a set X we can build it up into an equivalence relation. First throw in the diagonal \{(x,x)|x\in X\} to make it reflexive. Then throw in all the points (y,x) for xRy 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 R\subseteq X\times X, consider all the relations S on X that contain R — R\subseteq S\subseteq X\times X. Some of these S will be equivalence relations. In particular, the whole product X\times X 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 X is again an equivalence relation, so we can take the intersection of all equivalence relations on X containing R 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” G^+ of all elements g\in G with g\geq1. and the negative “cone” G^- of all elements g\in G with 1\geq g. In the latter case, we can multiply both sides by the inverse of g to get g^{-1}\geq1 in the positive cone. Notice that the identity 1 is in both cones, but the reflection described leaves it fixed. So for every element in g\in G we get a well-defined element \left|g\right|\in G^+ called its absolute value. Of course, we often assume that G is abelian and write this all additively instead of multiplicatively.

This function has a number of nice properties. First of all, \left|g\right| is always in G^+. Secondly, \left|g\right| is the identity in G if and only if g itself is the identity. Thirdly, \left|g\right|=\left|g^{-1}\right|. And finally, if G is abelian we have the “triangle inequality” \left|a+b\right|\leq\left|a\right|+\left|b\right|.

Okay, does that catch us up?

December 1, 2007 Posted by | Fundamentals, Orders | Leave a Comment

    Next Entries »

Follow

Get every new post delivered to your Inbox.

Join 217 other followers