Previous Up Next

13  Reciprocals and roots

Arithmetic, of course, provided one of the principal reasons for introducing Dedekind cuts in the first place, namely the solution of (algebraic and other) equations. Equations involving general continuous functions may be solved using the Intermediate Value Theorem, which we prove for ASD in Section J 14.

In this section we present a simpler technique that manipulates Dedekind cuts directly. This is sufficient to define the inverse of a strictly monotone function, for example to find cube roots. However, it is more natural to present the method symmetrically in the given function and its inverse, and then xx5/3, exp and log are equally simple examples. A particular problem of this kind is then formulated as a pair of binary relations. Anyone with a little knowledge of lattice or category theory will recognise this situation as an adjunction, or rather a pair of them.



Definition 13.1 A strictly monotone graph Q1Q2 between dense linear orders without endpoints (Definition 6.1) is a pair (⋖,·<) of binary relations that satisfy

  ∃ b.a<1 b⋖ xa ⋖ x∃ y.a⋖ y<2 x 
  ∃ b.x·< b<1 ax ·< a∃ y.x<2 y·< a 
  ∃ x.a⋖ x·< ba <1 b      x <2 y∃ a.x·< a⋖ y 

where a,b:Q1 and x,y:Q2. These objects could, for example, consist of just positive rationals, or carry the opposite of the usual order. Let R1 and R2 be their Dedekind completions. Semi-continuous functions may be encoded in a similar way, but using just one of the two relations.



Proposition 13.2 Any strictly monotone graph defines inverse functions R1R2 by

  f(δ,υ)(λ e.∃ d.e⋖ d∧δ d,   λ t.∃ u.u·< t∧υ u
  g(є,τ)(λ d.∃ e.d·< e∧є e,   λ u.∃ tt⋖ u∧ τ t),

for which  ax ⇔ a<1 f x ⇔ g a<2 x  and  x·< a ⇔ f x<1 a ⇔ x<2 g a.

Proof    The first four axioms make f(δ,υ) and g(є,τ) rounded if (δ,υ) and (є,τ) are. The other two transfer boundedness, disjointness and locatedness, and also make the maps inverse.         ▫


We can use this to define reciprocals and roots, but since their domains are restricted and reciprocals reverse the order, we must modify Q and R before using them in the Proposition.



Lemma 13.3 Let Q be a linearly ordered ring that has approximate division, and let Q1Q2Q be its open subspace of positive elements. Then

a<1 b ≡  ab,      x<2 y ≡  xy,      a⋖ x ≡  a x< 1,      x·< a ≡  1< a x 

define a strictly monotone graph Q1Q2.

Proof    Approximate division provides the six conditions

  ∃ b.ab∧ b x< 1a x< 1∃ y.a y< 1∧ yx 
  ∃ b.1< b x∧ ba1< a x∃ y.xy∧ 1< a y 
  ∃ x.a x< 1< b xab      xy∃ a.a y< 1< a x,

in particular 0< a< b  ⇒  ∃ x.a< a b x< b  ⇒  ∃ x.b x> 1> a x.         ▫



Theorem 13.4 R is an ordered field, in which x−1 is defined for x≠ 0 by

  (δ,υ)−1( λ d.∃ u.υ u∧ ((d u< 1∧δ 0)∨(1< d u∧ d< 0)), 
   λ u.∃ d.δ d∧ ((d u< 1∧ υ 0)∨(1< d u∧ 0< u))).

In the strictly positive or negative cases this is respectively

(λ d.∃ u.υ u∧ d u< 1,   λ u.(u> 0)∧(∃ d.δ d  ∧ 1< d u))

or

(λ d.(d< 0)∧(∃ u.υ u∧ 1< d u),   λ u.∃ d.δ d  ∧ d u< 1).

Proof    The previous two results define an involution on {x:ℝ ∣ x> 0}. If Q is a field then this agrees with the reciprocal on Q and with Moore’s formulae (Definition 2.3) in the legitimate case 0< ab, where

ab)−1  =  (δ1/b1/a)   and   (δba)−1 = (δ−1/a−1/b).

Without assuming that Q is a field, (єqq)≡(δqq)−1 for q> 0 is given by єq d≡(d q< 1) and τq u≡(1 < q u). The arithmetical laws follow from Lemma 11.18. The negative case is similar, and we observe that the given formula combines the two cases.         ▫



Remark 13.5 We do not need to consider 0 this time, but since

∃ d u.(δ,υ)−1(d,u)  =⇒  δ 0∨υ 0,

the value in any illegitimate case, including 0−1 and (δ−11)−1, is (⊥,⊥), which denotes the interval [−∞,+∞]. On the other hand, the reciprocal of any back-to-front interval containing zero, i.e. with δ 0∧υ 0⇔⊤, is (⊤,⊤)≡[+∞,−∞].

The reciprocals of intervals with endpoints are as follows:

[d,u]−1d=−∞d< 0d=0d> 0d=+∞ 
 u=−∞[0,            0][0,       d−1][0,      −∞][+∞,−∞][+∞,−∞] 
    u< 0[u−1,       0][u−1,  d−1][u−1, −∞][+∞,−∞][+∞,−∞] 
     u = 0[−∞,+∞][−∞,+∞][−∞,+∞][+∞, d−1][+∞,      0]  
    u> 0[−∞,+∞][−∞,+∞][−∞,+∞][u−1,  d−1][u−1,       0] 
 u=+∞[−∞,+∞][−∞,+∞][−∞,+∞][0,       d−1][0,            0]

This illustrates the one-sided nature of Scott continuity: for the ascending real number d, 0 is the limit of the negative values and +∞≡⊤ that of the positive ones, but −∞≡⊥ is isolated, whereas things are the other way round for u.



Theorem 13.6 If Q is Archimedean then so is R.

Proof    Given x,y:R with y> 0, put zx/y. Then z−½< d< z< u< z+½ for some d,u:Q with ud< 1. Then n−1< d< z< u< n+2 by the Archimedean principle for Q, whence either (n−1)y< x<(n+1)y or n y< x<(n+2)y.         ▫




Lemma 13.7 Q has approximate roots in the sense that, for d,u:Q and 1≤ n:ℕ,

   (0< du)∃ x:Q.dx2nu 
   (du)∃ x:Q.dx2n+1u.

Proof    These may be found in an Archimedean ordered commutative ring with approximate division by an algorithm similar to Proposition 12.7, for which we cite Babylonian clay tablets as the original source.

Alternatively, and without relying on the Archimedean principle, we may use the constructive approximate intermediate value theorem, namely

f eduf t  =⇒ ∃ x:[e,t]. df xu

The usual proof is that the non-empty open subspaces

D≡{x ∣ f xu}     and     U≡{x ∣ df x}

cover the interval [e,t], and so must intersect. This is one of the ways of saying that the real interval is connected, which we prove for ASD in Theorem J 13.9. As the intersection is open, it must contain a rational.

The result is applicable to f xx2 n when we put

The result is applicable to f xx2 n when we put

e

    dif  0< d< 1
    ½if  ½< d
    and     t

    uif  1< u
    2if  u< 2

and to f xx2 n+1 when we put

e

    dif  d< −1
    −2if  −2< d
    and     t

    uif  1< u
    2if  u< 2
        ▫



Proposition 13.8 R has (2n+1)st roots and [0,∞) has 2nth roots, where

  

(δ,υ)
1
 2n+1
 
(λ d.δ(d2n+1),  λ u.υ(u2n+1)) 
  +

(δ,υ)
1
 2n
 
(λ d.(d< 0)∨δ(d2n),  λ u.(u> 0)∧υ(u2n)). 

In the illegitimate case, √−1=0.

Proof    The strictly monotone graph is given by the relations (a< xm) and (xm< a), where m≡ 2n or 2n+1. If a< xm and 0< x then, by m-fold application of roundedness of division,

∃ 0< y1y2, …, ymx. max(0,a)< y1 y2 ⋯ ym < ⋯< y1 y2 xm−2 < y1 xm−1xm,

so a< ym, where 0< ymax(y1,…, ym)< x. Similarly if 0< x and xm< a then ∃ y> x.ym< a, whilst if m≡ 2n+1 and x< 0 then we switch the signs. Approximate roots provide the fifth interpolation property, and also the case x≡ 0, since Q has decidable equality. The other conditions are trivial.         ▫


Finally, we leave the interested reader to use this method to develop the exponential and logarithm functions ℝ⇄(0,∞) with base b, using 0< d< bk· 2n< u.


Previous Up Next