{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.LimitLaws where
open import Data.Empty using (⊥; ⊥-elim)
open import Data.Nat using (ℕ; suc; _≥_; _⊔_; s≤s) renaming (_≤_ to _≤ℕ_)
open import Data.Nat.Properties using (m≤m⊔n; m≤n⊔m)
open import Data.Product using (_,_)
open import Data.Rational using (0ℚ; _+_; _-_; _*_; _<_; _≤_; ∣_∣)
renaming (-_ to neg)
open import Data.Rational.Base using (positive)
open import Data.Rational.Properties using
(≤-refl; ≤-trans; ≤-<-trans; <-trans; <-irrefl; +-mono-<; +-inverseʳ
; 0≤p⇒∣p∣≡p; <⇒≤; pos*pos⇒pos; +-monoʳ-<; +-assoc; +-comm; positive⁻¹
; module ≤-Reasoning)
open ≤-Reasoning renaming (begin_ to begin≤_; _∎ to _≤∎)
open import Data.Sum using (inj₁; inj₂)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; sym; trans; cong; cong₂; subst; subst₂)
open import Relation.Nullary using (¬_)
open import Real using (ε; 0<ε; half; embed; embed-mono-≤; embed-suc-pos)
open import Real.Archimedean using (ε-archimedean)
open import Real.Interval using (RealI)
open import Real.IntervalEquiv using (centre; l; u; centre-l; centre-u)
open import Real.Interval.Arith using (negℝ)
open import Real.Interval.Complete using (_⟶_)
open import Real.Interval.Node using (centre-neg)
open import Real.Interval.Equiv using (_≈ℝ_)
open import Real.Interval.Rational using (r≤|r|; pos-diff)
open import Real.Interval.Kit using (recip-antitone; two-half; abs-swap; 0<half)
open import Real.Interval.Order using
(_<ℝ_) renaming (l-mono' to l-monoℓ; u-mono' to u-monoℓ)
open import Real.Interval.Apartness using (_#ℝ_)
open import Real.Interval.OrderLe using (≤ℝ-antisym; sub-mono)
open import Real.Interval.Mul using (cancelʳ; cancel-z)
open import Real.Interval.Mul.Order using (abs-neg)
ε-mono : ∀ {a b} → a ≤ℕ b → ε b ≤ ε a
ε-mono {a} {b} a≤b =
recip-antitone (positive⁻¹ (embed (suc a)) {{embed-suc-pos}})
(embed-mono-≤ (s≤s a≤b))
⟶-const : (c : RealI) → (λ (_ : ℕ) → c) ⟶ c
⟶-const c k = 0 , λ _ _ →
≤-<-trans
(begin≤
∣ centre c k - centre c k ∣
≡⟨ cong ∣_∣ (+-inverseʳ (centre c k)) ⟩
∣ 0ℚ ∣
≡⟨ 0≤p⇒∣p∣≡p {0ℚ} ≤-refl ⟩
0ℚ
≤∎)
(0<ε k)
⟶-neg : ∀ {f L} → f ⟶ L → (λ n → negℝ (f n)) ⟶ negℝ L
⟶-neg {f} {L} conv k =
let N , h = conv k
in N , λ n n≥N →
let
d = centre (f n) k - centre L k
e = h n n≥N
in ≤-<-trans
(begin≤
∣ centre (negℝ (f n)) k - centre (negℝ L) k ∣
≡⟨ cong₂ (λ a b → ∣ a - b ∣)
(centre-neg (f n) k) (centre-neg L k) ⟩
∣ neg (centre (f n) k) - neg (centre L k) ∣
≡⟨ abs-neg {centre (f n) k} {centre L k} ⟩
∣ d ∣
≤∎)
e
tight : ∀ {x y} → ¬ (x #ℝ y) → x ≈ℝ y
tight {x} {y} ¬x#y = ≤ℝ-antisym ¬y<x ¬x<y
where
¬y<x : ¬ (y <ℝ x)
¬y<x y<x = ¬x#y (inj₂ y<x)
¬x<y : ¬ (x <ℝ y)
¬x<y x<y = ¬x#y (inj₁ x<y)
add-right-< : ∀ {x y z} → x < y → x + z < y + z
add-right-< {x} {y} {z} x<y =
subst₂ (λ a b → a < b) (+-comm z x) (+-comm z y)
(+-monoʳ-< z x<y)
abs<⇒upper : ∀ {a c e} → ∣ c - a ∣ < e → c < a + e
abs<⇒upper {a} {c} {e} h =
let d< : c - a < e
d< = ≤-<-trans (r≤|r| (c - a)) h
add : (c - a) + a < e + a
add = add-right-< d<
lhs : (c - a) + a ≡ c
lhs = cancelʳ c a
rhs : e + a ≡ a + e
rhs = +-comm e a
in subst (λ z → c < z) rhs (subst (λ z → z < e + a) lhs add)
abs<⇒lower : ∀ {a c e} → ∣ c - a ∣ < e → a - e < c
abs<⇒lower {a} {c} {e} h =
let h' : ∣ a - c ∣ < e
h' = subst (λ z → z < e) (sym (abs-swap a c)) h
d< : a - c < e
d< = ≤-<-trans (r≤|r| (a - c)) h'
add : (a - c) + c < e + c
add = add-right-< d<
lhs : (a - c) + c ≡ a
lhs = cancelʳ a c
a< : a < e + c
a< = subst (λ z → z < e + c) lhs add
step : a - e < (e + c) - e
step = add-right-< a<
rhs≡ : (e + c) - e ≡ c
rhs≡ = cancel-z e c
in subst (λ z → a - e < z) rhs≡ step
gap-chain :
∀ {a b c e} → b - e < c → c < a + e → b - a < e + e
gap-chain {a} {b} {c} {e} lo hi =
let
mid : b - e < a + e
mid = ≤-<-trans (<⇒≤ lo) hi
add-e : (b - e) + e < (a + e) + e
add-e = add-right-< mid
lhs≡ : (b - e) + e ≡ b
lhs≡ = cancelʳ b e
b< : b < (a + e) + e
b< = subst (λ z → z < (a + e) + e) lhs≡ add-e
rhs≡ : (a + e) + e - a ≡ e + e
rhs≡ =
trans
(cong (_- a) (+-assoc a e e))
(cancel-z a (e + e))
in subst (λ z → b - a < z) rhs≡ (add-right-< b<)
gap-contradiction :
∀ {A B f j} → f ⟶ A → f ⟶ B → u A j < l B j → ⊥
gap-contradiction {A} {B} {f} {j} convA convB gap =
let
g = l B j - u A j
0<g : 0ℚ < g
0<g = pos-diff (u A j) (l B j) gap
q , εq< = ε-archimedean (g * half)
(positive⁻¹ (g * half)
{{pos*pos⇒pos g {{positive 0<g}} half {{positive 0<half}}}})
p = q ⊔ j
q≤p : q ≤ℕ p
q≤p = m≤m⊔n q j
j≤p : j ≤ℕ p
j≤p = m≤n⊔m q j
εp< : ε p < g * half
εp< = ≤-<-trans (ε-mono q≤p) εq<
N1 , w1 = convA p
N2 , w2 = convB p
N = N1 ⊔ N2
n≥N1 : N ≥ N1
n≥N1 = m≤m⊔n N1 N2
n≥N2 : N ≥ N2
n≥N2 = m≤n⊔m N1 N2
c = centre (f N) p
eA = w1 N n≥N1
eB = w2 N n≥N2
upper : c < centre A p + ε p
upper = abs<⇒upper eA
lower : centre B p - ε p < c
lower = abs<⇒lower eB
cA≤uAj : centre A p ≤ u A j
cA≤uAj = ≤-trans (centre-u A p) (u-monoℓ A j≤p)
cB≥lBj : l B j ≤ centre B p
cB≥lBj = ≤-trans (l-monoℓ B j≤p) (centre-l B p)
g≤sep : g ≤ centre B p - centre A p
g≤sep = sub-mono cB≥lBj cA≤uAj
sep<2ε : centre B p - centre A p < ε p + ε p
sep<2ε =
gap-chain {a = centre A p} {b = centre B p} {c = c} {e = ε p}
lower upper
2ε<g : ε p + ε p < g
2ε<g =
subst (λ z → ε p + ε p < z) (two-half g)
(+-mono-< εp< εp<)
g<2ε : g < ε p + ε p
g<2ε = ≤-<-trans g≤sep sep<2ε
in ⊥-elim (<-irrefl refl (<-trans g<2ε 2ε<g))
⟶-unique : ∀ {f L M} → f ⟶ L → f ⟶ M → L ≈ℝ M
⟶-unique {f} {L} {M} convL convM = tight ¬L#M
where
¬L#M : ¬ (L #ℝ M)
¬L#M (inj₁ (j , gap)) =
gap-contradiction {A = L} {B = M} {f = f} {j = j} convL convM gap
¬L#M (inj₂ (j , gap)) =
gap-contradiction {A = M} {B = L} {f = f} {j = j} convM convL gap