{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.Arith where
open import Data.Rational using (ℚ; 0ℚ; 1ℚ; _+_; _-_; _≤_)
open import Data.Rational.Base using (_÷_; 1/_) renaming (-_ to neg)
open import Data.Product using (_,_; proj₁; proj₂)
open import Data.Rational.Properties using
(+-mono-<; +-mono-≤; neg-antimono-<; neg-antimono-≤; *-distribʳ-+;
≤-reflexive; ≤-trans)
open import Relation.Binary.PropositionalEquality using
(_≡_; cong; sym; subst; module ≡-Reasoning)
open ≡-Reasoning
open import Real using (embed)
open import Real.Interval using (RealI; dyadic)
open import Real.Interval.Rational using (sub-add; neg-sub-neg)
div-add : (a b : ℚ) → (a + b) ÷ embed 2 ≡ (a ÷ embed 2) + (b ÷ embed 2)
div-add a b = begin
(a + b) ÷ embed 2
≡⟨ *-distribʳ-+ (1/ embed 2) a b ⟩
(a ÷ embed 2) + (b ÷ embed 2)
∎
0ℝ : RealI
0ℝ = dyadic 0ℚ 0
1ℝ : RealI
1ℝ = dyadic 1ℚ 0
infixl 6 _+ℝ_
_+ℝ_ : RealI → RealI → RealI
RealI.l (x +ℝ y) = RealI.l x + RealI.l y
RealI.u (x +ℝ y) = RealI.u x + RealI.u y
RealI.lo (x +ℝ y) = +-mono-< (RealI.lo x) (RealI.lo y)
RealI.next (x +ℝ y) = RealI.next x +ℝ RealI.next y
RealI.nest (x +ℝ y) = nest1 , nest2 , nest3
where
nest1 : RealI.l x + RealI.l y
≤ RealI.l (RealI.next x) + RealI.l (RealI.next y)
nest1 = +-mono-≤ (proj₁ (RealI.nest x)) (proj₁ (RealI.nest y))
nest2 : RealI.u (RealI.next x) + RealI.u (RealI.next y)
≤ RealI.u x + RealI.u y
nest2 = +-mono-≤ (proj₁ (proj₂ (RealI.nest x)))
(proj₁ (proj₂ (RealI.nest y)))
nest3 : (RealI.u (RealI.next x) + RealI.u (RealI.next y))
- (RealI.l (RealI.next x) + RealI.l (RealI.next y))
≤ ((RealI.u x + RealI.u y) - (RealI.l x + RealI.l y)) ÷ embed 2
nest3 =
let
ux = RealI.u x; uy = RealI.u y
lx = RealI.l x; ly = RealI.l y
ux' = RealI.u (RealI.next x); uy' = RealI.u (RealI.next y)
lx' = RealI.l (RealI.next x); ly' = RealI.l (RealI.next y)
wx = ux - lx; wy = uy - ly
wx' = ux' - lx'; wy' = uy' - ly'
step-x : wx' ≤ wx ÷ embed 2
step-x = proj₂ (proj₂ (RealI.nest x))
step-y : wy' ≤ wy ÷ embed 2
step-y = proj₂ (proj₂ (RealI.nest y))
step1 : wx' + wy' ≤ (wx ÷ embed 2) + (wy ÷ embed 2)
step1 = +-mono-≤ step-x step-y
step2 : (wx ÷ embed 2) + (wy ÷ embed 2) ≡ (wx + wy) ÷ embed 2
step2 = begin
(wx ÷ embed 2) + (wy ÷ embed 2)
≡⟨ sym (div-add wx wy) ⟩
(wx + wy) ÷ embed 2
∎
r-eq : (wx + wy) ÷ embed 2
≡ ((ux + uy) - (lx + ly)) ÷ embed 2
r-eq = begin
(wx + wy) ÷ embed 2
≡⟨ cong (λ z → z ÷ embed 2) (sym (sub-add ux uy lx ly)) ⟩
((ux + uy) - (lx + ly)) ÷ embed 2
∎
T : ℚ
T = ((ux + uy) - (lx + ly)) ÷ embed 2
core : wx' + wy' ≤ T
core = ≤-trans step1
(≤-trans (≤-reflexive step2) (≤-reflexive r-eq))
l-eq : wx' + wy' ≡ (ux' + uy') - (lx' + ly')
l-eq = begin
wx' + wy'
≡⟨ sym (sub-add ux' uy' lx' ly') ⟩
(ux' + uy') - (lx' + ly')
∎
in
subst (λ z → z ≤ T) l-eq core
negℝ : RealI → RealI
RealI.l (negℝ x) = neg (RealI.u x)
RealI.u (negℝ x) = neg (RealI.l x)
RealI.lo (negℝ x) = neg-antimono-< (RealI.lo x)
RealI.next (negℝ x) = negℝ (RealI.next x)
RealI.nest (negℝ x) = nest1 , nest2 , nest3
where
nest1 : neg (RealI.u x) ≤ neg (RealI.u (RealI.next x))
nest1 = neg-antimono-≤ (proj₁ (proj₂ (RealI.nest x)))
nest2 : neg (RealI.l (RealI.next x)) ≤ neg (RealI.l x)
nest2 = neg-antimono-≤ (proj₁ (RealI.nest x))
nest3 : neg (RealI.l (RealI.next x)) - neg (RealI.u (RealI.next x))
≤ (neg (RealI.l x) - neg (RealI.u x)) ÷ embed 2
nest3 =
let
a = RealI.l x; b = RealI.u x
a' = RealI.l (RealI.next x); b' = RealI.u (RealI.next x)
w-eq : neg a - neg b ≡ b - a
w-eq = neg-sub-neg a b
w'-eq : neg a' - neg b' ≡ b' - a'
w'-eq = neg-sub-neg a' b'
inner : b' - a' ≤ (b - a) ÷ embed 2
inner = proj₂ (proj₂ (RealI.nest x))
target-eq : (neg a - neg b) ÷ embed 2 ≡ (b - a) ÷ embed 2
target-eq = begin
(neg a - neg b) ÷ embed 2
≡⟨ cong (λ z → z ÷ embed 2) w-eq ⟩
(b - a) ÷ embed 2
∎
in
≤-trans
(≤-reflexive w'-eq)
(≤-trans
inner
(≤-reflexive (sym target-eq)))
infixl 6 _-ℝ_
_-ℝ_ : RealI → RealI → RealI
x -ℝ y = x +ℝ negℝ y