Defining the Reals
There are a number of schemes for constructing the real numbers starting from set theory. The most common approaches involve constructing the rationals from the ordinal integers and then either forming Dedekind cuts or Cauchy sequences of rationals. But I recently came across an interesting (and fairly new) scheme that I had never seen before. And instead of going via the rationals it jumps straight from the integers to the reals in a simple and intuitive way.
Suppose you have been given the task of plotting a line with gradient m on a computer screen with square pixels. You are told that for each x position on the screen you need to illuminate exactly one pixel in that column. The picture above should illustrate the sort of thing I mean. You need to define a function f such that for each x you illuminate the pixel (x,f(x)). The problem is that different people will choose f differently. Some people might make f(x)=⌊mx⌋. Others might choose f(x)=⌈mx⌉. Some might round mx to the nearest integer giving various choices for what to do when mx is half an odd integer. As the task has only been specified in terms of a gradient, some people might choose to plot an approximation to y=mx+c for various values of c. All of these people will plot different sets of pixels.
But...there are two things that can be said about all of these schemes:
In other words, given real numbers m, these crudely specified and rendered plots are a fine enough tool to distinguish between real numbers, but they're not so fine that they distinguish more than the real numbers.
And this intuition gives a nice way to define the real numbers. The idea is to define an almost homomorphism on the integers. f is an almost homomorphism if f(x+y)-f(x)-f(y) is bounded. Clearly the almost-homomorphisms form a group. Amongst the almost homomorphisms are the functions that are themselves bounded. It's not hard to see that according to the scheme I describe above these correspond to a gradient of zero.
The reals are simply the group of almost homomorphisms modulo the bounded functions. That's it!
For more details and proofs see the paper by Arthan. My line plotting example is a modern rendering (no pun intended) of De Morgan's colonnade and fence example.
I first learnt about this from the Wikipedia and the image above was borrowed from the article on the Bresenham line drawing algorithm.
Suppose you have been given the task of plotting a line with gradient m on a computer screen with square pixels. You are told that for each x position on the screen you need to illuminate exactly one pixel in that column. The picture above should illustrate the sort of thing I mean. You need to define a function f such that for each x you illuminate the pixel (x,f(x)). The problem is that different people will choose f differently. Some people might make f(x)=⌊mx⌋. Others might choose f(x)=⌈mx⌉. Some might round mx to the nearest integer giving various choices for what to do when mx is half an odd integer. As the task has only been specified in terms of a gradient, some people might choose to plot an approximation to y=mx+c for various values of c. All of these people will plot different sets of pixels.
But...there are two things that can be said about all of these schemes:
- for a given m, two reasonable people's choice of the function f will have a bounded difference and
- if two different people are given different gradients then no matter what reasonable scheme they use there will come point, if you travel far enough along the x axis, the two different choices of f(x) will eventually become arbitrarily far apart.
In other words, given real numbers m, these crudely specified and rendered plots are a fine enough tool to distinguish between real numbers, but they're not so fine that they distinguish more than the real numbers.
And this intuition gives a nice way to define the real numbers. The idea is to define an almost homomorphism on the integers. f is an almost homomorphism if f(x+y)-f(x)-f(y) is bounded. Clearly the almost-homomorphisms form a group. Amongst the almost homomorphisms are the functions that are themselves bounded. It's not hard to see that according to the scheme I describe above these correspond to a gradient of zero.
The reals are simply the group of almost homomorphisms modulo the bounded functions. That's it!
For more details and proofs see the paper by Arthan. My line plotting example is a modern rendering (no pun intended) of De Morgan's colonnade and fence example.
I first learnt about this from the Wikipedia and the image above was borrowed from the article on the Bresenham line drawing algorithm.
Labels: mathematics
posted by sigfpe at Friday, May 26, 2006
4 Comments:
If you don't mind, I'd like to think out loud a bit about other directions of generalization, possibly already pursued elsewhere.
This paper considers the space of "almost homomorphisms" of the \Z-module (i.e. ab gp) \Z; given an arbitrary ring R, it seems that we might be interested in the almost homomorphisms of R _as an R module_.
Well, why? Because vital to this argument is that \Z is naturally isomorphic to the space of homomorphisms of \Z: any homo f:\Z\to\Z is uniquely determined by f(1), which can take any value. In a general ab gp, this is not the case --- the space of \Z-endomorphisms of \Z^2 is not even commutative (it is the space of 2x2 \Z-matrices). But it is true that the space of R-endos of R is naturally isomorphic to R, again by identifying f with its value at 1. And, moreover, composition is naturally identified with multiplication.
So, great. But what would an R-almost-endo look like? Because we certainly want R-almost-endos. If we take the space of \Z-almost-endos of, say, R=\Z[i], then we cannot expect to get something small and commuting, whereas we expect the relationship between \Z and \R to be reflected by the relationship of \Z[i] to \C. The point of an R-homo is that not only does f(p+q)=f(p)+f(q), but f(mp)=mf(p). An R-almost-homo (which I think I'll start writing as an R-almo, short for "almomorphism", and it will be clear from context if I'm talking about almost endos (R-almo of A) or almost homos (R-almo from A to B)) has a bounded error in the first property, but I think that we cannot expect simply a bounded error in the second. Certainly the best bounds in the \Z case (as described in the paper) for f(mp) is that f(mp)-mf(p) < (m-1)C, where C is the bound on f(p+q)-f(p)-f(q), and m is a nonnegative integer. And, indeed, if we expected f(mp)-mf(p) to be bounded, then f(p) could be only boundedly far from pf(1), and modding by bounded functions reduces us back to \Z, rather than getting a construction of the reals.
No, we need something more flexible for f(mp). But what? Bounds don't work --- I want to extend to rings with measures, not rings with orders. Perhaps the best we can do is to say that, for any given m, the difference d^m_f (p) = f(mp)-mf(p) is bounded as p ranges, where the bound depends on m? It would be nice to make the bound linear in m --- no, almost linear. Perhaps, then, we want to say this: the volume of the range of d^m_f is bounded by some \Z-almo C(m) from R to \Z. Yes, perhaps that's it.
Oh, another thing concerns me. Vital to the embedding of \Z into \R in this construction was that, when modding out by bounded almos, we didn't kill any genuine homos. Can we be sure of that here? Well, say R is infinite (otherwise, naively, all almos are bounded, unless we use a different measure, but let's cross that bridge later). Then if f_c:p\mapsto cp is has finite range, then pigeonhole guarantees infinitely many p s.t. cp=0. We fix our problems if we demand that R is a domain --- if it isn't, the probably we have no right to expect R to embed into some continuum limit of R, because this continuum limit really is a continuum limit of the field of fractions of R. (You say you want the space of slopes of almost-lines --- an important subclass of almost-lines are those with rational slopes.)
Anyway, looking at \Z[i], certainly any almo of \Z extends to an almo of \Z[i] by f(p+iq)=f(p)+if(q). So \E(\Z[i]) certainly contains \R[i]=\C. (Naturally, \E(R) is the R-module of R-almos of R modulo boundeds.) Showing that that's all there is will take more time than I have tonight --- I'd like to show that \E(R) is always a ring (so an R-algebra, and, if R is a domain, a ring extension of R), and then perhaps that \E(R) is in fact a field, but doing so will require getting multiplication to work.
Going further, I'd be curious to know what happens with other measures. For instance, there are very few interesting measures on finite rings --- I could imagine endowing 0 with finite measure and all other points with measure \infty, in which case almos are required to be genuine homos. But other directions are also possible.
Hmm.
Or maybe the point is that I need a generalized-to-arbitrary-ring idea of "measure".
There is a FOM post at http://www.cs.nyu.edu/pipermail/fom/2003-August/007128.html
about generalizing this construction.
>I'd like to show that \E(R) is always a ring
If you start with an abelian group and replace "bounded" by "finite" in the definition of almost homomorphisms and the equivalence relation, the analogous construction always gives a ring. The IsarMathLib project (http://www.nongnu.org/isarmathlib/) has a formal verification of this fact.
I found it very interesting that the construction of the reals can be done in any topos, and then Cauchy's and Dedekind's way give different results (that's in "Elementary Categories, Elementary Toposes" you're consuming).
I guess this construction can also be done in any topos and gives Cauchy reals, there is an obvious sequence of rationals lurking behind these grid-points.
So, while this method of not mentioning rationals is nice and doesn't feel unnatural, it might be provable that this construction is essentially(?) the same as Cauchy's.
Post a Comment
<< Home