{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.RetractCauchy where
open import Data.Nat using (ℕ; suc; _⊔_; _^_; s≤s)
renaming (_≤_ to _≤N_; _≥_ to _≥N_; _*_ to _*ℕ_; _<_ to _<N_)
open import Data.Nat.Properties using (m≤m⊔n; m≤n⊔m; m≤m+n; m≤n+m; n<1+n; ^-monoʳ-≤)
renaming (≤-trans to ≤N-trans; ≤-<-trans to ≤N-<-trans; <-≤-trans to <N-≤-trans)
open import Data.Rational using
(ℚ; 0ℚ; 1ℚ; _+_; _-_; -_; _*_; _<_; _≤_; ∣_∣; 1/_; positive; Positive
; NonZero; NonNegative; nonNegative)
open import Data.Rational.Properties using
(≤-refl; ≤-reflexive; ≤-trans; <⇒≤; ≤-<-trans; <-≤-trans; <-trans; +-mono-<
; +-monoʳ-<; +-mono-≤; +-inverseʳ; ∣p+q∣≤∣p∣+∣q∣; ∣-p∣≡∣p∣
; positive⁻¹; *-inverseʳ; *-inverseˡ; 0≤p⇒∣p∣≡p; *-identityʳ; *-assoc
; *-comm; *-monoˡ-≤-nonNeg; *-monoʳ-<-pos; +-assoc; +-comm)
renaming (1/pos⇒pos to pos-recip)
open import Data.Product using (_,_)
open import Data.Sum using (inj₁; inj₂)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; cong; sym; trans; module ≡-Reasoning)
open ≡-Reasoning
open import Base.RationalRing using (telescope)
open import Real using
(CauchySeq; ε; 0<ε; embed; _s≈_; _≈_; embed-mono-≤; ε-half; embed-mono-<)
open Real.CauchySeq using (f; μ; cauchy)
open import Real.Interval.Equiv using (_≈ℝ_)
open import Real.IntervalEquiv using (realI→cauchy; centre; n<2^n)
open import Real.CauchyToInterval using
(cauchy→realI; M; K; centre-cauchy→realI; μ≤M; K≥k)
open import Real.Interval.Kit using (npos⇒∣p∣≡neg)
open import Real.Regular using (regularize; μr; μr≥k; μr-mono≤)
open import Real.Interval.Rational using (r≤|r|; negsub)
reassoc3 : ∀ (a b c : ℚ) → (a + b) + c ≡ b + (a + c)
reassoc3 a b c = begin
(a + b) + c
≡⟨ cong (λ v → v + c) (+-comm a b) ⟩
(b + a) + c
≡⟨ +-assoc b a c ⟩
b + (a + c) ∎
regularize≈ : (x : CauchySeq) → regularize x ≈ x
regularize≈ x k = 0 , λ n _ →
let q = f x n
eq : q + (- q) ≡ 0ℚ
eq = +-inverseʳ q
d : (q + (- q)) < ε k
d = ≤-<-trans (≤-reflexive eq) (0<ε k)
in (d , d)
realI→cauchy-cong : ∀ {x y} → x ≈ℝ y → realI→cauchy x ≈ realI→cauchy y
realI→cauchy-cong {x} {y} p k =
let N , h = p k
in N , λ n n≥N →
let d : ∣ centre x n - centre y n ∣ < ε k
d = h n n≥N
q = centre x n - centre y n
fwd : q < ε k
fwd = ≤-<-trans (r≤|r| q) d
r2 = centre y n - centre x n
bwd : r2 < ε k
bwd = ≤-<-trans (r≤|r| r2)
(≤-<-trans (≤-reflexive (sym (cong ∣_∣ (negsub (centre x n) (centre y n)))))
(≤-<-trans (≤-reflexive (∣-p∣≡∣p∣ q)) d))
in (fwd , bwd)
regular-retract : (x : CauchySeq)
→ realI→cauchy (cauchy→realI (regularize x)) ≈ regularize x
regular-retract x k = μr x k , body
where
z = regularize x
body : (n : ℕ) → n ≥N μr x k →
_s≈_ (f (realI→cauchy (cauchy→realI z)) n) (f z n) k
body n n≥N rewrite centre-cauchy→realI z n =
let
k≤n : k ≤N n
k≤n = ≤N-trans (μr≥k x k) n≥N
k≤Kn : k ≤N K n
k≤Kn = ≤N-trans k≤n (K≥k n)
M≥ : M z n ≥N μr x k
M≥ = ≤N-trans (μr-mono≤ x k (K n) k≤Kn)
(μ≤M z n)
d : ∣ f z (M z n) - f z n ∣ < ε k
d = Real.CauchySeq.cauchy z k (M z n) n M≥ n≥N
q = f z (M z n) - f z n
fwd : q < ε k
fwd = ≤-<-trans (r≤|r| q) d
r2 = f z n - f z (M z n)
bwd : r2 < ε k
bwd = ≤-<-trans (r≤|r| r2)
(≤-<-trans (≤-reflexive (sym (cong ∣_∣ (negsub (f z (M z n)) (f z n)))))
(≤-<-trans (≤-reflexive (∣-p∣≡∣p∣ q)) d))
in (fwd , bwd)
private
recip-antitone : ∀ (p q : ℚ) → 0ℚ < p → p ≤ q
→ .{{p-nz : NonZero p}} → .{{q-nz : NonZero q}} → (1/ q) ≤ (1/ p)
recip-antitone p q 0<p p≤q =
let iq = 1/ q
ip = 1/ p
0<q : 0ℚ < q
0<q = <-≤-trans 0<p p≤q
pos-ip : Positive ip
pos-ip = pos-recip p {{positive 0<p}}
pos-iq : Positive iq
pos-iq = pos-recip q {{positive 0<q}}
0<ip : 0ℚ < ip
0<ip = positive⁻¹ ip {{pos-ip}}
0<iq : 0ℚ < iq
0<iq = positive⁻¹ iq {{pos-iq}}
0≤iq : 0ℚ ≤ iq
0≤iq = <⇒≤ 0<iq
instance nonNeg-iq : NonNegative iq
nonNeg-iq = nonNegative 0≤iq
instance nonNeg-ip : NonNegative ip
nonNeg-ip = nonNegative (<⇒≤ 0<ip)
inv : iq * q ≡ 1ℚ
inv = *-inverseˡ q
t≤1 : iq * p ≤ 1ℚ
t≤1 = ≤-trans (*-monoˡ-≤-nonNeg iq {{nonNeg-iq}} p≤q)
(≤-reflexive inv)
in ≤-trans
(≤-reflexive (sym (*-identityʳ iq)))
(≤-trans
(≤-reflexive (cong (λ v → iq * v) (sym (*-inverseʳ p))))
(≤-trans
(≤-reflexive (sym (*-assoc iq p ip)))
(≤-trans
(≤-reflexive (*-comm (iq * p) ip))
(≤-trans
(*-monoˡ-≤-nonNeg ip {{nonNeg-ip}} t≤1)
(≤-reflexive (*-identityʳ ip))))))
recip-antitone-strict : ∀ (p q : ℚ)
→ .{{p-nz : NonZero p}} → .{{q-nz : NonZero q}}
→ 0ℚ < p → p < q → (1/ q) {{q-nz}} < (1/ p) {{p-nz}}
recip-antitone-strict p q 0<p p<q =
let iq = 1/ q
ip = 1/ p
0<q : 0ℚ < q
0<q = ≤-<-trans (<⇒≤ 0<p) p<q
pos-ip : Positive ip
pos-ip = pos-recip p {{positive 0<p}}
pos-iq : Positive iq
pos-iq = pos-recip q {{positive 0<q}}
s1 : iq * p < iq * q
s1 = *-monoʳ-<-pos iq {{pos-iq}} p<q
s2 : ip * (iq * p) < ip * (iq * q)
s2 = *-monoʳ-<-pos ip {{pos-ip}} s1
lhs : iq ≡ ip * (iq * p)
lhs = begin
iq
≡⟨ sym (*-identityʳ iq) ⟩
iq * 1ℚ
≡⟨ cong (λ v → iq * v) (sym (*-inverseʳ p)) ⟩
iq * (p * ip)
≡⟨ cong (λ v → iq * v) (*-comm p ip) ⟩
iq * (ip * p)
≡⟨ sym (*-assoc iq ip p) ⟩
(iq * ip) * p
≡⟨ cong (λ v → v * p) (*-comm iq ip) ⟩
(ip * iq) * p
≡⟨ *-assoc ip iq p ⟩
ip * (iq * p) ∎
rhs : ip * (iq * q) ≡ ip
rhs = begin
ip * (iq * q)
≡⟨ cong (λ v → ip * v) (*-inverseˡ q) ⟩
ip * 1ℚ
≡⟨ *-identityʳ ip ⟩
ip ∎
in ≤-<-trans (≤-reflexive lhs)
(<-≤-trans s2 (≤-reflexive rhs))
ε≤ : ∀ a b → b ≤N a → ε a ≤ ε b
ε≤ a b b≤a =
recip-antitone (embed (suc b)) (embed (suc a))
(positive⁻¹ (embed (suc b))) (embed-mono-≤ (s≤s b≤a))
ε< : ∀ a b → b <N a → ε a < ε b
ε< a b b<a =
recip-antitone-strict (embed (suc b)) (embed (suc a))
(positive⁻¹ (embed (suc b)))
(embed-mono-< (s≤s b<a))
both<⇒abs< : ∀ q e → q < e → - q < e → ∣ q ∣ < e
both<⇒abs< q e fwd bwd with Data.Rational.Properties.≤-total q 0ℚ
... | inj₁ q≤0 =
≤-<-trans (≤-reflexive (npos⇒∣p∣≡neg q≤0)) bwd
... | inj₂ 0≤q =
≤-<-trans (≤-reflexive (0≤p⇒∣p∣≡p 0≤q)) fwd
2ε<εr : ∀ r n → ε n < ε (suc (2 *ℕ r)) → ε n + ε n < ε r
2ε<εr r n d =
<-≤-trans (+-mono-< d d)
(≤-reflexive (ε-half r))
ε3<εk : ∀ r k n → ε n + ε n < ε r →
r ≡ suc (2 *ℕ suc (2 *ℕ k)) → ε n + ε r + ε n < ε k
ε3<εk r k n d eq =
let s = suc (2 *ℕ k)
en = ε n
er = ε r
es = ε s
e1 : en + er + en ≡ er + (en + en)
e1 = reassoc3 en er en
strict : er + (en + en) < er + er
strict = +-monoʳ-< er d
e2 : er + er ≡ es
e2 = begin
er + er
≡⟨ cong (λ i → ε i + ε i) eq ⟩
ε (suc (2 *ℕ s)) + ε (suc (2 *ℕ s))
≡⟨ ε-half s ⟩
es ∎
e3 : es < ε k
e3 = ε< s k (≤N-trans (n<1+n k) (s≤s (m≤m+n k (1 *ℕ k))))
in ≤-<-trans (≤-reflexive e1)
(<-trans (<-≤-trans strict (≤-reflexive e2)) e3)
cauchy→realI-cong : ∀ {x y} → x ≈ y → cauchy→realI x ≈ℝ cauchy→realI y
cauchy→realI-cong {x} {y} p k = Nth , body
where
r0 : ℕ
r0 = suc (2 *ℕ suc (2 *ℕ k))
Nth : ℕ
Nth = suc (2 *ℕ r0)
core : ∀ n → n ≥N Nth →
∣ f x (M x n) - f y (M y n) ∣ < ε k
core n n≥N =
let r = r0
N0 , w0 = p r
c = M x n ⊔ M y n ⊔ N0
c≥Mx : c ≥N M x n
c≥Mx = ≤N-trans (m≤m⊔n (M x n) (M y n)) (m≤m⊔n (M x n ⊔ M y n) N0)
c≥My : c ≥N M y n
c≥My = ≤N-trans (m≤n⊔m (M x n) (M y n)) (m≤m⊔n (M x n ⊔ M y n) N0)
c≥N0 : c ≥N N0
c≥N0 = m≤n⊔m (M x n ⊔ M y n) N0
c≥μxKn : c ≥N μ x (K n)
c≥μxKn = ≤N-trans (μ≤M x n) c≥Mx
c≥μyKn : c ≥N μ y (K n)
c≥μyKn = ≤N-trans (μ≤M y n) c≥My
leg1 : ∣ f x (M x n) - f x c ∣ < ε (K n)
leg1 = cauchy x (K n) (M x n) c (μ≤M x n) c≥μxKn
leg3 : ∣ f y c - f y (M y n) ∣ < ε (K n)
leg3 = cauchy y (K n) c (M y n) c≥μyKn (μ≤M y n)
fwd , bwd = w0 c c≥N0
bwd' : - (f x c - f y c) < ε r
bwd' = ≤-<-trans (≤-reflexive (negsub (f x c) (f y c))) bwd
mid : ∣ f x c - f y c ∣ < ε r
mid = both<⇒abs< (f x c - f y c) (ε r) fwd bwd'
a = f x (M x n) - f x c
b = f x c - f y c
d = f y c - f y (M y n)
ab-eq : a + b ≡ f x (M x n) - f y c
ab-eq = telescope (f x (M x n)) (f x c) (f y c)
t1 : (f x (M x n) - f y c) + d ≡ f x (M x n) - f y (M y n)
t1 = telescope (f x (M x n)) (f y c) (f y (M y n))
abd-eq : (a + b) + d ≡ f x (M x n) - f y (M y n)
abd-eq = trans (cong (λ v → v + d) ab-eq) t1
abs1 : ∣ a + b ∣ ≤ ∣ a ∣ + ∣ b ∣
abs1 = ∣p+q∣≤∣p∣+∣q∣ a b
abs2 : ∣ (a + b) + d ∣ ≤ ∣ a + b ∣ + ∣ d ∣
abs2 = ∣p+q∣≤∣p∣+∣q∣ (a + b) d
abs3 : ∣ (a + b) + d ∣ ≤ ∣ a ∣ + ∣ b ∣ + ∣ d ∣
abs3 = ≤-trans abs2 (+-mono-≤ abs1 ≤-refl)
tri : ∣ (a + b) + d ∣ < ε (K n) + ε r + ε (K n)
tri = ≤-<-trans abs3
(Data.Rational.Properties.+-mono-<
(Data.Rational.Properties.+-mono-<
leg1 mid) leg3)
n<2n : n <N 2 ^ n
n<2n = n<2^n n
2n≤Kn : 2 ^ n ≤N K n
2n≤Kn = ^-monoʳ-≤ 2 (m≤n+m n 2)
n<Kn : n <N K n
n<Kn = <N-≤-trans n<2n 2n≤Kn
Kn> : Nth <N K n
Kn> = ≤N-<-trans n≥N n<Kn
eKn< : ε (K n) < ε Nth
eKn< = ε< (K n) Nth Kn>
half2 : ε (K n) + ε (K n) < ε r
half2 = 2ε<εr r (K n) eKn<
total : ε (K n) + ε r + ε (K n) < ε k
total = ε3<εk r k (K n) half2 refl
goal : ∣ f x (M x n) - f y (M y n) ∣ < ε k
goal = ≤-<-trans
(≤-reflexive (cong ∣_∣ (sym abd-eq)))
(<-trans tri total)
in goal
body : ∀ n → n ≥N Nth →
∣ centre (cauchy→realI x) n - centre (cauchy→realI y) n ∣ < ε k
body n n≥Nth
rewrite centre-cauchy→realI x n | centre-cauchy→realI y n = core n n≥Nth
realI→cauchy-retract : (x : CauchySeq)
→ realI→cauchy (cauchy→realI x) ≈ x
realI→cauchy-retract x =
let z = regularize x
a = realI→cauchy (cauchy→realI x)
b = realI→cauchy (cauchy→realI z)
x≈z : x ≈ z
x≈z = Real.≈-sym {x = x} {y = z} (regularize≈ x)
step1 : cauchy→realI x ≈ℝ cauchy→realI z
step1 = cauchy→realI-cong x≈z
step2 : a ≈ b
step2 = realI→cauchy-cong step1
step3 : b ≈ z
step3 = regular-retract x
step4 : a ≈ z
step4 = Real.≈-trans {x = a} {y = b} {z = z} step2 step3
in Real.≈-trans {x = a} {y = z} {z = x} step4 (regularize≈ x)