{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.Rational where
open import Data.Empty using (⊥-elim)
open import Data.Integer using (+_; +<+) renaming (_*_ to _*ℤ_; _<_ to _<ℤ_)
import Data.Integer.Properties as ℤP
open import Data.Nat using (ℕ; zero; suc; z≤n; s≤s; _^_; _∸_)
renaming (_+_ to _+ℕ_; _*_ to _*ℕ_; _<_ to _<ℕ_)
import Data.Nat.Properties as ℕP
open import Data.Rational using (ℚ; 0ℚ; 1ℚ; _⊓_; _⊔_; _+_; _-_; _*_; _<_
; _≤_; 1/_; ∣_∣; fromℚᵘ; toℚᵘ; NonZero) renaming (-_ to neg)
open import Data.Rational.Properties using
(+-comm; +-inverseʳ; neg-distrib-+; +-mono-<-≤; ≤-refl; *-assoc; *-identityˡ
; *-comm; <⇒≤; <-cmp; ≤-trans; *-inverseʳ; *-identityʳ; ≤-antisym
; neg-antimono-≤; 0≤∣p∣; ∣-p∣≡∣p∣; *-inverseˡ; ∣p∣≡p∨∣p∣≡-p
; 0≤p⇒∣p∣≡p; toℚᵘ-cancel-<; toℚᵘ-fromℚᵘ; p⊓q≤p; p⊓q≤q; p≤p⊔q; p≤q⊔p
; p≤q⇒p⊓q≡p; p≥q⇒p⊓q≡q; p≤q⇒p⊔q≡q; p≥q⇒p⊔q≡p; ⊓-glb; ⊔-lub; ⊓-sel; ⊔-sel
; +-assoc; +-identityˡ)
open import Data.Rational.Unnormalised.Base using
(ℚᵘ; mkℚᵘ; _≃_; *≡*; *<*) renaming (_<_ to _<ᵘ_)
open import Data.Rational.Unnormalised.Properties using (<-respˡ-≃; <-respʳ-≃)
open import Data.Sum using (_⊎_; inj₁; inj₂)
open import Function.Base using (case_of_)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; cong; cong₂; sym; trans; subst; subst₂; module ≡-Reasoning)
open ≡-Reasoning
open import Relation.Nullary.Negation using (¬_)
open import Relation.Binary.Definitions using (tri<; tri≈; tri>)
open import Base.RationalRing using (neg-involutive; sub-add-split)
open import Real.Interval.Reasoning using (begin≤_; _≈⟨_⟩_; _≤⟨_⟩_; _≤∎)
pos-diff : ∀ a b → a < b → 0ℚ < b - a
pos-diff a b a<b =
subst (λ z → z < b - a)
(+-inverseʳ a)
(+-mono-<-≤ a<b (≤-refl {neg a}))
sub-add : (a b c d : ℚ) → (a + b) - (c + d) ≡ (a - c) + (b - d)
sub-add a b c d = sub-add-split a c b d
cancel-plus : ∀ x y z → (x + y) - (x + z) ≡ y - z
cancel-plus x y z = begin
(x + y) - (x + z)
≡⟨ cong (λ w → (x + y) + w) (neg-distrib-+ x z) ⟩
(x + y) + (neg x + neg z)
≡⟨ +-assoc x y (neg x + neg z) ⟩
x + (y + (neg x + neg z))
≡⟨ cong (λ w → x + w)
(trans (sym (+-assoc y (neg x) (neg z)))
(cong (λ w → w + neg z) (+-comm y (neg x)))) ⟩
x + ((neg x + y) + neg z)
≡⟨ cong (λ w → x + w) (+-assoc (neg x) y (neg z)) ⟩
x + (neg x + (y + neg z))
≡⟨ sym (+-assoc x (neg x) (y + neg z)) ⟩
(x + neg x) + (y + neg z)
≡⟨ cong (λ w → w + (y + neg z)) (+-inverseʳ x) ⟩
0ℚ + (y + neg z)
≡⟨ +-identityˡ (y + neg z) ⟩
y + neg z
≡⟨ refl ⟩
y - z
∎
negsub : ∀ x y → neg (x - y) ≡ y - x
negsub x y = begin
neg (x - y)
≡⟨ refl ⟩
neg (x + neg y)
≡⟨ neg-distrib-+ x (neg y) ⟩
neg x + neg (neg y)
≡⟨ cong (λ z → neg x + z) (neg-involutive y) ⟩
neg x + y
≡⟨ +-comm (neg x) y ⟩
y + neg x
≡⟨ refl ⟩
y - x
∎
neg-sub-neg : ∀ a b → neg a - neg b ≡ b - a
neg-sub-neg a b = begin
neg a - neg b
≡⟨ refl ⟩
neg a + neg (neg b)
≡⟨ cong (λ z → neg a + z) (neg-involutive b) ⟩
neg a + b
≡⟨ +-comm (neg a) b ⟩
b + neg a
≡⟨ refl ⟩
b - a
∎
tri-elim : ∀ {P : Set} (a b : ℚ)
→ (a < b → P) → (a ≡ b → P) → (b < a → P) → P
tri-elim a b lt eq gt =
case <-cmp a b of λ where
(tri< a<b _ _) → lt a<b
(tri≈ _ a≡b _) → eq a≡b
(tri> _ _ b<a) → gt b<a
min<max : ∀ a b → ¬ (a ≡ b) → a ⊓ b < a ⊔ b
min<max a b a≠b = tri-elim a b
(λ a<b →
subst₂ _<_
(sym (p≤q⇒p⊓q≡p (<⇒≤ a<b)))
(sym (p≤q⇒p⊔q≡q (<⇒≤ a<b)))
a<b)
(λ a≡b → ⊥-elim (a≠b a≡b))
(λ b<a →
subst₂ _<_
(sym (p≥q⇒p⊓q≡q (<⇒≤ b<a)))
(sym (p≥q⇒p⊔q≡p (<⇒≤ b<a)))
b<a)
r≤|r| : ∀ r → r ≤ ∣ r ∣
r≤|r| r =
let
helper : ∣ r ∣ ≡ r ⊎ ∣ r ∣ ≡ neg r → r ≤ ∣ r ∣
helper = λ where
(inj₁ |r|≡r) → begin≤
r ≈⟨ sym |r|≡r ⟩
∣ r ∣ ≤∎
(inj₂ |r|≡-r) →
let
0≤-r : 0ℚ ≤ neg r
0≤-r = subst (λ z → 0ℚ ≤ z) |r|≡-r (0≤∣p∣ r)
r≤0 : r ≤ 0ℚ
r≤0 = subst (λ z → z ≤ 0ℚ) (neg-involutive r) (neg-antimono-≤ 0≤-r)
in begin≤
r ≤⟨ r≤0 ⟩
0ℚ ≤⟨ 0≤-r ⟩
neg r ≈⟨ sym |r|≡-r ⟩
∣ r ∣ ≤∎
in helper (∣p∣≡p∨∣p∣≡-p r)
-r≤|r| : ∀ r → neg r ≤ ∣ r ∣
-r≤|r| r = subst (λ z → neg r ≤ z) (∣-p∣≡∣p∣ r) (r≤|r| (neg r))
mag : ℚ → ℚ → ℚ
mag l u = ∣ l ∣ ⊔ ∣ u ∣
mag-≤ : ∀ {l u x : ℚ} → l ≤ x → x ≤ u → ∣ x ∣ ≤ mag l u
mag-≤ {l} {u} {x} l≤x x≤u =
let
helper : ∣ x ∣ ≡ x ⊎ ∣ x ∣ ≡ neg x → ∣ x ∣ ≤ mag l u
helper = λ where
(inj₁ |x|≡x) → begin≤
∣ x ∣ ≈⟨ |x|≡x ⟩
x ≤⟨ x≤u ⟩
u ≤⟨ r≤|r| u ⟩
∣ u ∣ ≤⟨ p≤q⊔p ∣ l ∣ ∣ u ∣ ⟩
∣ l ∣ ⊔ ∣ u ∣ ≤∎
(inj₂ |x|≡-x) →
let
0≤-x : 0ℚ ≤ neg x
0≤-x = subst (λ z → 0ℚ ≤ z) |x|≡-x (0≤∣p∣ x)
x≤0 : x ≤ 0ℚ
x≤0 = subst (λ z → z ≤ 0ℚ) (neg-involutive x) (neg-antimono-≤ 0≤-x)
l≤0 : l ≤ 0ℚ
l≤0 = ≤-trans l≤x x≤0
0≤-l : 0ℚ ≤ neg l
0≤-l = neg-antimono-≤ l≤0
|l|≡-l : ∣ l ∣ ≡ neg l
|l|≡-l = subst (λ z → z ≡ neg l) (∣-p∣≡∣p∣ l)
(0≤p⇒∣p∣≡p {neg l} 0≤-l)
in begin≤
∣ x ∣ ≈⟨ |x|≡-x ⟩
neg x ≤⟨ neg-antimono-≤ l≤x ⟩
neg l ≈⟨ sym |l|≡-l ⟩
∣ l ∣ ≤⟨ p≤p⊔q ∣ l ∣ ∣ u ∣ ⟩
∣ l ∣ ⊔ ∣ u ∣ ≤∎
in helper (∣p∣≡p∨∣p∣≡-p x)
0<2^t : (t : ℕ) → 0 <ℕ 2 ^ t
0<2^t zero = s≤s z≤n
0<2^t (suc t) = ℕP.≤-trans (s≤s z≤n) (ℕP.*-monoʳ-≤ 2 (0<2^t t))
suc∸1 : {n : ℕ} → 0 <ℕ n → suc (n ∸ 1) ≡ n
suc∸1 {n} 0<n = begin
suc (n ∸ 1)
≡⟨ refl ⟩
1 +ℕ (n ∸ 1)
≡⟨ ℕP.+-comm 1 (n ∸ 1) ⟩
(n ∸ 1) +ℕ 1
≡⟨ ℕP.m∸n+n≡m 0<n ⟩
n
∎
0<sucd*2^t : (d t : ℕ) → 0 <ℕ suc d *ℕ 2 ^ t
0<sucd*2^t d t = ℕP.≤-trans (0<2^t t) (ℕP.m≤n*m (2 ^ t) (suc d))
rawComb : (N d t : ℕ) → ℚᵘ
rawComb N d t = mkℚᵘ (+ N) (suc d *ℕ 2 ^ t ∸ 1)
rawR : (k : ℕ) → ℚᵘ
rawR k = mkℚᵘ (+ 1) k
combFrac : (N d t : ℕ) → ℚ
combFrac N d t = fromℚᵘ (rawComb N d t)
flip-≃ : {a b : ℚᵘ} → _≃_ a b → _≃_ b a
flip-≃ (*≡* e) = *≡* (sym e)
rawCross : (N d k t : ℕ) →
N *ℕ suc k <ℕ suc d *ℕ 2 ^ t →
(+ N) *ℤ (+ suc k) <ℤ (+ 1) *ℤ (+ suc (suc d *ℕ 2 ^ t ∸ 1))
rawCross N d k t h =
let dd = suc d *ℕ 2 ^ t ∸ 1
dd-eq : suc dd ≡ suc d *ℕ 2 ^ t
dd-eq = suc∸1 (0<sucd*2^t d t)
in
ℤP.<-≤-trans
(ℤP.≤-<-trans
(ℤP.≤-reflexive (ℤP.+◃n≡+n (N *ℕ suc k)))
(ℤP.<-≤-trans
(+<+ h)
(ℤP.≤-reflexive (cong +_ (sym dd-eq)))))
(ℤP.≤-reflexive (sym (ℤP.*-identityˡ (+ suc dd))))
comb-strict : (N d k t : ℕ) →
N *ℕ suc k <ℕ suc d *ℕ 2 ^ t →
combFrac N d t < fromℚᵘ (rawR k)
comb-strict N d k t h =
toℚᵘ-cancel-<
(let eqL : _≃_ (toℚᵘ (combFrac N d t)) (rawComb N d t)
eqL = toℚᵘ-fromℚᵘ (rawComb N d t)
eqR : _≃_ (toℚᵘ (fromℚᵘ (rawR k))) (rawR k)
eqR = toℚᵘ-fromℚᵘ (rawR k)
cross : _<ᵘ_ (rawComb N d t) (rawR k)
cross = *<* (rawCross N d k t h)
p1 : _<ᵘ_ (toℚᵘ (combFrac N d t)) (rawR k)
p1 = <-respˡ-≃ (flip-≃ eqL) cross
p2 : _<ᵘ_ (toℚᵘ (combFrac N d t))
(toℚᵘ (fromℚᵘ (rawR k)))
p2 = <-respʳ-≃ (flip-≃ eqR) p1
in p2)
recip-*-hom : (a b : ℚ) ⦃ na : NonZero a ⦄ ⦃ nb : NonZero b ⦄
⦃ nab : NonZero (a * b) ⦄ →
(1/_) (a * b) ≡ (1/_) a * (1/_) b
recip-*-hom a b ⦃ na ⦄ ⦃ nb ⦄ ⦃ nab ⦄ =
let ia = (1/_) a
ib = (1/_) b
x = ia * ib
p : x * (a * b) ≡ 1ℚ
p =
begin (ia * ib) * (a * b)
≡⟨ *-assoc ia ib (a * b) ⟩
ia * (ib * (a * b))
≡⟨ cong (ia *_) (sym (*-assoc ib a b)) ⟩
ia * ((ib * a) * b)
≡⟨ cong (ia *_) (cong (λ z → z * b) (*-comm ib a)) ⟩
ia * ((a * ib) * b)
≡⟨ cong (ia *_) (*-assoc a ib b) ⟩
ia * (a * (ib * b))
≡⟨ sym (*-assoc ia a (ib * b)) ⟩
(ia * a) * (ib * b)
≡⟨ cong₂ (λ u v → u * v) (*-inverseˡ a) (*-inverseˡ b) ⟩
1ℚ ∎
q : x ≡ (1/_) (a * b)
q =
begin x
≡⟨ sym (*-identityʳ x) ⟩
x * 1ℚ
≡⟨ cong (x *_) (sym (*-inverseʳ (a * b) ⦃ nab ⦄)) ⟩
x * ((a * b) * (1/_) (a * b))
≡⟨ sym (*-assoc x (a * b) ((1/_) (a * b))) ⟩
(x * (a * b)) * (1/_) (a * b)
≡⟨ cong (λ z → z * (1/_) (a * b)) p ⟩
1ℚ * (1/_) (a * b)
≡⟨ *-identityˡ ((1/_) (a * b)) ⟩
(1/_) (a * b) ∎
in sym q
min-neg : ∀ a b → (neg a) ⊓ (neg b) ≡ neg (a ⊔ b)
min-neg a b = ≤-antisym upper lower
where
lower : neg (a ⊔ b) ≤ (neg a) ⊓ (neg b)
lower = ⊓-glb (neg-antimono-≤ (p≤p⊔q a b))
(neg-antimono-≤ (p≤q⊔p a b))
upper : (neg a) ⊓ (neg b) ≤ neg (a ⊔ b)
upper =
let
helper : a ⊔ b ≡ a ⊎ a ⊔ b ≡ b → (neg a) ⊓ (neg b) ≤ neg (a ⊔ b)
helper = λ where
(inj₁ max≡a) → begin≤
(neg a) ⊓ (neg b) ≤⟨ p⊓q≤p (neg a) (neg b) ⟩
neg a ≈⟨ cong neg (sym max≡a) ⟩
neg (a ⊔ b) ≤∎
(inj₂ max≡b) → begin≤
(neg a) ⊓ (neg b) ≤⟨ p⊓q≤q (neg a) (neg b) ⟩
neg b ≈⟨ cong neg (sym max≡b) ⟩
neg (a ⊔ b) ≤∎
in helper (⊔-sel a b)
max-neg : ∀ a b → (neg a) ⊔ (neg b) ≡ neg (a ⊓ b)
max-neg a b = ≤-antisym upper lower
where
upper : (neg a) ⊔ (neg b) ≤ neg (a ⊓ b)
upper = ⊔-lub (neg-antimono-≤ (p⊓q≤p a b))
(neg-antimono-≤ (p⊓q≤q a b))
lower : neg (a ⊓ b) ≤ (neg a) ⊔ (neg b)
lower =
let
helper : a ⊓ b ≡ a ⊎ a ⊓ b ≡ b → neg (a ⊓ b) ≤ (neg a) ⊔ (neg b)
helper = λ where
(inj₁ min≡a) → begin≤
neg (a ⊓ b) ≈⟨ cong neg min≡a ⟩
neg a ≤⟨ p≤p⊔q (neg a) (neg b) ⟩
(neg a) ⊔ (neg b) ≤∎
(inj₂ min≡b) → begin≤
neg (a ⊓ b) ≈⟨ cong neg min≡b ⟩
neg b ≤⟨ p≤q⊔p (neg a) (neg b) ⟩
(neg a) ⊔ (neg b) ≤∎
in helper (⊓-sel a b)