{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.Kit where
open import Data.Nat using (ℕ; suc; _^_; _∸_; s≤s; z≤n)
renaming (_*_ to _ℕ*_; _≤_ to _≤ℕ_; _+_ to _+ℕ_)
open import Data.Nat.Properties using (m≤m+n; ^-monoʳ-≤)
renaming (≤-trans to ≤-transℕ; ≤-reflexive to ≤-reflexiveℕ; *-assoc to *-assocℕ)
import Data.Nat.Properties as ℕP
import Data.Integer.Properties as ℤP
open import Data.Product using (_,_; Σ; proj₁; proj₂)
open import Data.Rational.Base using (1/_; _÷_; positive)
open import Data.Rational using
(ℚ; 0ℚ; 1ℚ; _+_; _-_; _*_; _≤_; _<_; ∣_∣; nonNegative; NonZero
; Positive; NonNegative) renaming (-_ to neg)
open import Data.Rational.Properties using
(+-inverseʳ; +-identityˡ; +-mono-≤; *-identityˡ; *-identityʳ; *-assoc; *-comm
; *-inverseʳ; *-inverseˡ; *-distribʳ-+; *-distribˡ-+; ≤-refl; ≤-reflexive
; ≤-trans; 0≤p⇒∣p∣≡p; pos⇒nonZero; positive⁻¹; 1/pos⇒pos; pos*pos⇒pos
; pos⇒nonNeg; <-≤-trans; ≤-<-trans; <⇒≤; *-monoˡ-≤-nonNeg; *-monoʳ-≤-nonNeg
; *-cancelˡ-≤-pos; *-cancelˡ-<-nonNeg; ∣p+q∣≤∣p∣+∣q∣; ∣-p∣≡∣p∣
; +-assoc; +-comm; +-inverseˡ; +-identityʳ; *-zeroˡ; *-monoʳ-<-pos
; neg-distribˡ-*)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; cong; cong₂; sym; trans; subst; module ≡-Reasoning)
open ≡-Reasoning
open import Base.RationalRing using (0<1; telescope)
open import Real using
(embed; half; embed2-nonZero; 2ℚ; 2ℚ≡1+1; ε; 0<ε; embed-mono-≤; embed-suc-pos
; 0<embed; embed-mono-<; reciprocal-cong; embed-*-hom)
open import Real.Interval using (RealI)
open import Real.Interval.Equiv using (_≈ℝ_)
open import Real.IntervalEquiv using
(centre; recipPow2; bound-w; pos-2^t; frac-strict; B<2^sucB; 2m; n<2^n; 1≤2^n
; recip≤1)
open import Real.Interval.Rational using (suc∸1; 0<2^t; negsub; recip-*-hom)
≈ℝ-of-eq : (x y : RealI)
→ (∀ n → centre x n ≡ centre y n) → x ≈ℝ y
≈ℝ-of-eq x y h k = 0 , λ n _ →
let
eq0 : centre x n - centre y n ≡ 0ℚ
eq0 = begin
centre x n - centre y n
≡⟨ cong (λ w → w - centre y n) (h n) ⟩
centre y n - centre y n
≡⟨ +-inverseʳ (centre y n) ⟩
0ℚ
∎
abs0 : ∣ centre x n - centre y n ∣ ≡ 0ℚ
abs0 = begin
∣ centre x n - centre y n ∣
≡⟨ cong ∣_∣ eq0 ⟩
∣ 0ℚ ∣
≡⟨ 0≤p⇒∣p∣≡p {0ℚ} (≤-refl {0ℚ}) ⟩
0ℚ
∎
in subst (λ z → z < ε k) (sym abs0) (0<ε k)
embed-suc∸1 : ∀ k → embed (suc (2 ^ k ∸ 1)) ≡ embed (2 ^ k)
embed-suc∸1 k = begin
embed (suc (2 ^ k ∸ 1))
≡⟨ cong embed (suc∸1 (0<2^t k)) ⟩
embed (2 ^ k)
∎
0<recipPow2 : ∀ n → 0ℚ < recipPow2 n
0<recipPow2 n =
positive⁻¹ (recipPow2 n)
{{1/pos⇒pos (embed (suc (2 ^ n ∸ 1))) {{embed-suc-pos}}}}
0≤recipPow2 : ∀ n → 0ℚ ≤ recipPow2 n
0≤recipPow2 n = <⇒≤ (0<recipPow2 n)
recip-antitone : ∀ {a b : ℚ} (0<a : 0ℚ < a) (a≤b : a ≤ b) →
1/_ (b) {{pos⇒nonZero b {{positive (<-≤-trans 0<a a≤b)}}}}
≤ 1/_ (a) {{pos⇒nonZero a {{positive 0<a}}}}
recip-antitone {a} {b} 0<a a≤b =
*-cancelˡ-≤-pos (a * b)
{{pos*pos⇒pos a {{positive 0<a}} b {{positive 0<b}}}}
(≤-trans (≤-reflexive ab·b⁻¹≡a)
(≤-trans a≤b
(≤-reflexive (sym ab·a⁻¹≡b))))
where
0<b : 0ℚ < b
0<b = <-≤-trans 0<a a≤b
ab·b⁻¹≡a : (a * b) * (1/_ (b) {{pos⇒nonZero b {{positive 0<b}}}}) ≡ a
ab·b⁻¹≡a =
begin
(a * b) * (1/_ (b) {{pos⇒nonZero b {{positive 0<b}}}})
≡⟨ *-assoc a b (1/_ (b) {{pos⇒nonZero b {{positive 0<b}}}}) ⟩
a * (b * (1/_ (b) {{pos⇒nonZero b {{positive 0<b}}}}))
≡⟨ cong (a *_) (*-inverseʳ b {{pos⇒nonZero b {{positive 0<b}}}}) ⟩
a * 1ℚ
≡⟨ *-identityʳ a ⟩
a
∎
ab·a⁻¹≡b : (a * b) * (1/_ (a) {{pos⇒nonZero a {{positive 0<a}}}}) ≡ b
ab·a⁻¹≡b =
begin
(a * b) * (1/_ (a) {{pos⇒nonZero a {{positive 0<a}}}})
≡⟨ *-assoc a b (1/_ (a) {{pos⇒nonZero a {{positive 0<a}}}}) ⟩
a * (b * (1/_ (a) {{pos⇒nonZero a {{positive 0<a}}}}))
≡⟨ cong (a *_) (*-comm b (1/_ (a) {{pos⇒nonZero a {{positive 0<a}}}})) ⟩
a * ((1/_ (a) {{pos⇒nonZero a {{positive 0<a}}}}) * b)
≡⟨ sym (*-assoc a (1/_ (a) {{pos⇒nonZero a {{positive 0<a}}}}) b) ⟩
(a * (1/_ (a) {{pos⇒nonZero a {{positive 0<a}}}})) * b
≡⟨ cong (_* b) (*-inverseʳ a {{pos⇒nonZero a {{positive 0<a}}}}) ⟩
1ℚ * b
≡⟨ *-identityˡ b ⟩
b
∎
recipPow2-mono : ∀ {n m : ℕ} → n ≤ℕ m → recipPow2 m ≤ recipPow2 n
recipPow2-mono {n} {m} n≤m =
recip-antitone {a = embed (suc (2 ^ n ∸ 1))} {b = embed (suc (2 ^ m ∸ 1))}
(positive⁻¹ (embed (suc (2 ^ n ∸ 1))) {{embed-suc-pos}})
(≤-trans (≤-reflexive (embed-suc∸1 n))
(≤-trans (embed-mono-≤ (^-monoʳ-≤ 2 n≤m))
(≤-reflexive (sym (embed-suc∸1 m)))))
n≤2n : ∀ n → n ≤ℕ 2 ℕ* n
n≤2n n = ≤-transℕ (m≤m+n n n) (≤-reflexiveℕ (sym (2m n)))
2*2n≡4n : ∀ n → 2 ℕ* (2 ℕ* n) ≡ 4 ℕ* n
2*2n≡4n n =
begin
2 ℕ* (2 ℕ* n)
≡⟨ sym (*-assocℕ 2 2 n) ⟩
(2 ℕ* 2) ℕ* n
≡⟨ refl ⟩
4 ℕ* n
∎
2n≤4n : ∀ n → 2 ℕ* n ≤ℕ 4 ℕ* n
2n≤4n n = ≤-transℕ (n≤2n (2 ℕ* n)) (≤-reflexiveℕ (2*2n≡4n n))
n≤4n : ∀ n → n ≤ℕ 4 ℕ* n
n≤4n n = ≤-transℕ (n≤2n n) (2n≤4n n)
*-mono-≤-nonNeg : ∀ {a a' b b' : ℚ} → 0ℚ ≤ a → a ≤ a' → 0ℚ ≤ b → b ≤ b' →
a * b ≤ a' * b'
*-mono-≤-nonNeg {a} {a'} {b} {b'} 0≤a a≤a' 0≤b b≤b' =
≤-trans (*-monoʳ-≤-nonNeg b {{nonNegative 0≤b}} a≤a')
(*-monoˡ-≤-nonNeg a' {{nonNegative (≤-trans 0≤a a≤a')}} b≤b')
recipPow2-bound : (C : ℚ) → 0ℚ ≤ C → (k : ℕ) →
Σ ℕ (λ N → ∀ n → N ≤ℕ n → C * recipPow2 n < ε k)
recipPow2-bound C 0≤C k =
N , λ n N≤n → ≤-<-trans (mono n N≤n) key
where
M : ℕ
M = proj₁ (bound-w C 0≤C)
C≤M : C ≤ embed M
C≤M = proj₂ (bound-w C 0≤C)
N : ℕ
N = suc (M ℕ* suc k)
key : embed M * recipPow2 N < ε k
key = frac-strict M k N (B<2^sucB (M ℕ* suc k))
mono : ∀ n → N ≤ℕ n → C * recipPow2 n ≤ embed M * recipPow2 N
mono n N≤n =
*-mono-≤-nonNeg 0≤C C≤M (0≤recipPow2 n) (recipPow2-mono N≤n)
≈ℝ-of-rec : (x y : RealI) (C : ℚ) → 0ℚ ≤ C →
(∀ n → ∣ centre x n - centre y n ∣ ≤ C * recipPow2 n) → x ≈ℝ y
≈ℝ-of-rec x y C 0≤C h k =
let N , w = recipPow2-bound C 0≤C k
in N , λ n N≤n → ≤-<-trans (h n) (w n N≤n)
abs-swap : ∀ a b → ∣ a - b ∣ ≡ ∣ b - a ∣
abs-swap a b = begin
∣ a - b ∣
≡⟨ cong ∣_∣ (sym (negsub b a)) ⟩
∣ neg (b - a) ∣
≡⟨ ∣-p∣≡∣p∣ (b - a) ⟩
∣ b - a ∣
∎
tri-diff : ∀ a b c → ∣ a - c ∣ ≤ ∣ a - b ∣ + ∣ b - c ∣
tri-diff a b c =
subst (λ z → ∣ z ∣ ≤ ∣ a - b ∣ + ∣ b - c ∣) (telescope a b c)
(∣p+q∣≤∣p∣+∣q∣ (a - b) (b - c))
add-self : ∀ W → W + W ≡ 2ℚ * W
add-self W =
begin
W + W
≡⟨ cong (λ z → z + W) (sym (*-identityˡ W)) ⟩
1ℚ * W + W
≡⟨ cong (λ z → 1ℚ * W + z) (sym (*-identityˡ W)) ⟩
1ℚ * W + 1ℚ * W
≡⟨ sym (*-distribʳ-+ W 1ℚ 1ℚ) ⟩
(1ℚ + 1ℚ) * W
≡⟨ cong (λ z → z * W) (sym 2ℚ≡1+1) ⟩
2ℚ * W
∎
2ℚ*half≡1 : 2ℚ * half ≡ 1ℚ
2ℚ*half≡1 = begin
2ℚ * half
≡⟨ *-inverseʳ (embed 2) {{embed2-nonZero}} ⟩
1ℚ
∎
half+half≡1 : half + half ≡ 1ℚ
half+half≡1 =
begin
half + half
≡⟨ add-self half ⟩
2ℚ * half
≡⟨ 2ℚ*half≡1 ⟩
1ℚ
∎
two-half : ∀ X → X * half + X * half ≡ X
two-half X =
begin
X * half + X * half
≡⟨ sym (*-distribˡ-+ X half half) ⟩
X * (half + half)
≡⟨ cong (X *_) half+half≡1 ⟩
X * 1ℚ
≡⟨ *-identityʳ X ⟩
X
∎
0<half : 0ℚ < half
0<half = positive⁻¹ half {{1/pos⇒pos (embed 2) {{embed-suc-pos}}}}
0≤half : 0ℚ ≤ half
0≤half = <⇒≤ 0<half
half≤1 : half ≤ 1ℚ
half≤1 =
*-cancelˡ-≤-pos 2ℚ {{embed-suc-pos {1}}}
(≤-trans (≤-reflexive 2ℚ*half≡1)
(≤-trans (embed-mono-≤ {1} {2} (s≤s z≤n))
(≤-reflexive (sym (*-identityʳ 2ℚ)))))
half-drop : ∀ {a b : ℚ} → 0ℚ ≤ a → a ≤ b → a * half ≤ b
half-drop {a} {b} 0≤a a≤b =
≤-trans (*-mono-≤-nonNeg 0≤a a≤b 0≤half half≤1)
(≤-reflexive (*-identityʳ b))
B+1-pos : (B : ℚ) → 0ℚ ≤ B → Positive (B + 1ℚ)
B+1-pos B 0≤B = positive (<-≤-trans 0<1 1≤B+1)
where
1≤B+1 : 1ℚ ≤ B + 1ℚ
1≤B+1 = ≤-trans (≤-reflexive (sym (+-identityˡ 1ℚ)))
(+-mono-≤ 0≤B (≤-refl {1ℚ}))
inv-distrib : (p q : ℚ) → .{{pp : Positive p}} → .{{qq : Positive q}} →
1/_ (p * q) {{pos⇒nonZero (p * q) {{pos*pos⇒pos p {{pp}} q {{qq}}}}}} ≡
(1/_ p {{pos⇒nonZero p {{pp}}}}) * (1/_ q {{pos⇒nonZero q {{qq}}}})
inv-distrib p q {{pp}} {{qq}} =
recip-*-hom p q
⦃ pos⇒nonZero p {{pp}} ⦄
⦃ pos⇒nonZero q {{qq}} ⦄
⦃ pos⇒nonZero (p * q) {{pos*pos⇒pos p {{pp}} q {{qq}}}} ⦄
strict-recip : (a b : ℚ) → (0<a : 0ℚ < a) → (a<b : a < b) →
1/_ b {{pos⇒nonZero b {{positive (<-≤-trans 0<a (<⇒≤ a<b))}}}}
< 1/_ a {{pos⇒nonZero a {{positive 0<a}}}}
strict-recip a b 0<a a<b =
let
0<b = <-≤-trans 0<a (<⇒≤ a<b)
a-nz = pos⇒nonZero a {{positive 0<a}}
b-nz = pos⇒nonZero b {{positive 0<b}}
ab-pos : Positive (a * b)
ab-pos = pos*pos⇒pos a {{positive 0<a}} b {{positive 0<b}}
ab-nn : NonNegative (a * b)
ab-nn = pos⇒nonNeg (a * b) {{ab-pos}}
lhs-eq : (a * b) * 1/_ b {{b-nz}} ≡ a
lhs-eq =
begin
(a * b) * 1/_ b {{b-nz}}
≡⟨ *-assoc a b _ ⟩
a * (b * 1/_ b {{b-nz}})
≡⟨ cong (a *_) (*-inverseʳ b {{b-nz}}) ⟩
a * 1ℚ
≡⟨ *-identityʳ a ⟩
a
∎
rhs-eq : b ≡ (a * b) * 1/_ a {{a-nz}}
rhs-eq =
begin
b
≡⟨ sym (*-identityʳ b) ⟩
b * 1ℚ
≡⟨ cong (b *_) (sym (*-inverseʳ a {{a-nz}})) ⟩
b * (a * 1/_ a {{a-nz}})
≡⟨ sym (*-assoc b a (1/_ a {{a-nz}})) ⟩
(b * a) * 1/_ a {{a-nz}}
≡⟨ cong (λ z → z * 1/_ a {{a-nz}}) (*-comm b a) ⟩
(a * b) * 1/_ a {{a-nz}}
∎
in *-cancelˡ-<-nonNeg (a * b) {{ab-nn}}
(<-≤-trans (≤-<-trans (≤-reflexive lhs-eq) a<b)
(≤-reflexive rhs-eq))
pick : (B : ℚ) → 0ℚ ≤ B → (k : ℕ) →
Σ ℕ (λ m → ε m * (B + 1ℚ) ≤ (ε k) ÷ embed 6)
pick B 0≤B k = m , bound
where
Bp = B + 1ℚ
1≤Bp : 1ℚ ≤ Bp
1≤Bp = ≤-trans (≤-reflexive (sym (+-identityˡ 1ℚ)))
(+-mono-≤ 0≤B (≤-refl {1ℚ}))
0<Bp : 0ℚ < Bp
0<Bp = <-≤-trans 0<1 1≤Bp
D = embed (suc k) * embed 6 * Bp
PE = embed (suc k) * embed 6
PE-pos : Positive PE
PE-pos = pos*pos⇒pos (embed (suc k)) {{embed-suc-pos}}
(embed 6) {{positive (0<embed 5)}}
0<D : 0ℚ < D
0<D = positive⁻¹ D {{pos*pos⇒pos PE {{PE-pos}} Bp {{positive 0<Bp}}}}
0≤D : 0ℚ ≤ D
0≤D = <⇒≤ 0<D
M = proj₁ (bound-w D 0≤D)
D≤M : D ≤ embed M
D≤M = proj₂ (bound-w D 0≤D)
m = suc M
0<embedM : 0ℚ < embed M
0<embedM = <-≤-trans 0<D D≤M
M≤sM : embed M ≤ embed (suc (suc M))
M≤sM = embed-mono-≤
(ℕP.m≤n⇒m≤1+n (ℕP.m≤n⇒m≤1+n (ℕP.≤-refl {M})))
M-nz : NonZero (embed M)
M-nz = pos⇒nonZero (embed M) {{positive 0<embedM}}
invM = 1/_ (embed M) {{M-nz}}
step1 : ε m ≤ invM
step1 = recip-antitone 0<embedM M≤sM
D-nz : NonZero D
D-nz = pos⇒nonZero D {{positive 0<D}}
invD = 1/_ D {{D-nz}}
step2 : invM ≤ invD
step2 = recip-antitone 0<D D≤M
εm≤1/D : ε m ≤ invD
εm≤1/D = ≤-trans step1 step2
Bp-nn : NonNegative Bp
Bp-nn = pos⇒nonNeg Bp {{positive 0<Bp}}
mult = *-monoʳ-≤-nonNeg Bp {{Bp-nn}} εm≤1/D
A = embed (suc k)
E = embed 6
P = A * E
A-nz : NonZero A
A-nz = pos⇒nonZero A {{embed-suc-pos}}
E-nz : NonZero E
E-nz = pos⇒nonZero E {{positive (0<embed 5)}}
P-pos : Positive P
P-pos = pos*pos⇒pos A {{embed-suc-pos}} E {{positive (0<embed 5)}}
Bp-pos : Positive Bp
Bp-pos = positive 0<Bp
Bp-nz : NonZero Bp
Bp-nz = pos⇒nonZero Bp {{Bp-pos}}
invBp = 1/_ Bp {{Bp-nz}}
invA = 1/_ A {{A-nz}}
invE = 1/_ E {{E-nz}}
invP = invA * invE
invD-expand : invD ≡ invA * invE * invBp
invD-expand = begin
invD
≡⟨ inv-distrib P Bp {{P-pos}} {{Bp-pos}} ⟩
(1/_ P {{pos⇒nonZero P {{P-pos}}}}) * invBp
≡⟨ cong (_* invBp) (inv-distrib A E {{embed-suc-pos}} {{positive (0<embed 5)}}) ⟩
invA * invE * invBp
∎
cancel : Bp * invD ≡ invP
cancel = begin
Bp * invD
≡⟨ cong (Bp *_) invD-expand ⟩
Bp * (invA * invE * invBp)
≡⟨ cong (Bp *_) (*-comm (invA * invE) invBp) ⟩
Bp * (invBp * (invA * invE))
≡⟨ sym (*-assoc Bp invBp (invA * invE)) ⟩
(Bp * invBp) * invP
≡⟨ cong (_* invP) (*-inverseʳ Bp {{Bp-nz}}) ⟩
1ℚ * invP
≡⟨ *-identityˡ invP ⟩
invP
∎
eq : invD * Bp ≡ (ε k) ÷ E
eq = begin
invD * Bp
≡⟨ *-comm invD Bp ⟩
Bp * invD
≡⟨ cancel ⟩
invP
≡⟨⟩
(ε k) ÷ E
∎
bound : ε m * Bp ≤ (ε k) ÷ E
bound = ≤-trans mult (≤-reflexive eq)
0<embed2 : 0ℚ < embed 2
0<embed2 = embed-mono-< (s≤s z≤n)
neg-of-nonpos : {x : ℚ} → x ≤ 0ℚ → 0ℚ ≤ neg x
neg-of-nonpos {x} x≤0 =
let step : x + neg x ≤ 0ℚ + neg x
step = +-mono-≤ x≤0 ≤-refl
lhs0 : x + neg x ≡ 0ℚ
lhs0 = +-inverseʳ x
step1 : 0ℚ ≤ 0ℚ + neg x
step1 = subst (λ z → z ≤ 0ℚ + neg x) lhs0 step
rhs : 0ℚ + neg x ≡ neg x
rhs = +-identityˡ (neg x)
in subst (λ z → 0ℚ ≤ z) rhs step1
npos⇒∣p∣≡neg : {x : ℚ} → x ≤ 0ℚ → ∣ x ∣ ≡ neg x
npos⇒∣p∣≡neg {x} x≤0 =
begin ∣ x ∣
≡⟨ sym (∣-p∣≡∣p∣ x) ⟩ ∣ neg x ∣
≡⟨ 0≤p⇒∣p∣≡p (neg-of-nonpos x≤0) ⟩ neg x ∎
halveQ : ℚ → ℚ
halveQ x = x * half
halveQ-mono : {a b : ℚ} → a ≤ b → halveQ a ≤ halveQ b
halveQ-mono {a} {b} p =
let embed2-pos : Positive (embed 2)
embed2-pos = positive (embed-mono-< (s≤s z≤n))
half≡ : half ≡ (1/_) (embed 2) {{pos⇒nonZero (embed 2) {{embed2-pos}}}}
half≡ = refl
half-pos : Positive half
half-pos = subst Positive (sym half≡)
(1/pos⇒pos (embed 2) {{embed2-pos}})
half≥0 : NonNegative half
half≥0 = pos⇒nonNeg half {{half-pos}}
in *-monoʳ-≤-nonNeg half {{half≥0}} p
0≤halveQ : {x : ℚ} → 0ℚ ≤ x → 0ℚ ≤ halveQ x
0≤halveQ {x} 0≤x =
subst (λ z → z ≤ halveQ x) (sym (*-zeroˡ half)) (halveQ-mono 0≤x)
halveQ-distrib : (a b : ℚ) → halveQ (a + b) ≡ halveQ a + halveQ b
halveQ-distrib a b = *-distribʳ-+ half a b
halveQ-double : (x : ℚ) → halveQ (x + x) ≡ x
halveQ-double x =
begin (x + x) * half
≡⟨ *-distribʳ-+ half x x ⟩ x * half + x * half
≡⟨ sym (*-distribˡ-+ x half half) ⟩ x * (half + half)
≡⟨ cong (x *_) half+half≡1 ⟩ x * 1ℚ
≡⟨ *-identityʳ x ⟩ x ∎
halveQ-neg : (a : ℚ) → halveQ (neg a) ≡ neg (halveQ a)
halveQ-neg a = sym (neg-distribˡ-* a half)
same⇒diff0 : {a b : ℚ} → a ≡ b → ∣ a - b ∣ ≡ 0ℚ
same⇒diff0 {a} {b} eq =
begin ∣ a - b ∣
≡⟨ cong ∣_∣ (trans (cong (λ x → x - b) eq) (+-inverseʳ b)) ⟩ ∣ 0ℚ ∣
≡⟨ 0≤p⇒∣p∣≡p ≤-refl ⟩ 0ℚ ∎
0≤diff : {a b : ℚ} → a ≤ b → 0ℚ ≤ b - a
0≤diff {a} {b} a≤b =
≤-trans (≤-reflexive (sym (+-inverseʳ a))) (+-mono-≤ a≤b ≤-refl)
move-≤ : {a b w : ℚ} → a - b ≤ w → a ≤ b + w
move-≤ {a} {b} {w} h =
let e : (a + neg b) + b ≡ a
e = trans (+-assoc a (neg b) b)
(trans (cong (a +_) (+-inverseˡ b)) (+-identityʳ a))
in subst (λ z → z ≤ b + w) e
(subst (λ z → (a + neg b) + b ≤ z) (+-comm w b)
(+-mono-≤ h ≤-refl))
move-≤-back : {a b w : ℚ} → a ≤ b + w → a - b ≤ w
move-≤-back {a} {b} {w} h =
let e : (b + w) + neg b ≡ w
e = trans (+-comm (b + w) (neg b))
(trans (sym (+-assoc (neg b) b w))
(trans (cong (_+ w) (+-inverseˡ b)) (+-identityˡ w)))
in subst (λ z → a + neg b ≤ z) e (+-mono-≤ h ≤-refl)
nz2n : (n : ℕ) → NonZero (embed (2 ^ n))
nz2n n = pos⇒nonZero (embed (2 ^ n)) {{pos-2^t n}}
nzSuc : (n : ℕ) → NonZero (embed (suc (2 ^ n ∸ 1)))
nzSuc n = pos⇒nonZero (embed (suc (2 ^ n ∸ 1)))
{{positive (embed-mono-< (s≤s z≤n))}}
recipPow2≡ : (n : ℕ) →
recipPow2 n ≡ (1/_) (embed (2 ^ n)) {{nz2n n}}
recipPow2≡ n =
reciprocal-cong (embed (suc (2 ^ n ∸ 1))) (embed (2 ^ n))
{{nzSuc n}} {{nz2n n}}
(embed-suc∸1 n)
recipPow2-pos : (n : ℕ) → Positive (recipPow2 n)
recipPow2-pos n =
let e-pos : Positive (embed (2 ^ n))
e-pos = positive (embed-mono-< (ℕP.≤-<-trans z≤n (n<2^n n)))
in subst Positive (sym (recipPow2≡ n))
(1/pos⇒pos (embed (2 ^ n)) {{e-pos}})
recipPow2-mul : (a b : ℕ) →
recipPow2 (a +ℕ b) ≡ recipPow2 a * recipPow2 b
recipPow2-mul a b =
let ea = embed (2 ^ a)
eb = embed (2 ^ b)
pa : Positive ea
pa = positive (embed-mono-< (ℕP.≤-<-trans z≤n (n<2^n a)))
pb : Positive eb
pb = positive (embed-mono-< (ℕP.≤-<-trans z≤n (n<2^n b)))
e0 : 2 ^ (a +ℕ b) ≡ (2 ^ a) ℕ* (2 ^ b)
e0 = ℕP.^-distribˡ-+-* 2 a b
e1 : embed (2 ^ (a +ℕ b)) ≡ ea * eb
e1 =
begin embed (2 ^ (a +ℕ b))
≡⟨ cong embed e0 ⟩
embed ((2 ^ a) ℕ* (2 ^ b))
≡⟨ embed-*-hom (2 ^ a) (2 ^ b) ⟩
ea * eb ∎
nab : NonZero (ea * eb)
nab = pos⇒nonZero (ea * eb)
{{pos*pos⇒pos ea {{pa}} eb {{pb}}}}
step : (1/_) (embed (2 ^ (a +ℕ b))) {{nz2n (a +ℕ b)}}
≡ (1/_) (ea * eb) {{nab}}
step = reciprocal-cong (embed (2 ^ (a +ℕ b))) (ea * eb)
{{nz2n (a +ℕ b)}} {{nab}} e1
in begin recipPow2 (a +ℕ b)
≡⟨ recipPow2≡ (a +ℕ b) ⟩
(1/_) (embed (2 ^ (a +ℕ b))) {{nz2n (a +ℕ b)}}
≡⟨ step ⟩
(1/_) (ea * eb) {{nab}}
≡⟨ recip-*-hom ea eb {{nz2n a}} {{nz2n b}} {{nab}} ⟩
(1/_) ea {{nz2n a}} * (1/_) eb {{nz2n b}}
≡⟨ cong₂ (λ p q → p * q) (sym (recipPow2≡ a)) (sym (recipPow2≡ b)) ⟩
recipPow2 a * recipPow2 b ∎
recipPow2-n≤1 : (n : ℕ) → recipPow2 n ≤ 1ℚ
recipPow2-n≤1 n =
let e = embed (2 ^ n)
1≤e : 1ℚ ≤ e
1≤e = embed-mono-≤ (1≤2^n n)
q : (1/_) e {{nz2n n}} ≤ 1ℚ
q = recip≤1 e 1≤e (nz2n n)
in subst (λ z → z ≤ 1ℚ) (sym (recipPow2≡ n)) q
recipPow2-≤ : (n : ℕ) → recipPow2 (n +ℕ n) ≤ recipPow2 n
recipPow2-≤ n =
let r = recipPow2 n
0≤r = 0≤recipPow2 n
e : recipPow2 (n +ℕ n) ≡ r * r
e = recipPow2-mul n n
s : r * r ≤ r
s = subst (λ z → r * r ≤ z) (*-identityʳ r)
(*-monoˡ-≤-nonNeg r {{nonNegative 0≤r}} (recipPow2-n≤1 n))
in ≤-trans (≤-reflexive e) s
frac-< : (d e : ℚ) (0<d : 0ℚ < d) {e-pos : Positive e} (C : ℚ)
→ C < d * e
→ C * (1/_) e {{pos⇒nonZero e {{e-pos}}}} < d
frac-< d e 0<d {e-pos} C h =
let ie = (1/_) e {{pos⇒nonZero e {{e-pos}}}}
ie-pos : Positive ie
ie-pos = 1/pos⇒pos e {{e-pos}}
ie·de≡d : ie * (d * e) ≡ d
ie·de≡d =
begin ie * (d * e)
≡⟨ sym (*-assoc ie d e) ⟩ (ie * d) * e
≡⟨ cong (_* e) (*-comm ie d) ⟩ (d * ie) * e
≡⟨ *-assoc d ie e ⟩ d * (ie * e)
≡⟨ cong (d *_) (*-inverseˡ e {{pos⇒nonZero e {{e-pos}}}}) ⟩
d * 1ℚ ≡⟨ *-identityʳ d ⟩ d ∎
ie·C< : ie * C < d
ie·C< = subst (λ z → ie * C < z) ie·de≡d
(*-monoʳ-<-pos ie {{ie-pos}} h)
in subst (λ z → z < d) (sym (*-comm C ie)) ie·C<
tail-bound : (C : ℚ) → 0ℚ ≤ C → (d : ℚ) → 0ℚ < d →
Σ ℕ (λ N → ∀ n → N ≤ℕ n → C * recipPow2 n < d)
tail-bound C 0≤C d 0<d =
let d-nz = pos⇒nonZero d {{positive 0<d}}
id = (1/_) d ⦃ d-nz ⦄
id-pos : Positive id
id-pos = 1/pos⇒pos d {{positive 0<d}}
q = C * id
0≤q : 0ℚ ≤ q
0≤q = subst (λ z → z ≤ q) (*-zeroˡ id)
(*-monoʳ-≤-nonNeg id {{pos⇒nonNeg id {{id-pos}}}} 0≤C)
K = proj₁ (bound-w q 0≤q)
q≤K = proj₂ (bound-w q 0≤q)
proof : ∀ n → K ≤ℕ n → C * recipPow2 n < d
proof n K≤n =
let K<2n : K Data.Nat.< 2 ^ n
K<2n = ℕP.<-≤-trans (n<2^n K) (^-monoʳ-≤ 2 K≤n)
e = embed (2 ^ n)
e-pos : Positive e
e-pos = positive (embed-mono-< (ℕP.≤-<-trans z≤n K<2n))
dq≡C : d * q ≡ C
dq≡C =
begin d * (C * id) ≡⟨ sym (*-assoc d C id) ⟩ (d * C) * id
≡⟨ cong (_* id) (*-comm d C) ⟩ (C * d) * id
≡⟨ *-assoc C d id ⟩ C * (d * id)
≡⟨ cong (C *_) (*-inverseʳ d {{d-nz}}) ⟩ C * 1ℚ
≡⟨ *-identityʳ C ⟩ C ∎
d·e>C : C < d * e
d·e>C =
let d-nn : NonNegative d
d-nn = pos⇒nonNeg d {{positive 0<d}}
in subst (λ z → z < d * e) dq≡C
(≤-<-trans (*-monoˡ-≤-nonNeg d {{d-nn}} q≤K)
(*-monoʳ-<-pos d {{positive 0<d}}
(embed-mono-< K<2n)))
in subst (λ z → C * z < d) (sym (recipPow2≡ n))
(frac-< d e 0<d {e-pos} C d·e>C)
in K , proof
add-right : {a b k l : ℚ} → ∣ a ∣ ≤ k → ∣ b ∣ ≤ l → ∣ a + b ∣ ≤ k + l
add-right {a} {b} {k} {l} pa pb =
≤-trans (∣p+q∣≤∣p∣+∣q∣ a b) (+-mono-≤ pa pb)