Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

September 22, 2023

Constructing the Real Numbers as Nearly Multiplicative Sequences

Posted by Emily Riehl

I’m in Regensburg this week attending a workshop on Interactions of Proof Assistants and Mathematics. One of the lecture series is being given by John Harrison, a Senior Principal Applied Scientist in the Automated Reasoning Group at Amazon Web Services, and a lead developer of the HOL Light interactive theorem prover. He just told us about a very cool construction of the non-negative real numbers as sequences of natural numbers satisfying a property he calls “near multiplicativity”. In particular, the integers and the rational numbers aren’t needed at all! This is how the reals are constructed in HOL Light and is described in more detail in a book he wrote entitled Theorem Proving with the Real Numbers.

Edit: as the commenters note, these are also known as the Eudoxus reals and were apparently discovered by our very own Stephen Schanuel and disseminated by Ross Street. Thanks for pointing me to the history of this construction!

The idea

One of the standard constructions of the real numbers is as equivalence classes of Cauchy sequences of rationals. Let us consider a non-negative real number aa. One way to say that a sequence q:q \colon \mathbb{N} \to \mathbb{Q} of rational numbers converges to aa is to ask there to exist a constant AA \in \mathbb{N} so that for all nn \in \mathbb{N},

|q na|An.|q_n - a | \le \frac{A}{n}.

These representations aren’t at all unique: many Cauchy sequences of rationals represent the same real number. And in particular, for any positive real number aa, it is possible to find a sequence of natural numbers a:a \colon \mathbb{N} \to \mathbb{N} so that the sequence na nnn \mapsto \frac{a_n}{n} converges to aa in the above sense, i.e.:

|a nna|An|\frac{a_n}{n} - a | \le \frac{A}{n}

or equivalently

|a nna|A.|a_n - n \cdot a | \le A.

This sequence a:a \colon \mathbb{N} \to \mathbb{N} will encode the real number aa (which is why I’ve given them the same name).

The construction

Now that I’ve explained the idea let’s try to characterize the sequences of natural numbers that will correspond to non-negative real numbers without presupposing the existence of non-negative real numbers. The idea is that a sequence a:a \colon \mathbb{N} \to \mathbb{N} will have the property that the sequence na nnn \mapsto \frac{a_n}{n} encodes some non-negative real number just when this sequence is Cauchy, which we express in the following way: there exists a constant AA \in \mathbb{N} so that for all n,mn,m \in \mathbb{N},

|a nna mm|An+Am,|\frac{a_n}{n} - \frac{a_m}{m} | \le \frac{A}{n} + \frac{A}{m},

or equivalently by

|ma nna m|(m+n)A.|m \cdot {a_n} - n \cdot {a_m} | \le (m + n) \cdot A.

Such sequences are called nearly multiplicative. Supposedly this is equivalent to the property of a sequence being nearly additive, meaning there exists a constant AA' \in \mathbb{N} so that for all m,nm,n \in \mathbb{N}

|a m+n(a m+a n)|A.|a_{m+n} - (a_m + a_n)| \le A'.

The non-negative reals are then equivalence classes of nearly multiplicative sequences of natural numbers, where the equivalence relation says that a,a:a, a' \colon \mathbb{N} \to \mathbb{N} represent the same real number when there exists CC \in \mathbb{N} so that for all nn \in \mathbb{N}

|a na n|C.|a_n - a'_n | \le C.

This is more or less the usual equivalence relation of Cauchy sequences, except with a specified rate of convergence.

Addition and multiplication

Now that we have the non-negative reals, how do we add and how do we multiply?

Given nearly multiplicative sequences a:a \colon \mathbb{N} \to \mathbb{N} and b:b \colon \mathbb{N} \to \mathbb{N}, their sum a+b:a + b \colon \mathbb{N} \to \mathbb{N} is defined by pointwise addition: (a+b) n:=a n+b n(a+b)_n := a_n + b_n. This is fairly intuitive.

More interestingly, their product ab:a \cdot b \colon \mathbb{N} \to \mathbb{N} is defined by function composition: (ab) n:=a b n(a \cdot b)_n := a_{b_n}. It’s a fun exercise to work out that this converges to the desired non-negative real number.

Posted at September 22, 2023 8:37 AM UTC

TrackBack URL for this Entry:

11 Comments & 0 Trackbacks

Re: Constructing the real numbers as nearly multiplicative sequences

I think these are the Eudoxus reals.

Posted by: Theo Johnson-Freyd on September 22, 2023 12:15 PM | Permalink | Reply to this

Re: Constructing the real numbers as nearly multiplicative sequences

Indeed they are, and as the corresponding nLab page shows, this is a topic well-treated by categorists (though sadly the link to the relevant discussion on the categories mailing list appears to be dead). Harrison on page 23 of his book attributes this construction to Steve Schanuel, who taught it to Ross Street, from whom I learned it. (I include this last link because it is missing from that nLab page.)

Posted by: Alexander Campbell on September 22, 2023 12:40 PM | Permalink | Reply to this

Re: Constructing the real numbers as nearly multiplicative sequences

Arthan 2004, The Eudoxus Real Numbers, says that John Harrison learned of Schanuel’s construction and used a variant in his 1996 thesis. The backmatter to his thesis book is online and I see no cites to Schanuel or Ross.

Maybe Harrison is in some sense claiming primacy because his thesis variant doesn’t have the completeness problems of Ross’s 1985 presentation which weren’t fixed until the early 2000s.

Posted by: RodMcGuire on September 22, 2023 8:33 PM | Permalink | Reply to this

Re: Constructing the real numbers as nearly multiplicative sequences

I was familiar with the works of Schanuel, Street et al. on the Eudoxus reals, but there’s something in Emily’s post that was new to me. Whereas Schanuel and company construct the reals from the integers —

\mathbb{Z} \mapsto \mathbb{R}

— what Emily describes is a construction of the nonnegative reals from the nonnegative integers —

+. \mathbb{N} \mapsto \mathbb{R}^+.

If you know about the first construction, it’s clear how the second construction works. Nevertheless, it got me wondering whether there’s more juice to be squeezed out of the fundamental idea.

Start with any commutative monoid (M,+,0)(M, +, 0), which could be \mathbb{Z}, \mathbb{N}, or something else. Suppose we also have a bornology on the monoid MM, by which I mean a collection of subsets called “bounded”, closed under taking subsets and finite unions, translation invariant, and including {0}\{0\}. It’s an order-ideal in the power set of MM, compatible with the monoid structure. We’ll probably also need to know that if BB and BB' are bounded then so is {b+b:bB,bB}\{b + b': b \in B, b' \in B'\}, so throw that in as another axiom if it doesn’t follow from the others.

I think this data is enough to imitate the Schanuel/Eudoxus construction, with the caveat that I might not have got quite the appropriate bornology axioms. Define an approximate endomorphism of MM to be a map of sets f:MMf: M \to M with the following property: there is some bounded set BMB \subseteq M such that for all x,yMx, y \in M, there exist b,bBb, b' \in B satisfying

f(x+y)+b=f(x)+f(y)+b. f(x + y) + b = f(x) + f(y) + b'.

Say that two approximate endomorphisms ff and gg are equivalent if there is some bounded set BB such that for all xMx \in M, there exist b,bBb, b' \in B satisfying

f(x)+b=g(x)+b. f(x) + b = g(x) + b'.

Then with luck, we can define a rig/semiring of equivalence classes of approximate endomorphisms. When M=M = \mathbb{Z}, this rig should be \mathbb{R}. So the construction generalizes Schanuel’s construction of \mathbb{R} from \mathbb{Z}.

(I hesitate here. I had to phrase both these displayed equations without using subtraction, since MM is a mere monoid. Is what I’m doing equivalent to passing to the group completion AA of MM and using a bornology on AA? And did I implicitly assume that MM is cancellative? In any case, I hope the idea is clear.)

Questions: does this work? Under what conditions is the multiplication on the rig (which is composition of approximate endomorphisms) commutative? And, most of all, are there any interesting examples apart from \mathbb{Z} and \mathbb{N}?

Posted by: Tom Leinster on September 23, 2023 2:50 PM | Permalink | Reply to this

Re: Constructing the real numbers as nearly multiplicative sequences

I wonder whether there’s also a higher level of abstraction at which to study this.

We know how to apply the “approximate endomorphism” construction to the monoid \mathbb{N} and the group \mathbb{Z}. Also, for an arbitrary metric space XX, one can take the monoid of equivalence classes of approximate endomorphisms of XX, using the usual notion of boundedness. I guess the same construction works for general bornological sets, i.e. sets equipped with a bornology.

Is there a unified theory that includes all these constructions? Maybe it would involve bornologies compatible with an algebraic structure. Has this been explored? Are we in the territory of coarse geometry here?

Posted by: Tom Leinster on September 23, 2023 3:10 PM | Permalink | Reply to this

Re: Constructing the real numbers as nearly multiplicative sequences

All right, I think the following works.

Take a finitely generated abelian group AA. If we choose a finite set of generators then we obtain a metric on AA, the distance between two points being the length of the shortest path between them on the Cayley graph. That is, if aba - b can be expressed as λ 1x 1++λ nx n\lambda_1 x_1 + \cdots + \lambda_n x_n, where the λ i\lambda_i are integers and the x ix_i are generators, then d(a,b)d(a, b) is at most |λ i|\sum |\lambda_i| — “at most” because d(a,b)d(a, b) is the infimum over all such ways of expressing aba - b as a combination of generators.

This gives a notion of what it means for a subset of AA to be bounded. Although the metric itself depends on the choice of generators, I think the notion of boundedness does not. It’s intrinsic to the group AA.

We can now say what it means for a map of sets f:AAf: A \to A to be an approximate endomorphism ({f(a+b)f(a)f(b):a,bA}\{f(a + b) - f(a) - f(b): a, b \in A\} is bounded) and for two approximate homomorphisms f,g:AAf, g: A \to A to be equivalent ({f(a)g(a):aA}\{f(a) - g(a): a \in A\} is bounded). And I believe the equivalence classes of approximate endomorphisms of AA form a ring, under pointwise addition and composition.

When A=A = \mathbb{Z}, this construction should give \mathbb{R}. When A= nA = \mathbb{Z}^n, I guess we get the ring End( n)End(\mathbb{R}^n) of linear endomorphisms of n\mathbb{R}^n, or equivalently, the ring of n×nn \times n real matrices.

Of course, there aren’t many finitely generated abelian groups! Every finitely generated abelian group can be expressed as nB\mathbb{Z}^n \oplus B for some natural number nn and finite abelian group BB. My guess is that applying our construction to nB\mathbb{Z}^n \oplus B just gives End( n)End(\mathbb{R}^n) again.

In a sense, we haven’t got much new relative to our starting point of obtaining \mathbb{R} from \mathbb{Z}. So, it would be nice to extend the construction above from finitely generated abelian groups to some more general context: perhaps finitely generated commutative monoids, or perhaps finitely generated nonabelian groups.

I haven’t tried either of these. The latter option seems to fit very much into the circle of ideas involving coarse geometry, the Gromov–Hausdorff metric, word metrics, and Gromov’s results on growth of groups. I wonder if it’s already been done.

Posted by: Tom Leinster on September 24, 2023 11:55 AM | Permalink | Reply to this

Re: Constructing the real numbers as nearly multiplicative sequences

Very nice reflections! Some quick remarks/thoughts:

a) If we just ignore the fact that one cannot really subtract in +\mathbb{N}^{+} (e.g. assume that we have a monomorphism into some group), one certainly recovers the construction Emily described. I have not thoroughly worked through the construction for \mathbb{Z}, but I’d assume it works there too.

b) I think your guess about nB\mathbb{Z}^{n} \oplus B must be correct, as the (Cayley) metric space corresponding to a finite group is coarsely equivalent to a point.

c) A first thing to check in attempting to generalise to monoids (e.g. commutative) would be whether it is still true that the coarse geometry is independent of the choice of generators. Of course, even if that is not true, one could always just try to work with a chosen set of generators and the corresponding metric (and notion of boundedness).

d) It would be really nice to be able to obtain the pp-adic numbers in this way. One could try to start with (p)\mathbb{Z}_{(p)}, the localisation of \mathbb{Z} at pp\mathbb{Z}, but it is not finitely generated. Is finite generation really necessary, though? One has to choose a set of generators, but let us say that we do so, say {1q}\left\{ \frac{1}{q} \right\} such that qq is prime and not equal to pp, or q=1q=1. Take the corresponding metric and notion of boundedness. Do we recover the pp-adic numbers? I haven’t tried to work it out, but intuitively it doesn’t seem impossible. If not, what do we get?

Posted by: Anonymous on September 25, 2023 10:12 PM | Permalink | Reply to this

Re: Constructing the real numbers as nearly multiplicative sequences

Hmm, with regard to d), for a generating set as an abelian group I suppose one actually needs {1m}\left\{ \frac{1}{m} \right\} where mm is not divisible by pp.

Posted by: Anonymous on September 25, 2023 11:02 PM | Permalink | Reply to this

Re: Constructing the real numbers as nearly multiplicative sequences

Just to throw out a few more thoughts (sorry, this got me interested!), it seems to me that any example where almost-endomorphisms are not all that obviously related to Cauchy sequences would likely be very instructive. If one is to have any hope of relating the rings which one obtains to completeness, I suspect one will have to replace the role of Cauchy sequences in defining completeness by something else, possibly the notion of a net.

In particular, an easier example than the pp-adic numbers might be to consider any non-finitely generated abelian sub-group of \mathbb{R}, for example \mathbb{Q}. Take the generating set {1m} m\left\{ \frac{1}{m} \right\}_{m \in \mathbb{Z}}. Can one somehow relate the notion of boundedness coming from this, and the resulting ring, to \mathbb{R}? More specifically, what is a good way to cook up a real number from an almost-endomorphism in this setting? Does the boundedness condition allow one to form the limit in \mathbb{R} of some kind of net, that limit being our desired real number?

And should this work in one way or another, one could of course ask whether can prove by an abstraction of the construction that the resulting ring is complete. Alternatively, one could try to look for examples where one obtains something which is not complete, but this may be a bit self-defeating, as, if there is to be some kind of general theory at all, it would not be surprising if one needs some kind of conditions on one’s starting abelian group/monoid/etc, e.g. to ensure that one’s almost-endomorphisms give rise to nets, or something else which one can take a limit of.

Posted by: Anonymous on September 26, 2023 12:43 PM | Permalink | Reply to this

Re: Constructing the Real Numbers as Nearly Multiplicative Sequences

In constructive mathematics, the construction of the real numbers using Cauchy sequences is not Cauchy complete, let alone Dedekind complete. However, if one uses entire relations instead of sequences in the definition of Cauchy real numbers, the resulting set of real numbers is Dedekind complete and Cauchy complete.

Similarly, in constructive mathematics, the construction of the (non-negative) Eudoxus real numbers using sequences of natural numbers yields a set isomorphic to the non-negative Cauchy real numbers, and thus isn’t Cauchy complete or Dedekind complete. However, I think that, similarly to the previous case, if one uses entire relations instead of sequences in the construction, one should get a set of real numbers which is Dedekind complete and Cauchy complete:

A entire relation RR on the natural numbers is nearly additive if there exists a natural number CC such that for all natural numbers mm and nn, there exists natural numbers aa, bb, and cc such that R(m,a)R(m, a), R(n,b)R(n, b), R(m+n,c)R(m + n, c) and |cab|C\vert c - a - b \vert \leq C.

Two nearly additive entire relations R,RR, R' on the natural numbers are equivalent to each other if there exists a natural number CC such that that for all natural numbers nn, there exist natural numbers aa and bb such that R(n,a)R(n, a) and R(n,b)R'(n, b) and |ba|<C\vert b - a \vert \lt C.

The non-negative reals are then equivalence classes of nearly additive entire relations on the natural numbers.

Posted by: Madeleine Birchfield on September 23, 2023 6:26 PM | Permalink | Reply to this

Re: Constructing the Real Numbers as Nearly Multiplicative Sequences

Granted that this construction yields a semiring R +R^+ containing N +\mathbf{N}^+ one needs rather more for it to be a construction of “the” reals. I think one needs to show, among other things, (1) R +R^+ has cancellation, so we can speak of the ring RR containing R +R^+; (2) RR strictly contains Q\mathbf Q (for example, exhibiting an element xx such that xx=2x \cdot x = 2); (3) a definition of an order on RR in which Q\mathbf Q is dense and Z\mathbf Z is unbounded; (4) some version of the fundamental axiom, for example, that the supremum of a bounded set exists in RR.

Posted by: James Sheppard on September 26, 2023 2:02 PM | Permalink | Reply to this

Post a New Comment