Reciprocals and roots

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 x↦ x^5/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 Q₁↔ Q₂ between dense linear orders without endpoints (Definition 6.1) is a pair (⋖,·<) of binary relations that satisfy

∃ b.a<₁ b⋖ x	⇔	a ⋖ x	⇔	∃ y.a⋖ y<₂ x
∃ b.x·< b<₁ a	⇔	x ·< a	⇔	∃ y.x<₂ y·< a
∃ x.a⋖ x·< b	⇔	a <₁ b x <₂ y	⇔	∃ a.x·< a⋖ y

where a,b:Q₁ and x,y:Q₂. These objects could, for example, consist of just positive rationals, or carry the opposite of the usual order. Let R₁ and R₂ 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 R₁≅ R₂ by

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

for which a⋖ x ⇔ a<₁ f x ⇔ g a<₂ x and x·< a ⇔ f x<₁ a ⇔ x<₂ 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 Q₁≡ Q₂⊂ Q be its open subspace of positive elements. Then

a<₁ b ≡ a< b, x<₂ y ≡ x> y, a⋖ x ≡ a x< 1, x·< a ≡ 1< a x

define a strictly monotone graph Q₁↔ Q₂.

Proof Approximate division provides the six conditions

∃ b.a< b∧ b x< 1	⇔	a x< 1	⇔	∃ y.a y< 1∧ y> x
∃ b.1< b x∧ b< a	⇔	1< a x	⇔	∃ y.x> y∧ 1< a y
∃ x.a x< 1< b x	⇔	a< b x> y	⇔	∃ 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⁻¹ is defined for x≠ 0 by

(δ,υ)⁻¹	≡	( λ 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))

(λ 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< a≤ b, where

(δ_a,υ_b)⁻¹ = (δ_1/b,υ_1/a) and (δ_−b,υ_−a)⁻¹ = (δ_−1/a,υ_−1/b).

Without assuming that Q is a field, (є_q,τ_q)≡(δ_q,υ_q)⁻¹ 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.(δ,υ)⁻¹(d,u) =⇒ δ 0∨υ 0,

the value in any illegitimate case, including 0⁻¹ and (δ₋₁,υ₁)⁻¹, 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]⁻¹	d=−∞	d< 0	d=0	d> 0	d=+∞
u=−∞	[0, 0]	[0, d⁻¹]	[0, −∞]	[+∞,−∞]	[+∞,−∞]
u< 0	[u⁻¹, 0]	[u⁻¹, d⁻¹]	[u⁻¹, −∞]	[+∞,−∞]	[+∞,−∞]
u = 0	[−∞,+∞]	[−∞,+∞]	[−∞,+∞]	[+∞, d⁻¹]	[+∞, 0]
u> 0	[−∞,+∞]	[−∞,+∞]	[−∞,+∞]	[u⁻¹, d⁻¹]	[u⁻¹, 0]
u=+∞	[−∞,+∞]	[−∞,+∞]	[−∞,+∞]	[0, d⁻¹]	[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 z≡ x/y. Then z−½< d< z< u< z+½ for some d,u:Q with u−d< 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< d< u)	⇒	∃ x:Q.d< x²ⁿ< u
(d< u)	⇒	∃ x:Q.d< x²ⁿ⁺¹< u.

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 e< d< u< f t =⇒ ∃ x:[e,t]. d< f x< u.

The usual proof is that the non-empty open subspaces

D≡{x ∣ f x< u} and U≡{x ∣ d< f 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 x≡ x^{2 n} when we put

e≡

⎧
⎨
⎩

d	if 0< d< 1
½	if ½< d

and t≡

⎧
⎨
⎩

u	if 1< u
2	if u< 2

and to f x≡ x^{2 n+1} when we put

e≡

⎧
⎨
⎩

d	if d< −1
−2	if −2< d

and t≡

⎧
⎨
⎩

u	if 1< u
2	if u< 2

▫

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

⎛
⎝

(δ,υ)

⎞
⎠

2n+1

≡

(λ d.δ(d²ⁿ⁺¹), λ u.υ(u²ⁿ⁺¹))

⎛
⎝

(δ,υ)

⎞
⎠

≡

(λ d.(d< 0)∨δ(d²ⁿ), λ u.(u> 0)∧υ(u²ⁿ)).

In the illegitimate case, √−1=0.

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

∃ 0< y₁, y₂, …, y_m< x. max(0,a)< y₁ y₂ ⋯ y_m < ⋯< y₁ y₂ x^m−2 < y₁ x^m−1 < x^m,

so a< y^m, where 0< y≡max(y₁,…, y_m)< x. Similarly if 0< x and x^m< a then ∃ y> x.y^m< 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< b^{k· 2⁻ⁿ}< u.