## 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 $a$. One way to say that a sequence $q \colon \mathbb{N} \to \mathbb{Q}$ of rational numbers converges to $a$ is to ask there to exist a constant $A \in \mathbb{N}$ so that for all $n \in \mathbb{N}$,

$|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 $a$, it is possible to find a sequence of natural numbers $a \colon \mathbb{N} \to \mathbb{N}$ so that the sequence $n \mapsto \frac{a_n}{n}$ converges to $a$ in the above sense, i.e.:

$|\frac{a_n}{n} - a | \le \frac{A}{n}$

or equivalently

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

This sequence $a \colon \mathbb{N} \to \mathbb{N}$ will encode the real number $a$ (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 \colon \mathbb{N} \to \mathbb{N}$ will have the property that the sequence $n \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 $A \in \mathbb{N}$ so that for all $n,m \in \mathbb{N}$,

$|\frac{a_n}{n} - \frac{a_m}{m} | \le \frac{A}{n} + \frac{A}{m},$

or equivalently by

$|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 $A' \in \mathbb{N}$ so that for all $m,n \in \mathbb{N}$

$|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' \colon \mathbb{N} \to \mathbb{N}$ represent the same real number when there exists $C \in \mathbb{N}$ so that for all $n \in \mathbb{N}$

$|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.

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

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

More interestingly, their product $a \cdot b \colon \mathbb{N} \to \mathbb{N}$ is defined by function composition: $(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:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3502

### 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)$, which could be $\mathbb{Z}$, $\mathbb{N}$, or something else. Suppose we also have a bornology on the monoid $M$, by which I mean a collection of subsets called “bounded”, closed under taking subsets and finite unions, translation invariant, and including $\{0\}$. It’s an order-ideal in the power set of $M$, compatible with the monoid structure. We’ll probably also need to know that if $B$ and $B'$ are bounded then so is $\{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 $M$ to be a map of sets $f: M \to M$ with the following property: there is some bounded set $B \subseteq M$ such that for all $x, y \in M$, there exist $b, b' \in B$ satisfying

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

Say that two approximate endomorphisms $f$ and $g$ are equivalent if there is some bounded set $B$ such that for all $x \in M$, there exist $b, b' \in B$ satisfying

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

Then with luck, we can define a rig/semiring of equivalence classes of approximate endomorphisms. When $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 $M$ is a mere monoid. Is what I’m doing equivalent to passing to the group completion $A$ of $M$ and using a bornology on $A$? And did I implicitly assume that $M$ 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 $X$, one can take the monoid of equivalence classes of approximate endomorphisms of $X$, 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 $A$. If we choose a finite set of generators then we obtain a metric on $A$, the distance between two points being the length of the shortest path between them on the Cayley graph. That is, if $a - b$ can be expressed as $\lambda_1 x_1 + \cdots + \lambda_n x_n$, where the $\lambda_i$ are integers and the $x_i$ are generators, then $d(a, b)$ is at most $\sum |\lambda_i|$ — “at most” because $d(a, b)$ is the infimum over all such ways of expressing $a - b$ as a combination of generators.

This gives a notion of what it means for a subset of $A$ 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 $A$.

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

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

Of course, there aren’t many finitely generated abelian groups! Every finitely generated abelian group can be expressed as $\mathbb{Z}^n \oplus B$ for some natural number $n$ and finite abelian group $B$. My guess is that applying our construction to $\mathbb{Z}^n \oplus B$ just gives $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 $\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 $p$-adic numbers in this way. One could try to start with $\mathbb{Z}_{(p)}$, the localisation of $\mathbb{Z}$ at $p\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 $\left\{ \frac{1}{q} \right\}$ such that $q$ is prime and not equal to $p$, or $q=1$. Take the corresponding metric and notion of boundedness. Do we recover the $p$-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 $\left\{ \frac{1}{m} \right\}$ where $m$ is not divisible by $p$.

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 $p$-adic numbers might be to consider any non-finitely generated abelian sub-group of $\mathbb{R}$, for example $\mathbb{Q}$. Take the generating set $\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 $R$ on the natural numbers is nearly additive if there exists a natural number $C$ such that for all natural numbers $m$ and $n$, there exists natural numbers $a$, $b$, and $c$ such that $R(m, a)$, $R(n, b)$, $R(m + n, c)$ and $\vert c - a - b \vert \leq C$.

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

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

Granted that this construction yields a semiring $R^+$ containing $\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^+$ has cancellation, so we can speak of the ring $R$ containing $R^+$; (2) $R$ strictly contains $\mathbf Q$ (for example, exhibiting an element $x$ such that $x \cdot x = 2$); (3) a definition of an order on $R$ in which $\mathbf Q$ is dense and $\mathbf Z$ is unbounded; (4) some version of the fundamental axiom, for example, that the supremum of a bounded set exists in $R$.