{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.Inverse where
open import Data.Nat using (ℕ; _⊔_; _^_; _≥_)
renaming (_≤_ to _≤ℕ_; _+_ to _+ℕ_; _*_ to _ℕ*_)
open import Data.Nat.Properties using (m≤m⊔n; m≤n⊔m; m≤m+n; m≤n+m)
renaming (≤-trans to ≤ℕ-trans; ≤-refl to ≤ℕ-refl)
import Data.Nat.Properties as ℕP
open import Data.Product using (_,_; proj₁; proj₂)
open import Data.Sum using (_⊎_; inj₁; inj₂)
open import Data.Rational using
(ℚ; 0ℚ; 1ℚ; _+_; _-_; _*_; _<_; _≤_; ∣_∣; NonZero; Positive; NonNegative
; positive; nonNegative)
open import Data.Rational.Base using (1/_) renaming (-_ to neg)
open import Data.Rational.Properties using
(≤-refl; ≤-trans; <⇒≤; ≤-<-trans; <-≤-trans; +-mono-≤; *-comm; *-assoc
; *-inverseʳ; *-monoˡ-≤-nonNeg; positive⁻¹; 1/pos⇒pos; pos⇒nonZero
; pos⇒nonNeg; 0≤∣p∣; ∣p*q∣≡∣p∣*∣q∣; 0≤p⇒∣p∣≡p; *-distribʳ-+
; neg-distribˡ-*; nonNeg*nonNeg⇒nonNeg; nonNeg+nonNeg⇒nonNeg;
nonNegative⁻¹)
open import Relation.Binary.PropositionalEquality using
(_≡_; cong; sym; module ≡-Reasoning)
open ≡-Reasoning
open import Real using (CauchySeq; embed-mono-≤; half; embed; embed-suc-pos)
open CauchySeq renaming (f to seq-f)
open import Real.Interval using (RealI)
open import Real.Interval.Arith using (0ℝ; 1ℝ; negℝ)
open import Real.Interval.Mul using (_*ℝ_)
open import Real.Interval.Equiv using (_≈ℝ_; ≈ℝ-refl; ≈ℝ-sym; ≈ℝ-trans)
open import Real.IntervalEquiv using
(l; u; centre; width; centre-diff; bound-w; recipPow2; μx-dom)
open import Real.Interval.Order using (_<ℝ_)
open import Real.Interval.Kit using
(0≤half; *-mono-≤-nonNeg; recipPow2-bound;
recip-antitone; tri-diff)
open import Real.Interval.Node using (centre-1ℝ; 0≤width-n; width-rec)
open import Real.Interval.Mul.Core using (term1)
open import Real.Interval.Mul.Laws using (*ℝ-comm)
open import Real.Interval.Mul.Cong using (*ℝ-cong)
open import Real.Interval.Mul.Order using (≈-neg; negℝ-*ℝ)
open import Real.Interval.ArithLaws using (negℝ-negℝ; negℝ-0ℝ)
open import Real.Interval.OrderLaws using (≈-<-resp; <-neg)
open import Real.Interval.Recip using
(recipℝ; recipℝ'; recipCauchy; realI→posCauchy; PosCauchy; recip-modulus
; embed-n≥2b²; 2n*b²≤4^n; recip-modulus-≥2n)
open import Real.CauchyToInterval using (M; K; μ≤M; centre-cauchy→realI)
open import Real.Interval.Reasoning using (begin≤_; _≈⟨_⟩_; _≤⟨_⟩_; _≤∎)
open import Real.Interval.Reasoning.Equiv
≈ℝ-of-recN : (x y : RealI) (N₀ : ℕ) (C : ℚ) → 0ℚ ≤ C →
(∀ n → n ≥ N₀ → ∣ centre x n - centre y n ∣ ≤ C * recipPow2 n) →
x ≈ℝ y
≈ℝ-of-recN x y N₀ C 0≤C h k =
let N₁ , w = recipPow2-bound C 0≤C k
N = N₀ ⊔ N₁
in N , λ n n≥N →
let n≥N₀ = ≤ℕ-trans (m≤m⊔n N₀ N₁) n≥N
n≥N₁ = ≤ℕ-trans (m≤n⊔m N₀ N₁) n≥N
in ≤-<-trans (h n n≥N₀) (w n n≥N₁)
module ReciprocalSetup (x : RealI) (0<x : 0ℝ <ℝ x) where
R : RealI
R = recipℝ x 0<x
pc : PosCauchy
pc = realI→posCauchy x 0<x
cs : CauchySeq
cs = recipCauchy pc
n₀ : ℕ
n₀ = proj₁ 0<x
b : ℚ
b = l x n₀
δn<lxn : u 0ℝ n₀ < b
δn<lxn = proj₂ 0<x
0<b : 0ℚ < b
0<b = PosCauchy.0<b pc
b-pos : Positive b
b-pos = positive 0<b
b-nz : NonZero b
b-nz = pos⇒nonZero b {{b-pos}}
w0 : ℚ
w0 = width x 0
wR0 : ℚ
wR0 = width R 0
0≤w0 : 0ℚ ≤ w0
0≤w0 = 0≤width-n x 0
0≤wR0 : 0ℚ ≤ wR0
0≤wR0 = 0≤width-n R 0
w0-nn : NonNegative w0
w0-nn = nonNegative 0≤w0
wR0-nn : NonNegative wR0
wR0-nn = nonNegative 0≤wR0
half-nn : NonNegative half
half-nn = nonNegative 0≤half
invb : ℚ
invb = (1/ b) {{b-nz}}
invb-pos : Positive invb
invb-pos = 1/pos⇒pos b {{b-pos}}
invb-nn : NonNegative invb
invb-nn = pos⇒nonNeg invb {{invb-pos}}
w0*wR0-nn : NonNegative (w0 * wR0)
w0*wR0-nn = nonNeg*nonNeg⇒nonNeg w0 {{w0-nn}} wR0 {{wR0-nn}}
t1-nn : NonNegative (w0 * wR0 * half)
t1-nn = nonNeg*nonNeg⇒nonNeg (w0 * wR0) {{w0*wR0-nn}} half {{half-nn}}
t2-nn : NonNegative (w0 * invb)
t2-nn = nonNeg*nonNeg⇒nonNeg w0 {{w0-nn}} invb {{invb-nn}}
C : ℚ
C = w0 * wR0 * half + w0 * invb
0≤C : 0ℚ ≤ C
0≤C = nonNegative⁻¹ C
{{nonNeg+nonNeg⇒nonNeg (w0 * wR0 * half) {{t1-nn}}
(w0 * invb) {{t2-nn}}}}
e2-pos : Positive (embed 2)
e2-pos = embed-suc-pos
e2-nn : NonNegative (embed 2)
e2-nn = pos⇒nonNeg (embed 2) {{e2-pos}}
b-nn : NonNegative b
b-nn = pos⇒nonNeg b {{b-pos}}
e2*b-nn : NonNegative (embed 2 * b)
e2*b-nn = nonNeg*nonNeg⇒nonNeg (embed 2) {{e2-nn}} b {{b-nn}}
C-aux : ℚ
C-aux = embed 2 * b * b
0≤C-aux : 0ℚ ≤ C-aux
0≤C-aux = nonNegative⁻¹ C-aux
{{nonNeg*nonNeg⇒nonNeg (embed 2 * b) {{e2*b-nn}} b {{b-nn}}}}
N-b : ℕ
N-b = proj₁ (bound-w C-aux 0≤C-aux)
C-aux≤N-b : C-aux ≤ embed N-b
C-aux≤N-b = proj₂ (bound-w C-aux 0≤C-aux)
N : ℕ
N = 4 ⊔ N-b
N≥4 : N ≥ 4
N≥4 = m≤m⊔n 4 N-b
N≥N-b : N ≥ N-b
N≥N-b = m≤n⊔m 4 N-b
embed-2b²≤N : embed 2 * b * b ≤ embed N
embed-2b²≤N =
≤-trans C-aux≤N-b
(embed-mono-≤ (≤ℕ-trans N≥N-b (≤ℕ-refl {N})))
embed-n≥2b²-inst : ∀ n → n ≥ N → embed 2 * b * b ≤ embed n
embed-n≥2b²-inst = embed-n≥2b² b N embed-2b²≤N
2n-inst : ∀ n → n ≥ N → embed (2 ℕ* n) * b * b ≤ embed (4 ^ n)
2n-inst = 2n*b²≤4^n b 0<b N N≥4 embed-n≥2b²-inst
recip-modulus-≥2n-inst :
∀ n → n ≥ N → recip-modulus b 0<b (K (2 ℕ* n)) ≥ 2 ℕ* n
recip-modulus-≥2n-inst = recip-modulus-≥2n b 0<b N 2n-inst
term1-inst :
∀ n →
∣ centre (x *ℝ R) n - centre x (2 ℕ* n) * centre R (2 ℕ* n) ∣
≤ (w0 * wR0 * half) * recipPow2 n
term1-inst n = term1 x R n
j : ℕ → ℕ
j n = PosCauchy.N₀ pc +ℕ M cs (2 ℕ* n)
Mcs≥2n : ∀ n → n ≥ N → M cs (2 ℕ* n) ≥ 2 ℕ* n
Mcs≥2n n n≥N =
≤ℕ-trans (≤ℕ-trans (recip-modulus-≥2n-inst n n≥N)
(μx-dom x r))
(μ≤M cs (2 ℕ* n))
where
r = recip-modulus b 0<b (K (2 ℕ* n))
j≥2n : ∀ n → n ≥ N → j n ≥ 2 ℕ* n
j≥2n n n≥N =
≤ℕ-trans (Mcs≥2n n n≥N)
(m≤n+m (M cs (2 ℕ* n)) (PosCauchy.N₀ pc))
jn≥N₀ : ∀ n → PosCauchy.N₀ pc ≤ℕ j n
jn≥N₀ n = m≤m+n (PosCauchy.N₀ pc) (M cs (2 ℕ* n))
centre-R-close : ∀ n → n ≥ N →
∣ centre R (2 ℕ* n) * centre x (2 ℕ* n) - 1ℚ ∣
≤ (1/ b) {{b-nz}} * width x (2 ℕ* n)
centre-R-close n n≥N = begin≤
∣ centre R (2 ℕ* n) * c - 1ℚ ∣
≈⟨ abs-target ⟩
∣ c * invd - 1ℚ ∣
≈⟨ abs-lemma ⟩
∣ c - d ∣ * invd
≤⟨ step1 ⟩
width x (2 ℕ* n) * invd
≤⟨ step2 ⟩
width x (2 ℕ* n) * invb
≈⟨ *-comm (width x (2 ℕ* n)) invb ⟩
invb * width x (2 ℕ* n)
≤∎
where
c = centre x (2 ℕ* n)
d = centre x (j n)
b≤d : b ≤ d
b≤d = PosCauchy.lower pc (j n) (jn≥N₀ n)
0<d : 0ℚ < d
0<d = <-≤-trans 0<b b≤d
d-pos : Positive d
d-pos = positive 0<d
d-nz : NonZero d
d-nz = pos⇒nonZero d {{d-pos}}
invd = (1/ d) {{d-nz}}
invd-pos : Positive invd
invd-pos = 1/pos⇒pos d {{d-pos}}
0≤invd : 0ℚ ≤ invd
0≤invd = <⇒≤ (positive⁻¹ invd {{invd-pos}})
centreR≡ : centre R (2 ℕ* n) ≡ invd
centreR≡ =
begin
centre R (2 ℕ* n)
≡⟨ centre-cauchy→realI cs (2 ℕ* n) ⟩
seq-f cs (M cs (2 ℕ* n))
≡⟨⟩
invd
∎
diff≤width : ∣ c - d ∣ ≤ width x (2 ℕ* n)
diff≤width =
centre-diff x (2 ℕ* n) (2 ℕ* n) (j n)
(≤ℕ-refl {2 ℕ* n}) (j≥2n n n≥N)
invd≤invb : invd ≤ invb
invd≤invb = recip-antitone 0<b b≤d
prod-minus1 : c * invd - 1ℚ ≡ (c - d) * invd
prod-minus1 =
begin
c * invd - 1ℚ
≡⟨ cong (λ z → c * invd - z)
(sym (*-inverseʳ d {{d-nz}})) ⟩
c * invd - d * invd
≡⟨ cong (λ z → c * invd + z) (neg-distribˡ-* d invd) ⟩
c * invd + neg d * invd
≡⟨ sym (*-distribʳ-+ invd c (neg d)) ⟩
(c + neg d) * invd
≡⟨⟩
(c - d) * invd
∎
abs-lemma : ∣ c * invd - 1ℚ ∣ ≡ ∣ c - d ∣ * invd
abs-lemma =
begin
∣ c * invd - 1ℚ ∣
≡⟨ cong ∣_∣ prod-minus1 ⟩
∣ (c - d) * invd ∣
≡⟨ ∣p*q∣≡∣p∣*∣q∣ (c - d) invd ⟩
∣ c - d ∣ * ∣ invd ∣
≡⟨ cong (∣ c - d ∣ *_) (0≤p⇒∣p∣≡p 0≤invd) ⟩
∣ c - d ∣ * invd
∎
abs-target : ∣ centre R (2 ℕ* n) * c - 1ℚ ∣
≡ ∣ c * invd - 1ℚ ∣
abs-target =
begin
∣ centre R (2 ℕ* n) * c - 1ℚ ∣
≡⟨ cong (λ z → ∣ z * c - 1ℚ ∣) centreR≡ ⟩
∣ invd * c - 1ℚ ∣
≡⟨ cong (λ z → ∣ z - 1ℚ ∣) (*-comm invd c) ⟩
∣ c * invd - 1ℚ ∣
∎
step1 : ∣ c - d ∣ * invd ≤ width x (2 ℕ* n) * invd
step1 =
*-mono-≤-nonNeg (0≤∣p∣ (c - d)) diff≤width
0≤invd (≤-refl {invd})
step2 : width x (2 ℕ* n) * invd
≤ width x (2 ℕ* n) * invb
step2 =
*-monoˡ-≤-nonNeg (width x (2 ℕ* n))
{{nonNegative (0≤width-n x (2 ℕ* n))}} invd≤invb
term2 : ∀ n → n ≥ N →
∣ centre x (2 ℕ* n) * centre R (2 ℕ* n) - 1ℚ ∣
≤ (w0 * invb) * recipPow2 n
term2 n n≥N = begin≤
∣ c * centre R (2 ℕ* n) - 1ℚ ∣
≈⟨ abs-comm ⟩
∣ centre R (2 ℕ* n) * c - 1ℚ ∣
≤⟨ centre-R-close n n≥N ⟩
invb * width x (2 ℕ* n)
≤⟨ *-monoˡ-≤-nonNeg invb {{invb-nn}} (width-rec x n) ⟩
invb * (w0 * r)
≈⟨ reorder ⟩
(w0 * invb) * r
≤∎
where
c = centre x (2 ℕ* n)
r = recipPow2 n
abs-comm :
∣ c * centre R (2 ℕ* n) - 1ℚ ∣
≡ ∣ centre R (2 ℕ* n) * c - 1ℚ ∣
abs-comm =
cong (λ z → ∣ z - 1ℚ ∣)
(*-comm c (centre R (2 ℕ* n)))
reorder : invb * (w0 * r) ≡ (w0 * invb) * r
reorder =
begin
invb * (w0 * r)
≡⟨ sym (*-assoc invb w0 r) ⟩
(invb * w0) * r
≡⟨ cong (_* r) (*-comm invb w0) ⟩
(w0 * invb) * r
∎
body : ∀ n → n ≥ N →
∣ centre (x *ℝ R) n - centre 1ℝ n ∣ ≤ C * recipPow2 n
body n n≥N = begin≤
∣ centre (x *ℝ R) n - centre 1ℝ n ∣
≈⟨ cong (λ z → ∣ centre (x *ℝ R) n - z ∣) (centre-1ℝ n) ⟩
∣ P - 1ℚ ∣
≤⟨ tri-diff P Q 1ℚ ⟩
∣ P - Q ∣ + ∣ Q - 1ℚ ∣
≤⟨ +-mono-≤ (term1-inst n) (term2 n n≥N) ⟩
t1c * r + t2c * r
≈⟨ sym (*-distribʳ-+ r t1c t2c) ⟩
C * r
≤∎
where
P = centre (x *ℝ R) n
Q = centre x (2 ℕ* n) * centre R (2 ℕ* n)
r = recipPow2 n
t1c = w0 * wR0 * half
t2c = w0 * invb
*ℝ-inverse-pos : (x : RealI) (0<x : 0ℝ <ℝ x)
→ x *ℝ recipℝ x 0<x ≈ℝ 1ℝ
*ℝ-inverse-pos x 0<x = ≈ℝ-of-recN (x *ℝ R) 1ℝ N C 0≤C body
where
open ReciprocalSetup x 0<x
*ℝ-neg : (x y : RealI) → x *ℝ negℝ y ≈ℝ negℝ (x *ℝ y)
*ℝ-neg x y =
beginℝ
x *ℝ negℝ y
≈ℝ⟨ *ℝ-comm x (negℝ y) ⟩
negℝ y *ℝ x
≈ℝ⟨ ≈ℝ-sym (negℝ-*ℝ y x) ⟩
negℝ (y *ℝ x)
≈ℝ⟨ ≈-neg (*ℝ-comm y x) ⟩
negℝ (x *ℝ y)
∎ℝ
*ℝ-inverse : (x : RealI) (nz : (0ℝ <ℝ x) ⊎ (x <ℝ 0ℝ))
→ x *ℝ recipℝ' x nz ≈ℝ 1ℝ
*ℝ-inverse x (inj₁ 0<x) = *ℝ-inverse-pos x 0<x
*ℝ-inverse x (inj₂ x<0) =
let
nx : RealI
nx = negℝ x
0<nx : 0ℝ <ℝ nx
0<nx = ≈-<-resp negℝ-0ℝ (<-neg x 0ℝ x<0)
rnx : RealI
rnx = recipℝ nx 0<nx
pos-inv : nx *ℝ rnx ≈ℝ 1ℝ
pos-inv = *ℝ-inverse-pos nx 0<nx
step1 : x *ℝ negℝ rnx ≈ℝ negℝ (x *ℝ rnx)
step1 = *ℝ-neg x rnx
step2 : negℝ (x *ℝ rnx) ≈ℝ negℝ (negℝ nx *ℝ rnx)
step2 = ≈-neg (*ℝ-cong {x = x} {x' = negℝ nx} {y = rnx} {y' = rnx}
(≈ℝ-sym (negℝ-negℝ x)) ≈ℝ-refl)
step3 : negℝ (negℝ nx *ℝ rnx) ≈ℝ negℝ (negℝ (nx *ℝ rnx))
step3 = ≈-neg (≈ℝ-sym (negℝ-*ℝ nx rnx))
step4 : negℝ (negℝ (nx *ℝ rnx)) ≈ℝ negℝ (negℝ 1ℝ)
step4 = ≈-neg (≈-neg pos-inv)
step5 : negℝ (negℝ 1ℝ) ≈ℝ 1ℝ
step5 = negℝ-negℝ 1ℝ
in
≈ℝ-trans step1
(≈ℝ-trans step2
(≈ℝ-trans step3
(≈ℝ-trans step4 step5)))