{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.Countermodel where
open import Data.Nat using (ℕ; zero; suc; z≤n)
open import Data.Product using (_,_)
open import Data.Rational using (ℚ; 0ℚ; _+_; _-_; _*_; _<_; _≤_; ∣_∣)
renaming (-_ to neg)
open import Data.Rational.Base using (positive; _÷_; 1/_)
open import Data.Rational.Properties using
(≤-refl; ≤-reflexive; ≤-trans; ≤-<-trans; <-trans; <-irrefl; +-mono-<
; +-mono-<-≤; +-inverseˡ; +-inverseʳ; +-identityˡ; +-identityʳ; +-assoc; +-comm
; neg-distrib-+; neg-antimono-<; 0≤p⇒∣p∣≡p; <⇒≤; positive⁻¹; pos*pos⇒pos
; +-mono-≤; *-assoc; *-comm; *-identityˡ; *-inverseʳ; pos⇒nonZero; *-zeroˡ)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; sym; trans; cong; cong₂; subst; subst₂)
open import Base.RationalRing using (neg-involutive; +interchange)
open import Relation.Nullary using (¬_)
open import Real using (ε; 0<ε; half; embed; 2ℚ)
open import Real.Interval using (RealI; Nest; pos-pow)
open import Real.IntervalEquiv using
(centre; l; u; width; node; 0<width; centre-l; centre-u; l-mono; u-mono; width-step)
open import Real.Interval.Arith using (_+ℝ_)
open import Real.Interval.Complete using (_⟶_)
open import Real.Interval.Node using (centre-add)
open import Real.Interval.Rational using (cancel-plus)
open import Real.Interval.Kit using (two-half; 0≤half; add-self; *-mono-≤-nonNeg)
open import Real.Interval.Mul using (cancelʳ; cancel-z)
prepend :
(l0 u0 : ℚ) (l0<u0 : l0 < u0) (tail : RealI) → Nest l0 u0 tail → RealI
prepend l0 u0 l0<u0 tail nest = record
{ l = l0; u = u0; lo = l0<u0; next = tail; nest = nest }
shift-cancel : ∀ c d w → (c + d) - (w + d) ≡ c - w
shift-cancel c d w =
trans (cong₂ _-_ (+-comm c d) (+-comm w d))
(cancel-plus d c w)
diff-double : ∀ q W → (q + W) - (q - W) ≡ W + W
diff-double q W =
let step1 : neg (q - W) ≡ neg q + W
step1 =
trans (neg-distrib-+ q (neg W))
(cong (neg q +_) (neg-involutive W))
step2 : (q + W) - (q - W) ≡ (q + W) + (neg q + W)
step2 = cong ((q + W) +_) step1
inner : neg q + (q + W) ≡ W
inner =
trans (sym (+-assoc (neg q) q W))
(trans (cong (λ z → z + W) (+-inverseˡ q))
(+-identityˡ W))
step3 : (q + W) + (neg q + W) ≡ W + W
step3 =
trans (sym (+-assoc (q + W) (neg q) W))
(trans (cong (λ z → z + W) (+-comm (q + W) (neg q)))
(cong (λ z → z + W) inner))
in trans step2 step3
double-div2 : ∀ W → (W + W) ÷ embed 2 ≡ W
double-div2 W =
let h = (1/ embed 2) {{pos⇒nonZero (embed 2) {{pos-pow 0}}}}
in trans (cong (_÷ embed 2) (add-self W))
(trans (*-assoc 2ℚ W h)
(trans (cong (2ℚ *_) (*-comm W h))
(trans (sym (*-assoc 2ℚ h W))
(trans (cong (λ z → z * W)
(*-inverseʳ (embed 2) {{pos⇒nonZero (embed 2) {{pos-pow 0}}}}))
(*-identityˡ W)))))
shifted : (L : RealI) (d : ℚ) → 0ℚ < d → RealI
shifted L d 0<d = prepend l0 u0 l0<u0 (node L 1) (n1 , n2 , n3)
where
q = centre L 0 + d
W = width L 0 + d
l0 = q - W
u0 = q + W
l0<u0 : l0 < u0
l0<u0 =
let w = width L 0
raw : 0ℚ + w < d + w
raw = +-mono-<-≤ 0<d ≤-refl
step1 = subst (λ z → z < d + w) (+-identityˡ w) raw
w<W : w < W
w<W = subst (λ z → w < z) (+-comm d w) step1
0<W : 0ℚ < W
0<W = <-trans (0<width L) w<W
negW<0 : neg W < 0ℚ
negW<0 = neg-antimono-< 0<W
negW<W : neg W < W
negW<W = <-trans negW<0 0<W
raw2 : neg W + q < W + q
raw2 = +-mono-<-≤ negW<W ≤-refl
in subst₂ (λ a b → a < b) (+-comm (neg W) q) (+-comm W q) raw2
a = l L 0
b = u L 0
c = centre L 0
w = width L 0
a+w≡b : a + w ≡ b
a+w≡b = trans (+-comm a w) (cancelʳ b a)
n1old : l0 ≤ a
n1old =
let test : l0 ≡ (c + d) - (w + d)
test = refl
l0≡ : l0 ≡ c - w
l0≡ = trans test (shift-cancel c d w)
c≤a+w : c ≤ a + w
c≤a+w = subst (λ z → c ≤ z) (sym a+w≡b) (centre-u L 0)
step : c - w ≤ (a + w) - w
step = +-mono-≤ c≤a+w (≤-refl {neg w})
back : (a + w) - w ≡ a
back = trans (cong (λ z → z - w) (+-comm a w)) (cancel-z w a)
p1 : l0 ≤ c - w
p1 = ≤-reflexive l0≡
p2 : c - w ≤ a
p2 = subst (λ z → c - w ≤ z) back step
in ≤-trans p1 p2
n1 : l0 ≤ l (node L 1) 0
n1 = ≤-trans n1old (l-mono L {n = 0} {m = 1} (z≤n {1}))
n2old : b ≤ u0
n2old =
let a≤c : a ≤ c
a≤c = centre-l L 0
bw≤cw : a + w ≤ c + w
bw≤cw = +-mono-≤ a≤c (≤-refl {w})
bw≤cw' : b ≤ c + w
bw≤cw' = subst (λ z → z ≤ c + w) a+w≡b bw≤cw
s2raw : (c + w) + 0ℚ ≤ (c + w) + d
s2raw = +-mono-≤ (≤-refl {c + w}) (<⇒≤ 0<d)
s2 : c + w ≤ c + (w + d)
s2 = subst₂ (λ a b → a ≤ b) (+-identityʳ (c + w))
(+-assoc c w d) s2raw
c<cd : 0ℚ + c < d + c
c<cd = +-mono-<-≤ 0<d (≤-refl {c})
c≤c+d : c ≤ c + d
c≤c+d = <⇒≤ (subst₂ (λ a b → a < b) (+-identityˡ c) (+-comm d c) c<cd)
s3 : c + (w + d) ≤ (c + d) + (w + d)
s3 = +-mono-≤ c≤c+d (≤-refl {w + d})
core2 : b ≤ u0
core2 = ≤-trans bw≤cw' (≤-trans s2 s3)
in core2
n2 : u (node L 1) 0 ≤ u0
n2 = ≤-trans (u-mono L {n = 0} {m = 1} (z≤n {1})) n2old
n3old : w ≤ (u0 - l0) ÷ embed 2
n3old =
let diff≡ : u0 - l0 ≡ W + W
diff≡ = diff-double q W
div≡ : (W + W) ÷ embed 2 ≡ W
div≡ = double-div2 W
raw≤ : 0ℚ + w < d + w
raw≤ = +-mono-<-≤ 0<d (≤-refl {w})
s1 = subst (λ z → z < d + w) (+-identityˡ w) raw≤
w≤W : w ≤ W
w≤W = <⇒≤ (subst (λ z → w < z) (+-comm d w) s1)
bridge : u0 - l0 ≡ (q + W) - (q - W)
bridge = refl
e : (u0 - l0) ÷ embed 2 ≡ W
e = trans (cong (_÷ embed 2) (trans bridge diff≡)) div≡
e' : W ≡ (u0 - l0) ÷ embed 2
e' = sym e
in subst (λ z → w ≤ z) e' w≤W
half≤ : ∀ x → 0ℚ ≤ x → x ÷ embed 2 ≤ x
half≤ x 0≤x =
let
0≤xh : 0ℚ ≤ x * half
0≤xh = subst (λ z → z ≤ x * half) (*-zeroˡ half)
(*-mono-≤-nonNeg (≤-refl {0ℚ}) 0≤x 0≤half (≤-refl {half}))
p : x * half ≤ x * half + x * half
p = ≤-trans (≤-reflexive (sym (+-identityʳ (x * half))))
(+-mono-≤ (≤-refl {x * half}) 0≤xh)
q : x * half + x * half ≡ x
q = two-half x
in subst (λ z → x * half ≤ z) q p
n3 : width (node L 1) 0 ≤ (u0 - l0) ÷ embed 2
n3 =
let w1≤w0 : width L 1 ≤ width L 0
w1≤w0 = ≤-trans (width-step L)
(half≤ (width L 0) (<⇒≤ (0<width L)))
in ≤-trans w1≤w0 n3old
avg-sym : ∀ q W → ((q - W) + (q + W)) ÷ embed 2 ≡ q
avg-sym q W =
let s : (q - W) + (q + W) ≡ q + q
s =
trans (+interchange q (neg W) q W)
(trans (cong ((q + q) +_) (+-inverseˡ W))
(+-identityʳ (q + q)))
in trans (cong (_÷ embed 2) s) (double-div2 q)
shifted-centre0 :
∀ L d (0<d : 0ℚ < d) → centre (shifted L d 0<d) 0 ≡ centre L 0 + d
shifted-centre0 L d 0<d = avg-sym (centre L 0 + d) (width L 0 + d)
shifted-tail :
∀ L d (0<d : 0ℚ < d) → node (shifted L d 0<d) 1 ≡ RealI.next L
shifted-tail L d 0<d = refl
shifted-converges :
∀ L d (0<d : 0ℚ < d) (d<ε0 : d < ε 0) →
(λ (_ : ℕ) → shifted L d 0<d) ⟶ L
shifted-converges L d 0<d d<ε0 k = 0 , λ n _ → goal k
where
s = shifted L d 0<d
node-shift : (k' : ℕ) → node s (suc k') ≡ node L (suc k')
node-shift zero = shifted-tail L d 0<d
node-shift (suc k') = cong RealI.next (node-shift k')
goal0 : ∣ centre s 0 - centre L 0 ∣ < ε 0
goal0 =
let e0 : centre s 0 ≡ centre L 0 + d
e0 = shifted-centre0 L d 0<d
step1 : centre s 0 - centre L 0 ≡ (centre L 0 + d) - centre L 0
step1 = cong (λ z → z - centre L 0) e0
step2 : (centre L 0 + d) - centre L 0 ≡ d
step2 = cancel-z (centre L 0) d
diff : centre s 0 - centre L 0 ≡ d
diff = trans step1 step2
full : ∣ centre s 0 - centre L 0 ∣ ≡ d
full = trans (cong ∣_∣ diff) (0≤p⇒∣p∣≡p (<⇒≤ 0<d))
in ≤-<-trans (≤-reflexive full) d<ε0
goal+ : ∀ k' → ∣ centre s (suc k') - centre L (suc k') ∣ < ε (suc k')
goal+ k' =
let ce : centre s (suc k') ≡ centre L (suc k')
ce = cong (λ r → (RealI.l r + RealI.u r) ÷ embed 2) (node-shift k')
diff0 : centre s (suc k') - centre L (suc k') ≡ 0ℚ
diff0 = trans (cong (λ z → z - centre L (suc k')) ce)
(+-inverseʳ (centre L (suc k')))
abs0 : ∣ centre s (suc k') - centre L (suc k') ∣ ≡ 0ℚ
abs0 = trans (cong ∣_∣ diff0) (0≤p⇒∣p∣≡p (≤-refl {0ℚ}))
in subst (λ z → z < ε (suc k')) (sym abs0) (0<ε (suc k'))
goal : ∀ k → ∣ centre s k - centre L k ∣ < ε k
goal zero = goal0
goal (suc k') = goal+ k'
d0 : ℚ
d0 = ε 0 * half
d0-pos : 0ℚ < d0
d0-pos = positive⁻¹ d0
⦃ pos*pos⇒pos (ε 0) half ⦃ positive (0<ε 0) ⦄ ⦄
sum-goal-fails :
∀ L → let f = shifted L d0 d0-pos
in ¬ (∣ centre (f +ℝ f) 0 - centre (L +ℝ L) 0 ∣ < ε 0)
sum-goal-fails L lt =
<-irrefl refl (subst (λ z → z < ε 0) final-eq lt)
where
f = shifted L d0 d0-pos
c = centre L 0
cf≡ : centre f 0 ≡ c + d0
cf≡ = shifted-centre0 L d0 d0-pos
eq1 : centre (f +ℝ f) 0 ≡ (c + d0) + (c + d0)
eq1 = trans (centre-add f f 0) (cong₂ _+_ cf≡ cf≡)
eq2 : centre (L +ℝ L) 0 ≡ c + c
eq2 = centre-add L L 0
expand-eq : (c + d0) + (c + d0) ≡ (c + c) + (d0 + d0)
expand-eq = +interchange c d0 c d0
step1 : (c + d0) + (c + d0) - (c + c) ≡
(c + c) + (d0 + d0) - (c + c)
step1 = cong (λ z → z - (c + c)) expand-eq
step2 : (c + c) + (d0 + d0) - (c + c) ≡ d0 + d0
step2 = cancel-z (c + c) (d0 + d0)
diff-eq : (c + d0) + (c + d0) - (c + c) ≡ d0 + d0
diff-eq = trans step1 step2
diff : centre (f +ℝ f) 0 - centre (L +ℝ L) 0 ≡ d0 + d0
diff = trans (cong₂ _-_ eq1 eq2) diff-eq
0<d0d0 : 0ℚ < d0 + d0
0<d0d0 =
subst (λ z → z < d0 + d0) (sym (+-identityʳ 0ℚ))
(+-mono-< d0-pos d0-pos)
d0+d0-pos : 0ℚ ≤ d0 + d0
d0+d0-pos = <⇒≤ 0<d0d0
abs-d0d0 : ∣ d0 + d0 ∣ ≡ d0 + d0
abs-d0d0 = 0≤p⇒∣p∣≡p d0+d0-pos
d0+d0≡ε0 : d0 + d0 ≡ ε 0
d0+d0≡ε0 = two-half (ε 0)
final-eq :
∣ centre (f +ℝ f) 0 - centre (L +ℝ L) 0 ∣ ≡ ε 0
final-eq = trans (cong ∣_∣ diff) (trans abs-d0d0 d0+d0≡ε0)