{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.ContinuityRecipBasic where
open import Real.Interval.OrderComplete using (half-pos)
open import Data.Empty using (⊥-elim)
open import Data.Nat using (ℕ; suc) renaming (_*_ to _*ℕ_; _≤_ to _≤ℕ_)
open import Data.Nat.Properties as ℕP using (n≤1+n)
renaming (≤-trans to ≤ℕ-trans; <⇒≤ to <⇒≤ℕ)
open import Data.Product using (Σ; _×_; _,_; proj₁; proj₂)
open import Data.Rational using
(ℚ; 0ℚ; 1ℚ; _+_; _-_; -_; _*_; _≤_; _<_; ∣_∣; NonZero; Positive; positive
; _⊓_)
open import Data.Rational.Base using (1/_; nonNegative)
open import Data.Rational.Properties using
(neg-antimono-≤; pos⇒nonZero; positive⁻¹; 1/pos⇒pos; pos*pos⇒pos; <⇒≤
; ≤-trans; ≤-refl; ≤-reflexive; *-comm; *-identityˡ; *-identityʳ
; *-distribʳ-+; +-assoc; +-comm; +-inverseʳ; +-identityʳ; +-mono-≤
; *-monoˡ-≤-nonNeg; *-monoʳ-≤-nonNeg; ⊓-sel; p⊓q≤p; p⊓q≤q; ≤-<-trans
; <-trans; <-irrefl; *-cancelˡ-<-nonNeg; ∣p*q∣≡∣p∣*∣q∣; 0≤p⇒∣p∣≡p
; 0≤∣p∣)
open import Data.Sum using (_⊎_; inj₁; inj₂)
open import Relation.Binary.Definitions using (tri<; tri≈; tri>)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; sym; trans; cong; subst; module ≡-Reasoning)
open ≡-Reasoning
open import Base.RationalRing using (0<1)
open import Real using
(ε; 0<ε; CauchySeq; half; embed; 0≤embed; embed-mono-≤; embed-*-hom)
open CauchySeq renaming (f to seq-f; μ to seq-μ)
open import Real.CauchyToInterval using (M; K; K≥k; μ≤M; node-go; cauchy→realI)
open import Real.IntervalEquiv using
(l; u; width; 1≤embed-suc; centre; centre-l; centre-u; centre-diff; bound-w
; realI→cauchy; μx-dom)
open import Real.Interval using (RealI; δ; δ-pos; double-half)
open import Real.Interval.Arith using (0ℝ)
open import Real.Interval.Continuity using (Close; sub-add-cancel)
open import Real.Interval.ContinuityClose using (close-endpoint-bounds)
open import Real.Interval.ContinuityProdGap using (within)
open import Real.Interval.ContinuityProdBudget using (width-shift)
open import Real.Interval.ContinuityMul using (shift-bound; sub-left-≤)
open import Real.Interval.Kit using (recip-antitone; 0<embed2)
open import Real.Interval.Mul using (sub-monoˡ)
open import Real.Interval.Mul.Order using (u-dyadic-0)
open import Real.Interval.Order using (_<ℝ_)
open import Real.Interval.OrderLe using (sub-mono)
open import Real.Interval.Recip using
(inv-sub; recip-modulus; recip-modulus-lower ; realI→posCauchy; recipCauchy)
open import Real.Interval.Reasoning using (begin≤_; _≈⟨_⟩_; _≤⟨_⟩_; _≤∎)
sub-neg-trans : (a b d : ℚ) → - d ≤ a - b → b - d ≤ a
sub-neg-trans a b d h =
let s1 : - d + b ≤ (a - b) + b
s1 = +-mono-≤ h ≤-refl
s2 : - d + b ≤ a
s2 = subst (λ z → - d + b ≤ z) (sub-add-cancel a b) s1
in subst (λ z → z ≤ a) (+-comm (- d) b) s2
close-abs :
(d : ℚ) (x x' : RealI) → Close d x x' →
Σ ℕ (λ m → ∀ t → m ≤ℕ t →
∣ l x t - l x' t ∣ ≤ d × ∣ u x t - u x' t ∣ ≤ d)
close-abs = close-endpoint-bounds
l-shift-upper :
(d : ℚ) (x x' : RealI) (m : ℕ) →
(∀ t → m ≤ℕ t → ∣ l x t - l x' t ∣ ≤ d) →
∀ t → m ≤ℕ t → l x t ≤ l x' t + d
l-shift-upper d x x' m hl t mt =
let a = l x t; b = l x' t
hi = proj₂ (within (a - b) d (hl t mt))
in sub-left-≤ a b d hi
u-shift-upper :
(d : ℚ) (x x' : RealI) (m : ℕ) →
(∀ t → m ≤ℕ t → ∣ u x t - u x' t ∣ ≤ d) →
∀ t → m ≤ℕ t → u x' t ≤ u x t + d
u-shift-upper d x x' m hu t mt =
let a = u x t; b = u x' t
lo = proj₁ (within (a - b) d (hu t mt))
h1 = sub-neg-trans a b d lo
h2 : (b - d) + d ≤ a + d
h2 = +-mono-≤ h1 ≤-refl
in subst (λ z → z ≤ a + d) (sub-add-cancel b d) h2
width-near :
(d : ℚ) (x x' : RealI) (m : ℕ) →
(∀ t → m ≤ℕ t → ∣ l x t - l x' t ∣ ≤ d × ∣ u x t - u x' t ∣ ≤ d) →
∀ t → m ≤ℕ t → width x' t ≤ width x t + (d + d)
width-near d x x' m h t mt =
let hi : u x' t ≤ u x t + d
hi = u-shift-upper d x x' m (λ s ms → proj₂ (h s ms)) t mt
lo : l x t ≤ l x' t + d
lo = l-shift-upper d x x' m (λ s ms → proj₁ (h s ms)) t mt
in width-shift (l x t) (u x t) (l x' t) (u x' t) d hi lo
l-near-lower :
(d : ℚ) (x x' : RealI) (m : ℕ) →
(∀ t → m ≤ℕ t → ∣ l x t - l x' t ∣ ≤ d) →
∀ t → m ≤ℕ t → l x t - d ≤ l x' t
l-near-lower d x x' m hl t mt =
let a = l x t; b = l x' t
hi = proj₂ (within (a - b) d (hl t mt))
in shift-bound a b d hi
add-mono-≤ : (a c d : ℚ) → c ≤ d → a + c ≤ a + d
add-mono-≤ a c d h = +-mono-≤ {x = a} {y = a} {u = c} {v = d} ≤-refl h
add-left : (a b c : ℚ) → a ≤ b → a + c ≤ b + c
add-left a b c h = +-mono-≤ {x = a} {y = b} {u = c} {v = c} h ≤-refl
sub-le-right : (a c d : ℚ) → d ≤ c → a - c ≤ a - d
sub-le-right a c d h = add-mono-≤ a (- c) (- d) (neg-antimono-≤ h)
sub-add-right : (a b d : ℚ) → (a + d) - b ≡ (a - b) + d
sub-add-right a b d = begin
(a + d) - b
≡⟨ +-assoc a d (- b) ⟩
a + (d + (- b))
≡⟨ cong (a +_) (+-comm d (- b)) ⟩
a + (- b + d)
≡⟨ sym (+-assoc a (- b) d) ⟩
(a - b) + d
∎
centre-gap-upper :
(d W : ℚ) (x x' : RealI) (m : ℕ) →
u x m ≤ u x' m + d → width x' m ≤ W →
centre x m ≤ centre x' m + (W + d)
centre-gap-upper d W x x' m hu hW =
let step1 : centre x m - centre x' m ≤ u x m - l x' m
step1 = sub-mono {a = centre x m} {a' = u x m} {b = centre x' m} {b' = l x' m}
(centre-u x m) (centre-l x' m)
step2 : u x m - l x' m ≤ (u x' m + d) - l x' m
step2 = sub-monoˡ {a = u x m} {b = u x' m + d} {c = l x' m} hu
step3 : (u x' m + d) - l x' m ≡ width x' m + d
step3 = sub-add-right (u x' m) (l x' m) d
step4 : width x' m + d ≤ W + d
step4 = add-left (width x' m) W d hW
chain : centre x m - centre x' m ≤ W + d
chain = ≤-trans step1 (≤-trans step2 (≤-trans (≤-reflexive step3) step4))
in sub-left-≤ (centre x m) (centre x' m) (W + d) chain
centre-gap-lower :
(d W : ℚ) (x x' : RealI) (m : ℕ) →
u x' m ≤ u x m + d → width x m ≤ W →
centre x' m ≤ centre x m + (W + d)
centre-gap-lower d W x x' m hu hW =
let step1 : centre x' m - centre x m ≤ u x' m - l x m
step1 = sub-mono {a = centre x' m} {a' = u x' m} {b = centre x m} {b' = l x m}
(centre-u x' m) (centre-l x m)
step2 : u x' m - l x m ≤ (u x m + d) - l x m
step2 = sub-monoˡ {a = u x' m} {b = u x m + d} {c = l x m} hu
step3 : (u x m + d) - l x m ≡ width x m + d
step3 = sub-add-right (u x m) (l x m) d
step4 : width x m + d ≤ W + d
step4 = add-left (width x m) W d hW
chain : centre x' m - centre x m ≤ W + d
chain = ≤-trans step1 (≤-trans step2 (≤-trans (≤-reflexive step3) step4))
in sub-left-≤ (centre x' m) (centre x m) (W + d) chain
centre-cross-upper :
(d Wx Wx' : ℚ) (x x' : RealI) (nu nu' q : ℕ) →
nu ≤ℕ q → nu' ≤ℕ q →
width x nu ≤ Wx → width x' q ≤ Wx' → width x' nu' ≤ Wx' →
u x q ≤ u x' q + d →
centre x nu ≤ centre x' nu' + (Wx' + ((Wx' + d) + Wx))
centre-cross-upper d Wx Wx' x x' nu nu' q nu≤q nu'≤q hx hxq hxu hu =
let hA1 : centre x nu ≤ centre x q + width x nu
hA1 = sub-left-≤ (centre x nu) (centre x q) (width x nu)
(proj₂ (within (centre x nu - centre x q) (width x nu)
(centre-diff x nu nu q ℕP.≤-refl nu≤q)))
hA2 : centre x q + width x nu ≤ centre x q + Wx
hA2 = add-mono-≤ (centre x q) (width x nu) Wx hx
hA : centre x nu ≤ centre x q + Wx
hA = ≤-trans hA1 hA2
hB : centre x q ≤ centre x' q + (Wx' + d)
hB = centre-gap-upper d Wx' x x' q hu hxq
hC1 : centre x' q ≤ centre x' nu' + width x' nu'
hC1 = sub-left-≤ (centre x' q) (centre x' nu') (width x' nu')
(proj₂ (within (centre x' q - centre x' nu') (width x' nu')
(centre-diff x' nu' q nu' nu'≤q ℕP.≤-refl)))
hC2 : centre x' nu' + width x' nu' ≤ centre x' nu' + Wx'
hC2 = add-mono-≤ (centre x' nu') (width x' nu') Wx' hxu
hC : centre x' q ≤ centre x' nu' + Wx'
hC = ≤-trans hC1 hC2
hC' : centre x' q + (Wx' + d) ≤ (centre x' nu' + Wx') + (Wx' + d)
hC' = add-left (centre x' q) (centre x' nu' + Wx') (Wx' + d) hC
in begin≤ centre x nu
≤⟨ hA ⟩
centre x q + Wx
≤⟨ add-left (centre x q) (centre x' q + (Wx' + d)) Wx hB ⟩
(centre x' q + (Wx' + d)) + Wx
≤⟨ add-left (centre x' q + (Wx' + d)) ((centre x' nu' + Wx') + (Wx' + d)) Wx hC' ⟩
((centre x' nu' + Wx') + (Wx' + d)) + Wx
≈⟨ +-assoc (centre x' nu' + Wx') (Wx' + d) Wx ⟩
(centre x' nu' + Wx') + ((Wx' + d) + Wx)
≈⟨ +-assoc (centre x' nu') Wx' ((Wx' + d) + Wx) ⟩
centre x' nu' + (Wx' + ((Wx' + d) + Wx))
≤∎
centre-cross-lower :
(d Wx Wx' : ℚ) (x x' : RealI) (nu nu' q : ℕ) →
nu ≤ℕ q → nu' ≤ℕ q →
width x q ≤ Wx → width x nu ≤ Wx → width x' nu' ≤ Wx' →
u x' q ≤ u x q + d →
centre x' nu' ≤ centre x nu + (Wx + ((Wx + d) + Wx'))
centre-cross-lower d Wx Wx' x x' nu nu' q nu≤q nu'≤q hxq hx hxu hu =
let hA1 : centre x' nu' ≤ centre x' q + width x' nu'
hA1 = sub-left-≤ (centre x' nu') (centre x' q) (width x' nu')
(proj₂ (within (centre x' nu' - centre x' q) (width x' nu')
(centre-diff x' nu' nu' q ℕP.≤-refl nu'≤q)))
hA2 : centre x' q + width x' nu' ≤ centre x' q + Wx'
hA2 = add-mono-≤ (centre x' q) (width x' nu') Wx' hxu
hA : centre x' nu' ≤ centre x' q + Wx'
hA = ≤-trans hA1 hA2
hB : centre x' q ≤ centre x q + (Wx + d)
hB = centre-gap-lower d Wx x x' q hu hxq
hC1 : centre x q ≤ centre x nu + width x nu
hC1 = sub-left-≤ (centre x q) (centre x nu) (width x nu)
(proj₂ (within (centre x q - centre x nu) (width x nu)
(centre-diff x nu q nu nu≤q ℕP.≤-refl)))
hC2 : centre x nu + width x nu ≤ centre x nu + Wx
hC2 = add-mono-≤ (centre x nu) (width x nu) Wx hx
hC : centre x q ≤ centre x nu + Wx
hC = ≤-trans hC1 hC2
hC' : centre x q + (Wx + d) ≤ (centre x nu + Wx) + (Wx + d)
hC' = add-left (centre x q) (centre x nu + Wx) (Wx + d) hC
in begin≤ centre x' nu'
≤⟨ hA ⟩
centre x' q + Wx'
≤⟨ add-left (centre x' q) (centre x q + (Wx + d)) Wx' hB ⟩
(centre x q + (Wx + d)) + Wx'
≤⟨ add-left (centre x q + (Wx + d)) ((centre x nu + Wx) + (Wx + d)) Wx' hC' ⟩
((centre x nu + Wx) + (Wx + d)) + Wx'
≈⟨ +-assoc (centre x nu + Wx) (Wx + d) Wx' ⟩
(centre x nu + Wx) + ((Wx + d) + Wx')
≈⟨ +-assoc (centre x nu) Wx ((Wx + d) + Wx') ⟩
centre x nu + (Wx + ((Wx + d) + Wx'))
≤∎
pos-embed2 : Positive (embed 2)
pos-embed2 = positive 0<embed2
c : ℚ → ℚ
c b = (b * half) ⊓ 1ℚ
pos-meet : (p q : ℚ) → 0ℚ < p → 0ℚ < q → 0ℚ < p ⊓ q
pos-meet p q 0p 0q = h (⊓-sel p q)
where
h : p ⊓ q ≡ p ⊎ p ⊓ q ≡ q → 0ℚ < p ⊓ q
h (inj₁ e) = subst (λ z → 0ℚ < z) (sym e) 0p
h (inj₂ e) = subst (λ z → 0ℚ < z) (sym e) 0q
0<c : (b : ℚ) → 0ℚ < b → 0ℚ < c b
0<c b 0<b = pos-meet (b * half) 1ℚ hb 0<1
where
hb : 0ℚ < b * half
hb = positive⁻¹ (b * half)
{{pos*pos⇒pos b {{positive 0<b}} half {{half-pos}}}}
0≤c : (b : ℚ) → 0ℚ < b → 0ℚ ≤ c b
0≤c b 0<b = <⇒≤ (0<c b 0<b)
c≤bhalf : (b : ℚ) → c b ≤ b * half
c≤bhalf b = p⊓q≤p (b * half) 1ℚ
c≤1 : (b : ℚ) → c b ≤ 1ℚ
c≤1 b = p⊓q≤q (b * half) 1ℚ
c+c≤b : (b : ℚ) → c b + c b ≤ b
c+c≤b b =
let h1 : c b + c b ≤ b * half + b * half
h1 = +-mono-≤ {x = c b} {y = b * half} {u = c b} {v = b * half}
(c≤bhalf b) (c≤bhalf b)
h2 : b * half + b * half ≡ b
h2 = begin
b * half + b * half
≡⟨ sym (*-distribʳ-+ half b b) ⟩
(b + b) * half
≡⟨ double-half b ⟩
b
∎
in ≤-trans h1 (≤-reflexive h2)
c≤b-c : (b : ℚ) → c b ≤ b - c b
c≤b-c b =
let step1 : (c b + c b) - c b ≤ b - c b
step1 = sub-monoˡ {a = c b + c b} {b = b} {c = c b} (c+c≤b b)
step2 : (c b + c b) - c b ≡ c b
step2 = begin
(c b + c b) - c b
≡⟨ refl ⟩
(c b + c b) + (- c b)
≡⟨ +-assoc (c b) (c b) (- c b) ⟩
c b + (c b + (- c b))
≡⟨ cong (c b +_) (+-inverseʳ (c b)) ⟩
c b + 0ℚ
≡⟨ +-identityʳ (c b) ⟩
c b
∎
in ≤-trans (≤-reflexive (sym step2)) step1
1/1≡1 : 1/ 1ℚ ≡ 1ℚ
1/1≡1 = refl
ε≤1 : (k : ℕ) → ε k ≤ 1ℚ
ε≤1 k =
subst (λ z → ε k ≤ z) (sym 1/1≡1)
(recip-antitone {a = 1ℚ} {b = embed (suc k)} 0<1 (1≤embed-suc k))
εk*ε9≤1 : (k : ℕ) → ε k * ε 9 ≤ 1ℚ
εk*ε9≤1 k =
let q : ε k * ε 9 ≤ 1ℚ * ε 9
q = *-monoʳ-≤-nonNeg (ε 9) {{nonNegative (<⇒≤ (0<ε 9))}} (ε≤1 k)
q' : ε k * ε 9 ≤ ε 9
q' = subst (λ z → ε k * ε 9 ≤ z) (*-identityˡ (ε 9)) q
in ≤-trans q' (ε≤1 9)
slack : (b : ℚ) → ℕ → ℚ
slack b k = ((c b) * (c b)) * (ε k * ε 9)
0<c*c : (b : ℚ) → 0ℚ < b → 0ℚ < c b * c b
0<c*c b 0<b =
positive⁻¹ (c b * c b)
{{pos*pos⇒pos (c b) {{positive (0<c b 0<b)}} (c b) {{positive (0<c b 0<b)}}}}
0<slack : (b : ℚ) (k : ℕ) → 0ℚ < b → 0ℚ < slack b k
0<slack b k 0<b =
positive⁻¹ ((c b * c b) * (ε k * ε 9))
{{pos*pos⇒pos (c b * c b) {{positive (0<c*c b 0<b)}}
(ε k * ε 9)
{{pos*pos⇒pos (ε k) {{positive (0<ε k)}}
(ε 9) {{positive (0<ε 9)}}}}}}
slack≤c : (b : ℚ) (k : ℕ) → 0ℚ < b → slack b k ≤ c b
slack≤c b k 0<b =
let h1 : (c b * c b) * (ε k * ε 9) ≤ (c b * c b) * 1ℚ
h1 = *-monoˡ-≤-nonNeg (c b * c b)
{{nonNegative (<⇒≤ (0<c*c b 0<b))}} (εk*ε9≤1 k)
h2 : (c b * c b) * 1ℚ ≤ c b * c b
h2 = ≤-reflexive (*-identityʳ (c b * c b))
h3 : c b * c b ≤ c b * 1ℚ
h3 = *-monoˡ-≤-nonNeg (c b) {{nonNegative (<⇒≤ (0<c b 0<b))}} (c≤1 b)
h4 : c b * 1ℚ ≤ c b
h4 = ≤-reflexive (*-identityʳ (c b))
in ≤-trans h1 (≤-trans h2 (≤-trans h3 h4))
c≤b-slack : (b : ℚ) (k : ℕ) → 0ℚ < b → c b ≤ b - slack b k
c≤b-slack b k 0<b =
let step1 : b - c b ≤ b - slack b k
step1 = sub-le-right b (c b) (slack b k) (slack≤c b k 0<b)
in ≤-trans (c≤b-c b) step1
gap-abs :
(A B W : ℚ) (0A : 0ℚ < A) (0B : 0ℚ < B) →
∣ B + - A ∣ ≤ W →
∣ (1/ A) {{pos⇒nonZero A {{positive 0A}}}}
- (1/ B) {{pos⇒nonZero B {{positive 0B}}}} ∣
≤ W * (1/ (A * B))
{{pos⇒nonZero (A * B)
{{pos*pos⇒pos A {{positive 0A}} B {{positive 0B}}}}}}
gap-abs A B W 0A 0B hW =
let nzA : NonZero A
nzA = pos⇒nonZero A {{positive 0A}}
nzB : NonZero B
nzB = pos⇒nonZero B {{positive 0B}}
AB-pos : Positive (A * B)
AB-pos = pos*pos⇒pos A {{positive 0A}} B {{positive 0B}}
nzAB : NonZero (A * B)
nzAB = pos⇒nonZero (A * B) {{AB-pos}}
iP : ℚ
iP = (1/ (A * B)) {{nzAB}}
iP-pos : Positive iP
iP-pos = 1/pos⇒pos (A * B) {{AB-pos}}
0≤iP : 0ℚ ≤ iP
0≤iP = <⇒≤ (positive⁻¹ iP {{iP-pos}})
e1 : (1/ A) {{nzA}} - (1/ B) {{nzB}} ≡ (B + - A) * iP
e1 = inv-sub A B {{nzA}} {{nzB}} {{nzAB}}
e2 : ∣ (1/ A) {{nzA}} - (1/ B) {{nzB}} ∣ ≡ ∣ B + - A ∣ * ∣ iP ∣
e2 = trans (cong ∣_∣ e1) (∣p*q∣≡∣p∣*∣q∣ (B + - A) iP)
e3 : ∣ B + - A ∣ * ∣ iP ∣ ≡ ∣ B + - A ∣ * iP
e3 = cong (∣ B + - A ∣ *_) (0≤p⇒∣p∣≡p 0≤iP)
e4 : ∣ B + - A ∣ * iP ≤ W * iP
e4 = *-monoʳ-≤-nonNeg iP {{nonNegative 0≤iP}} hW
in subst (λ z → z ≤ W * iP) (sym (trans e2 e3)) e4
gap-c :
(A B c W : ℚ) (0A : 0ℚ < A) (0B : 0ℚ < B) (0c : 0ℚ < c) →
c ≤ A → c ≤ B → ∣ B + - A ∣ ≤ W →
∣ (1/ A) {{pos⇒nonZero A {{positive 0A}}}}
- (1/ B) {{pos⇒nonZero B {{positive 0B}}}} ∣
≤ W * (1/ (c * c))
{{pos⇒nonZero (c * c)
{{pos*pos⇒pos c {{positive 0c}} c {{positive 0c}}}}}}
gap-c A B c W 0A 0B 0c c≤A c≤B hW =
let AB-pos : Positive (A * B)
AB-pos = pos*pos⇒pos A {{positive 0A}} B {{positive 0B}}
nzAB : NonZero (A * B)
nzAB = pos⇒nonZero (A * B) {{AB-pos}}
cc-pos : Positive (c * c)
cc-pos = pos*pos⇒pos c {{positive 0c}} c {{positive 0c}}
nzcc : NonZero (c * c)
nzcc = pos⇒nonZero (c * c) {{cc-pos}}
iP : ℚ
iP = (1/ (A * B)) {{nzAB}}
iC : ℚ
iC = (1/ (c * c)) {{nzcc}}
s1 : c * c ≤ c * B
s1 = *-monoˡ-≤-nonNeg c {{nonNegative (<⇒≤ 0c)}} c≤B
s2 : c * B ≤ A * B
s2 = *-monoʳ-≤-nonNeg B {{nonNegative (<⇒≤ 0B)}} c≤A
cc≤AB : c * c ≤ A * B
cc≤AB = ≤-trans s1 s2
mono : iP ≤ iC
mono = recip-antitone {a = c * c} {b = A * B}
(positive⁻¹ (c * c) {{cc-pos}}) cc≤AB
W-nn : 0ℚ ≤ W
W-nn = ≤-trans (0≤∣p∣ (B + - A)) hW
in ≤-trans (gap-abs A B W 0A 0B hW)
(*-monoˡ-≤-nonNeg W {{nonNegative W-nn}} mono)
l-cauchy→realI : (cs : CauchySeq) (n : ℕ) →
l (cauchy→realI cs) n ≡ seq-f cs (M cs n) - δ n
l-cauchy→realI cs n = cong RealI.l (node-go cs n)
u-cauchy→realI : (cs : CauchySeq) (n : ℕ) →
u (cauchy→realI cs) n ≡ seq-f cs (M cs n) + δ n
u-cauchy→realI cs n = cong RealI.u (node-go cs n)
0<b*b : (b : ℚ) → 0ℚ < b → 0ℚ < b * b
0<b*b b b>0 =
positive⁻¹ (b * b) {{pos*pos⇒pos b {{positive b>0}} b {{positive b>0}}}}
Bsq-index : (b : ℚ) → 0ℚ < b → ℕ
Bsq-index b 0<b = proj₁ (bound-w (b * b) (<⇒≤ (0<b*b b 0<b)))
≤-from-embed-< : (N M : ℕ) → embed N < embed (suc M) → N ≤ℕ M
≤-from-embed-< N M h with ℕP.<-cmp N M
... | tri< N<M _ _ = <⇒≤ℕ N<M
... | tri≈ p q r = ℕP.≤-reflexive q
... | tri> _ _ M<N =
⊥-elim (<-irrefl refl (≤-<-trans (embed-mono-≤ M<N) h))
recip-modulus-grow :
(b : ℚ) (0<b : 0ℚ < b) (N i : ℕ) →
(N *ℕ Bsq-index b 0<b) ≤ℕ i →
N ≤ℕ recip-modulus b 0<b i
recip-modulus-grow b 0<b N i thresh =
let bsq = b * b
B = Bsq-index b 0<b
bsq≤eB : bsq ≤ embed B
bsq≤eB = proj₂ (bound-w bsq (<⇒≤ (0<b*b b 0<b)))
h1 : embed N * bsq ≤ embed N * embed B
h1 = *-monoˡ-≤-nonNeg (embed N) {{nonNegative (0≤embed N)}} bsq≤eB
h2 : embed N * bsq ≤ embed (N *ℕ B)
h2 = ≤-trans h1 (≤-reflexive (sym (embed-*-hom N B)))
h3 : embed (N *ℕ B) ≤ embed i
h3 = embed-mono-≤ thresh
h4 : embed i ≤ embed (suc i)
h4 = embed-mono-≤ (n≤1+n i)
lo : embed N * bsq ≤ embed (suc i)
lo = ≤-trans h2 (≤-trans h3 h4)
M' = recip-modulus b 0<b i
hi : embed (suc i) < bsq * embed (suc M')
hi = recip-modulus-lower b 0<b i
mid : embed N * bsq < bsq * embed (suc M')
mid = ≤-<-trans lo hi
comm : bsq * embed N < bsq * embed (suc M')
comm = subst (λ z → z < bsq * embed (suc M')) (*-comm (embed N) bsq) mid
cancel : embed N < embed (suc M')
cancel = *-cancelˡ-<-nonNeg bsq {{nonNegative (<⇒≤ (0<b*b b 0<b))}} comm
N≤M' : N ≤ℕ M'
N≤M' = ≤-from-embed-< N M' cancel
in N≤M'
M-recip-grow :
(x : RealI) (0<x : 0ℝ <ℝ x) (N : ℕ) →
Σ ℕ (λ n → N ≤ℕ M (recipCauchy (realI→posCauchy x 0<x)) n)
M-recip-grow x 0<x N =
let n₀ = proj₁ 0<x
b = l x n₀
0<b : 0ℚ < l x n₀
0<b = <-trans (δ-pos n₀)
(subst (λ z → z < l x n₀) (u-dyadic-0 n₀) (proj₂ 0<x))
cs = recipCauchy (realI→posCauchy x 0<x)
n = N *ℕ Bsq-index b 0<b
Kn≥ : (N *ℕ Bsq-index b 0<b) ≤ℕ K n
Kn≥ = K≥k n
g1 : N ≤ℕ recip-modulus b 0<b (K n)
g1 = recip-modulus-grow b 0<b N (K n) Kn≥
g2 : recip-modulus b 0<b (K n) ≤ℕ seq-μ (realI→cauchy x) (recip-modulus b 0<b (K n))
g2 = μx-dom x (recip-modulus b 0<b (K n))
g3 : seq-μ cs (K n) ≤ℕ M cs n
g3 = μ≤M cs n
in n , ≤ℕ-trans g1 (≤ℕ-trans g2 g3)