{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.OrderLe where
open import Data.Empty using (⊥-elim)
open import Data.Product using (_×_; _,_)
open import Data.Sum using (inj₁; inj₂)
open import Data.Rational using (ℚ; 0ℚ; _+_; _-_; _*_; _≤_; ∣_∣)
renaming (-_ to neg)
open import Data.Rational.Properties using
(≤-refl; ≤-reflexive; +-mono-≤; +-assoc; +-comm; +-identityˡ; ≮⇒≥; +-identityʳ
; +-inverseˡ; +-inverseʳ; *-distribʳ-+; neg-antimono-≤; neg-distrib-+
; ∣p∣≡p∨∣p∣≡-p)
open import Relation.Nullary using (¬_)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; sym; cong; cong₂; module ≡-Reasoning)
open ≡-Reasoning
open import Base.RationalRing using (neg-involutive)
open import Real.Interval using (RealI)
open import Real.Interval.Arith using (_+ℝ_; negℝ; _-ℝ_)
open import Real.Interval.ArithLaws using (+ℝ-comm)
open import Real.Interval.Equiv using (_≈ℝ_; ≈ℝ-sym)
open import Real.IntervalEquiv using
(l; u; centre; width; width-n; centre-l; centre-u; recipPow2)
open import Real.Interval.Order using (_<ℝ_; <-irrefl; <-trans; <-cotrans)
open import Real.Interval.OrderComplete.Base using (_≤ℝ_)
open import Real.Interval.Node using (0≤width-n; centre-add; centre-neg)
open import Real.Interval.Kit using (≈ℝ-of-rec; ≈ℝ-of-eq)
open import Real.Interval.OrderLaws using (≈-<-resp; <-sub)
open import Real.Interval.Mul using (sub-monoˡ)
open import Real.Interval.Mul.Order using (≈-<-respʳ)
open import Real.Interval.Reasoning using (begin≤_; _≤⟨_⟩_; _≤∎)
sub-mono : {a a' b b' : ℚ} → a ≤ a' → b' ≤ b → a - b ≤ a' - b'
sub-mono {a} {a'} {b} {b'} p q = begin≤
a - b
≤⟨ sub-monoˡ p ⟩
a' - b
≤⟨ +-mono-≤ (≤-refl {a'}) (neg-antimono-≤ q) ⟩
a' - b'
≤∎
reassoc : (a b c : ℚ) → (a - b) + (b - c) ≡ a - c
reassoc a b c =
begin
(a - b) + (b - c)
≡⟨ +-assoc a (neg b) (b - c) ⟩
a + (neg b + (b - c))
≡⟨ cong (a +_) (sym (+-assoc (neg b) b (neg c))) ⟩
a + ((neg b + b) + neg c)
≡⟨ cong (a +_) (cong (_+ neg c) (+-inverseˡ b)) ⟩
a + (0ℚ + neg c)
≡⟨ cong (a +_) (+-identityˡ (neg c)) ⟩
a - c
∎
neg-diff-flip : (a b : ℚ) → neg (a - b) ≡ b - a
neg-diff-flip a b =
begin
neg (a - b)
≡⟨ neg-distrib-+ a (neg b) ⟩
neg a + neg (neg b)
≡⟨ cong (neg a +_) (neg-involutive b) ⟩
neg a + b
≡⟨ +-comm (neg a) b ⟩
b + neg a
≡⟨⟩
b - a
∎
≤ℝ-refl : {x : RealI} → x ≤ℝ x
≤ℝ-refl {x} = <-irrefl x
<⇒≤ℝ : {x y : RealI} → x <ℝ y → x ≤ℝ y
<⇒≤ℝ {x} x<y y<x = <-irrefl x (<-trans x<y y<x)
≈⇒≤ℝ : {x y : RealI} → x ≈ℝ y → x ≤ℝ y
≈⇒≤ℝ {x} {y} x≈y y<x =
<-irrefl x (≈-<-resp (≈ℝ-sym x≈y) y<x)
<⇒¬≤ℝ : {x y : RealI} → x <ℝ y → ¬ (y ≤ℝ x)
<⇒¬≤ℝ x<y y≤x = y≤x x<y
module AntisymAux (x y : RealI)
(x≤y : x ≤ℝ y) (y≤x : y ≤ℝ x) where
gap1 : ∀ n → l x n ≤ u y n
gap1 n = ≮⇒≥ (λ hyp → x≤y (n , hyp))
gap2 : ∀ n → l y n ≤ u x n
gap2 n = ≮⇒≥ (λ hyp → y≤x (n , hyp))
cx-cy≤ : ∀ n → centre x n - centre y n ≤ width x n + width y n
cx-cy≤ n =
begin≤
centre x n - centre y n
≤⟨ sub-mono (centre-u x n) (centre-l y n) ⟩
u x n - l y n
≤⟨ ≤-reflexive (sym (reassoc (u x n) (l x n) (l y n))) ⟩
(u x n - l x n) + (l x n - l y n)
≤⟨ +-mono-≤
(≤-reflexive (refl {x = u x n - l x n}))
(sub-monoˡ {a = l x n} {b = u y n} {c = l y n} (gap1 n)) ⟩
(u x n - l x n) + (u y n - l y n)
≤⟨ ≤-reflexive (refl {x = (u x n - l x n) + (u y n - l y n)}) ⟩
width x n + width y n
≤∎
cy-cx≤ : ∀ n → centre y n - centre x n ≤ width y n + width x n
cy-cx≤ n =
begin≤
centre y n - centre x n
≤⟨ sub-mono (centre-u y n) (centre-l x n) ⟩
u y n - l x n
≤⟨ ≤-reflexive (sym (reassoc (u y n) (l y n) (l x n))) ⟩
(u y n - l y n) + (l y n - l x n)
≤⟨ +-mono-≤
(≤-reflexive (refl {x = u y n - l y n}))
(sub-monoˡ {a = l y n} {b = u x n} {c = l x n} (gap2 n)) ⟩
(u y n - l y n) + (u x n - l x n)
≤⟨ ≤-reflexive (refl {x = (u y n - l y n) + (u x n - l x n)}) ⟩
width y n + width x n
≤∎
abs≤ : ∀ n → ∣ centre x n - centre y n ∣ ≤ width x n + width y n
abs≤ n with ∣p∣≡p∨∣p∣≡-p (centre x n - centre y n)
... | inj₁ eq = begin≤
∣ centre x n - centre y n ∣
≤⟨ ≤-reflexive eq ⟩
centre x n - centre y n
≤⟨ cx-cy≤ n ⟩
width x n + width y n
≤∎
... | inj₂ eq = begin≤
∣ centre x n - centre y n ∣
≤⟨ ≤-reflexive eq ⟩
neg (centre x n - centre y n)
≤⟨ ≤-reflexive (neg-diff-flip (centre x n) (centre y n)) ⟩
centre y n - centre x n
≤⟨ cy-cx≤ n ⟩
width y n + width x n
≤⟨ ≤-reflexive (+-comm (width y n) (width x n)) ⟩
width x n + width y n
≤∎
C : ℚ
C = width x 0 + width y 0
0≤C : 0ℚ ≤ C
0≤C = begin≤
0ℚ
≤⟨ +-mono-≤ (0≤width-n x 0) (0≤width-n y 0) ⟩
width x 0 + width y 0
≤∎
geo≤ : ∀ n → width x n + width y n ≤ C * recipPow2 n
geo≤ n =
begin≤
width x n + width y n
≤⟨ +-mono-≤ (width-n x n) (width-n y n) ⟩
(width x 0 * recipPow2 n) + (width y 0 * recipPow2 n)
≤⟨ ≤-reflexive (sym (*-distribʳ-+ (recipPow2 n) (width x 0) (width y 0))) ⟩
C * recipPow2 n
≤∎
body : ∀ n →
∣ centre x n - centre y n ∣ ≤ C * recipPow2 n
body n = begin≤
∣ centre x n - centre y n ∣
≤⟨ abs≤ n ⟩
width x n + width y n
≤⟨ geo≤ n ⟩
C * recipPow2 n
≤∎
≤ℝ-antisym : {x y : RealI} → x ≤ℝ y → y ≤ℝ x → x ≈ℝ y
≤ℝ-antisym {x} {y} x≤y y≤x =
≈ℝ-of-rec x y (AntisymAux.C x y x≤y y≤x)
(AntisymAux.0≤C x y x≤y y≤x)
(AntisymAux.body x y x≤y y≤x)
≈⇒≤ℝ∧ : {x y : RealI} → x ≈ℝ y → (x ≤ℝ y) × (y ≤ℝ x)
≈⇒≤ℝ∧ x≈y = ≈⇒≤ℝ x≈y , ≈⇒≤ℝ (≈ℝ-sym x≈y)
≤ℝ-resp-≈ : {x x' y y' : RealI} →
x ≈ℝ x' → y ≈ℝ y' → x ≤ℝ y → x' ≤ℝ y'
≤ℝ-resp-≈ {x} {x'} {y} {y'} x≈x' y≈y' x≤y y'<x' =
x≤y (≈-<-respʳ (≈ℝ-sym x≈x')
(≈-<-resp (≈ℝ-sym y≈y') y'<x'))
<-≤ℝ-trans : {x y z : RealI} → x <ℝ y → y ≤ℝ z → x <ℝ z
<-≤ℝ-trans {x} {y} {z} x<y y≤z
with <-cotrans x<y
... | inj₁ x<z = x<z
... | inj₂ z<y = ⊥-elim (y≤z z<y)
≤ℝ-<trans : {x y z : RealI} → x ≤ℝ y → y <ℝ z → x <ℝ z
≤ℝ-<trans {x} {y} {z} x≤y y<z
with <-cotrans y<z
... | inj₁ y<x = ⊥-elim (x≤y y<x)
... | inj₂ x<z = x<z
+-cancelʳ : (a b : RealI) → (a +ℝ b) -ℝ b ≈ℝ a
+-cancelʳ a b = ≈ℝ-of-eq ((a +ℝ b) -ℝ b) a λ n →
begin
centre ((a +ℝ b) -ℝ b) n
≡⟨ centre-add (a +ℝ b) (negℝ b) n ⟩
centre (a +ℝ b) n + centre (negℝ b) n
≡⟨ cong₂ _+_ (centre-add a b n) (centre-neg b n) ⟩
(centre a n + centre b n) + neg (centre b n)
≡⟨ +-assoc (centre a n) (centre b n) (neg (centre b n)) ⟩
centre a n + (centre b n + neg (centre b n))
≡⟨ cong (centre a n +_) (+-inverseʳ (centre b n)) ⟩
centre a n + 0ℚ
≡⟨ +-identityʳ (centre a n) ⟩
centre a n
∎
<-+mono-reflect : {x y z : RealI} → y +ℝ z <ℝ x +ℝ z → y <ℝ x
<-+mono-reflect {x} {y} {z} h =
≈-<-respʳ (+-cancelʳ x z)
(≈-<-resp (+-cancelʳ y z) (<-sub (y +ℝ z) (x +ℝ z) z h))
≤ℝ-+-mono : {x y z : RealI} → x ≤ℝ y → x +ℝ z ≤ℝ y +ℝ z
≤ℝ-+-mono {x} {y} {z} x≤y y+z<x+z =
x≤y (<-+mono-reflect {x} {y} {z} y+z<x+z)
≤ℝ-+-monoˡ : {x y z : RealI} → x ≤ℝ y → z +ℝ x ≤ℝ z +ℝ y
≤ℝ-+-monoˡ {x} {y} {z} x≤y =
≤ℝ-resp-≈ (+ℝ-comm x z) (+ℝ-comm y z)
(≤ℝ-+-mono {x} {y} {z} x≤y)