{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.ApartnessInvertible where
open import Data.Empty using (⊥-elim)
open import Data.Nat using (ℕ; zero; suc; _∸_; _^_; z≤n; s≤s)
renaming (_*_ to _ℕ*_; _+_ to _ℕ+_; _<_ to _ℕ<_; _≤_ to _ℕ≤_; _≥_ to _ℕ≥_)
open import Data.Nat.Properties using (m≤m⊔n; m≤n⊔m; *-suc; ^-monoʳ-≤)
renaming (<⇒≤ to ℕ<⇒≤)
open import Data.Product using (Σ; _×_; _,_)
open import Data.Sum using (_⊎_; inj₁; inj₂; [_,_]′)
open import Data.Rational using
(ℚ; 0ℚ; 1ℚ; _+_; _-_; _*_; _<_; _≤_; _⊓_; ∣_∣; _÷_; 1/_) renaming (-_ to neg)
open import Data.Rational.Base using (positive; nonNegative; Positive; NonZero)
open import Data.Rational.Properties using
(+-identityˡ; +-identityʳ; +-inverseˡ; +-inverseʳ; +-comm; +-assoc; ≤-trans
; *-identityˡ; *-identityʳ; *-assoc; *-comm; *-distribʳ-+; *-zeroˡ; <⇒≤
; *-inverseˡ; *-inverseʳ; +-mono-<; +-monoˡ-<; +-mono-≤; neg-distrib-+
; ∣-p∣≡∣p∣; *-monoʳ-<-pos; *-monoˡ-<-pos; +-monoʳ-<; neg-distribˡ-*
; ≤-refl; *-distribˡ-+; +-mono-≤-<; 1/-involutive; neg-antimono-<
; neg-antimono-≤; *-monoʳ-≤-nonNeg; <-trans; <-irrefl; ≤-reflexive
; ≤-<-trans; <-≤-trans; p⊓q≤p; p⊓q≤q; <-cmp; 1/pos⇒pos; pos⇒nonNeg
; pos⇒nonZero; positive⁻¹; pos*pos⇒pos)
open import Function.Base using (case_of_)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; cong; cong₂; sym; trans; subst; subst₂; module ≡-Reasoning)
open ≡-Reasoning
open import Relation.Nullary using (¬_)
open import Relation.Binary.Definitions using (tri<; tri≈; tri>)
open import Base.RationalRing using (+interchange)
open import Real using
(ε; 0<ε; half; 2ℚ; 2ℚ≡1+1; 0<embed; embed; embed-mono-<; embed-mono-≤)
open import Real.Interval using (RealI; dyadic; δ; δ-pos; δ-half; δs≤δ; embedℚ)
open import Real.IntervalEquiv using
(node; l; u; width; centre; width-n; pow2; posPow2; denom-eq; recipPow2
; 0<width; n<2^n; 1≤2^n)
open import Real.Interval.Arith using (0ℝ; 1ℝ; _+ℝ_; negℝ; _-ℝ_)
open import Real.Interval.Mul using (_*ℝ_)
open import Real.Interval.Mul.Order using (δ-mono; u-dyadic-0)
open import Real.Interval.Order using (_<ℝ_; l-mono'; u-mono')
open import Real.Interval.AbsTriangle using (l0ℝ)
open import Real.Interval.Apartness using (_#ℝ_)
open import Real.Interval.Equiv using (_≈ℝ_)
open import Real.Interval.Node using
(l-dyadic; u-dyadic; l-hom; u-hom; node-*ℝ; l-neg; u-neg; 0≤width-n)
open import Real.Interval.Rational using (r≤|r|; pos-diff; negsub; suc∸1)
open import Real.Interval.Kit using
(0<half; 2ℚ*half≡1; half+half≡1; add-self; strict-recip; recipPow2-mono)
open import Real.Interval.Embed using (centre-embedℚ)
open import Real.Interval.DensityArch using (archimedean)
open import Real.Interval.Reasoning using (begin≤_; _≈⟨_⟩_; _≤⟨_⟩_; _≤∎)
node-2 : (r : RealI) (n : ℕ) →
node r (2 ℕ* suc n) ≡ RealI.next (RealI.next (node r (2 ℕ* n)))
node-2 r n =
begin
node r (2 ℕ* suc n)
≡⟨ cong (node r) (*-suc 2 n) ⟩
node r (2 ℕ+ 2 ℕ* n)
≡⟨ refl ⟩
RealI.next (RealI.next (node r (2 ℕ* n)))
∎
l-mul4 : (x y : RealI) (n : ℕ) →
l (x *ℝ y) n
≡ ((l x (2 ℕ* n) * l y (2 ℕ* n)) ⊓ (l x (2 ℕ* n) * u y (2 ℕ* n)))
⊓ ((u x (2 ℕ* n) * l y (2 ℕ* n)) ⊓ (u x (2 ℕ* n) * u y (2 ℕ* n)))
l-mul4 x y n =
begin
l (x *ℝ y) n
≡⟨ refl ⟩
RealI.l (node (x *ℝ y) n)
≡⟨ cong RealI.l (node-*ℝ x y n) ⟩
RealI.l (node x (2 ℕ* n) *ℝ node y (2 ℕ* n))
≡⟨ refl ⟩
((l x (2 ℕ* n) * l y (2 ℕ* n)) ⊓ (l x (2 ℕ* n) * u y (2 ℕ* n)))
⊓ ((u x (2 ℕ* n) * l y (2 ℕ* n)) ⊓ (u x (2 ℕ* n) * u y (2 ℕ* n)))
∎
⊓-pos : {p q : ℚ} → 0ℚ < p ⊓ q → (0ℚ < p) × (0ℚ < q)
⊓-pos {p} {q} h = <-≤-trans h (p⊓q≤p p q) , <-≤-trans h (p⊓q≤q p q)
pos-prod-pos : {a b : ℚ} → 0ℚ < a → 0ℚ < a * b → 0ℚ < b
pos-prod-pos {a} {b} a>0 ab>0 =
let ia : ℚ
ia = 1/_ a {{pos⇒nonZero a {{positive a>0}}}}
ia-pos : Positive ia
ia-pos = 1/pos⇒pos a {{positive a>0}}
s1 : 0ℚ * ia < (a * b) * ia
s1 = *-monoˡ-<-pos ia {{ia-pos}} ab>0
s2 : 0ℚ * ia ≡ 0ℚ
s2 = *-zeroˡ ia
s3 : (a * b) * ia ≡ b
s3 =
begin
(a * b) * ia
≡⟨ *-assoc a b ia ⟩
a * (b * ia)
≡⟨ cong (a *_) (*-comm b ia) ⟩
a * (ia * b)
≡⟨ sym (*-assoc a ia b) ⟩
(a * ia) * b
≡⟨ cong (_* b) (*-inverseʳ a {{pos⇒nonZero a {{positive a>0}}}}) ⟩
1ℚ * b
≡⟨ *-identityˡ b ⟩
b
∎
in subst (λ z → 0ℚ < z) s3 (subst (λ z → z < (a * b) * ia) s2 s1)
neg-prod-pos : {a b : ℚ} → a < 0ℚ → 0ℚ < a * b → b < 0ℚ
neg-prod-pos {a} {b} a<0 ab>0 = helper
where
bad : ¬ (0ℚ ≤ b)
bad b≥0 =
<-irrefl refl
(<-≤-trans ab>0
(≤-trans
(*-monoʳ-≤-nonNeg b {{nonNegative b≥0}} (<⇒≤ a<0))
(≤-reflexive (*-zeroˡ b))))
helper : b < 0ℚ
helper = case <-cmp b 0ℚ of λ
{ (tri< lt _ _) → lt
; (tri≈ _ eq _) → ⊥-elim (bad (≤-reflexive (sym eq)))
; (tri> _ _ gt) → ⊥-elim (bad (<⇒≤ gt))
}
same-sign : {a b c d : ℚ} →
0ℚ < a * c → 0ℚ < a * d → 0ℚ < b * c → 0ℚ < b * d →
(0ℚ < a) ⊎ (b < 0ℚ)
same-sign {a} {b} {c} {d} ac>0 ad>0 bc>0 bd>0 with <-cmp a 0ℚ
... | tri< a<0 _ _ =
inj₂ (neg-prod-pos {c} {b} c<0
(subst (0ℚ <_) (*-comm b c) bc>0))
where
c<0 : c < 0ℚ
c<0 = neg-prod-pos {a} {c} a<0 ac>0
... | tri≈ _ a≈0 _ =
⊥-elim (<-irrefl refl
(subst (0ℚ <_) (trans (cong (_* c) a≈0) (*-zeroˡ c)) ac>0))
... | tri> _ _ a>0 = inj₁ a>0
div-half : (p : ℚ) → p ÷ embed 2 ≡ p * half
div-half p = refl
centre-half : (r : RealI) (n : ℕ) →
centre r n - width r n ÷ embed 2 ≡ l r n
centre-half r n =
let a = l r n
b = u r n
h = half
s1 : (a + b) * h - (b - a) * h ≡ ((a + b) - (b - a)) * h
s1 = sym (begin
((a + b) - (b - a)) * h
≡⟨ *-distribʳ-+ h (a + b) (neg (b - a)) ⟩
(a + b) * h + (neg (b - a)) * h
≡⟨ cong ((a + b) * h +_) (sym (neg-distribˡ-* (b - a) h)) ⟩
(a + b) * h - (b - a) * h
∎)
s2 : (a + b) - (b - a) ≡ a + a
s2 = begin
(a + b) - (b - a)
≡⟨ refl ⟩
(a + b) + neg (b - a)
≡⟨ cong ((a + b) +_) (negsub b a) ⟩
(a + b) + (a - b)
≡⟨ refl ⟩
(a + b) + (a + neg b)
≡⟨ +interchange a b a (neg b) ⟩
(a + a) + (b + neg b)
≡⟨ cong ((a + a) +_) (+-inverseʳ b) ⟩
(a + a) + 0ℚ
≡⟨ +-identityʳ (a + a) ⟩
a + a
∎
s3 : ((a + b) - (b - a)) * h ≡ a
s3 =
begin
((a + b) - (b - a)) * h
≡⟨ cong (_* h) s2 ⟩
(a + a) * h
≡⟨ cong (_* h) (add-self a) ⟩
(2ℚ * a) * h
≡⟨ *-assoc 2ℚ a h ⟩
2ℚ * (a * h)
≡⟨ cong (2ℚ *_) (*-comm a h) ⟩
2ℚ * (h * a)
≡⟨ sym (*-assoc 2ℚ h a) ⟩
(2ℚ * h) * a
≡⟨ cong (_* a) 2ℚ*half≡1 ⟩
1ℚ * a
≡⟨ *-identityˡ a ⟩
a
∎
in begin
centre r n - width r n ÷ embed 2
≡⟨ refl ⟩
(a + b) ÷ embed 2 - (b - a) ÷ embed 2
≡⟨ cong₂ _-_ (div-half (a + b)) (div-half (b - a)) ⟩
(a + b) * h - (b - a) * h
≡⟨ s1 ⟩
((a + b) - (b - a)) * h
≡⟨ s3 ⟩
a
∎
l≥centre-width : (r : RealI) (n : ℕ) →
centre r n - width r n ≤ l r n
l≥centre-width r n =
let c = centre r n
w = width r n
wh = w ÷ embed 2
w≥0 : 0ℚ ≤ w
w≥0 = 0≤width-n r n
wh≥0 : 0ℚ ≤ wh
wh≥0 =
*-monoʳ-≤-nonNeg half
{{pos⇒nonNeg half {{positive 0<half}}}}
w≥0
wh≤w : wh ≤ w
wh≤w =
begin≤
wh
≈⟨ sym (+-identityʳ wh) ⟩
wh + 0ℚ
≤⟨ +-mono-≤ (≤-refl {wh}) wh≥0 ⟩
wh + wh
≈⟨ begin
wh + wh
≡⟨ sym (cong₂ _+_ (div-half w) (div-half w)) ⟩
w * half + w * half
≡⟨ sym (*-distribˡ-+ w half half) ⟩
w * (half + half)
≡⟨ cong (w *_) half+half≡1 ⟩
w * 1ℚ
≡⟨ *-identityʳ w ⟩
w
∎ ⟩
w
≤∎
step2 : c + neg w ≤ c + neg wh
step2 = +-mono-≤ (≤-refl {c}) (neg-antimono-≤ wh≤w)
in ≤-trans
(≤-trans (≤-reflexive refl) step2)
(≤-reflexive (centre-half r n))
δs*2≡δ : (n : ℕ) → δ (suc n) * 2ℚ ≡ δ n
δs*2≡δ n =
begin
δ (suc n) * 2ℚ
≡⟨ cong (δ (suc n) *_) (sym 2ℚ≡1+1) ⟩
δ (suc n) * (1ℚ + 1ℚ)
≡⟨ *-distribˡ-+ (δ (suc n)) 1ℚ 1ℚ ⟩
δ (suc n) * 1ℚ + δ (suc n) * 1ℚ
≡⟨ cong₂ _+_ (*-identityʳ (δ (suc n))) (*-identityʳ (δ (suc n))) ⟩
δ (suc n) + δ (suc n)
≡⟨ δ-half n ⟩
δ n
∎
pow2-1≡2ℚ : pow2 1 ≡ 2ℚ
pow2-1≡2ℚ = refl
δ-pow2 : (n : ℕ) → δ n * pow2 n ≡ δ 0
δ-pow2 zero = *-identityʳ (δ 0)
δ-pow2 (suc n) =
begin
δ (suc n) * pow2 (suc n)
≡⟨ cong (δ (suc n) *_) (sym (denom-eq n)) ⟩
δ (suc n) * (pow2 n * pow2 1)
≡⟨ sym (*-assoc (δ (suc n)) (pow2 n) (pow2 1)) ⟩
(δ (suc n) * pow2 n) * pow2 1
≡⟨ cong₂ _*_ (*-comm (δ (suc n)) (pow2 n)) refl ⟩
(pow2 n * δ (suc n)) * pow2 1
≡⟨ trans (*-assoc (pow2 n) (δ (suc n)) (pow2 1))
(cong (pow2 n *_) (begin
δ (suc n) * pow2 1
≡⟨ cong (δ (suc n) *_) pow2-1≡2ℚ ⟩
δ (suc n) * 2ℚ
≡⟨ δs*2≡δ n ⟩
δ n
∎)) ⟩
pow2 n * δ n
≡⟨ *-comm (pow2 n) (δ n) ⟩
δ n * pow2 n
≡⟨ δ-pow2 n ⟩
δ 0
∎
pow2-nz : (n : ℕ) → NonZero (pow2 n)
pow2-nz n = pos⇒nonZero (pow2 n) {{posPow2 n}}
δ≤δ0/pow2 : (n : ℕ) →
δ n ≤ δ 0 * (1/_ (pow2 n) {{pow2-nz n}})
δ≤δ0/pow2 n = ≤-reflexive (begin
δ n
≡⟨ sym (*-identityʳ (δ n)) ⟩
δ n * 1ℚ
≡⟨ cong (δ n *_) (sym (*-inverseʳ (pow2 n) {{pow2-nz n}})) ⟩
δ n * (pow2 n * (1/_ (pow2 n) {{pow2-nz n}}))
≡⟨ sym (*-assoc (δ n) (pow2 n) (1/_ (pow2 n) {{pow2-nz n}})) ⟩
(δ n * pow2 n) * (1/_ (pow2 n) {{pow2-nz n}})
≡⟨ cong (_* (1/_ (pow2 n) {{pow2-nz n}})) (δ-pow2 n) ⟩
δ 0 * (1/_ (pow2 n) {{pow2-nz n}})
∎)
δ-mono-aux : (n k : ℕ) → δ (k ℕ+ n) ≤ δ n
δ-mono-aux n zero = ≤-refl
δ-mono-aux n (suc k) = ≤-trans (δs≤δ (k ℕ+ n)) (δ-mono-aux n k)
pow2-mono : {n m : ℕ} → n ℕ≤ m → pow2 n ≤ pow2 m
pow2-mono {n} {m} n≤m = embed-mono-≤ (^-monoʳ-≤ 2 n≤m)
pow2-arch : (q : ℚ) → 0ℚ < q → Σ ℕ (λ n → q < pow2 n)
pow2-arch q q>0 =
let (n , x<e) = archimedean (dyadic q 0)
(k , wk) = x<e
uq : u (dyadic q 0) k ≡ δ k + q
uq = u-dyadic q k
le : l (embedℚ (embed n)) k ≡ neg (δ k) + embed n
le = l-dyadic (embed n) k
wk' : δ k + q < neg (δ k) + embed n
wk' = subst₂ _<_ uq le wk
t3 : δ k + (neg (δ k) + embed n) ≡ embed n
t3 = trans (sym (+-assoc (δ k) (neg (δ k)) (embed n)))
(trans (cong (_+ embed n) (+-inverseʳ (δ k)))
(+-identityˡ (embed n)))
s1 : (δ k + δ k) + q < embed n
s1 = subst₂ _<_ (sym (+-assoc (δ k) (δ k) q)) t3
(+-monoʳ-< (δ k) wk')
p1 : q ≤ q + 0ℚ
p1 = ≤-reflexive (sym (+-identityʳ q))
p2 : q + 0ℚ ≤ q + (δ k + δ k)
p2 = +-mono-≤ (≤-refl {q})
(+-mono-≤ (<⇒≤ (δ-pos k)) (<⇒≤ (δ-pos k)))
p3 : q + (δ k + δ k) ≤ (δ k + δ k) + q
p3 = ≤-reflexive (+-comm q (δ k + δ k))
q≤s1 : q ≤ (δ k + δ k) + q
q≤s1 = ≤-trans p1 (≤-trans p2 p3)
s2 : q < embed n
s2 = ≤-<-trans q≤s1 s1
s3 : embed n ≤ pow2 n
s3 = embed-mono-≤ {n} {2 ^ n} (ℕ<⇒≤ (n<2^n n))
in n , <-≤-trans s2 s3
δ-small : (q : ℚ) → 0ℚ < q → Σ ℕ (λ n → δ n < q)
δ-small q q>0 =
let rq = 1/_ q {{pos⇒nonZero q {{positive q>0}}}}
tgt = δ 0 * rq
tgt-pos : Positive tgt
tgt-pos = pos*pos⇒pos (δ 0) {{positive (δ-pos 0)}}
rq {{1/pos⇒pos q {{positive q>0}}}}
tgt>0 : 0ℚ < tgt
tgt>0 = positive⁻¹ tgt {{tgt-pos}}
(n , pt) = pow2-arch tgt tgt>0
δ-eq : (δ 0 * rq) * q ≡ δ 0
δ-eq = begin
(δ 0 * rq) * q
≡⟨ *-assoc (δ 0) rq q ⟩
δ 0 * (rq * q)
≡⟨ cong (δ 0 *_) (*-inverseˡ q {{pos⇒nonZero q {{positive q>0}}}}) ⟩
δ 0 * 1ℚ
≡⟨ *-identityʳ (δ 0) ⟩
δ 0
∎
s1 : δ 0 < pow2 n * q
s1 = subst (λ z → z < pow2 n * q) δ-eq
(subst (λ z → z < pow2 n * q)
(sym (*-comm (δ 0 * rq) q))
(subst (λ z → q * (δ 0 * rq) < z)
(*-comm q (pow2 n))
(*-monoʳ-<-pos q {{positive q>0}} pt)))
inv-eq : (1/_ (pow2 n) {{pow2-nz n}}) * (pow2 n * q) ≡ q
inv-eq = begin
(1/_ (pow2 n) {{pow2-nz n}}) * (pow2 n * q)
≡⟨ *-comm (1/_ (pow2 n) {{pow2-nz n}}) (pow2 n * q) ⟩
(pow2 n * q) * (1/_ (pow2 n) {{pow2-nz n}})
≡⟨ *-assoc (pow2 n) q (1/_ (pow2 n) {{pow2-nz n}}) ⟩
pow2 n * (q * (1/_ (pow2 n) {{pow2-nz n}}))
≡⟨ cong (pow2 n *_) (*-comm q (1/_ (pow2 n) {{pow2-nz n}})) ⟩
pow2 n * ((1/_ (pow2 n) {{pow2-nz n}}) * q)
≡⟨ sym (*-assoc (pow2 n) (1/_ (pow2 n) {{pow2-nz n}}) q) ⟩
(pow2 n * (1/_ (pow2 n) {{pow2-nz n}})) * q
≡⟨ cong (_* q) (*-inverseʳ (pow2 n) {{pow2-nz n}}) ⟩
1ℚ * q
≡⟨ *-identityˡ q ⟩
q
∎
s2 : δ 0 * (1/_ (pow2 n) {{pow2-nz n}}) < q
s2 = subst (λ z → z < q) (*-comm (1/_ (pow2 n) {{pow2-nz n}}) (δ 0))
(subst (λ z → (1/_ (pow2 n) {{pow2-nz n}}) * (δ 0) < z) inv-eq
(*-monoʳ-<-pos (1/_ (pow2 n) {{pow2-nz n}})
{{1/pos⇒pos (pow2 n) {{posPow2 n}}}}
s1))
in n , ≤-<-trans (δ≤δ0/pow2 n) s2
recipPow2-small : (q : ℚ) → 0ℚ < q → Σ ℕ (λ n → recipPow2 n < q)
recipPow2-small q q>0 =
let rq = 1/_ q {{pos⇒nonZero q {{positive q>0}}}}
rq>0 = positive⁻¹ rq {{1/pos⇒pos q {{positive q>0}}}}
(n , pq) = pow2-arch rq rq>0
D = embed (suc (2 ^ n ∸ 1))
D≡pow2n : D ≡ pow2 n
D≡pow2n = cong embed (suc∸1 {2 ^ n} (1≤2^n n))
rq<D : rq < D
rq<D = subst (λ z → rq < z) (sym D≡pow2n) pq
s1 : recipPow2 n < 1/_ rq {{pos⇒nonZero rq {{positive rq>0}}}}
s1 = subst₂ _<_ refl refl (strict-recip rq D rq>0 rq<D)
s2 : 1/_ rq {{pos⇒nonZero rq {{positive rq>0}}}} ≡ q
s2 = 1/-involutive q {{pos⇒nonZero q {{positive q>0}}}}
in n , subst (recipPow2 n <_) s2 s1
width-small : (r : RealI) (N : ℕ) (q : ℚ) → 0ℚ < q →
Σ ℕ (λ n → (n ℕ≥ N) × width r n < q)
width-small r N q q>0 =
let w0 = width r 0
w0>0 = 0<width r
iw = 1/_ w0 {{pos⇒nonZero w0 {{positive w0>0}}}}
tgt = q * iw
tgt>0 : 0ℚ < tgt
tgt>0 = positive⁻¹ tgt
{{pos*pos⇒pos q {{positive q>0}} iw
{{1/pos⇒pos w0 {{positive w0>0}}}}}}
(m , rm) = recipPow2-small tgt tgt>0
n = Data.Nat._⊔_ N m
n≥N : n ℕ≥ N
n≥N = m≤m⊔n N m
rm' : recipPow2 n < tgt
rm' = ≤-<-trans (recipPow2-mono (m≤n⊔m N m)) rm
s-m : w0 * recipPow2 n < w0 * tgt
s-m = *-monoʳ-<-pos w0 {{positive w0>0}} rm'
w0*tgt≡q : w0 * tgt ≡ q
w0*tgt≡q =
begin
w0 * (q * iw)
≡⟨ sym (*-assoc w0 q iw) ⟩
(w0 * q) * iw
≡⟨ cong (_* iw) (*-comm w0 q) ⟩
(q * w0) * iw
≡⟨ *-assoc q w0 iw ⟩
q * (w0 * iw)
≡⟨ cong (q *_) (*-inverseʳ w0 {{pos⇒nonZero w0 {{positive w0>0}}}}) ⟩
q * 1ℚ
≡⟨ *-identityʳ q ⟩
q
∎
w0rm : w0 * recipPow2 n < q
w0rm = <-≤-trans s-m (≤-reflexive w0*tgt≡q)
in n , n≥N , ≤-<-trans (width-n r n) w0rm
2<5 : 2 ℕ< 5
2<5 = s≤s (s≤s (s≤s z≤n))
ε4<half : ε 4 < half
ε4<half =
strict-recip (embed 2) (embed 5)
(0<embed 1)
(embed-mono-< {2} {5} 2<5)
1-2e>0 : 0ℚ < 1ℚ - 2ℚ * ε 4
1-2e>0 = pos-diff (2ℚ * ε 4) 1ℚ
(subst₂ _<_ (add-self (ε 4)) (half+half≡1)
(+-mono-< ε4<half ε4<half))
u-sub : (x y : RealI) (n : ℕ) →
u (x -ℝ y) n ≡ u x n - l y n
u-sub x y n =
begin
u (x -ℝ y) n
≡⟨ refl ⟩
u (x +ℝ negℝ y) n
≡⟨ u-hom x (negℝ y) n ⟩
u x n + u (negℝ y) n
≡⟨ cong (u x n +_) (u-neg y n) ⟩
u x n + neg (l y n)
∎
l-sub : (x y : RealI) (n : ℕ) →
l (x -ℝ y) n ≡ l x n - u y n
l-sub x y n =
begin
l (x -ℝ y) n
≡⟨ refl ⟩
l (x +ℝ negℝ y) n
≡⟨ l-hom x (negℝ y) n ⟩
l x n + l (negℝ y) n
≡⟨ cong (l x n +_) (l-neg y n) ⟩
l x n + neg (u y n)
∎
d<0⇒x<y : (x y : RealI) → (x -ℝ y) <ℝ 0ℝ → x <ℝ y
d<0⇒x<y x y (n , wn) =
let w2 : u x n - l y n < neg (δ n)
w2 = subst₂ _<_ (u-sub x y n) (l0ℝ n) wn
w3 : (u x n - l y n) + (l y n + δ n) < neg (δ n) + (l y n + δ n)
w3 = +-monoˡ-< (l y n + δ n) w2
lhs≡ : (u x n - l y n) + (l y n + δ n) ≡ u x n + δ n
lhs≡ =
begin
(u x n - l y n) + (l y n + δ n)
≡⟨ refl ⟩
(u x n + neg (l y n)) + (l y n + δ n)
≡⟨ +-assoc (u x n) (neg (l y n)) (l y n + δ n) ⟩
u x n + (neg (l y n) + (l y n + δ n))
≡⟨ cong (u x n +_) (+-comm (neg (l y n)) (l y n + δ n)) ⟩
u x n + ((l y n + δ n) + neg (l y n))
≡⟨ cong (u x n +_) (+-assoc (l y n) (δ n) (neg (l y n))) ⟩
u x n + (l y n + (δ n + neg (l y n)))
≡⟨ cong (u x n +_) (cong (l y n +_) (+-comm (δ n) (neg (l y n)))) ⟩
u x n + (l y n + (neg (l y n) + δ n))
≡⟨ cong (u x n +_) (sym (+-assoc (l y n) (neg (l y n)) (δ n))) ⟩
u x n + ((l y n + neg (l y n)) + δ n)
≡⟨ cong (u x n +_) (cong (_+ δ n) (+-inverseʳ (l y n))) ⟩
u x n + (0ℚ + δ n)
≡⟨ cong (u x n +_) (+-identityˡ (δ n)) ⟩
u x n + δ n
∎
rhs≡ : neg (δ n) + (l y n + δ n) ≡ l y n
rhs≡ =
begin
neg (δ n) + (l y n + δ n)
≡⟨ +-comm (neg (δ n)) (l y n + δ n) ⟩
(l y n + δ n) + neg (δ n)
≡⟨ +-assoc (l y n) (δ n) (neg (δ n)) ⟩
l y n + (δ n + neg (δ n))
≡⟨ cong (l y n +_) (+-inverseʳ (δ n)) ⟩
l y n + 0ℚ
≡⟨ +-identityʳ (l y n) ⟩
l y n
∎
w4 : u x n + δ n < l y n
w4 = subst₂ _<_ lhs≡ rhs≡ w3
w5 : u x n < u x n + δ n
w5 = subst (λ z → z < u x n + δ n) (+-identityʳ (u x n))
(+-mono-≤-< (≤-refl {u x n}) (δ-pos n))
in n , <-trans w5 w4
0<d⇒y<x : (x y : RealI) → 0ℝ <ℝ (x -ℝ y) → y <ℝ x
0<d⇒y<x x y (n , wn) =
let w2 : δ n < l x n - u y n
w2 = subst₂ _<_ (u-dyadic-0 n) (l-sub x y n) wn
w3 : u y n + δ n < u y n + (l x n - u y n)
w3 = +-monoʳ-< (u y n) w2
rhs≡ : u y n + (l x n - u y n) ≡ l x n
rhs≡ =
begin
u y n + (l x n - u y n)
≡⟨ refl ⟩
u y n + (l x n + neg (u y n))
≡⟨ sym (+-assoc (u y n) (l x n) (neg (u y n))) ⟩
(u y n + l x n) + neg (u y n)
≡⟨ cong (_+ neg (u y n)) (+-comm (u y n) (l x n)) ⟩
(l x n + u y n) + neg (u y n)
≡⟨ +-assoc (l x n) (u y n) (neg (u y n)) ⟩
l x n + (u y n + neg (u y n))
≡⟨ cong (l x n +_) (+-inverseʳ (u y n)) ⟩
l x n + 0ℚ
≡⟨ +-identityʳ (l x n) ⟩
l x n
∎
w4 : u y n + δ n < l x n
w4 = subst₂ _<_ refl rhs≡ w3
w5 : u y n < u y n + δ n
w5 = subst (λ z → z < u y n + δ n) (+-identityʳ (u y n))
(+-monoʳ-< (u y n) (δ-pos n))
in n , <-trans w5 w4
#0⇒# : (x y : RealI) → (x -ℝ y) #ℝ 0ℝ → x #ℝ y
#0⇒# x y (inj₁ d<0) = inj₁ (d<0⇒x<y x y d<0)
#0⇒# x y (inj₂ 0<d) = inj₂ (0<d⇒y<x x y 0<d)
1-e<c : (c : ℚ) → 1ℚ - c < ε 4 → 1ℚ - ε 4 < c
1-e<c c s-a = subst₂ _<_ t6 t7 t5
where
t1 : neg (ε 4) + (1ℚ - c) < neg (ε 4) + ε 4
t1 = +-monoʳ-< (neg (ε 4)) s-a
t2 : neg (ε 4) + ε 4 ≡ 0ℚ
t2 = +-inverseˡ (ε 4)
t3 : neg (ε 4) + (1ℚ - c) < 0ℚ
t3 = subst (λ z → neg (ε 4) + (1ℚ - c) < z) t2 t1
t4' : (1ℚ - ε 4) + neg c ≡ neg (ε 4) + (1ℚ - c)
t4' = begin
(1ℚ - ε 4) + neg c
≡⟨ refl ⟩
(1ℚ + neg (ε 4)) + neg c
≡⟨ +-assoc 1ℚ (neg (ε 4)) (neg c) ⟩
1ℚ + (neg (ε 4) + neg c)
≡⟨ cong (1ℚ +_) (+-comm (neg (ε 4)) (neg c)) ⟩
1ℚ + (neg c + neg (ε 4))
≡⟨ sym (+-assoc 1ℚ (neg c) (neg (ε 4))) ⟩
(1ℚ + neg c) + neg (ε 4)
≡⟨ +-comm (1ℚ + neg c) (neg (ε 4)) ⟩
neg (ε 4) + (1ℚ + neg c)
≡⟨ refl ⟩
neg (ε 4) + (1ℚ - c)
∎
t4 : (1ℚ - ε 4) + neg c < 0ℚ
t4 = subst (λ z → z < 0ℚ) (sym t4') t3
t5 : ((1ℚ - ε 4) + neg c) + c < 0ℚ + c
t5 = +-monoˡ-< c t4
t6 : ((1ℚ - ε 4) + neg c) + c ≡ 1ℚ - ε 4
t6 = begin
((1ℚ - ε 4) + neg c) + c
≡⟨ +-assoc (1ℚ - ε 4) (neg c) c ⟩
(1ℚ - ε 4) + (neg c + c)
≡⟨ cong ((1ℚ - ε 4) +_) (+-inverseˡ c) ⟩
(1ℚ - ε 4) + 0ℚ
≡⟨ +-identityʳ (1ℚ - ε 4) ⟩
1ℚ - ε 4
∎
t7 : 0ℚ + c ≡ c
t7 = +-identityˡ c
1-2e<c-e : (c : ℚ) → 1ℚ - ε 4 < c → 1ℚ - 2ℚ * ε 4 < c - ε 4
1-2e<c-e c s-b =
subst₂ _<_ e1 e2 (+-monoʳ-< (neg (ε 4)) s-b)
where
e1 : neg (ε 4) + (1ℚ - ε 4) ≡ 1ℚ - 2ℚ * ε 4
e1 = begin
neg (ε 4) + (1ℚ - ε 4)
≡⟨ +-comm (neg (ε 4)) (1ℚ - ε 4) ⟩
(1ℚ - ε 4) + neg (ε 4)
≡⟨ refl ⟩
(1ℚ + neg (ε 4)) + neg (ε 4)
≡⟨ +-assoc 1ℚ (neg (ε 4)) (neg (ε 4)) ⟩
1ℚ + (neg (ε 4) + neg (ε 4))
≡⟨ cong (1ℚ +_) (sym (neg-distrib-+ (ε 4) (ε 4))) ⟩
1ℚ + neg (ε 4 + ε 4)
≡⟨ cong (1ℚ +_) (cong neg (add-self (ε 4))) ⟩
1ℚ + neg (2ℚ * ε 4)
∎
e2 : neg (ε 4) + c ≡ c - ε 4
e2 = +-comm (neg (ε 4)) c
inv⇒d#0 : (d : RealI) → Σ RealI (λ z → (d *ℝ z) ≈ℝ 1ℝ) → d #ℝ 0ℝ
inv⇒d#0 d (z , dz≈1) =
let Np = dz≈1 4
(N , Np') = Np
(n₀ , n₀≥N , w₀) = width-small (d *ℝ z) N (ε 4) (0<ε 4)
c1e : ∣ centre (d *ℝ z) n₀ - centre 1ℝ n₀ ∣ < ε 4
c1e = Np' n₀ n₀≥N
c1 : centre 1ℝ n₀ ≡ 1ℚ
c1 = centre-embedℚ 1ℚ n₀
c1e' : ∣ centre (d *ℝ z) n₀ - 1ℚ ∣ < ε 4
c1e' = subst (λ y → ∣ centre (d *ℝ z) n₀ - y ∣ < ε 4) c1 c1e
c = centre (d *ℝ z) n₀
neg≡ : neg (c - 1ℚ) ≡ 1ℚ - c
neg≡ = negsub c 1ℚ
|1-c|≡ : ∣ 1ℚ - c ∣ ≡ ∣ c - 1ℚ ∣
|1-c|≡ = trans (cong ∣_∣ (sym neg≡)) (∣-p∣≡∣p∣ (c - 1ℚ))
s-a : 1ℚ - c < ε 4
s-a = ≤-<-trans
(subst (λ z → 1ℚ - c ≤ z) |1-c|≡ (r≤|r| (1ℚ - c)))
c1e'
s-b : 1ℚ - ε 4 < c
s-b = 1-e<c c s-a
s-c : 1ℚ - 2ℚ * ε 4 < c - ε 4
s-c = 1-2e<c-e c s-b
s-d : c - ε 4 < c - width (d *ℝ z) n₀
s-d = +-monoʳ-< c (neg-antimono-< w₀)
s-e : 1ℚ - 2ℚ * ε 4 < c - width (d *ℝ z) n₀
s-e = <-trans s-c s-d
s-f : 1ℚ - 2ℚ * ε 4 < l (d *ℝ z) n₀
s-f = <-≤-trans s-e (l≥centre-width (d *ℝ z) n₀)
lgt : 0ℚ < l (d *ℝ z) n₀
lgt = <-trans 1-2e>0 s-f
deep : 0ℚ < ((l d (2 ℕ* n₀) * l z (2 ℕ* n₀)) ⊓ (l d (2 ℕ* n₀) * u z (2 ℕ* n₀)))
⊓ ((u d (2 ℕ* n₀) * l z (2 ℕ* n₀)) ⊓ (u d (2 ℕ* n₀) * u z (2 ℕ* n₀)))
deep = subst (0ℚ <_) (l-mul4 d z n₀) lgt
(l1 , l2) = ⊓-pos deep
(ac , ad) = ⊓-pos l1
(bc , bd) = ⊓-pos l2
signs : (0ℚ < l d (2 ℕ* n₀)) ⊎ (u d (2 ℕ* n₀) < 0ℚ)
signs = same-sign {l d (2 ℕ* n₀)} {u d (2 ℕ* n₀)} {l z (2 ℕ* n₀)} {u z (2 ℕ* n₀)}
ac ad bc bd
pos-case : 0ℚ < l d (2 ℕ* n₀) → d #ℝ 0ℝ
pos-case ld>0 =
let (m , δm<ld) = δ-small (l d (2 ℕ* n₀)) ld>0
n = Data.Nat._⊔_ (2 ℕ* n₀) m
n≥2n : 2 ℕ* n₀ ℕ≤ n
n≥2n = m≤m⊔n (2 ℕ* n₀) m
m≤n : m ℕ≤ n
m≤n = m≤n⊔m (2 ℕ* n₀) m
δn≤δm : δ n ≤ δ m
δn≤δm = δ-mono {m} {n} m≤n
δn<ld : δ n < l d (2 ℕ* n₀)
δn<ld = ≤-<-trans δn≤δm δm<ld
ldn : l d (2 ℕ* n₀) ≤ l d n
ldn = l-mono' d {2 ℕ* n₀} {n} n≥2n
δn<ldn : δ n < l d n
δn<ldn = <-≤-trans δn<ld ldn
in inj₂ (n , subst₂ _<_ (sym (u-dyadic-0 n)) refl δn<ldn)
neg-case : u d (2 ℕ* n₀) < 0ℚ → d #ℝ 0ℝ
neg-case ud<0 =
let nd = neg (u d (2 ℕ* n₀))
0<nd : 0ℚ < nd
0<nd = neg-antimono-< ud<0
(m , δm<nd) = δ-small nd 0<nd
n = Data.Nat._⊔_ (2 ℕ* n₀) m
n≥2n : 2 ℕ* n₀ ℕ≤ n
n≥2n = m≤m⊔n (2 ℕ* n₀) m
m≤n : m ℕ≤ n
m≤n = m≤n⊔m (2 ℕ* n₀) m
δn≤δm : δ n ≤ δ m
δn≤δm = δ-mono {m} {n} m≤n
δn<nd : δ n < neg (u d (2 ℕ* n₀))
δn<nd = ≤-<-trans δn≤δm δm<nd
udn≤ : u d n ≤ u d (2 ℕ* n₀)
udn≤ = u-mono' d {2 ℕ* n₀} {n} n≥2n
u2n<-δn : u d (2 ℕ* n₀) < neg (δ n)
u2n<-δn = subst₂ _<_
(begin
δ n + (u d (2 ℕ* n₀) + neg (δ n))
≡⟨ sym (+-assoc (δ n) (u d (2 ℕ* n₀)) (neg (δ n))) ⟩
(δ n + u d (2 ℕ* n₀)) + neg (δ n)
≡⟨ cong (_+ neg (δ n)) (+-comm (δ n) (u d (2 ℕ* n₀))) ⟩
(u d (2 ℕ* n₀) + δ n) + neg (δ n)
≡⟨ +-assoc (u d (2 ℕ* n₀)) (δ n) (neg (δ n)) ⟩
u d (2 ℕ* n₀) + (δ n + neg (δ n))
≡⟨ cong (u d (2 ℕ* n₀) +_) (+-inverseʳ (δ n)) ⟩
u d (2 ℕ* n₀) + 0ℚ
≡⟨ +-identityʳ (u d (2 ℕ* n₀)) ⟩
u d (2 ℕ* n₀)
∎)
(begin
neg (u d (2 ℕ* n₀)) + (u d (2 ℕ* n₀) + neg (δ n))
≡⟨ sym (+-assoc (neg (u d (2 ℕ* n₀))) (u d (2 ℕ* n₀)) (neg (δ n))) ⟩
(neg (u d (2 ℕ* n₀)) + u d (2 ℕ* n₀)) + neg (δ n)
≡⟨ cong (_+ neg (δ n)) (+-inverseˡ (u d (2 ℕ* n₀))) ⟩
0ℚ + neg (δ n)
≡⟨ +-identityˡ (neg (δ n)) ⟩
neg (δ n)
∎)
(+-monoˡ-< (u d (2 ℕ* n₀) + neg (δ n)) δn<nd)
udn<-δn : u d n < neg (δ n)
udn<-δn = ≤-<-trans udn≤ u2n<-δn
in inj₁ (n , subst₂ _<_ refl (sym (l0ℝ n)) udn<-δn)
in [ pos-case , neg-case ]′ signs
invertible⇒# : (x y : RealI) →
Σ RealI (λ z → ((x -ℝ y) *ℝ z) ≈ℝ 1ℝ × (z *ℝ (x -ℝ y)) ≈ℝ 1ℝ) →
x #ℝ y
invertible⇒# x y (z , lhs , rhs) =
#0⇒# x y (inv⇒d#0 (x -ℝ y) (z , lhs))