{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.OrderLaws where
open import Data.Nat using (ℕ; zero; suc; _≥_; _⊔_; _^_; _∸_; s≤s; z≤n)
renaming (_≤_ to _≤ℕ_; _+_ to _+ℕ_)
open import Data.Nat.Properties using (m≤m⊔n; m≤n⊔m; m∸n+n≡m)
renaming (≤-trans to ≤ℕ-trans; +-suc to +-sucℕ; +-comm to +-commℕ
; +-identityʳ to +-identityʳℕ)
open import Data.Product using (Σ; _,_; _×_; proj₁; proj₂)
open import Data.Rational using
(ℚ; 0ℚ; 1ℚ; _+_; _-_; _*_; _≤_; _<_; ∣_∣; Positive; NonZero; positive)
open import Data.Rational.Base using (1/_) renaming (-_ to neg)
open import Data.Rational.Properties using
(≤-refl; ≤-reflexive; ≤-trans; <⇒≤; ≤-<-trans; <-≤-trans; <-trans; +-mono-≤
; +-mono-<; +-monoˡ-<; +-monoʳ-<; *-monoˡ-≤-nonNeg; *-monoʳ-<-pos
; *-monoˡ-<-pos; pos⇒nonZero; positive⁻¹; 1/pos⇒pos; pos⇒nonNeg; *-inverseʳ
; *-inverseˡ; *-comm; *-assoc; *-identityʳ; *-identityˡ; *-zeroˡ; *-zeroʳ
; *-distribˡ-+; +-inverseʳ; +-inverseˡ; +-identityʳ; +-identityˡ; +-comm
; +-assoc; neg-distrib-+; neg-antimono-≤; neg-antimono-<; ∣-p∣≡∣p∣)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; cong; cong₂; sym; subst; module ≡-Reasoning)
open ≡-Reasoning
open import Base.RationalRing using (neg-involutive)
open import Real using (embed; ε; half; embed-suc-pos; embed-mono-<)
open import Real.Interval using (RealI)
open import Real.IntervalEquiv using
(node; l; u; centre; width; width-n; width-1step; centre-l; centre-u; u-mono
; l-mono; recipPow2; bound-w; n<2^n; 0<width)
open import Real.Interval.Equiv using (_≈ℝ_)
open import Real.Interval.Order using (_<ℝ_)
open import Real.Interval.Kit using
(0<half; half≤1; two-half; half+half≡1; 0<recipPow2; embed-suc∸1)
open import Real.Interval.Node using (l-hom; u-hom; l-neg; u-neg)
open import Real.Interval.Mul using (le-shift)
open import Real.Interval.Arith using (_+ℝ_; _-ℝ_; negℝ)
open import Real.Interval.Rational using (r≤|r|)
open import Real.Archimedean using (ε-archimedean)
width-below : (r : RealI) (b : ℚ) → 0ℚ < b → Σ ℕ (λ m → width r m < b)
width-below r b 0<b = M , result
where
w0 : ℚ
w0 = width r 0
0<w0 : 0ℚ < w0
0<w0 = 0<width r
b-pos : Positive b
b-pos = positive 0<b
b-nz : NonZero b
b-nz = pos⇒nonZero b {{b-pos}}
inv-b : ℚ
inv-b = 1/_ b {{b-nz}}
0<inv-b : 0ℚ < inv-b
0<inv-b = positive⁻¹ inv-b {{1/pos⇒pos b {{b-pos}}}}
0≤inv-b : 0ℚ ≤ inv-b
0≤inv-b = <⇒≤ 0<inv-b
w0-pos : Positive w0
w0-pos = positive 0<w0
q : ℚ
q = w0 * inv-b
0≤q : 0ℚ ≤ q
0≤q = subst (λ z → z ≤ w0 * inv-b) (*-zeroʳ w0)
(*-monoˡ-≤-nonNeg w0 {{pos⇒nonNeg w0 {{w0-pos}}}} 0≤inv-b)
M : ℕ
M = proj₁ (bound-w q 0≤q)
q≤M : q ≤ embed M
q≤M = proj₂ (bound-w q 0≤q)
M<2^m : M Data.Nat.< 2 ^ M
M<2^m = n<2^n M
M<2^m' : embed M < embed (2 ^ M)
M<2^m' = embed-mono-< M<2^m
q<2^m : q < embed (2 ^ M)
q<2^m = ≤-<-trans q≤M M<2^m'
em-inv : ℚ
em-inv = recipPow2 M
0<em-inv : 0ℚ < em-inv
0<em-inv = 0<recipPow2 M
recipPow2-eq : recipPow2 M ≡ em-inv
recipPow2-eq = refl
1b-inv-b : inv-b * b ≡ 1ℚ
1b-inv-b = *-inverseˡ b {{b-nz}}
step1 : (w0 * inv-b) * b < embed (2 ^ M) * b
step1 = *-monoˡ-<-pos b {{b-pos}} q<2^m
lhs≡ : (w0 * inv-b) * b ≡ w0
lhs≡ = begin
(w0 * inv-b) * b
≡⟨ *-assoc w0 inv-b b ⟩
w0 * (inv-b * b)
≡⟨ cong (w0 *_) 1b-inv-b ⟩
w0 * 1ℚ
≡⟨ *-identityʳ w0 ⟩
w0
∎
w0<em-b : w0 < embed (2 ^ M) * b
w0<em-b = subst (λ z → z < embed (2 ^ M) * b) lhs≡ step1
step2 : w0 * em-inv < (embed (2 ^ M) * b) * em-inv
step2 = *-monoˡ-<-pos em-inv {{positive 0<em-inv}} w0<em-b
s : ℚ
s = embed (suc (2 ^ M ∸ 1))
s≡E : s ≡ embed (2 ^ M)
s≡E = embed-suc∸1 M
s-nz : NonZero s
s-nz = pos⇒nonZero s {{embed-suc-pos}}
E*em-inv≡1 : embed (2 ^ M) * em-inv ≡ 1ℚ
E*em-inv≡1 = begin
embed (2 ^ M) * em-inv
≡⟨ cong (λ t → t * em-inv) (sym s≡E) ⟩
s * em-inv
≡⟨ *-inverseʳ s {{s-nz}} ⟩
1ℚ
∎
rhs≡ : (embed (2 ^ M) * b) * em-inv ≡ b
rhs≡ = begin
(embed (2 ^ M) * b) * em-inv
≡⟨ *-assoc (embed (2 ^ M)) b em-inv ⟩
embed (2 ^ M) * (b * em-inv)
≡⟨ cong (embed (2 ^ M) *_) (*-comm b em-inv) ⟩
embed (2 ^ M) * (em-inv * b)
≡⟨ sym (*-assoc (embed (2 ^ M)) em-inv b) ⟩
(embed (2 ^ M) * em-inv) * b
≡⟨ cong (_* b) E*em-inv≡1 ⟩
1ℚ * b
≡⟨ *-identityˡ b ⟩
b
∎
w0-em-inv<b : w0 * em-inv < b
w0-em-inv<b = subst (λ z → w0 * em-inv < z) rhs≡ step2
result : width r M < b
result = ≤-<-trans (width-n r M)
(≤-<-trans (≤-reflexive (cong (w0 *_) recipPow2-eq))
w0-em-inv<b)
width-step-dec : (r : RealI) (n : ℕ) → width r (suc n) ≤ width r n
width-step-dec r n =
≤-trans (width-1step r n)
(≤-trans (*-monoˡ-≤-nonNeg (width r n)
{{pos⇒nonNeg (width r n)
{{positive (0<width (node r n))}}}}
half≤1)
(≤-reflexive (*-identityʳ (width r n))))
width-mono-ge : (r : RealI) (n k : ℕ) → width r (n +ℕ k) ≤ width r n
width-mono-ge r n zero =
≤-reflexive (cong (width r) (+-identityʳℕ n))
width-mono-ge r n (suc k) =
≤-trans (subst (λ j → width r j ≤ width r (n +ℕ k)) (sym (+-sucℕ n k))
(width-step-dec r (n +ℕ k)))
(width-mono-ge r n k)
width-dec : (r : RealI) {n m : ℕ} → n ≤ℕ m → width r m ≤ width r n
width-dec r {n} {m} n≤m =
subst (λ j → width r j ≤ width r n)
(begin
n +ℕ (m ∸ n)
≡⟨ +-commℕ n (m ∸ n) ⟩
(m ∸ n) +ℕ n
≡⟨ m∸n+n≡m n≤m ⟩
m
∎)
(width-mono-ge r n (m ∸ n))
width-below-strict : (r : RealI) (b : ℚ) (M₀ : ℕ) → 0ℚ < b
→ Σ ℕ (λ m → M₀ ≤ℕ m × width r m < b)
width-below-strict r b M₀ 0<b =
m , m≤m⊔n M₀ M , ≤-<-trans (width-dec r (m≤n⊔m M₀ M)) wb
where
w-res : Σ ℕ (λ j → width r j < b)
w-res = width-below r b 0<b
M : ℕ
M = proj₁ w-res
wb : width r M < b
wb = proj₂ w-res
m : ℕ
m = M₀ ⊔ M
u≤c+w : (r : RealI) (k : ℕ) → u r k ≤ centre r k + width r k
u≤c+w r k =
le-shift {x = u r k} {y = width r k} {z = centre r k}
(subst (λ z → z ≤ centre r k)
(sym (sub-cancel-2 (u r k) (l r k)))
(centre-l r k))
where
sub-cancel-2 : ∀ a b → a - (a - b) ≡ b
sub-cancel-2 a b = begin
a - (a - b)
≡⟨⟩
a + neg (a + neg b)
≡⟨ cong (a +_) (neg-distrib-+ a (neg b)) ⟩
a + (neg a + neg (neg b))
≡⟨ sym (+-assoc a (neg a) (neg (neg b))) ⟩
(a + neg a) + neg (neg b)
≡⟨ cong (λ z → z + neg (neg b)) (+-inverseʳ a) ⟩
0ℚ + neg (neg b)
≡⟨ +-identityˡ (neg (neg b)) ⟩
neg (neg b)
≡⟨ neg-involutive b ⟩
b ∎
1<2 : 1ℚ < embed 2
1<2 = embed-mono-< {1} {2} (s≤s (s≤s z≤n))
half<1 : half < 1ℚ
half<1 =
subst (λ z → half < z)
(*-inverseʳ (embed 2) {{pos⇒nonZero (embed 2) {{embed-suc-pos}}}})
(*-monoˡ-<-pos half {{positive 0<half}} 1<2)
half+half²<1 : half + half * half < 1ℚ
half+half²<1 =
let
step1 : half + half * half ≡ half * (1ℚ + half)
step1 = begin
half + half * half
≡⟨ cong (λ z → z + half * half) (sym (*-identityʳ half)) ⟩
half * 1ℚ + half * half
≡⟨ sym (*-distribˡ-+ half 1ℚ half) ⟩
half * (1ℚ + half)
∎
step2 : half * (1ℚ + half) < half * (1ℚ + 1ℚ)
step2 = *-monoʳ-<-pos half {{positive 0<half}}
(+-monoˡ-< 1ℚ half<1)
step3 : half * (1ℚ + 1ℚ) ≡ 1ℚ
step3 = begin
half * (1ℚ + 1ℚ)
≡⟨ sym (*-distribˡ-+ half 1ℚ 1ℚ) ⟩
half * 1ℚ + half * 1ℚ
≡⟨ cong₂ _+_ (*-identityʳ half) (*-identityʳ half) ⟩
half + half
≡⟨ half+half≡1 ⟩
1ℚ
∎
in subst (λ z → half + half * half < z) step3
(subst (λ z → z < half * (1ℚ + 1ℚ)) (sym step1) step2)
3d/4<d : (d : ℚ) → 0ℚ < d → d * half + (d * half) * half < d
3d/4<d d 0<d =
subst (λ z → z < d)
(begin
d * (half + half * half)
≡⟨ *-distribˡ-+ d half (half * half) ⟩
d * half + d * (half * half)
≡⟨ cong (d * half +_) (sym (*-assoc d half half)) ⟩
d * half + (d * half) * half
∎)
(subst (λ z → d * (half + half * half) < z) (*-identityʳ d)
(*-monoʳ-<-pos d {{positive 0<d}} half+half²<1))
≈-<-resp : {x y z : RealI} → x ≈ℝ y → x <ℝ z → y <ℝ z
≈-<-resp {x} {y} {z} x≈y (n , uxn<lzn) = m , uym<lzm
where
d : ℚ
d = l z n - u x n
0<d : 0ℚ < d
0<d = subst (λ w → w < l z n - u x n) (+-inverseʳ (u x n))
(+-monoˡ-< (neg (u x n)) uxn<lzn)
b : ℚ
b = d * half
0<b : 0ℚ < b
0<b = subst (λ w → w < b) (*-zeroˡ half)
(*-monoˡ-<-pos half {{positive 0<half}} 0<d)
e-res : Σ ℕ (λ j → ε j < b)
e-res = ε-archimedean b 0<b
k : ℕ
k = proj₁ e-res
εk<b : ε k < b
εk<b = proj₂ e-res
xy-res : Σ ℕ (λ j → ∀ p → p ≥ j → ∣ centre x p - centre y p ∣ < ε k)
xy-res = x≈y k
N : ℕ
N = proj₁ xy-res
hN : ∀ p → p ≥ N → ∣ centre x p - centre y p ∣ < ε k
hN = proj₂ xy-res
ws-res : Σ ℕ (λ j → (n ⊔ N) ≤ℕ j × width y j < b)
ws-res = width-below-strict y b (n ⊔ N) 0<b
m : ℕ
m = proj₁ ws-res
m≥nN : (n ⊔ N) ≤ℕ m
m≥nN = proj₁ (proj₂ ws-res)
wym<b : width y m < b
wym<b = proj₂ (proj₂ ws-res)
m≥n : n ≤ℕ m
m≥n = ≤ℕ-trans (m≤m⊔n n N) m≥nN
m≥N : N ≤ℕ m
m≥N = ≤ℕ-trans (m≤n⊔m n N) m≥nN
neg-diff : centre y m - centre x m ≡ neg (centre x m - centre y m)
neg-diff = begin
centre y m - centre x m
≡⟨⟩
centre y m + neg (centre x m)
≡⟨ +-comm (centre y m) (neg (centre x m)) ⟩
neg (centre x m) + centre y m
≡⟨ cong (neg (centre x m) +_) (sym (neg-involutive (centre y m))) ⟩
neg (centre x m) + neg (neg (centre y m))
≡⟨ sym (neg-distrib-+ (centre x m) (neg (centre y m))) ⟩
neg (centre x m + neg (centre y m))
≡⟨⟩
neg (centre x m - centre y m) ∎
swp : ∣ centre y m - centre x m ∣ ≡ ∣ centre x m - centre y m ∣
swp = begin
∣ centre y m - centre x m ∣
≡⟨ cong ∣_∣ neg-diff ⟩
∣ neg (centre x m - centre y m) ∣
≡⟨ ∣-p∣≡∣p∣ (centre x m - centre y m) ⟩
∣ centre x m - centre y m ∣
∎
cy-cx<b : ∣ centre y m - centre x m ∣ < b
cy-cx<b =
subst (λ z → z < b) (sym swp)
(<-trans (hN m m≥N) εk<b)
uxm≤uxn : u x m ≤ u x n
uxm≤uxn = u-mono x m≥n
lzn≤lzm : l z n ≤ l z m
lzn≤lzm = l-mono z m≥n
uy≤cy+wy : u y m ≤ centre y m + width y m
uy≤cy+wy = u≤c+w y m
cx≤uxm : centre x m ≤ u x m
cx≤uxm = centre-u x m
uy-ux-le : u y m - u x m ≤ width y m + ∣ centre y m - centre x m ∣
uy-ux-le =
let
a : u y m - u x m ≤ (centre y m + width y m) - centre x m
a = +-mono-≤ uy≤cy+wy (neg-antimono-≤ cx≤uxm)
b' : (centre y m + width y m) - centre x m
≡ width y m + (centre y m - centre x m)
b' = begin
(centre y m + width y m) - centre x m
≡⟨⟩
(centre y m + width y m) + neg (centre x m)
≡⟨ +-assoc (centre y m) (width y m) (neg (centre x m)) ⟩
centre y m + (width y m + neg (centre x m))
≡⟨ cong (centre y m +_) (+-comm (width y m) (neg (centre x m))) ⟩
centre y m + (neg (centre x m) + width y m)
≡⟨ sym (+-assoc (centre y m) (neg (centre x m)) (width y m)) ⟩
(centre y m + neg (centre x m)) + width y m
≡⟨ +-comm (centre y m + neg (centre x m)) (width y m) ⟩
width y m + (centre y m + neg (centre x m))
≡⟨⟩
width y m + (centre y m - centre x m) ∎
c : centre y m - centre x m ≤ ∣ centre y m - centre x m ∣
c = r≤|r| (centre y m - centre x m)
a' : u y m - u x m ≤ width y m + (centre y m - centre x m)
a' = subst (λ w → u y m - u x m ≤ w) b' a
in ≤-trans a' (+-mono-≤ (≤-refl {width y m}) c)
uy-ux<b : u y m - u x m < b + b
uy-ux<b = ≤-<-trans uy-ux-le (+-mono-< wym<b cy-cx<b)
b+b≡d : b + b ≡ d
b+b≡d = two-half d
uy-ux<d : u y m - u x m < d
uy-ux<d = subst (λ w → u y m - u x m < w) b+b≡d uy-ux<b
be≤0 : u x m - u x n ≤ 0ℚ
be≤0 = subst (λ z → u x m - u x n ≤ z) (+-inverseʳ (u x n))
(+-mono-≤ uxm≤uxn (≤-refl {neg (u x n)}))
cpart : l z n + (u x m - u x n) ≤ l z n
cpart = subst (λ w → l z n + (u x m - u x n) ≤ w)
(+-identityʳ (l z n))
(+-mono-≤ (≤-refl {l z n}) be≤0)
raw : (u y m - u x m) + u x m < (l z n - u x n) + u x m
raw = +-monoˡ-< (u x m) uy-ux<d
lhs≡ : (u y m - u x m) + u x m ≡ u y m
lhs≡ = begin
(u y m - u x m) + u x m
≡⟨ +-assoc (u y m) (neg (u x m)) (u x m) ⟩
u y m + (neg (u x m) + u x m)
≡⟨ cong (u y m +_) (+-inverseˡ (u x m)) ⟩
u y m + 0ℚ
≡⟨ +-identityʳ (u y m) ⟩
u y m
∎
rhs≡ : (l z n - u x n) + u x m ≡ l z n + (u x m - u x n)
rhs≡ = begin
(l z n - u x n) + u x m
≡⟨ +-assoc (l z n) (neg (u x n)) (u x m) ⟩
l z n + (neg (u x n) + u x m)
≡⟨ cong (l z n +_) (+-comm (neg (u x n)) (u x m)) ⟩
l z n + (u x m + neg (u x n))
≡⟨⟩
l z n + (u x m - u x n)
∎
a< : u y m < l z n + (u x m - u x n)
a< = subst (λ w → w < l z n + (u x m - u x n)) lhs≡
(subst (λ w → (u y m - u x m) + u x m < w) rhs≡ raw)
uym<lzm : u y m < l z m
uym<lzm = <-≤-trans (<-≤-trans a< cpart) lzn≤lzm
<-+mono : (x y z : RealI) → x <ℝ y → x +ℝ z <ℝ y +ℝ z
<-+mono x y z (n , p) = k , goal
where
g : ℚ
g = l y n - u x n
0<g : 0ℚ < g
0<g = subst (λ w → w < l y n - u x n) (+-inverseʳ (u x n))
(+-monoˡ-< (neg (u x n)) p)
k-res : Σ ℕ (λ j → n ≤ℕ j × width z j < g)
k-res = width-below-strict z g n 0<g
k : ℕ
k = proj₁ k-res
k≥n : n ≤ℕ k
k≥n = proj₁ (proj₂ k-res)
wzk<g : width z k < g
wzk<g = proj₂ (proj₂ k-res)
uxk≤uxn : u x k ≤ u x n
uxk≤uxn = u-mono x k≥n
lyn≤lyk : l y n ≤ l y k
lyn≤lyk = l-mono y k≥n
ux+g≡ly : u x n + g ≡ l y n
ux+g≡ly = begin
u x n + g
≡⟨⟩
u x n + (l y n + neg (u x n))
≡⟨ sym (+-assoc (u x n) (l y n) (neg (u x n))) ⟩
(u x n + l y n) + neg (u x n)
≡⟨ cong (λ z → z + neg (u x n)) (+-comm (u x n) (l y n)) ⟩
(l y n + u x n) + neg (u x n)
≡⟨ +-assoc (l y n) (u x n) (neg (u x n)) ⟩
l y n + (u x n + neg (u x n))
≡⟨ cong (l y n +_) (+-inverseʳ (u x n)) ⟩
l y n + 0ℚ
≡⟨ +-identityʳ (l y n) ⟩
l y n
∎
l+w≡u : l z k + width z k ≡ u z k
l+w≡u = begin
l z k + width z k
≡⟨⟩
l z k + (u z k + neg (l z k))
≡⟨ sym (+-assoc (l z k) (u z k) (neg (l z k))) ⟩
(l z k + u z k) + neg (l z k)
≡⟨ cong (λ w → w + neg (l z k)) (+-comm (l z k) (u z k)) ⟩
(u z k + l z k) + neg (l z k)
≡⟨ +-assoc (u z k) (l z k) (neg (l z k)) ⟩
u z k + (l z k + neg (l z k))
≡⟨ cong (u z k +_) (+-inverseʳ (l z k)) ⟩
u z k + 0ℚ
≡⟨ +-identityʳ (u z k) ⟩
u z k
∎
first : u x k + width z k ≤ u x n + width z k
first = +-mono-≤ uxk≤uxn (≤-refl {width z k})
second : u x n + width z k < u x n + g
second = +-monoʳ-< (u x n) wzk<g
mid : u x k + width z k < l y n
mid = subst (λ w → u x k + width z k < w) ux+g≡ly
(≤-<-trans first second)
core : u x k + width z k < l y k
core = <-≤-trans mid lyn≤lyk
added : (u x k + width z k) + l z k < l y k + l z k
added = +-monoˡ-< (l z k) core
reorder : (u x k + width z k) + l z k
≡ u x k + (l z k + width z k)
reorder = begin
(u x k + width z k) + l z k
≡⟨ +-assoc (u x k) (width z k) (l z k) ⟩
u x k + (width z k + l z k)
≡⟨ cong (u x k +_) (+-comm (width z k) (l z k)) ⟩
u x k + (l z k + width z k)
∎
shifted : u x k + (l z k + width z k) < l y k + l z k
shifted = subst (λ q → q < l y k + l z k) reorder added
shifted-final : u x k + u z k < l y k + l z k
shifted-final =
subst (λ a → u x k + a < l y k + l z k) l+w≡u shifted
lhs≡ : u (x +ℝ z) k ≡ u x k + u z k
lhs≡ = u-hom x z k
rhs≡ : l (y +ℝ z) k ≡ l y k + l z k
rhs≡ = l-hom y z k
goal : u (x +ℝ z) k < l (y +ℝ z) k
goal = subst (λ a → a < l (y +ℝ z) k) (sym lhs≡)
(subst (λ b → u x k + u z k < b) (sym rhs≡) shifted-final)
<-neg : (x y : RealI) → x <ℝ y → negℝ y <ℝ negℝ x
<-neg x y (n , p) = n , goal
where
raw : neg (l y n) < neg (u x n)
raw = neg-antimono-< p
lhs≡ : u (negℝ y) n ≡ neg (l y n)
lhs≡ = u-neg y n
rhs≡ : l (negℝ x) n ≡ neg (u x n)
rhs≡ = l-neg x n
goal : u (negℝ y) n < l (negℝ x) n
goal = subst (λ a → a < l (negℝ x) n) (sym lhs≡)
(subst (λ b → neg (l y n) < b) (sym rhs≡) raw)
<-sub : (x y z : RealI) → x <ℝ y → x -ℝ z <ℝ y -ℝ z
<-sub x y z p = <-+mono x y (negℝ z) p