12  Multiplication

We would like to develop multiplication in a way that follows addition as closely as possible. In that case, Example 11.9 showed that the extension of the Moore operation is well defined, and Lemma 11.16 that it preserves locatedness. The first of these tasks is complicated for multiplication by negation and intervals, including the back-to-front ones (Remark 2.20):

Lemma 12.1 Kaucher multiplication³ [a,z]≡[d,u]⊗[e,t] is defined by

where p≡min(d t,u e)≤ 0 and q≡max(d e,u t)≥ 0. It agrees with ordinary multiplication in Q when d=u and e=t, and with Moore’s operation (Definition 2.3) when d≤ u and e≤ t. Also, a is a monotone function of d and e and an antitone one of u and t, and vice versa for z.         ▫

Even though this is rather complicated, we can break it up into small pieces:

Lemma 12.2 The following functions are defined on the ascending reals, R:

1. constants;
2. multiplication by q≥ 0: δ↦λ a.∃ d.δ d∧(a< d q);
3. minimum, min(δ,є)≡λ d.δ d∧є d;
4. maximum, max(δ,є)≡λ d.δ d∨є d; and
5. addition, δ⊕є≡ λ a.∃ d e.δ d∧є e∧ a< d+e.

There are similar functions on R, and negation interchanges them.         ▫

Proposition 12.3 Kaucher multiplication provides a map

that extends multiplication on Q in the sense of Remark 11.5. It also preserves roundedness, boundedness and disjointness.

Proof    Looking at pairs of entries in the table, we observe, for example, that a depends on d for fixed e, t and u in at worst a piecewise linear way. The pieces are either constant or multiplication by some q≥ 0 (or q≤ 0 in the order-reversing cases), and they are combined using min or max. These functions are rounded on Q, or defined R→R etc., by the previous lemma, and it’s enough to check this componentwise.

Alternatively, we may follow Example 11.9 directly:

in various cases, in each of which there is d′< d, e′< e, t< t′ or u< u′ with the same property.

Hence we have a map (R×R)× (R×R)→(R×R), but R and R are retracts of Σ^Q, so we also have one (Σ^Q×Σ^Q)×(Σ^Q×Σ^Q)→(Σ^Q×Σ^Q) that preserves roundedness.

Since the Kaucher product of intervals with rational endpoints, i.e. as in the table, is finite, it preserves boundedness of general intervals. Similarly, since it agrees with Moore’s operation for disjoint intervals, it also preserves disjointness of general intervals. Beware, however, that the product of a forward and a backward interval may be either way round, depending on the widths of the arguments.         ▫

Exercise 12.4 Use the argument so far to show that R is a Q-module, cf. [Joh77, §6.6].

Remark 12.5 The final task is to show that products are located, cf. Lemma 11.16. Let’s look at this from a programmer’s perspective again. If we are asked to calculate x y to precision 0< p< 1, we need to decide how precisely to compute the factors x and y. For addition, p/2 is fine (cf. Exercise 2), but for multiplication,

1. if x and y are both small in magnitude, i.e. |x|,|y|< 1, then it suffices to find each of them to within p; but
2. if x is large (legally, if 0< M< |x|, but we’re thinking of the situation where M is in the millions), we need to find y correspondingly more precisely, to within p/M;
3. similarly, if y is large then we need to know x more precisely.

Since we did not include division in the assumptions about Q, whereas we used subtraction in Example 11.9, we have a difficulty in the construction of multiplication even for positive real numbers. In any place-value representation, such as binary floating point, division may be performed as accurately as required, by first shifting the divisor by sufficiently many (n) places and then dividing to give an integer quotient. Proposition 12.7 is the same idea in abstract form; in the next section we shall show that this is enough to provide genuine division in R.

Lemma 12.6 Any linearly ordered ring Q is an integral domain, admitting cancellation:

Proposition 12.7 Q has approximate division, for a,q,z:Q,

Proof    Either 0< 4q< z−a or 0< z−a< 8q.

In the first case, we may apply the Archimedean principle directly with the given q:

Then 4q< z−a< q(k′+1)−q(k−1), so k< k′−2 by the previous lemma. Hence m≡ k+1< k′−1, where m:ℤ⊂ Q, has the required property.

In the second case, the Archimedean principle for 8q (as p) and z−a (as q) provides k:ℤ with 8q< 2n(z−a), and then 0< k< 2ⁿ for some n:ℕ. Let h satisfy 0< h+h< 1 (Lemma 11.4). Then

for which the first case gives a< m′ q′=m′ q hⁿ< z, so m≡ m′ hⁿ is the required approximate quotient.         ▫

Returning to the question of locatedness, recall that we needed to strengthen this notion in Proposition 11.15 in order to define addition. Curiously, we do not need to do this (or to apply the Archimedean principle) again for multiplication.

Lemma 12.8 Any arithmetically located positive cut (δ,υ):R is multiplicatively located:

where the last conjunct corresponds to u−d< p in Proposition 11.15.

Proof    By roundedness of δ, let 0< r:Q with δ r. By approximate division in Q, let 0< p:Q with 0< z p< r(z−a). By arithmetic locatedness, let 0< d< u:Q with δ d∧υ u∧ (u−d< p). Since we have δ r∧υ u, disjointness of (δ,υ) gives r< u, so z(u−d) < z p < r(z−a) < u(z−a). Hence u a< z d as required.         ▫

Lemma 12.9 The product of an arithmetically located positive cut (δ,υ), i.e. such that δ 0, with any cut (є,τ) is another cut (α,σ), cf. Lemma 11.16.

Proof    Suppose that 0< a< z. By multiplicative locatedness of (δ,υ), there are 0< d< u with δ d∧υ u∧ (u a< d z). Then, using approximate division by d u, there are e,t with

So a< d e, e< t and u t< z by Lemma 12.6, whilst є e∨τ t by order-locatedness. Hence

More generally, given a< z, either

• 0< z, in which case there is some a′ with 0,a≤max(0,a)< a′< z, so α a′∨σ z by the foregoing argument, and hence α a∨σ z since α is lower; or
• a< 0, where we apply the previous case to −z<−a, ⊖(є,τ) and ⊖(α,σ).         ▫

It only remains to prove locatedness of the product of two numbers that are both small. Note that we can bound a product away from zero iff we can do so for both factors, and in that case the previous result applies. The point of the fifth case below is therefore to constrain the product to be near to zero.

Lemma 12.10 The product of any two real numbers (cuts) x,y:R is another cut.

Proof    If a< z then a< 0∨ 0< z, so 0< m≡max(z,−a) and

It only remains to consider the last of these five cases, which is itself a disjunction because of the definition of <max (Proposition 9.8). Then essentially

We need to explain these inequalities in terms of cuts x≡(δ,υ) and y≡(є,τ):

Proposition 12.11 R is an ordered commutative ring.         ▫

We shall use division in the next section to prove that R is Archimedean, but let us consider very briefly the necessity of that hypothesis on Q.

Remark 12.12 There are Cauchy-complete ordered fields with infinitesimals but, classically, any Dedekind-complete Abelian group must be Archimedean. This is because the sets

form a Dedekind cut that is located only in the weaker order-theoretic sense: since every u−d is infinite, (D,U) is not arithmetically located.

The significance of the Archimedean property in Greek mathematics was recognised by Otto Stolz [Sto83]. He coined the name because, although the principle had been used “implicitly” by Eudoxus and Euclid, Archimedes had stated it as an Axiom. (He had also made far deeper use of it, in his Method, but Stolz was writing before the discovery of the most important Archimedes codex.)

Stolz also gave this argument that Dedekind completeness implies the Archimedean principle [ibid., p. 511]. His result was disputed by his contemporaries, possibly because of its context in the debate at the time over the axiomatics of Euclid, but there is also a lot of extraneous discussion that makes one wonder whether he fully understood Dedekind completeness. However, we consider that his proof is valid, because it includes the two key points, namely the construction of the limit of an increasing sequence as the cut (D,U), and the problem with the value (D,U)−1. The constructive least upper bound principle and arithmetic locatedness are also “implicit” in this paper.

Remark 12.13 What does this argument say about Conway’s number system? Recall that it is a proper class. Although the class D above is equivalent as a left cut to the set ℕ, the class U cannot be expressed as a right cut, so {D ∣ U} is not a legitimate Conway Number — he calls it a gap [Con76, p. 37].

The argument also fails in ASD, for an analogous reason: U is not definable in the calculus as an open subspace. The point is really that the space D of finite numbers is overt, as it is given by an existential quantifier, or as the numbers for which repeated decrementation terminates. On the other hand, U consists of infinite or non-terminating numbers, so it is the canonical example of a non-overt subspace in recursion theory. Since U is not overt, it’s not open, so it’s not defined by a predicate. Hence D is not closed or compact, so we do not expect Section J 9 to provide its supremum.

We do not know whether there is in fact a Dedekind-complete but non-Archimedean “real line” in ASD. This is a difficult but intriguing problem in recursion theory. Careful study of John Conway’s construction may yield a recursive analogue (when this conjecture was put to him, he considered it plausible). The principal difficulty arises from the alternating quantifiers in the definition of <, as the arithmetic operations are clearly constructive [Ros01]. Even if such a model does exist, Stolz’s argument would still show that the sequence 0, 1, …, has no limit: any infinite element ω is “inaccessible” from finite values.

Such an object could, of course, be rather useful to develop differential calculus in a “non-standard” way [Koc81, Rob66]. It would also illustrate the importance of overtness very clearly. Here we have simply “left the door open” to such a possibility, by using approximate division and arithmetic locatedness in the proof, instead of the Archimedean principle itself.

Theorem 12.14 Let Q be any linearly ordered field (or commutative ring with approximate division) for which every Dedekind cut is arithmetically located. Then these cuts form a commutative ring.         ▫