{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.Mul.Order where
open import Data.Nat using (ℕ; zero; suc; _^_; s≤s; z≤n; _≥_)
renaming (_⊔_ to _⊔ℕ_; _≤_ to _≤ℕ_; _<_ to _<ℕ_; _+_ to _+ℕ_; _*_ to _ℕ*_)
open import Data.Nat.Properties using
(m≤m⊔n; m≤n⊔m; *-suc; m<m+n; m≤m+n; ^-monoʳ-≤; *-monoʳ-≤)
renaming (≤-trans to ≤ℕ-trans; *-comm to *-commℕ; *-identityʳ to *-identityʳℕ)
open import Data.Product using (Σ; _,_; _×_; proj₁; proj₂)
open import Data.Rational using
(ℚ; 0ℚ; _⊓_; _⊔_; _+_; _-_; _*_; _<_; _≤_; ∣_∣; nonNegative; positive)
renaming (-_ to neg)
open import Data.Rational.Properties using
(+-identityʳ; neg-distrib-+; neg-distribˡ-*; ≤-trans; <⇒≤; ≤-<-trans
; <-≤-trans; *-monoˡ-≤-nonNeg; *-monoʳ-≤-nonNeg; pos*pos⇒pos; positive⁻¹
; *-zeroˡ; ∣-p∣≡∣p∣; ∣p+q∣≤∣p∣+∣q∣; neg-antimono-<; +-mono-<
; p≤q⇒p⊓q≡p; ⊓-comm; ⊔-comm; ≮⇒≥; p≤q⊔p; <-irrefl; <-trans; ≤-refl)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; cong; cong₂; sym; subst; subst₂; module ≡-Reasoning)
open ≡-Reasoning
open import Base.RationalRing using (neg-involutive)
open import Real using (embed; ε; half; embed-mono-≤; embed-suc-pos; ε-half)
open import Real.Archimedean using (ε-archimedean)
open import Real.IntervalEquiv using (node; l; u; centre; l-mono; u-mono)
open import Real.Interval using (RealI; δ; δ-pos; pos-pow)
open import Real.Interval.Arith using (0ℝ; _+ℝ_; _-ℝ_; negℝ)
open import Real.Interval.ArithLaws using
(x-ℝx; +ℝ-assoc; +ℝ-inverseˡ; +ℝ-identityˡ; +ℝ-identityʳ)
open import Real.Interval.Equiv using (_≈ℝ_; ≈ℝ-refl; ≈ℝ-sym; ≈ℝ-trans)
open import Real.Interval.Kit using
(n≤2n; *-mono-≤-nonNeg; recip-antitone; ≈ℝ-of-eq)
open import Real.Interval.Mul using (_*ℝ_)
open import Real.Interval.Mul.Laws using (*ℝ-distribʳ-+; *ℝ-comm)
open import Real.Interval.Node using
(node-*ℝ; node-negℝ; centre-add; u-dyadic; l-dyadic; centre-neg; l-neg; u-neg)
open import Real.Interval.Order using (_<ℝ_)
open import Real.Interval.OrderComplete.Base using (_≤ℝ_; ≤ℝ-trans)
open import Real.Interval.OrderLaws using (<-+mono; <-neg; <-sub; ≈-<-resp)
open import Real.Interval.Rational using (sub-add; max-neg; min-neg)
0<2^n-ℕ : ∀ n → 0 <ℕ 2 ^ n
0<2^n-ℕ zero = s≤s z≤n
0<2^n-ℕ (suc n) = ≤ℕ-trans (s≤s z≤n) (*-monoʳ-≤ 2 (0<2^n-ℕ n))
2*2^n≡2^n+2^n : ∀ n → 2 ℕ* 2 ^ n ≡ 2 ^ n +ℕ 2 ^ n
2*2^n≡2^n+2^n n =
begin
2 ℕ* 2 ^ n
≡⟨ *-commℕ 2 (2 ^ n) ⟩
2 ^ n ℕ* 2
≡⟨ *-suc (2 ^ n) 1 ⟩
2 ^ n +ℕ (2 ^ n ℕ* 1)
≡⟨ cong ((2 ^ n) +ℕ_) (*-identityʳℕ (2 ^ n)) ⟩
2 ^ n +ℕ 2 ^ n
∎
sucn≤2^n : ∀ n → suc n ≤ℕ 2 ^ n
sucn≤2^n zero = s≤s z≤n
sucn≤2^n (suc n) =
let
ih : suc n ≤ℕ 2 ^ n
ih = sucn≤2^n n
step1 : suc (suc n) ≤ℕ suc (2 ^ n)
step1 = s≤s {m = suc n} {n = 2 ^ n} ih
step2 : suc (2 ^ n) ≤ℕ 2 ^ n +ℕ 2 ^ n
step2 = m<m+n (2 ^ n) {2 ^ n} (0<2^n-ℕ n)
step3 : suc (suc n) ≤ℕ 2 ^ n +ℕ 2 ^ n
step3 = ≤ℕ-trans step1 step2
step4 : 2 ^ n +ℕ 2 ^ n ≡ 2 ^ suc n
step4 = sym (2*2^n≡2^n+2^n n)
in subst (λ z → suc (suc n) ≤ℕ z) step4 step3
δ≤ε : ∀ j → δ j ≤ ε j
δ≤ε j =
recip-antitone
{a = embed (suc j)} {b = embed (2 ^ suc j)}
(positive⁻¹ (embed (suc j)) {{embed-suc-pos}})
(embed-mono-≤ suclemma)
where
suclemma : suc j ≤ℕ 2 ^ suc j
suclemma =
≤ℕ-trans (sucn≤2^n j)
(subst (λ z → 2 ^ j ≤ℕ z)
(sym (2*2^n≡2^n+2^n j))
(m≤m+n (2 ^ j) (2 ^ j)))
δ-mono : ∀ {j K} → j ≤ℕ K → δ K ≤ δ j
δ-mono {j} {K} j≤K =
recip-antitone
{a = embed (2 ^ suc j)} {b = embed (2 ^ suc K)}
(positive⁻¹ (embed (2 ^ suc j)) {{pos-pow j}})
(embed-mono-≤ (^-monoʳ-≤ 2 (s≤s j≤K)))
neg-max4 : ∀ a b c d →
neg (((a ⊔ b) ⊔ (c ⊔ d)))
≡ ((neg a ⊓ neg b) ⊓ (neg c ⊓ neg d))
neg-max4 a b c d =
begin
neg (((a ⊔ b) ⊔ (c ⊔ d)))
≡⟨ sym (min-neg (a ⊔ b) (c ⊔ d)) ⟩
neg (a ⊔ b) ⊓ neg (c ⊔ d)
≡⟨ sym (cong₂ _⊓_ (min-neg a b) (min-neg c d)) ⟩
(neg a ⊓ neg b) ⊓ (neg c ⊓ neg d)
∎
neg-min4 : ∀ a b c d →
neg (((a ⊓ b) ⊓ (c ⊓ d)))
≡ ((neg a ⊔ neg b) ⊔ (neg c ⊔ neg d))
neg-min4 a b c d =
begin
neg (((a ⊓ b) ⊓ (c ⊓ d)))
≡⟨ sym (max-neg (a ⊓ b) (c ⊓ d)) ⟩
neg (a ⊓ b) ⊔ neg (c ⊓ d)
≡⟨ sym (cong₂ _⊔_ (max-neg a b) (max-neg c d)) ⟩
(neg a ⊔ neg b) ⊔ (neg c ⊔ neg d)
∎
l-prod-pos : (a b : RealI) →
0ℚ < RealI.l a → 0ℚ < RealI.l b →
RealI.l (a *ℝ b) ≡ RealI.l a * RealI.l b
l-prod-pos a b 0<la 0<lb =
let
La = RealI.l a; Ua = RealI.u a
Lb = RealI.l b; Ub = RealI.u b
c1 = La * Lb; c2 = La * Ub; c3 = Ua * Lb; c4 = Ua * Ub
0≤La = <⇒≤ 0<la
0≤Lb = <⇒≤ 0<lb
c1≤c2 = *-monoˡ-≤-nonNeg La {{nonNegative 0≤La}} (<⇒≤ (RealI.lo b))
c1≤c3 = *-monoʳ-≤-nonNeg Lb {{nonNegative 0≤Lb}} (<⇒≤ (RealI.lo a))
c3≤c4 = *-monoˡ-≤-nonNeg Ua
{{nonNegative (≤-trans 0≤La (<⇒≤ (RealI.lo a)))}}
(<⇒≤ (RealI.lo b))
in begin
(c1 ⊓ c2) ⊓ (c3 ⊓ c4)
≡⟨ cong (λ z → z ⊓ (c3 ⊓ c4)) (p≤q⇒p⊓q≡p c1≤c2) ⟩
c1 ⊓ (c3 ⊓ c4)
≡⟨ cong (c1 ⊓_) (p≤q⇒p⊓q≡p c3≤c4) ⟩
c1 ⊓ c3
≡⟨ p≤q⇒p⊓q≡p c1≤c3 ⟩
c1
∎
u-dyadic-0 : (K : ℕ) → u 0ℝ K ≡ δ K
u-dyadic-0 K =
begin
u 0ℝ K
≡⟨ u-dyadic 0ℚ K ⟩
δ K + 0ℚ
≡⟨ +-identityʳ (δ K) ⟩
δ K
∎
abs-neg : ∀ {a b : ℚ} → ∣ neg a - neg b ∣ ≡ ∣ a - b ∣
abs-neg {a} {b} =
begin
∣ neg a - neg b ∣
≡⟨ cong ∣_∣ (sym (neg-distrib-+ a (neg b))) ⟩
∣ neg (a + neg b) ∣
≡⟨ ∣-p∣≡∣p∣ (a - b) ⟩
∣ a - b ∣
∎
neg-flip : ∀ {x y : ℚ} → neg x < neg y → y < x
neg-flip {x} {y} h =
subst₂ _<_
(neg-involutive y) (neg-involutive x)
(neg-antimono-< {neg x} {neg y} h)
≈-neg : {x y : RealI} → x ≈ℝ y → negℝ x ≈ℝ negℝ y
≈-neg {x} {y} p k =
let N , h = p k
in N , λ n n≥N →
let
d = h n n≥N
rw : ∣ centre (negℝ x) n - centre (negℝ y) n ∣
≡ ∣ centre x n - centre y n ∣
rw =
begin
∣ centre (negℝ x) n - centre (negℝ y) n ∣
≡⟨ cong ∣_∣ (cong₂ _-_ (centre-neg x n) (centre-neg y n)) ⟩
∣ neg (centre x n) - neg (centre y n) ∣
≡⟨ abs-neg {centre x n} {centre y n} ⟩
∣ centre x n - centre y n ∣
∎
in subst (λ w → w < ε k) (sym rw) d
<-neg-inv : {a b : RealI} → negℝ a <ℝ negℝ b → b <ℝ a
<-neg-inv {a} {b} (n , h) = n , goal
where
h1 : neg (l a n) < neg (u b n)
h1 = subst₂ _<_ (u-neg a n) (l-neg b n) h
goal : u b n < l a n
goal = neg-flip h1
≈-<-respʳ : {x y z : RealI} → y ≈ℝ z → x <ℝ y → x <ℝ z
≈-<-respʳ {x} {y} {z} y≈z x<y =
<-neg-inv {a = z} {b = x}
(≈-<-resp (≈ℝ-sym (≈-neg (≈ℝ-sym y≈z))) (<-neg x y x<y))
≈-<-trans-helper : {a a' b b' : RealI} →
a ≈ℝ a' → a' <ℝ b' → b' ≈ℝ b → a <ℝ b
≈-<-trans-helper {a} {a'} {b'} {b} a≈a' a'<b' b'≈b =
≈-<-respʳ b'≈b (≈-<-resp (≈ℝ-sym a≈a') a'<b')
private
neg-max-min : ∀ La Ua Lb Ub →
neg (((La * Lb) ⊔ (La * Ub)) ⊔ ((Ua * Lb) ⊔ (Ua * Ub)))
≡ (((neg Ua * Lb) ⊓ (neg Ua * Ub)) ⊓ ((neg La * Lb) ⊓ (neg La * Ub)))
neg-max-min La Ua Lb Ub =
begin
neg (((La * Lb) ⊔ (La * Ub)) ⊔ ((Ua * Lb) ⊔ (Ua * Ub)))
≡⟨ neg-max4 (La * Lb) (La * Ub) (Ua * Lb) (Ua * Ub) ⟩
(neg (La * Lb) ⊓ neg (La * Ub)) ⊓ (neg (Ua * Lb) ⊓ neg (Ua * Ub))
≡⟨ cong₂ _⊓_
(cong₂ _⊓_
(neg-distribˡ-* La Lb) (neg-distribˡ-* La Ub))
(cong₂ _⊓_
(neg-distribˡ-* Ua Lb) (neg-distribˡ-* Ua Ub)) ⟩
((neg La * Lb) ⊓ (neg La * Ub)) ⊓ ((neg Ua * Lb) ⊓ (neg Ua * Ub))
≡⟨ ⊓-comm (((neg La) * Lb) ⊓ ((neg La) * Ub))
(((neg Ua) * Lb) ⊓ ((neg Ua) * Ub)) ⟩
((neg Ua * Lb) ⊓ (neg Ua * Ub)) ⊓ ((neg La * Lb) ⊓ (neg La * Ub))
∎
neg-min-max : ∀ La Ua Lb Ub →
neg (((La * Lb) ⊓ (La * Ub)) ⊓ ((Ua * Lb) ⊓ (Ua * Ub)))
≡ (((neg Ua * Lb) ⊔ (neg Ua * Ub)) ⊔ ((neg La * Lb) ⊔ (neg La * Ub)))
neg-min-max La Ua Lb Ub =
begin
neg (((La * Lb) ⊓ (La * Ub)) ⊓ ((Ua * Lb) ⊓ (Ua * Ub)))
≡⟨ neg-min4 (La * Lb) (La * Ub) (Ua * Lb) (Ua * Ub) ⟩
(neg (La * Lb) ⊔ neg (La * Ub)) ⊔ (neg (Ua * Lb) ⊔ neg (Ua * Ub))
≡⟨ cong₂ _⊔_
(cong₂ _⊔_
(neg-distribˡ-* La Lb) (neg-distribˡ-* La Ub))
(cong₂ _⊔_
(neg-distribˡ-* Ua Lb) (neg-distribˡ-* Ua Ub)) ⟩
((neg La * Lb) ⊔ (neg La * Ub)) ⊔ ((neg Ua * Lb) ⊔ (neg Ua * Ub))
≡⟨ ⊔-comm (((neg La) * Lb) ⊔ ((neg La) * Ub))
(((neg Ua) * Lb) ⊔ ((neg Ua) * Ub)) ⟩
((neg Ua * Lb) ⊔ (neg Ua * Ub)) ⊔ ((neg La * Lb) ⊔ (neg La * Ub))
∎
negℝ-*ℝ : (x y : RealI) → negℝ (x *ℝ y) ≈ℝ (negℝ x) *ℝ y
negℝ-*ℝ x y = ≈ℝ-of-eq _ _ centre-eq
where
l-eq : ∀ n → RealI.l (node (negℝ (x *ℝ y)) n)
≡ RealI.l (node ((negℝ x) *ℝ y) n)
l-eq n =
let
a = node x (2 ℕ* n); b = node y (2 ℕ* n)
La = RealI.l a; Ua = RealI.u a
Lb = RealI.l b; Ub = RealI.u b
LHS-unfold :
RealI.l (node (negℝ (x *ℝ y)) n)
≡ neg (((La * Lb) ⊔ (La * Ub)) ⊔ ((Ua * Lb) ⊔ (Ua * Ub)))
LHS-unfold =
begin
RealI.l (node (negℝ (x *ℝ y)) n)
≡⟨ cong RealI.l (node-negℝ (x *ℝ y) n) ⟩
RealI.l (negℝ (node (x *ℝ y) n))
≡⟨ cong (λ Z → neg (RealI.u Z)) (node-*ℝ x y n) ⟩
neg (((La * Lb) ⊔ (La * Ub)) ⊔ ((Ua * Lb) ⊔ (Ua * Ub)))
∎
RHS-unfold :
RealI.l (node ((negℝ x) *ℝ y) n)
≡ ((neg Ua * Lb) ⊓ (neg Ua * Ub)) ⊓ ((neg La * Lb) ⊓ (neg La * Ub))
RHS-unfold =
begin
RealI.l (node ((negℝ x) *ℝ y) n)
≡⟨ cong RealI.l (node-*ℝ (negℝ x) y n) ⟩
RealI.l (node (negℝ x) (2 ℕ* n) *ℝ node y (2 ℕ* n))
≡⟨ cong₂ (λ p q → ((p * Lb) ⊓ (p * Ub)) ⊓ ((q * Lb) ⊓ (q * Ub)))
(cong RealI.l (node-negℝ x (2 ℕ* n)))
(cong RealI.u (node-negℝ x (2 ℕ* n))) ⟩
((neg Ua * Lb) ⊓ (neg Ua * Ub)) ⊓ ((neg La * Lb) ⊓ (neg La * Ub))
∎
in begin
RealI.l (node (negℝ (x *ℝ y)) n)
≡⟨ LHS-unfold ⟩
neg (((La * Lb) ⊔ (La * Ub)) ⊔ ((Ua * Lb) ⊔ (Ua * Ub)))
≡⟨ neg-max-min La Ua Lb Ub ⟩
((neg Ua * Lb) ⊓ (neg Ua * Ub)) ⊓ ((neg La * Lb) ⊓ (neg La * Ub))
≡˘⟨ RHS-unfold ⟩
RealI.l (node ((negℝ x) *ℝ y) n)
∎
u-eq : ∀ n → RealI.u (node (negℝ (x *ℝ y)) n)
≡ RealI.u (node ((negℝ x) *ℝ y) n)
u-eq n =
let
a = node x (2 ℕ* n); b = node y (2 ℕ* n)
La = RealI.l a; Ua = RealI.u a
Lb = RealI.l b; Ub = RealI.u b
LHS-unfold :
RealI.u (node (negℝ (x *ℝ y)) n)
≡ neg (((La * Lb) ⊓ (La * Ub)) ⊓ ((Ua * Lb) ⊓ (Ua * Ub)))
LHS-unfold = begin
RealI.u (node (negℝ (x *ℝ y)) n)
≡⟨ cong RealI.u (node-negℝ (x *ℝ y) n) ⟩
RealI.u (negℝ (node (x *ℝ y) n))
≡⟨ cong (λ Z → neg (RealI.l Z)) (node-*ℝ x y n) ⟩
neg (((La * Lb) ⊓ (La * Ub)) ⊓ ((Ua * Lb) ⊓ (Ua * Ub)))
∎
RHS-unfold :
RealI.u (node ((negℝ x) *ℝ y) n)
≡ ((neg Ua * Lb) ⊔ (neg Ua * Ub)) ⊔ ((neg La * Lb) ⊔ (neg La * Ub))
RHS-unfold = begin
RealI.u (node ((negℝ x) *ℝ y) n)
≡⟨ cong RealI.u (node-*ℝ (negℝ x) y n) ⟩
RealI.u (node (negℝ x) (2 ℕ* n) *ℝ node y (2 ℕ* n))
≡⟨ cong₂ (λ p q → ((p * Lb) ⊔ (p * Ub)) ⊔ ((q * Lb) ⊔ (q * Ub)))
(cong RealI.l (node-negℝ x (2 ℕ* n)))
(cong RealI.u (node-negℝ x (2 ℕ* n))) ⟩
((neg Ua * Lb) ⊔ (neg Ua * Ub)) ⊔ ((neg La * Lb) ⊔ (neg La * Ub))
∎
in begin
RealI.u (node (negℝ (x *ℝ y)) n)
≡⟨ LHS-unfold ⟩
neg (((La * Lb) ⊓ (La * Ub)) ⊓ ((Ua * Lb) ⊓ (Ua * Ub)))
≡⟨ neg-min-max La Ua Lb Ub ⟩
((neg Ua * Lb) ⊔ (neg Ua * Ub)) ⊔ ((neg La * Lb) ⊔ (neg La * Ub))
≡⟨ sym RHS-unfold ⟩
RealI.u (node ((negℝ x) *ℝ y) n)
∎
centre-eq : ∀ n → centre (negℝ (x *ℝ y)) n
≡ centre ((negℝ x) *ℝ y) n
centre-eq n = cong₂ (λ a b → (a + b) * half) (l-eq n) (u-eq n)
+ℝ-cong : {x x' y y' : RealI} → x ≈ℝ x' → y ≈ℝ y' →
x +ℝ y ≈ℝ x' +ℝ y'
+ℝ-cong {x} {x'} {y} {y'} x≈x' y≈y' k =
let
fine = suc (2 ℕ* k)
N1 , h1 = x≈x' fine
N2 , h2 = y≈y' fine
N = N1 ⊔ℕ N2
in N , λ n n≥N →
let
n≥N1 = ≤ℕ-trans (m≤m⊔n N1 N2) n≥N
n≥N2 = ≤ℕ-trans (m≤n⊔m N1 N2) n≥N
d1 = h1 n n≥N1
d2 = h2 n n≥N2
cx = centre x n; cx' = centre x' n
cy = centre y n; cy' = centre y' n
eq : centre (x +ℝ y) n - centre (x' +ℝ y') n
≡ (cx - cx') + (cy - cy')
eq =
begin
centre (x +ℝ y) n - centre (x' +ℝ y') n
≡⟨ cong₂ _-_ (centre-add x y n) (centre-add x' y' n) ⟩
(cx + cy) - (cx' + cy')
≡⟨ sub-add cx cy cx' cy' ⟩
(cx - cx') + (cy - cy')
∎
bound : ∣ (cx - cx') + (cy - cy') ∣ ≤ ∣ cx - cx' ∣ + ∣ cy - cy' ∣
bound = ∣p+q∣≤∣p∣+∣q∣ (cx - cx') (cy - cy')
cc : ε fine + ε fine ≡ ε k
cc = ε-half k
in subst (λ z → ∣ z ∣ < ε k) (sym eq)
(subst (λ z → ∣ (cx - cx') + (cy - cy') ∣ < z) cc
(≤-<-trans bound (+-mono-< d1 d2)))
pos*pos : (a b : RealI) → 0ℝ <ℝ a → 0ℝ <ℝ b → 0ℝ <ℝ a *ℝ b
pos*pos a b (n , δn<lan) (m , δm<lbm) = K , goal
where
L = l a n
M = l b m
0<L : 0ℚ < L
0<L = <-≤-trans (δ-pos n)
(<⇒≤ (subst (λ z → z < L) (u-dyadic-0 n) δn<lan))
0<M : 0ℚ < M
0<M = <-≤-trans (δ-pos m)
(<⇒≤ (subst (λ z → z < M) (u-dyadic-0 m) δm<lbm))
0<LM : 0ℚ < L * M
0<LM = positive⁻¹ (L * M)
{{pos*pos⇒pos L {{positive 0<L}} M {{positive 0<M}}}}
j : ℕ
j = proj₁ (ε-archimedean (L * M) 0<LM)
δj<LM : δ j < L * M
δj<LM = ≤-<-trans (δ≤ε j) (proj₂ (ε-archimedean (L * M) 0<LM))
K : ℕ
K = j ⊔ℕ n ⊔ℕ m
K≥j : K ≥ j
K≥j = ≤ℕ-trans (m≤m⊔n j n) (m≤m⊔n (j ⊔ℕ n) m)
K≥n : K ≥ n
K≥n = ≤ℕ-trans (m≤n⊔m j n) (m≤m⊔n (j ⊔ℕ n) m)
K≥m : K ≥ m
K≥m = m≤n⊔m (j ⊔ℕ n) m
δK<LM : δ K < L * M
δK<LM = ≤-<-trans (δ-mono K≥j) δj<LM
2K≥n : 2 ℕ* K ≥ n
2K≥n = ≤ℕ-trans K≥n (n≤2n K)
2K≥m : 2 ℕ* K ≥ m
2K≥m = ≤ℕ-trans K≥m (n≤2n K)
la' = l a (2 ℕ* K)
lb' = l b (2 ℕ* K)
L≤la' : L ≤ la'
L≤la' = l-mono a 2K≥n
M≤lb' : M ≤ lb'
M≤lb' = l-mono b 2K≥m
0<la' : 0ℚ < la'
0<la' = <-≤-trans 0<L L≤la'
0<lb' : 0ℚ < lb'
0<lb' = <-≤-trans 0<M M≤lb'
LM≤la'lb' : L * M ≤ la' * lb'
LM≤la'lb' =
*-mono-≤-nonNeg (<⇒≤ 0<L) L≤la' (<⇒≤ 0<M) M≤lb'
l-prod : l (a *ℝ b) K ≡ la' * lb'
l-prod =
begin
l (a *ℝ b) K
≡⟨ cong RealI.l (node-*ℝ a b K) ⟩
RealI.l (node a (2 ℕ* K) *ℝ node b (2 ℕ* K))
≡⟨ l-prod-pos (node a (2 ℕ* K)) (node b (2 ℕ* K)) 0<la' 0<lb' ⟩
la' * lb'
∎
goal : u 0ℝ K < l (a *ℝ b) K
goal = subst (λ z → z < l (a *ℝ b) K) (sym (u-dyadic-0 K))
(subst (λ z → δ K < z) (sym l-prod)
(<-≤-trans δK<LM LM≤la'lb'))
mul-sub-distrib : (a b c : RealI) →
(a -ℝ b) *ℝ c ≈ℝ a *ℝ c -ℝ b *ℝ c
mul-sub-distrib a b c =
≈ℝ-trans (*ℝ-distribʳ-+ c a (negℝ b))
(≈ℝ-trans
(+ℝ-cong (≈ℝ-refl {a *ℝ c}) (≈ℝ-sym (negℝ-*ℝ b c)))
(≈ℝ-sym (≈ℝ-refl {a *ℝ c -ℝ b *ℝ c})))
<-*mono : (x y z : RealI) → x <ℝ y → 0ℝ <ℝ z → x *ℝ z <ℝ y *ℝ z
<-*mono x y z x<y 0<z =
let
0<y-x : 0ℝ <ℝ y -ℝ x
0<y-x = ≈-<-resp (x-ℝx x) (<-sub x y x x<y)
0<prod : 0ℝ <ℝ (y -ℝ x) *ℝ z
0<prod = pos*pos (y -ℝ x) z 0<y-x 0<z
distrib : (y -ℝ x) *ℝ z ≈ℝ y *ℝ z -ℝ x *ℝ z
distrib = mul-sub-distrib y x z
0<diff : 0ℝ <ℝ y *ℝ z -ℝ x *ℝ z
0<diff = ≈-<-respʳ distrib 0<prod
added : 0ℝ +ℝ (x *ℝ z) <ℝ (y *ℝ z -ℝ x *ℝ z) +ℝ (x *ℝ z)
added = <-+mono 0ℝ (y *ℝ z -ℝ x *ℝ z) (x *ℝ z) 0<diff
left-eq : 0ℝ +ℝ (x *ℝ z) ≈ℝ x *ℝ z
left-eq = +ℝ-identityˡ (x *ℝ z)
right-eq : (y *ℝ z -ℝ x *ℝ z) +ℝ (x *ℝ z) ≈ℝ y *ℝ z
right-eq =
≈ℝ-trans
(+ℝ-assoc (y *ℝ z) (negℝ (x *ℝ z)) (x *ℝ z))
(≈ℝ-trans
(+ℝ-cong (≈ℝ-refl {y *ℝ z}) (+ℝ-inverseˡ (x *ℝ z)))
(+ℝ-identityʳ (y *ℝ z)))
in ≈-<-trans-helper (≈ℝ-sym left-eq) added right-eq
δ-below : (g : ℚ) → 0ℚ < g → (k : ℕ) →
Σ ℕ (λ m → k ≤ℕ m × δ m < g)
δ-below g 0<g k =
let
n , εn<g = ε-archimedean g 0<g
m = k ⊔ℕ n
k≤m = m≤m⊔n k n
n≤m = m≤n⊔m k n
in m , k≤m , ≤-<-trans (δ-mono n≤m) (≤-<-trans (δ≤ε n) εn<g)
u-corner-0 : (a b : RealI) → u a 0 * u b 0 ≤ u (a *ℝ b) 0
u-corner-0 a b =
let
chain : u a 0 * u b 0 ≤ u (node a 0 *ℝ node b 0) 0
chain =
≤-trans
(p≤q⊔p (u a 0 * l b 0) (u a 0 * u b 0))
(p≤q⊔p ((l a 0 * l b 0) ⊔ (l a 0 * u b 0))
((u a 0 * l b 0) ⊔ (u a 0 * u b 0)))
in subst (λ z → u a 0 * u b 0 ≤ z)
(sym (cong RealI.u (node-*ℝ a b 0)))
chain
u-prod-corner : (x y : RealI) (n : ℕ) →
u x (2 ℕ* n) * u y (2 ℕ* n) ≤ u (x *ℝ y) n
u-prod-corner x y n =
subst (λ z → u x (2 ℕ* n) * u y (2 ℕ* n) ≤ z)
(sym (cong RealI.u (node-*ℝ x y n)))
(u-corner-0 (node x (2 ℕ* n)) (node y (2 ℕ* n)))
l-0 : ∀ m → l 0ℝ m ≡ neg (δ m)
l-0 m =
begin
l 0ℝ m
≡⟨ l-dyadic 0ℚ m ⟩
neg (δ m) + 0ℚ
≡⟨ +-identityʳ (neg (δ m)) ⟩
neg (δ m)
∎
u-nonNeg : (x : RealI) → 0ℝ ≤ℝ x → (k : ℕ) → 0ℚ ≤ u x k
u-nonNeg x x≥0 k =
≮⇒≥ (λ uk<0 →
let
g = neg (u x k)
0<g : 0ℚ < g
0<g = neg-antimono-< uk<0
sel = δ-below g 0<g k
m = proj₁ sel
k≤m = proj₁ (proj₂ sel)
δm<g = proj₂ (proj₂ sel)
uk≡ : u x k ≡ neg g
uk≡ = sym (neg-involutive (u x k))
below : u x k < neg (δ m)
below = subst (λ z → z < neg (δ m)) (sym uk≡) (neg-antimono-< δm<g)
um< : u x m < neg (δ m)
um< = ≤-<-trans (u-mono x k≤m) below
in x≥0 (m , subst (λ z → u x m < z) (sym (l-0 m)) um<))
*ℝ-nonNeg : (x y : RealI) → 0ℝ ≤ℝ x → 0ℝ ≤ℝ y → 0ℝ ≤ℝ (x *ℝ y)
*ℝ-nonNeg x y x≥0 y≥0 (n , h) =
let
c = u x (2 ℕ* n) * u y (2 ℕ* n)
0≤0y : 0ℚ ≤ 0ℚ * u y (2 ℕ* n)
0≤0y = subst (λ z → 0ℚ ≤ z) (sym (*-zeroˡ (u y (2 ℕ* n)))) (≤-refl {0ℚ})
0≤c : 0ℚ ≤ c
0≤c = ≤-trans 0≤0y
(*-monoʳ-≤-nonNeg (u y (2 ℕ* n))
{{nonNegative (u-nonNeg y y≥0 (2 ℕ* n))}}
(u-nonNeg x x≥0 (2 ℕ* n)))
0≤u : 0ℚ ≤ u (x *ℝ y) n
0≤u = ≤-trans 0≤c (u-prod-corner x y n)
u<neg : u (x *ℝ y) n < neg (δ n)
u<neg = subst (λ z → u (x *ℝ y) n < z) (l-0 n) h
negδ<0 : neg (δ n) < 0ℚ
negδ<0 = neg-antimono-< (δ-pos n)
u<0 : u (x *ℝ y) n < 0ℚ
u<0 = <-trans u<neg negδ<0
in <-irrefl refl (≤-<-trans 0≤u u<0)
≤-resp-≈ˡ : {x y z : RealI} → x ≈ℝ y → x ≤ℝ z → y ≤ℝ z
≤-resp-≈ˡ {x} {y} {z} x≈y x≤z z<y = x≤z (≈-<-respʳ (≈ℝ-sym x≈y) z<y)
≤-resp-≈ʳ : {x y z : RealI} → x ≤ℝ y → y ≈ℝ z → x ≤ℝ z
≤-resp-≈ʳ {x} {y} {z} x≤y y≈z z<x = x≤y (≈-<-resp (≈ℝ-sym y≈z) z<x)
*ℝ-≤-mono : (x y z : RealI) → x ≤ℝ y → 0ℝ ≤ℝ z →
x *ℝ z ≤ℝ y *ℝ z
*ℝ-≤-mono x y z x≤y 0≤z r =
let
sum-to-y : (y -ℝ x) +ℝ x ≈ℝ y
sum-to-y =
≈ℝ-trans (+ℝ-assoc y (negℝ x) x)
(≈ℝ-trans
(+ℝ-cong (≈ℝ-refl {y}) (+ℝ-inverseˡ x))
(+ℝ-identityʳ y))
0≤d : 0ℝ ≤ℝ (y -ℝ x)
0≤d h =
x≤y (≈-<-trans-helper (≈ℝ-sym sum-to-y)
(<-+mono (y -ℝ x) 0ℝ x h)
(+ℝ-identityˡ x))
0≤dz : 0ℝ ≤ℝ (y -ℝ x) *ℝ z
0≤dz = *ℝ-nonNeg (y -ℝ x) z 0≤d 0≤z
shifted : y *ℝ z -ℝ x *ℝ z <ℝ 0ℝ
shifted = ≈-<-respʳ (x-ℝx (x *ℝ z))
(<-sub (y *ℝ z) (x *ℝ z) (x *ℝ z) r)
corner : (y -ℝ x) *ℝ z <ℝ 0ℝ
corner = ≈-<-resp (≈ℝ-sym (mul-sub-distrib y x z)) shifted
in 0≤dz corner
*ℝ-square-mono : (x y : RealI) → 0ℝ ≤ℝ x → x ≤ℝ y →
x *ℝ x ≤ℝ y *ℝ y
*ℝ-square-mono x y 0≤x x≤y =
let
0≤y : 0ℝ ≤ℝ y
0≤y = ≤ℝ-trans 0≤x x≤y
left : x *ℝ x ≤ℝ x *ℝ y
left = ≤-resp-≈ʳ (*ℝ-≤-mono x y x x≤y 0≤x) (≈ℝ-sym (*ℝ-comm x y))
right : x *ℝ y ≤ℝ y *ℝ y
right = *ℝ-≤-mono x y y x≤y 0≤y
in ≤ℝ-trans left right