{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Pushback where
open import Data.Nat using (ℕ; zero; suc; s≤s; z≤n; _⊔_; _≥_; _*_; _^_)
renaming (_+_ to _+N_; _≤_ to _≤N_; _<_ to _<N_)
open import Data.Nat.Properties as ℕP using (≤-trans; m≤m+n; m≤m⊔n; m≤n⊔m; +-suc)
open import Data.Product using (Σ; _,_)
open import Data.Rational using (ℚ; _+_; _-_; _<_; _≤_; ∣_∣)
open import Data.Rational.Properties using
(<⇒≤; ≤-<-trans; +-mono-<-≤) renaming (<-trans to ℚ<-trans)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; trans; subst; sym; cong)
open import Real using (CauchySeq; ε; 0<ε; embed; 0<embed; ε-half; embed-mono-<)
open CauchySeq renaming (f to seq-f; μ to seq-μ; cauchy to seq-cauchy)
open import Real.Convergence using (Converges)
open import Real.Interval using (RealI)
open import Real.IntervalEquiv using (node; centre; n<2^n)
open import Real.Interval.Kit using (tri-diff; strict-recip)
open import Real.Interval.Complete using (_⟶_)
open import Real.CauchyToInterval using
(cauchy→realI; M; K; μ≤M; point; centre-point; centre-cauchy→realI)
ε-< : ∀ {i j} → i Data.Nat.< j → ε j < ε i
ε-< {i} {j} i<j = strict-recip (embed (suc i)) (embed (suc j))
(0<embed i) (embed-mono-< (s≤s i<j))
centre-approximates : (x : CauchySeq) (l : ℚ) →
Converges (seq-f x) l →
∀ k → Σ ℕ λ n →
∣ centre (cauchy→realI x) n - l ∣ < ε k
centre-approximates x l cv k =
let h = suc (2 * k)
n = h
N0 , w0 = cv (ε h) (0<ε h)
mn = M x n ⊔ N0
M≤mn = ℕP.m≤m⊔n (M x n) N0
N0≤mn = ℕP.m≤n⊔m (M x n) N0
h<2h : h <N 2 ^ h
h<2h = n<2^n h
1<2 : 1 <N 2
1<2 = s≤s (s≤s z≤n)
h≤s : h ≤N suc h
h≤s = ℕP.n≤1+n h
h<ss : h <N suc (suc h)
h<ss = s≤s h≤s
2h<Kh : 2 ^ h <N 2 ^ suc (suc h)
2h<Kh = ℕP.^-monoʳ-< 2 1<2 h<ss
h<Kh : h <N K h
h<Kh = ℕP.<-trans h<2h 2h<Kh
μ≤mn : seq-μ x (K n) ≤N mn
μ≤mn = ℕP.≤-trans (μ≤M x n) M≤mn
c1 : ∣ seq-f x (M x n) - seq-f x mn ∣ < ε (K n)
c1 = seq-cauchy x (K n) (M x n) mn (μ≤M x n) μ≤mn
c1′ : ∣ seq-f x (M x n) - seq-f x mn ∣ < ε h
c1′ = ℚ<-trans c1 (ε-< h<Kh)
c2 : ∣ seq-f x mn - l ∣ < ε h
c2 = w0 mn N0≤mn
sum< : ∣ seq-f x (M x n) - seq-f x mn ∣ + ∣ seq-f x mn - l ∣ < ε h + ε h
sum< = +-mono-<-≤ c1′ (<⇒≤ c2)
tri≤ : ∣ seq-f x (M x n) - l ∣ ≤
∣ seq-f x (M x n) - seq-f x mn ∣ + ∣ seq-f x mn - l ∣
tri≤ = tri-diff (seq-f x (M x n)) (seq-f x mn) l
bound : ∣ seq-f x (M x n) - l ∣ < ε h + ε h
bound = ≤-<-trans tri≤ sum<
final : ∣ seq-f x (M x n) - l ∣ < ε k
final = subst (λ z → ∣ seq-f x (M x n) - l ∣ < z) (ε-half k) bound
eq = centre-cauchy→realI x n
in n , subst (λ z → ∣ z - l ∣ < ε k) (sym eq) final
node-next : (r : RealI) (k : ℕ) →
node (RealI.next r) k ≡ RealI.next (node r k)
node-next r zero = refl
node-next r (suc k) = cong RealI.next (node-next r k)
centre-shift : (x : RealI) (n k : ℕ) →
centre (node x n) k ≡ centre x (n +N k)
centre-shift x zero k = refl
centre-shift x (suc n) k =
trans (cong (λ r → centre r zero) (node-next (node x n) k))
(trans (centre-shift x n (suc k))
(cong (centre x) (+-suc n k)))
tail-seq : CauchySeq → ℕ → RealI
tail-seq x n = node (cauchy→realI x) n
pushback : (x : CauchySeq) (l : ℚ) →
Converges (seq-f x) l → tail-seq x ⟶ point l
pushback x l cv k =
let h = suc (2 * k)
N0 , w0 = cv (ε h) (0<ε h)
bound-at : (j : ℕ) → j ≥ h →
∣ seq-f x (M x j) - l ∣ < ε k
bound-at j j≥h =
let mn = M x j ⊔ N0
M≤mn = m≤m⊔n (M x j) N0
N0≤mn = m≤n⊔m (M x j) N0
μ≤mn = ≤-trans (μ≤M x j) M≤mn
h<Kh : h <N K h
h<Kh = ℕP.<-≤-trans (n<2^n h)
(ℕP.^-monoʳ-≤ 2 (ℕP.m≤n+m h 2))
Kh≤Kj : K h ≤N K j
Kh≤Kj = ℕP.^-monoʳ-≤ 2 (s≤s (s≤s j≥h))
h<Kj : h <N K j
h<Kj = ℕP.<-≤-trans h<Kh Kh≤Kj
c1 = seq-cauchy x (K j) (M x j) mn (μ≤M x j) μ≤mn
c1′ = ℚ<-trans c1 (ε-< h<Kj)
c2 = w0 mn N0≤mn
sum< = +-mono-<-≤ c1′ (<⇒≤ c2)
tri≤ = tri-diff (seq-f x (M x j)) (seq-f x mn) l
bound = ≤-<-trans tri≤ sum<
in subst (λ z → ∣ seq-f x (M x j) - l ∣ < z) (ε-half k) bound
proof : (n : ℕ) → n ≥ h →
∣ centre (tail-seq x n) k - centre (point l) k ∣ < ε k
proof n n≥h =
let j = n +N k
j≥h : j ≥ h
j≥h = ℕP.≤-trans n≥h (m≤m+n n k)
cs = centre-shift (cauchy→realI x) n k
cp = centre-point l k
eq : centre (tail-seq x n) k ≡ seq-f x (M x j)
eq = trans cs (centre-cauchy→realI x j)
b = bound-at j j≥h
in subst (λ z → ∣ z - centre (point l) k ∣ < ε k) (sym eq)
(subst (λ z → ∣ seq-f x (M x j) - z ∣ < ε k) (sym cp) b)
in h , proof