{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.AbsTriangle where
open import Data.Product using (_,_; proj₁; proj₂)
open import Data.Sum.Base using (inj₁; inj₂)
open import Data.Nat using (ℕ; suc)
renaming (_⊔_ to _⊔N_; _+_ to _+N_; _≤_ to _≤N_)
open import Data.Nat.Properties using (m≤n⊔m; m≤m⊔n; +-suc)
renaming (+-identityʳ to +-identityʳℕ)
open import Data.Rational using
(ℚ; 0ℚ; 1ℚ; _⊔_; _+_; _-_; _*_; _≤_; _<_; _≥_; ∣_∣; positive)
renaming (-_ to neg)
open import Data.Rational.Base using (nonNegative)
open import Data.Rational.Properties using
(≤-refl; ≤-reflexive; ≤-trans; <⇒≤; +-mono-≤; +-mono-<-≤; +-comm; +-assoc
; +-identityˡ; +-identityʳ; +-inverseʳ; +-inverseˡ; *-assoc; *-identityˡ
; *-identityʳ; *-distribʳ-+; *-distribˡ-+; pos⇒nonNeg; ∣p+q∣≤∣p∣+∣q∣
; ∣p-q∣≤∣p∣+∣q∣; 0≤∣p∣; 0≤p⇒∣p∣≡p; ∣-p∣≡∣p∣; *-monoˡ-≤-nonNeg
; ≤-total; neg-distrib-+; neg-antimono-≤; neg-antimono-<; ∣p*q∣≡∣p∣*∣q∣
; p≤q⊔p; ⊔-lub; *-zeroˡ; <-trans; ≤-<-trans; <-irrefl; *-zeroʳ
; ∣p∣≡p∨∣p∣≡-p)
open import Function.Base using (case_of_)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; cong; cong₂; sym; trans; subst; module ≡-Reasoning)
open ≡-Reasoning
open import Base.RationalRing using (+interchange; neg-involutive; neg-sub)
open import Real using (embed; half; 2ℚ≡1+1)
open import Real.Interval using (RealI; δ; δ-pos; dyadic)
open import Real.Interval.Arith using (0ℝ; _+ℝ_; negℝ)
open import Real.Interval.Equiv using (_≈ℝ_)
open import Real.IntervalEquiv using
(l; u; centre; width; width-n; centre-l; centre-u; l-mono; u-mono; node
; recipPow2; node-suc)
open import Real.Interval.Node using
(centre-add; 0≤width-n; l-hom; u-hom; l-neg; u-neg; node-dyadic)
open import Real.Interval.Abs using
(∣_∣ℝ; absLo; absHi; lo-pos; hi-pos; lo-neg; hi-neg; lo-mid)
open import Real.Interval.Kit using
(≈ℝ-of-rec; half+half≡1; 0≤recipPow2; recipPow2-mul; recipPow2-n≤1
; recipPow2-≤; halveQ; 0≤half; halveQ-mono; 0≤halveQ; halveQ-distrib
; halveQ-neg; same⇒diff0; 0≤diff; move-≤; move-≤-back; neg-of-nonpos
; npos⇒∣p∣≡neg; tail-bound; 0<embed2)
open import Real.Interval.Rational using (r≤|r|)
open import Real.Interval.OrderComplete.Base using (_≤ℝ_)
open import Real.Interval.Reasoning using (begin≤_; _≤⟨_⟩_; _≤∎)
abs-centre-≤ : (l u : ℚ) (l≤u : l ≤ u) →
∣ halveQ (absLo l u + absHi l u) - ∣ halveQ (l + u) ∣ ∣ ≤ u - l
abs-centre-≤ l u l≤u with ≤-total l 0ℚ | ≤-total u 0ℚ
... | inj₂ 0≤l | _ =
let 0≤u = ≤-trans 0≤l l≤u
lp = lo-pos 0≤l 0≤u
hp = hi-pos 0≤l 0≤u
A≡ : halveQ (absLo l u + absHi l u) ≡ halveQ (l + u)
A≡ = trans (cong halveQ (cong₂ _+_ lp hp)) refl
0≤c : 0ℚ ≤ halveQ (l + u)
0≤c =
let 0≤sum : 0ℚ ≤ l + u
0≤sum = +-mono-≤ 0≤l 0≤u
h : halveQ 0ℚ ≤ halveQ (l + u)
h = halveQ-mono 0≤sum
h0 : halveQ 0ℚ ≡ 0ℚ
h0 = *-zeroˡ half
in subst (λ z → z ≤ halveQ (l + u)) (sym h0) h
B≡ : ∣ halveQ (l + u) ∣ ≡ halveQ (l + u)
B≡ = 0≤p⇒∣p∣≡p 0≤c
eq : halveQ (absLo l u + absHi l u) ≡ ∣ halveQ (l + u) ∣
eq = trans A≡ (sym B≡)
in subst (λ z → z ≤ u - l) (sym (same⇒diff0 eq))
(0≤diff l≤u)
... | inj₁ l≤0 | inj₁ u≤0 =
let l≤u' = l≤u
lp = lo-neg l≤u' u≤0
hp = hi-neg l≤u' u≤0
A≡ : halveQ (absLo l u + absHi l u) ≡ neg (halveQ (l + u))
A≡ = begin
halveQ (absLo l u + absHi l u)
≡⟨ cong halveQ (cong₂ _+_ lp hp) ⟩
halveQ (neg u + neg l)
≡⟨ halveQ-distrib (neg u) (neg l) ⟩
halveQ (neg u) + halveQ (neg l)
≡⟨ cong₂ _+_ (halveQ-neg u) (halveQ-neg l) ⟩
neg (halveQ u) + neg (halveQ l)
≡⟨ +-comm (neg (halveQ u)) (neg (halveQ l)) ⟩
neg (halveQ l) + neg (halveQ u)
≡⟨ sym (neg-distrib-+ (halveQ l) (halveQ u)) ⟩
neg (halveQ l + halveQ u)
≡⟨ cong neg (sym (halveQ-distrib l u)) ⟩
neg (halveQ (l + u)) ∎
su≤0 : l + u ≤ 0ℚ
su≤0 = begin≤ l + u
≤⟨ +-mono-≤ l≤0 u≤0 ⟩ 0ℚ + 0ℚ
≤⟨ ≤-reflexive (+-identityˡ 0ℚ) ⟩ 0ℚ ≤∎
c≤0 : halveQ (l + u) ≤ 0ℚ
c≤0 =
let h : halveQ (l + u) ≤ halveQ 0ℚ
h = halveQ-mono su≤0
h0 : halveQ 0ℚ ≡ 0ℚ
h0 = *-zeroˡ half
in subst (λ z → halveQ (l + u) ≤ z) h0 h
B≡ : ∣ halveQ (l + u) ∣ ≡ neg (halveQ (l + u))
B≡ = npos⇒∣p∣≡neg c≤0
eq : halveQ (absLo l u + absHi l u) ≡ ∣ halveQ (l + u) ∣
eq = trans A≡ (sym B≡)
in subst (λ z → z ≤ u - l) (sym (same⇒diff0 eq))
(0≤diff l≤u)
... | inj₁ l≤0 | inj₂ 0≤u =
let p = u
q = neg l
p≥0 = 0≤u
q≥0 = neg-of-nonpos l≤0
lp = lo-mid l≤0 p≥0
A≡ : halveQ (absLo l u + absHi l u) ≡ halveQ (p ⊔ q)
A≡ = begin
halveQ (absLo l u + absHi l u)
≡⟨ cong (λ z → halveQ (z + absHi l u)) lp ⟩
halveQ (0ℚ + absHi l u)
≡⟨ cong halveQ (+-identityˡ (absHi l u)) ⟩
halveQ (p ⊔ q) ∎
s≡ : l + u ≡ p - q
s≡ = begin l + u
≡⟨ +-comm l u ⟩ u + l
≡⟨ cong (u +_) (sym (neg-involutive l)) ⟩ u + neg (neg l)
≡⟨ refl ⟩ p - q ∎
B≡ : ∣ halveQ (l + u) ∣ ≡ halveQ ∣ p - q ∣
B≡ = begin
∣ halveQ (l + u) ∣
≡⟨ cong ∣_∣ (cong halveQ s≡) ⟩
∣ halveQ (p - q) ∣
≡⟨ ∣p*q∣≡∣p∣*∣q∣ (p - q) half ⟩
∣ p - q ∣ * ∣ half ∣
≡⟨ cong (∣ p - q ∣ *_) (0≤p⇒∣p∣≡p 0≤half) ⟩
∣ p - q ∣ * half
≡⟨ refl ⟩
halveQ ∣ p - q ∣ ∎
max≤pq : p ⊔ q ≤ p + q
max≤pq = ⊔-lub (begin≤ p
≤⟨ ≤-reflexive (sym (+-identityʳ p)) ⟩ p + 0ℚ
≤⟨ +-mono-≤ (≤-refl {p}) q≥0 ⟩ p + q ≤∎)
(begin≤ q
≤⟨ ≤-reflexive (sym (+-identityʳ q)) ⟩ q + 0ℚ
≤⟨ +-mono-≤ (≤-refl {q}) p≥0 ⟩ q + p
≤⟨ ≤-reflexive (+-comm q p) ⟩ p + q ≤∎)
diff≤pq : ∣ p - q ∣ ≤ p + q
diff≤pq = begin≤ ∣ p - q ∣
≤⟨ ∣p-q∣≤∣p∣+∣q∣ p q ⟩ ∣ p ∣ + ∣ q ∣
≤⟨ ≤-reflexive (cong₂ _+_ (0≤p⇒∣p∣≡p p≥0) (0≤p⇒∣p∣≡p q≥0)) ⟩
p + q ≤∎
0≤max : 0ℚ ≤ p ⊔ q
0≤max = begin≤ 0ℚ
≤⟨ q≥0 ⟩ q
≤⟨ p≤q⊔p p q ⟩ p ⊔ q ≤∎
bound : ∣ halveQ (p ⊔ q) - halveQ ∣ p - q ∣ ∣ ≤ p + q
bound =
let a = halveQ (p ⊔ q)
b = halveQ ∣ p - q ∣
s1 : ∣ a ∣ + ∣ b ∣ ≤ a + b
s1 = ≤-reflexive
(cong₂ _+_ (0≤p⇒∣p∣≡p (0≤halveQ 0≤max))
(0≤p⇒∣p∣≡p (0≤halveQ (0≤∣p∣ (p - q)))))
s2 : a + b ≤ halveQ (p + q) + halveQ (p + q)
s2 = +-mono-≤ (halveQ-mono max≤pq) (halveQ-mono diff≤pq)
s3 : halveQ (p + q) + halveQ (p + q) ≤ p + q
s3 = ≤-reflexive
let x = p + q
in begin x * half + x * half
≡⟨ sym (*-distribˡ-+ x half half) ⟩ x * (half + half)
≡⟨ cong (x *_) half+half≡1 ⟩ x * 1ℚ
≡⟨ *-identityʳ x ⟩ x ∎
in ≤-trans (∣p-q∣≤∣p∣+∣q∣ a b)
(≤-trans s1 (≤-trans s2 s3))
eq : halveQ (absLo l u + absHi l u) ≡ halveQ (p ⊔ q)
eq = A≡
X = halveQ (absLo l u + absHi l u)
Y = halveQ (p ⊔ q)
Z = ∣ halveQ (l + u) ∣
W = halveQ ∣ p - q ∣
diff-eq : ∣ X - Z ∣ ≡ ∣ Y - W ∣
diff-eq = cong₂ (λ a b → ∣ a - b ∣) eq B≡
in subst (λ t → t ≤ p + q) (sym diff-eq) bound
abs-centre-triangle :
(l1 u1 l2 u2 : ℚ) (l1≤u1 : l1 ≤ u1) (l2≤u2 : l2 ≤ u2) →
let w1 = u1 - l1
w2 = u2 - l2
A = halveQ (absLo (l1 + l2) (u1 + u2) + absHi (l1 + l2) (u1 + u2))
B = halveQ (absLo l1 u1 + absHi l1 u1)
C = halveQ (absLo l2 u2 + absHi l2 u2)
in A - (B + C) ≤ embed 2 * (w1 + w2)
abs-centre-triangle l1 u1 l2 u2 l1≤u1 l2≤u2 =
let w1 = u1 - l1
w2 = u2 - l2
sum≤ : l1 + l2 ≤ u1 + u2
sum≤ = +-mono-≤ l1≤u1 l2≤u2
A = halveQ (absLo (l1 + l2) (u1 + u2) + absHi (l1 + l2) (u1 + u2))
B = halveQ (absLo l1 u1 + absHi l1 u1)
C = halveQ (absLo l2 u2 + absHi l2 u2)
p = halveQ (l1 + u1)
q = halveQ (l2 + u2)
centreSum : halveQ ((l1 + l2) + (u1 + u2)) ≡ p + q
centreSum =
let a = halveQ l1
b = halveQ l2
c = halveQ u1
d = halveQ u2
regroup : (a + b) + (c + d) ≡ (a + c) + (b + d)
regroup =
begin (a + b) + (c + d)
≡⟨ sym (+-assoc (a + b) c d) ⟩
((a + b) + c) + d
≡⟨ cong (_+ d) (+-assoc a b c) ⟩
(a + (b + c)) + d
≡⟨ cong (λ z → (a + z) + d) (+-comm b c) ⟩
(a + (c + b)) + d
≡⟨ cong (_+ d) (sym (+-assoc a c b)) ⟩
((a + c) + b) + d
≡⟨ +-assoc (a + c) b d ⟩
(a + c) + (b + d) ∎
in
begin halveQ ((l1 + l2) + (u1 + u2))
≡⟨ halveQ-distrib (l1 + l2) (u1 + u2) ⟩
halveQ (l1 + l2) + halveQ (u1 + u2)
≡⟨ cong₂ _+_ (halveQ-distrib l1 l2) (halveQ-distrib u1 u2) ⟩
(a + b) + (c + d)
≡⟨ regroup ⟩
(a + c) + (b + d)
≡⟨ cong₂ _+_ (sym (halveQ-distrib l1 u1)) (sym (halveQ-distrib l2 u2)) ⟩
p + q ∎
h1raw = abs-centre-≤ (l1 + l2) (u1 + u2) sum≤
boundEq : (u1 + u2) - (l1 + l2) ≡ w1 + w2
boundEq =
begin (u1 + u2) - (l1 + l2)
≡⟨ cong ((u1 + u2) +_) (neg-distrib-+ l1 l2) ⟩
(u1 + u2) + (neg l1 + neg l2)
≡⟨ +interchange u1 u2 (neg l1) (neg l2) ⟩
(u1 + neg l1) + (u2 + neg l2)
≡⟨ refl ⟩
w1 + w2 ∎
h1 : ∣ A - ∣ halveQ ((l1 + l2) + (u1 + u2)) ∣ ∣ ≤ w1 + w2
h1 = subst (λ z → ∣ A - ∣ halveQ ((l1 + l2) + (u1 + u2)) ∣ ∣ ≤ z)
boundEq h1raw
h1' : ∣ A - ∣ p + q ∣ ∣ ≤ w1 + w2
h1' = subst (λ z → ∣ A - ∣ z ∣ ∣ ≤ w1 + w2) centreSum h1
h2 = abs-centre-≤ l1 u1 l1≤u1
h3 = abs-centre-≤ l2 u2 l2≤u2
abs-neg : {X w : ℚ} → ∣ X ∣ ≤ w → neg X ≤ w
abs-neg {X} {w} h =
let k : neg X ≤ ∣ neg X ∣
k = r≤|r| (neg X)
e : ∣ neg X ∣ ≡ ∣ X ∣
e = ∣-p∣≡∣p∣ X
in ≤-trans k (≤-trans (≤-reflexive e) h)
s1 : A - ∣ p + q ∣ ≤ w1 + w2
s1 = ≤-trans (r≤|r| (A - ∣ p + q ∣)) h1'
s2 : ∣ p + q ∣ ≤ ∣ p ∣ + ∣ q ∣
s2 = ∣p+q∣≤∣p∣+∣q∣ p q
s3 : ∣ p ∣ - B ≤ w1
s3 =
let e : neg (B - ∣ p ∣) ≡ ∣ p ∣ - B
e =
begin neg (B - ∣ p ∣)
≡⟨ neg-distrib-+ B (neg ∣ p ∣) ⟩
neg B + neg (neg ∣ p ∣)
≡⟨ cong (neg B +_) (neg-involutive ∣ p ∣) ⟩
neg B + ∣ p ∣
≡⟨ +-comm (neg B) ∣ p ∣ ⟩
∣ p ∣ + neg B
≡⟨ refl ⟩
∣ p ∣ - B ∎
in subst (λ z → z ≤ w1) e (abs-neg h2)
s4 : ∣ q ∣ - C ≤ w2
s4 =
let e : neg (C - ∣ q ∣) ≡ ∣ q ∣ - C
e =
begin neg (C - ∣ q ∣)
≡⟨ neg-distrib-+ C (neg ∣ q ∣) ⟩
neg C + neg (neg ∣ q ∣)
≡⟨ cong (neg C +_) (neg-involutive ∣ q ∣) ⟩
neg C + ∣ q ∣
≡⟨ +-comm (neg C) ∣ q ∣ ⟩
∣ q ∣ + neg C
≡⟨ refl ⟩
∣ q ∣ - C ∎
in subst (λ z → z ≤ w2) e (abs-neg h3)
t1 : A ≤ ∣ p + q ∣ + (w1 + w2)
t1 = move-≤ s1
t3 : ∣ p ∣ ≤ B + w1
t3 = move-≤ s3
t4 : ∣ q ∣ ≤ C + w2
t4 = move-≤ s4
rearrange : (B + w1) + (C + w2) ≡ B + C + (w1 + w2)
rearrange =
begin (B + w1) + (C + w2)
≡⟨ sym (+-assoc (B + w1) C w2) ⟩
B + w1 + C + w2
≡⟨ cong (λ z → z + w2)
(begin (B + w1) + C
≡⟨ +-assoc B w1 C ⟩
B + (w1 + C)
≡⟨ cong (B +_) (+-comm w1 C) ⟩
B + (C + w1) ∎) ⟩
(B + (C + w1)) + w2
≡⟨ +-assoc B (C + w1) w2 ⟩
B + ((C + w1) + w2)
≡⟨ cong (B +_) (+-assoc C w1 w2) ⟩
B + (C + (w1 + w2))
≡⟨ sym (+-assoc B C (w1 + w2)) ⟩
B + C + (w1 + w2) ∎
t5 : ∣ p ∣ + ∣ q ∣ ≤ B + C + (w1 + w2)
t5 =
subst (λ z → ∣ p ∣ + ∣ q ∣ ≤ z) rearrange
(+-mono-≤ t3 t4)
t2 : ∣ p + q ∣ + (w1 + w2) ≤
(∣ p ∣ + ∣ q ∣) + (w1 + w2)
t2 = +-mono-≤ s2 (≤-refl {w1 + w2})
t6 : A ≤ B + C + embed 2 * (w1 + w2)
t6 =
let up : (∣ p ∣ + ∣ q ∣) + (w1 + w2) ≤
(B + C + (w1 + w2)) + (w1 + w2)
up = +-mono-≤ t5 (≤-refl {w1 + w2})
chain : A ≤ (B + C + (w1 + w2)) + (w1 + w2)
chain = ≤-trans (≤-trans t1 t2) up
double : embed 2 * (w1 + w2) ≡ (w1 + w2) + (w1 + w2)
double =
begin embed 2 * (w1 + w2)
≡⟨ cong (λ z → z * (w1 + w2)) 2ℚ≡1+1 ⟩
(1ℚ + 1ℚ) * (w1 + w2)
≡⟨ *-distribʳ-+ (w1 + w2) 1ℚ 1ℚ ⟩
(1ℚ * (w1 + w2)) + (1ℚ * (w1 + w2))
≡⟨ cong₂ _+_ (*-identityˡ (w1 + w2)) (*-identityˡ (w1 + w2)) ⟩
(w1 + w2) + (w1 + w2) ∎
merge :
(B + C + (w1 + w2)) + (w1 + w2) ≡
B + C + embed 2 * (w1 + w2)
merge =
let w = w1 + w2
in
begin (B + C + w) + w
≡⟨ +-assoc (B + C) w w ⟩
(B + C) + (w + w)
≡⟨ cong ((B + C) +_) (sym double) ⟩
(B + C) + embed 2 * w ∎
in subst (λ z → A ≤ z) merge chain
in let t6' : A ≤ (B + C) + embed 2 * (w1 + w2)
t6' =
let t6right : B + C + embed 2 * (w1 + w2) ≡
(B + C) + embed 2 * (w1 + w2)
t6right = refl
in subst (λ z → A ≤ z) (sym t6right) t6
in move-≤-back t6'
≤ℝ-of-rec : (A B : RealI) (C : ℚ) → 0ℚ ≤ C →
(h : ∀ n → centre A n - centre B n ≤ C * recipPow2 n) →
A ≤ℝ B
≤ℝ-of-rec A B C 0≤C h (n0 , gap) =
let d = l A n0 - u B n0
0<d : 0ℚ < d
0<d =
let raw : u B n0 + neg (u B n0) < l A n0 + neg (u B n0)
raw = +-mono-<-≤ gap (≤-refl {neg (u B n0)})
zeroeq : u B n0 + neg (u B n0) ≡ 0ℚ
zeroeq = +-inverseʳ (u B n0)
in subst (λ z → z < l A n0 + neg (u B n0)) zeroeq raw
tb = tail-bound C 0≤C d 0<d
m0 = proj₁ tb
h2 = proj₂ tb
m = n0 ⊔N m0
m0≤m : m0 ≤N m
m0≤m = m≤n⊔m n0 m0
m≥n0 : n0 ≤N m
m≥n0 = m≤m⊔n n0 m0
cA≥l0 : centre A m ≥ l A n0
cA≥l0 =
let p : l A n0 ≤ l A m
p = l-mono A m≥n0
q : l A m ≤ centre A m
q = centre-l A m
in ≤-trans p q
cB≤u0 : centre B m ≤ u B n0
cB≤u0 =
let p : centre B m ≤ u B m
p = centre-u B m
q : u B m ≤ u B n0
q = u-mono B m≥n0
in ≤-trans p q
diff≥d : centre A m - centre B m ≥ d
diff≥d = +-mono-≤ cA≥l0 (neg-antimono-≤ cB≤u0)
upper : centre A m - centre B m < d
upper = ≤-<-trans (h m) (h2 m m0≤m)
in let dd : d < d
dd = ≤-<-trans diff≥d upper
in <-irrefl refl dd
l0ℝ : (n : ℕ) → l 0ℝ n ≡ neg (δ n)
l0ℝ n =
let eq : node 0ℝ n ≡ dyadic 0ℚ n
eq = node-dyadic 0ℚ 0 n
in subst (λ z → RealI.l z ≡ neg (δ n)) (sym eq)
(let e : RealI.l (dyadic 0ℚ n) ≡ neg (δ n)
e =
begin RealI.l (dyadic 0ℚ n)
≡⟨ refl ⟩
neg (δ n) + 0ℚ
≡⟨ +-identityʳ (neg (δ n)) ⟩
neg (δ n) ∎
in e)
labs-nonneg : (x : RealI) (n : ℕ) → 0ℚ ≤ RealI.l (node ∣ x ∣ℝ n)
labs-nonneg x 0 =
p≤q⊔p (RealI.l x ⊔ neg (RealI.u x)) 0ℚ
labs-nonneg x (suc n) =
let nx = RealI.next (RealI.next x)
eq : node ∣ x ∣ℝ (suc n) ≡ node ∣ nx ∣ℝ n
eq =
begin node ∣ x ∣ℝ (suc n)
≡⟨ node-suc ∣ x ∣ℝ n ⟩
node (RealI.next ∣ x ∣ℝ) n
≡⟨ cong (λ z → node z n) refl ⟩
node ∣ nx ∣ℝ n ∎
in subst (λ z → 0ℚ ≤ RealI.l z) (sym eq) (labs-nonneg nx n)
abs-nonneg : (x : RealI) → 0ℝ ≤ℝ ∣ x ∣ℝ
abs-nonneg x (n , h) =
let 0≤labs : 0ℚ ≤ l ∣ x ∣ℝ n
0≤labs = labs-nonneg x n
u≥l : l ∣ x ∣ℝ n ≤ u ∣ x ∣ℝ n
u≥l = <⇒≤ (RealI.lo (node ∣ x ∣ℝ n))
u≥0 : u ∣ x ∣ℝ n ≥ 0ℚ
u≥0 = ≤-trans 0≤labs u≥l
l0ℝ≡ : l 0ℝ n ≡ neg (δ n)
l0ℝ≡ = l0ℝ n
negδ<0 : neg (δ n) < 0ℚ
negδ<0 = neg-antimono-< (δ-pos n)
h' : u ∣ x ∣ℝ n < neg (δ n)
h' = subst (λ z → u ∣ x ∣ℝ n < z) l0ℝ≡ h
u<0 : u ∣ x ∣ℝ n < 0ℚ
u<0 = <-trans h' negδ<0
in let dd : 0ℚ < 0ℚ
dd = ≤-<-trans u≥0 u<0
in <-irrefl refl dd
node-abs : (x : RealI) (n : ℕ) → node ∣ x ∣ℝ n ≡ ∣ node x (n +N n) ∣ℝ
node-abs x 0 =
begin node ∣ x ∣ℝ 0
≡⟨ refl ⟩
∣ x ∣ℝ
≡⟨ refl ⟩
∣ node x 0 ∣ℝ
≡⟨ cong ∣_∣ℝ (cong (node x) (sym (+-identityʳℕ 0))) ⟩
∣ node x (0 +N 0) ∣ℝ ∎
node-abs x (suc n) =
begin node ∣ x ∣ℝ (suc n)
≡⟨ node-suc ∣ x ∣ℝ n ⟩
node (RealI.next ∣ x ∣ℝ) n
≡⟨ cong (λ z → node z n) refl ⟩
node ∣ RealI.next (RealI.next x) ∣ℝ n
≡⟨ node-abs (RealI.next (RealI.next x)) n ⟩
∣ node (RealI.next (RealI.next x)) (n +N n) ∣ℝ
≡⟨ cong ∣_∣ℝ
(begin node (RealI.next (RealI.next x)) (n +N n)
≡⟨ sym (node-suc (RealI.next x) (n +N n)) ⟩
node (RealI.next x) (suc (n +N n))
≡⟨ sym (node-suc x (suc (n +N n))) ⟩
node x (suc (suc (n +N n)))
≡⟨ cong (node x) (sym (cong suc (+-suc n n))) ⟩
node x ((suc n) +N (suc n)) ∎) ⟩
∣ node x ((suc n) +N (suc n)) ∣ℝ ∎
l-abs-node : (x : RealI) (n : ℕ) →
RealI.l (node ∣ x ∣ℝ n) ≡
absLo (l x (n +N n)) (u x (n +N n))
l-abs-node x n =
let e : node ∣ x ∣ℝ n ≡ ∣ node x (n +N n) ∣ℝ
e = node-abs x n
in subst (λ z → RealI.l z ≡ absLo (l x (n +N n)) (u x (n +N n))) (sym e) refl
u-abs-node : (x : RealI) (n : ℕ) →
RealI.u (node ∣ x ∣ℝ n) ≡
absHi (l x (n +N n)) (u x (n +N n))
u-abs-node x n =
let e : node ∣ x ∣ℝ n ≡ ∣ node x (n +N n) ∣ℝ
e = node-abs x n
in subst (λ z → RealI.u z ≡ absHi (l x (n +N n)) (u x (n +N n))) (sym e) refl
centre-abs-node : (x : RealI) (n : ℕ) →
centre ∣ x ∣ℝ n ≡
halveQ (absLo (l x (n +N n)) (u x (n +N n)) +
absHi (l x (n +N n)) (u x (n +N n)))
centre-abs-node x n =
begin centre ∣ x ∣ℝ n
≡⟨ refl ⟩
halveQ (RealI.l (node ∣ x ∣ℝ n) + RealI.u (node ∣ x ∣ℝ n))
≡⟨ cong₂ (λ a b → halveQ (a + b)) (l-abs-node x n) (u-abs-node x n) ⟩
halveQ (absLo (l x (n +N n)) (u x (n +N n)) +
absHi (l x (n +N n)) (u x (n +N n))) ∎
abs-triangle : (x y : RealI) →
∣ x +ℝ y ∣ℝ ≤ℝ ∣ x ∣ℝ +ℝ ∣ y ∣ℝ
abs-triangle x y =
let s0 = width x 0 + width y 0
C = embed 2 * s0
s0≥0 : 0ℚ ≤ s0
s0≥0 = +-mono-≤ (0≤width-n x 0) (0≤width-n y 0)
0≤C : 0ℚ ≤ C
0≤C =
let p : embed 2 * 0ℚ ≤ embed 2 * s0
p = *-monoˡ-≤-nonNeg (embed 2)
{{pos⇒nonNeg (embed 2) {{positive 0<embed2}}}} s0≥0
z : embed 2 * 0ℚ ≡ 0ℚ
z = *-zeroʳ (embed 2)
in subst (λ z → z ≤ C) z p
h : ∀ n →
centre ∣ x +ℝ y ∣ℝ n - centre (∣ x ∣ℝ +ℝ ∣ y ∣ℝ) n
≤ C * recipPow2 n
h n =
let nn = n +N n
l1d = l x nn
u1d = u x nn
l2d = l y nn
u2d = u y nn
l1d≤u1d : l1d ≤ u1d
l1d≤u1d = <⇒≤ (RealI.lo (node x nn))
l2d≤u2d : l2d ≤ u2d
l2d≤u2d = <⇒≤ (RealI.lo (node y nn))
main = abs-centre-triangle l1d u1d l2d u2d l1d≤u1d l2d≤u2d
A = halveQ (absLo (l1d + l2d) (u1d + u2d) +
absHi (l1d + l2d) (u1d + u2d))
Bd = halveQ (absLo l1d u1d + absHi l1d u1d)
Cd = halveQ (absLo l2d u2d + absHi l2d u2d)
Bn = centre ∣ x ∣ℝ n
Cn = centre ∣ y ∣ℝ n
Aeq : centre ∣ x +ℝ y ∣ℝ n ≡ A
Aeq =
let pl : l (x +ℝ y) nn ≡ l1d + l2d
pl = l-hom x y nn
pu : u (x +ℝ y) nn ≡ u1d + u2d
pu = u-hom x y nn
in
begin centre ∣ x +ℝ y ∣ℝ n
≡⟨ refl ⟩
halveQ (RealI.l (node ∣ x +ℝ y ∣ℝ n) +
RealI.u (node ∣ x +ℝ y ∣ℝ n))
≡⟨ cong₂ (λ a b → halveQ (a + b))
(l-abs-node (x +ℝ y) n) (u-abs-node (x +ℝ y) n) ⟩
halveQ (absLo (l (x +ℝ y) nn) (u (x +ℝ y) nn) +
absHi (l (x +ℝ y) nn) (u (x +ℝ y) nn))
≡⟨ cong₂ (λ a b → halveQ (absLo a b + absHi a b)) pl pu ⟩
A ∎
Beq : centre (∣ x ∣ℝ +ℝ ∣ y ∣ℝ) n ≡ Bn + Cn
Beq = centre-add ∣ x ∣ℝ ∣ y ∣ℝ n
s1 : A - (Bd + Cd) ≤ embed 2 * ((u1d - l1d) + (u2d - l2d))
s1 = main
eq : Bn + Cn ≡ Bd + Cd
eq =
begin Bn + Cn
≡⟨ cong₂ _+_ (centre-abs-node x n) (centre-abs-node y n) ⟩
Bd + Cd ∎
s2 : A - (Bn + Cn) ≤ embed 2 * ((u1d - l1d) + (u2d - l2d))
s2 = subst (λ z → A - z ≤ embed 2 * ((u1d - l1d) + (u2d - l2d)))
(sym eq) s1
w1d≤ : width x nn ≤ width x 0 * recipPow2 n
w1d≤ =
let p : width x nn ≤ width x 0 * recipPow2 nn
p = width-n x nn
r = recipPow2 n
0≤r : 0ℚ ≤ r
0≤r = 0≤recipPow2 n
q : recipPow2 nn ≤ r
q =
let e : recipPow2 nn ≡ r * r
e = recipPow2-mul n n
s : r * r ≤ r
s =
subst (λ z → r * r ≤ z) (*-identityʳ r)
(*-monoˡ-≤-nonNeg r {{nonNegative 0≤r}}
(recipPow2-n≤1 n))
in ≤-trans (≤-reflexive e) s
in ≤-trans p (*-monoˡ-≤-nonNeg (width x 0)
{{nonNegative (0≤width-n x 0)}} q)
w2d≤ : width y nn ≤ width y 0 * recipPow2 n
w2d≤ =
let p : width y nn ≤ width y 0 * recipPow2 nn
p = width-n y nn
r = recipPow2 n
0≤r : 0ℚ ≤ r
0≤r = 0≤recipPow2 n
q : recipPow2 nn ≤ r
q =
let e : recipPow2 nn ≡ r * r
e = recipPow2-mul n n
s : r * r ≤ r
s =
subst (λ z → r * r ≤ z) (*-identityʳ r)
(*-monoˡ-≤-nonNeg r {{nonNegative 0≤r}}
(recipPow2-n≤1 n))
in ≤-trans (≤-reflexive e) s
in ≤-trans p (*-monoˡ-≤-nonNeg (width y 0)
{{nonNegative (0≤width-n y 0)}} q)
wsum≤ : (u1d - l1d) + (u2d - l2d) ≤ s0 * recipPow2 n
wsum≤ =
let p : width x nn + width y nn ≤
(width x 0 * recipPow2 n) + (width y 0 * recipPow2 n)
p = +-mono-≤ w1d≤ w2d≤
dist :
(width x 0 * recipPow2 n) + (width y 0 * recipPow2 n)
≡ s0 * recipPow2 n
dist = sym (*-distribʳ-+ (recipPow2 n) (width x 0) (width y 0))
in subst (λ z → width x nn + width y nn ≤ z) dist p
double≤ : embed 2 * ((u1d - l1d) + (u2d - l2d)) ≤
embed 2 * (s0 * recipPow2 n)
double≤ = *-monoˡ-≤-nonNeg (embed 2)
{{pos⇒nonNeg (embed 2) {{positive 0<embed2}}}} wsum≤
last : embed 2 * (s0 * recipPow2 n) ≡ C * recipPow2 n
last =
begin embed 2 * (s0 * recipPow2 n)
≡⟨ sym (*-assoc (embed 2) s0 (recipPow2 n)) ⟩
(embed 2 * s0) * recipPow2 n
≡⟨ refl ⟩
C * recipPow2 n ∎
in ≤-trans
(subst (λ z → centre ∣ x +ℝ y ∣ℝ n - z ≤
embed 2 * (s0 * recipPow2 n))
(sym Beq)
(subst (λ z → z - (Bn + Cn) ≤
embed 2 * (s0 * recipPow2 n))
(sym Aeq)
(≤-trans s2 double≤)))
(≤-reflexive last)
in ≤ℝ-of-rec ∣ x +ℝ y ∣ℝ (∣ x ∣ℝ +ℝ ∣ y ∣ℝ) C 0≤C h
abs-centre-even-helper : (A B C : ℚ) →
A - B ≤ (A - C) + (C - B)
abs-centre-even-helper A B C =
let e : (A - C) + (C - B) ≡ A - B
e =
begin (A + neg C) + (C + neg B)
≡⟨ sym (+-assoc (A + neg C) C (neg B)) ⟩
A + neg C + C + neg B
≡⟨ cong (λ z → z + neg B)
(begin (A + neg C) + C
≡⟨ +-assoc A (neg C) C ⟩
A + (neg C + C)
≡⟨ cong (A +_) (+-inverseˡ C) ⟩
A + 0ℚ
≡⟨ +-identityʳ A ⟩ A ∎) ⟩
A + neg B ∎
in ≤-reflexive (sym e)
abs-centre-even : (l u : ℚ) (l≤u : l ≤ u) →
let A = halveQ (absLo (neg u) (neg l) + absHi (neg u) (neg l))
B = halveQ (absLo l u + absHi l u)
in ∣ A - B ∣ ≤ embed 2 * (u - l)
abs-centre-even l u l≤u =
let w = u - l
neg≤ : neg u ≤ neg l
neg≤ =
let p : l ≤ u
p = l≤u
in neg-antimono-≤ p
A = halveQ (absLo (neg u) (neg l) + absHi (neg u) (neg l))
B = halveQ (absLo l u + absHi l u)
c = halveQ (l + u)
pneg = halveQ (neg u + neg l)
pneg≡ : pneg ≡ neg c
pneg≡ =
begin pneg
≡⟨ halveQ-distrib (neg u) (neg l) ⟩
halveQ (neg u) + halveQ (neg l)
≡⟨ cong (_+ halveQ (neg l)) (halveQ-neg u) ⟩
neg (halveQ u) + halveQ (neg l)
≡⟨ cong (neg (halveQ u) +_) (halveQ-neg l) ⟩
neg (halveQ u) + neg (halveQ l)
≡⟨ sym (neg-distrib-+ (halveQ u) (halveQ l)) ⟩
neg (halveQ u + halveQ l)
≡⟨ cong neg (+-comm (halveQ u) (halveQ l)) ⟩
neg (halveQ l + halveQ u)
≡⟨ cong neg (sym (halveQ-distrib l u)) ⟩
neg (halveQ (l + u)) ∎
h1 = abs-centre-≤ (neg u) (neg l) neg≤
h2 = abs-centre-≤ l u l≤u
neg-eq : (neg l) - (neg u) ≡ w
neg-eq =
begin (neg l) - (neg u)
≡⟨ cong (neg l +_) (neg-involutive u) ⟩
neg l + u
≡⟨ +-comm (neg l) u ⟩
u + neg l
≡⟨ refl ⟩
u - l
≡⟨ refl ⟩
w ∎
h1' : ∣ A - ∣ pneg ∣ ∣ ≤ w
h1' = subst (λ z → ∣ A - ∣ pneg ∣ ∣ ≤ z) neg-eq h1
h2' : ∣ B - ∣ c ∣ ∣ ≤ w
h2' = h2
abs≡ : ∣ pneg ∣ ≡ ∣ c ∣
abs≡ =
begin ∣ pneg ∣
≡⟨ cong ∣_∣ pneg≡ ⟩
∣ neg c ∣
≡⟨ ∣-p∣≡∣p∣ c ⟩
∣ c ∣ ∎
main : ∣ A - B ∣ ≤ embed 2 * w
main =
let e1 : ∣ A - ∣ c ∣ ∣ ≤ w
e1 = subst (λ z → ∣ A - z ∣ ≤ w) abs≡ h1'
t1 : A - ∣ c ∣ ≤ w
t1 = ≤-trans (r≤|r| (A - ∣ c ∣)) e1
a-aux : ∣ c ∣ - B ≡ neg (B - ∣ c ∣)
a-aux = begin
∣ c ∣ - B
≡⟨⟩
∣ c ∣ + neg B
≡⟨ +-comm ∣ c ∣ (neg B) ⟩
neg B + ∣ c ∣
≡⟨ cong (neg B +_) (sym (neg-involutive ∣ c ∣)) ⟩
neg B + neg (neg ∣ c ∣)
≡⟨ sym (neg-distrib-+ B (neg ∣ c ∣)) ⟩
neg (B + neg ∣ c ∣)
≡⟨⟩
neg (B - ∣ c ∣) ∎
t2 : ∣ c ∣ - B ≤ w
t2 = subst (λ z → z ≤ w) (sym a-aux)
(≤-trans (r≤|r| (neg (B - ∣ c ∣)))
(≤-trans (≤-reflexive (∣-p∣≡∣p∣ (B - ∣ c ∣))) h2'))
s : A - B ≤ w + w
s =
let k : A - B ≤ (A - ∣ c ∣) + (∣ c ∣ - B)
k = abs-centre-even-helper A B ∣ c ∣
d : (A - ∣ c ∣) + (∣ c ∣ - B) ≤ w + w
d = +-mono-≤ t1 t2
in ≤-trans k d
t1' : B - ∣ c ∣ ≤ w
t1' = ≤-trans (r≤|r| (B - ∣ c ∣)) h2'
a-aux' : ∣ c ∣ - A ≡ neg (A - ∣ c ∣)
a-aux' = begin
∣ c ∣ - A
≡⟨⟩
∣ c ∣ + neg A
≡⟨ +-comm ∣ c ∣ (neg A) ⟩
neg A + ∣ c ∣
≡⟨ cong (neg A +_) (sym (neg-involutive ∣ c ∣)) ⟩
neg A + neg (neg ∣ c ∣)
≡⟨ sym (neg-distrib-+ A (neg ∣ c ∣)) ⟩
neg (A + neg ∣ c ∣)
≡⟨⟩
neg (A - ∣ c ∣) ∎
t2' : ∣ c ∣ - A ≤ w
t2' = subst (λ z → z ≤ w) (sym a-aux')
(≤-trans (r≤|r| (neg (A - ∣ c ∣)))
(≤-trans (≤-reflexive (∣-p∣≡∣p∣ (A - ∣ c ∣))) e1))
s' : B - A ≤ w + w
s' =
let k' : B - A ≤ (B - ∣ c ∣) + (∣ c ∣ - A)
k' = abs-centre-even-helper B A ∣ c ∣
d' : (B - ∣ c ∣) + (∣ c ∣ - A) ≤ w + w
d' = +-mono-≤ t1' t2'
in ≤-trans k' d'
sAbs : ∣ A - B ∣ ≤ w + w
sAbs = case_of_ {B = ∣ A - B ∣ ≤ w + w}
(∣p∣≡p∨∣p∣≡-p (A - B))
λ { (inj₁ abs≡') →
subst (λ z → z ≤ w + w) (sym abs≡') s
; (inj₂ abs≡') →
subst (λ z → z ≤ w + w)
(sym (trans abs≡' (neg-sub A B))) s'
}
double : w + w ≡ embed 2 * w
double =
begin w + w
≡⟨ cong₂ _+_ (sym (*-identityˡ w)) (sym (*-identityˡ w)) ⟩
1ℚ * w + 1ℚ * w
≡⟨ sym (*-distribʳ-+ w 1ℚ 1ℚ) ⟩
(1ℚ + 1ℚ) * w
≡⟨ cong (_* w) (sym 2ℚ≡1+1) ⟩
embed 2 * w ∎
in subst (λ z → ∣ A - B ∣ ≤ z) double sAbs
in main
abs-even : (x : RealI) → ∣ negℝ x ∣ℝ ≈ℝ ∣ x ∣ℝ
abs-even x =
let C = embed 2 * width x 0
C≥0 : 0ℚ ≤ C
C≥0 =
let w≥0 : 0ℚ ≤ width x 0
w≥0 = 0≤width-n x 0
p : embed 2 * 0ℚ ≤ embed 2 * width x 0
p = *-monoˡ-≤-nonNeg (embed 2)
{{pos⇒nonNeg (embed 2) {{positive 0<embed2}}}} w≥0
z : embed 2 * 0ℚ ≡ 0ℚ
z = *-zeroʳ (embed 2)
in subst (λ z → z ≤ C) z p
h : ∀ n →
∣ centre ∣ negℝ x ∣ℝ n - centre ∣ x ∣ℝ n ∣ ≤ C * recipPow2 n
h n =
let l0 = l x (n +N n)
u0 = u x (n +N n)
l0≤u0 : l0 ≤ u0
l0≤u0 = <⇒≤ (RealI.lo (node x (n +N n)))
main = abs-centre-even l0 u0 l0≤u0
Aeq : centre ∣ negℝ x ∣ℝ n ≡
halveQ (absLo (neg u0) (neg l0) + absHi (neg u0) (neg l0))
Aeq =
let e = centre-abs-node (negℝ x) n
pl : l (negℝ x) (n +N n) ≡ neg u0
pl = l-neg x (n +N n)
pu : u (negℝ x) (n +N n) ≡ neg l0
pu = u-neg x (n +N n)
in trans e
(cong₂ (λ a b → halveQ (absLo a b + absHi a b)) pl pu)
main' :
∣ centre ∣ negℝ x ∣ℝ n - centre ∣ x ∣ℝ n ∣ ≤
embed 2 * (u0 - l0)
main' =
let A = halveQ (absLo (neg u0) (neg l0) + absHi (neg u0) (neg l0))
B = halveQ (absLo l0 u0 + absHi l0 u0)
Beq : centre ∣ x ∣ℝ n ≡ B
Beq = centre-abs-node x n
eq : centre ∣ negℝ x ∣ℝ n - centre ∣ x ∣ℝ n ≡ A - B
eq = cong₂ _-_ Aeq Beq
in subst (λ z → ∣ z ∣ ≤ embed 2 * (u0 - l0)) (sym eq) main
w≤ : width x (n +N n) ≤ width x 0 * recipPow2 n
w≤ =
let p : width x (n +N n) ≤ width x 0 * recipPow2 (n +N n)
p = width-n x (n +N n)
q : recipPow2 (n +N n) ≤ recipPow2 n
q = recipPow2-≤ n
in ≤-trans p
(*-monoˡ-≤-nonNeg (width x 0)
{{nonNegative (0≤width-n x 0)}} q)
double≤ : embed 2 * (u0 - l0) ≤
embed 2 * (width x 0 * recipPow2 n)
double≤ = *-monoˡ-≤-nonNeg (embed 2)
{{pos⇒nonNeg (embed 2) {{positive 0<embed2}}}} w≤
last : embed 2 * (width x 0 * recipPow2 n) ≡ C * recipPow2 n
last =
begin
embed 2 * (width x 0 * recipPow2 n)
≡⟨ sym (*-assoc (embed 2) (width x 0) (recipPow2 n)) ⟩
(embed 2 * width x 0) * recipPow2 n
≡⟨ refl ⟩
C * recipPow2 n ∎
in ≤-trans main' (≤-trans double≤ (≤-reflexive last))
in ≈ℝ-of-rec ∣ negℝ x ∣ℝ ∣ x ∣ℝ C C≥0 h