{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.Complete where
open import Data.Nat using (ℕ; _⊔_; _≥_) renaming (_≤_ to _≤ℕ_)
open import Data.Nat.Properties using
(m≤m⊔n; m≤n⊔m) renaming (≤-trans to ≤ℕ-trans; ≤-refl to ≤ℕ-refl)
open import Data.Product using (Σ; _,_; _×_; proj₁; proj₂)
open import Data.Rational using
(ℚ; 0ℚ; _+_; _-_; _*_; _<_; _≤_; ∣_∣; positive)
open import Data.Rational.Properties using
(≤-<-trans; +-mono-<; <-trans; +-monoʳ-<; +-identityʳ; pos*pos⇒pos;
positive⁻¹)
open import Relation.Binary.PropositionalEquality using (_≡_; sym; subst)
open import Real using (CauchySeq; half; ε; 0<ε)
open import Real.Interval using (RealI)
open import Real.IntervalEquiv using (width; centre; centre-diff)
open import Real.CauchyToInterval using
(cauchy→realI; M; centre-cauchy→realI; K; μ≤M; K≥k)
open import Real.Interval.Kit using (0<half; two-half; tri-diff)
ε-half< : ∀ k → ε k * half < ε k
ε-half< k =
let
a : ℚ
a = ε k * half
0<a : 0ℚ < a
0<a = positive⁻¹ a
{{pos*pos⇒pos (ε k) {{positive (0<ε k)}}
half {{positive 0<half}}}}
a<a+a : a < a + a
a<a+a = subst (λ z → z < a + a) (+-identityʳ a)
(+-monoʳ-< a 0<a)
a+a≡ : a + a ≡ ε k
a+a≡ = two-half (ε k)
in subst (λ z → a < z) a+a≡ a<a+a
CauchyI : (ℕ → RealI) → Set
CauchyI f = Σ (ℕ → ℕ) (λ μ →
(∀ k → μ k ≥ k) ×
(∀ k j → k ≤ℕ j → μ k ≤ℕ μ j) ×
(∀ k → (∀ n → n ≥ μ k → width (f n) k < ε k * half) ×
(∀ n m → n ≥ μ k → m ≥ μ k →
∣ centre (f n) n - centre (f m) m ∣ < ε k * half)))
toCauchy : (f : ℕ → RealI) → CauchyI f → CauchySeq
toCauchy f cf = record
{ f = λ n → centre (f n) n
; μ = proj₁ cf
; cauchy = λ k n m n≥μ m≥μ →
<-trans (proj₂ (proj₂ (proj₂ (proj₂ cf)) k) n m n≥μ m≥μ)
(ε-half< k)
}
lim : (f : ℕ → RealI) → CauchyI f → RealI
lim f cf = cauchy→realI (toCauchy f cf)
_⟶_ : (ℕ → RealI) → RealI → Set
f ⟶ L = ∀ k → Σ ℕ (λ N → ∀ n → n ≥ N →
∣ centre (f n) k - centre L k ∣ < ε k)
complete : (f : ℕ → RealI) (cf : CauchyI f) → f ⟶ lim f cf
complete f cf k = N , proof
where
μ : ℕ → ℕ
μ = proj₁ cf
μ≥ : ∀ i → μ i ≥ i
μ≥ = proj₁ (proj₂ cf)
μ-mono : ∀ i j → i ≤ℕ j → μ i ≤ℕ μ j
μ-mono = proj₁ (proj₂ (proj₂ cf))
width-cond : ∀ i n → n ≥ μ i → width (f n) i < ε i * half
width-cond i = proj₁ (proj₂ (proj₂ (proj₂ cf)) i)
centre-cond : ∀ i n m → n ≥ μ i → m ≥ μ i →
∣ centre (f n) n - centre (f m) m ∣ < ε i * half
centre-cond i = proj₂ (proj₂ (proj₂ (proj₂ cf)) i)
cs : CauchySeq
cs = toCauchy f cf
L : RealI
L = cauchy→realI cs
j : ℕ
j = M cs k
j≥μk : j ≥ μ k
j≥μk = ≤ℕ-trans (μ-mono k (K k) (K≥k k))
(μ≤M cs k)
centre-L : centre L k ≡ centre (f j) j
centre-L = centre-cauchy→realI cs k
N : ℕ
N = μ k ⊔ j
N≥μk : N ≥ μ k
N≥μk = m≤m⊔n (μ k) j
N≥j : N ≥ j
N≥j = m≤n⊔m (μ k) j
proof : ∀ n → n ≥ N → ∣ centre (f n) k - centre L k ∣ < ε k
proof n n≥N =
let
n≥μk : n ≥ μ k
n≥μk = ≤ℕ-trans N≥μk n≥N
n≥j : n ≥ j
n≥j = ≤ℕ-trans N≥j n≥N
k≤j : k ≤ℕ j
k≤j = ≤ℕ-trans (μ≥ k) j≥μk
k≤n : k ≤ℕ n
k≤n = ≤ℕ-trans k≤j n≥j
tri1 : ∣ centre (f n) k - centre (f n) n ∣ ≤ width (f n) k
tri1 = centre-diff (f n) k k n (≤ℕ-refl {k}) k≤n
first : ∣ centre (f n) k - centre (f n) n ∣ < ε k * half
first = ≤-<-trans tri1 (width-cond k n n≥μk)
second : ∣ centre (f n) n - centre (f j) j ∣ < ε k * half
second = centre-cond k n j n≥μk j≥μk
tri : ∣ centre (f n) k - centre (f j) j ∣
< ε k * half + ε k * half
tri = ≤-<-trans
(tri-diff (centre (f n) k) (centre (f n) n) (centre (f j) j))
(+-mono-< first second)
sum-eps : ε k * half + ε k * half ≡ ε k
sum-eps = two-half (ε k)
final : ∣ centre (f n) k - centre L k ∣ < ε k
final = subst (λ z → ∣ centre (f n) k - z ∣ < ε k)
(sym centre-L)
(subst (λ z → ∣ centre (f n) k - centre (f j) j ∣ < z)
sum-eps
tri)
in final