{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.DensityArch where
open import Data.Nat using (ℕ; suc) renaming (_+_ to _+N_; _≤_ to _≤N_)
open import Data.Nat.Properties using () renaming (+-comm to +-commℕ)
open import Data.Product using (Σ; _,_; proj₁; proj₂; _×_)
open import Data.Rational using
(ℚ; 0ℚ; 1ℚ; _+_; _-_; _*_; _<_; _>_; _≤_; _≥_; ∣_∣)
open import Data.Rational.Base using (positive; -_)
open import Data.Rational.Properties using
(≤-trans; ≤-refl; ≤-reflexive; <-≤-trans; ≤-<-trans; +-mono-≤; +-monoˡ-<
; +-assoc; +-identityˡ; +-identityʳ; +-inverseˡ; *-assoc; *-identityˡ
; *-identityʳ; *-comm; *-distribˡ-+; *-distribʳ-+; pos⇒nonNeg; 0≤∣p∣
; neg-antimono-≤; neg-distribˡ-*; +-comm; +-inverseʳ; *-monoˡ-<-pos
; *-monoʳ-≤-nonNeg; +-monoʳ-<)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; trans; sym; cong; cong₂; subst; module ≡-Reasoning)
open ≡-Reasoning
open import Real using (embed; half; embed-+-hom)
open import Base.RationalRing using (neg-involutive)
open import Real.Interval using (RealI; embedℚ; δ; sub-cancel)
open import Real.IntervalEquiv using (l; u; width; bound-w; l-mono; u-mono)
open import Real.Interval.Node using (l-dyadic; u-dyadic)
open import Real.Interval.Kit using (0<half; half+half≡1; add-self; 2ℚ*half≡1)
open import Real.Interval.Order using (_<ℝ_)
open import Real.Interval.OrderLaws using (width-below-strict)
open import Real.Interval.Rational using (r≤|r|; pos-diff; cancel-plus)
open import Real.Interval.Reasoning using (begin≤_; _≤∎; _≈⟨_⟩_; _≤⟨_⟩_; _<⟨_⟩≤[_])
embed1≡1 : embed 1 ≡ 1ℚ
embed1≡1 = refl
1-half≡half : 1ℚ - half ≡ half
1-half≡half = begin
1ℚ - half
≡⟨ cong (λ w → w - half) (sym half+half≡1) ⟩
(half + half) - half
≡⟨ cong (λ w → (half + half) - w) (sym (+-identityʳ half)) ⟩
(half + half) - (half + 0ℚ)
≡⟨ cancel-plus half half 0ℚ ⟩
half - 0ℚ
≡⟨ +-identityʳ half ⟩
half
∎
embed-suc-half : ∀ N → embed (suc N) - half ≡ embed N + half
embed-suc-half N = begin
embed (suc N) - half
≡⟨ cong (λ w → w - half) (cong embed (sym (+-commℕ N 1))) ⟩
embed (N +N 1) - half
≡⟨ cong (λ w → w - half) (embed-+-hom N 1) ⟩
(embed N + embed 1) - half
≡⟨ cong (λ w → (embed N + w) - half) embed1≡1 ⟩
(embed N + 1ℚ) - half
≡⟨ +-assoc (embed N) 1ℚ (- half) ⟩
embed N + (1ℚ - half)
≡⟨ cong (embed N +_) 1-half≡half ⟩
embed N + half
∎
archimedean : (x : RealI) → Σ ℕ (λ n → x <ℝ embedℚ (embed n))
archimedean x = n , (0 , goal)
where
ux0 : ℚ
ux0 = u x 0
abs-ux0 : ℚ
abs-ux0 = ∣ ux0 ∣
0≤abs : 0ℚ ≤ abs-ux0
0≤abs = 0≤∣p∣ ux0
N : ℕ
N = proj₁ (bound-w abs-ux0 0≤abs)
abs≤N : abs-ux0 ≤ embed N
abs≤N = proj₂ (bound-w abs-ux0 0≤abs)
ux0≤abs : ux0 ≤ abs-ux0
ux0≤abs = r≤|r| ux0
ux0≤N : ux0 ≤ embed N
ux0≤N = ≤-trans ux0≤abs abs≤N
n : ℕ
n = suc N
raw : 0ℚ + embed N < half + embed N
raw = +-monoˡ-< (embed N) 0<half
step1 : embed N < half + embed N
step1 = subst (λ z → z < half + embed N) (+-identityˡ (embed N)) raw
N<N+half : embed N < embed N + half
N<N+half = subst (λ z → embed N < z) (+-comm half (embed N)) step1
ux0<N+half : ux0 < embed N + half
ux0<N+half = ≤-<-trans ux0≤N N<N+half
l-target : l (embedℚ (embed n)) 0 ≡ - δ 0 + embed n
l-target = l-dyadic (embed n) 0
commute : (- δ 0) + embed n ≡ embed n - δ 0
commute = +-comm (- δ 0) (embed n)
δ0≡half : δ 0 ≡ half
δ0≡half = refl
half-eq : embed n - δ 0 ≡ embed n - half
half-eq = cong (λ z → embed n - z) δ0≡half
target≡ : l (embedℚ (embed n)) 0 ≡ embed N + half
target≡ = begin
l (embedℚ (embed n)) 0
≡⟨ l-target ⟩
(- δ 0) + embed n
≡⟨ commute ⟩
embed n - δ 0
≡⟨ half-eq ⟩
embed n - half
≡⟨ embed-suc-half N ⟩
embed N + half
∎
goal : u x 0 < l (embedℚ (embed n)) 0
goal =
u x 0
<⟨ ux0<N+half ⟩≤[
≤-reflexive (sym target≡) ]
width-0ℝ : ∀ m → width (embedℚ 0ℚ) m ≡ δ m + δ m
width-0ℝ m = begin
width (embedℚ 0ℚ) m
≡⟨ cong₂ (λ x y → x - y) (u-dyadic 0ℚ m) (l-dyadic 0ℚ m) ⟩
(δ m + 0ℚ) - ((- δ m) + 0ℚ)
≡⟨ sub-cancel (δ m) (- δ m) 0ℚ ⟩
δ m + (- (- δ m))
≡⟨ cong (δ m +_) (neg-involutive (δ m)) ⟩
δ m + δ m
∎
2δ<d⇒δ<half-d : ∀ {δ d} → δ + δ < d → δ < d * half
2δ<d⇒δ<half-d {δ} {d} h =
subst (λ z → z < d * half) lhs≡ step
where
h2 : embed 2 * δ < d
h2 = subst (λ z → z < d) (add-self δ) h
step : (embed 2 * δ) * half < d * half
step = *-monoˡ-<-pos half {{positive 0<half}} h2
lhs≡ : ((embed 2) * δ) * half ≡ δ
lhs≡ = begin
((embed 2) * δ) * half
≡⟨ *-assoc (embed 2) δ half ⟩
(embed 2) * (δ * half)
≡⟨ cong ((embed 2) *_) (*-comm δ half) ⟩
(embed 2) * (half * δ)
≡⟨ sym (*-assoc (embed 2) half δ) ⟩
((embed 2) * half) * δ
≡⟨ cong (_* δ) 2ℚ*half≡1 ⟩
1ℚ * δ
≡⟨ *-identityˡ δ ⟩
δ
∎
midpoint-l : ∀ a b → (a + b) * half - a ≡ (b - a) * half
midpoint-l a b = begin
(a + b) * half - a
≡⟨ cong (λ z → (a + b) * half - z) (sym (*-identityʳ a)) ⟩
(a + b) * half - a * 1ℚ
≡⟨ cong (λ z → (a + b) * half - z) (sym merge) ⟩
(a + b) * half - (a * half + a * half)
≡⟨ cong (λ z → z - (a * half + a * half))
(*-distribʳ-+ half a b) ⟩
(a * half + b * half) - (a * half + a * half)
≡⟨ cancel-plus (a * half) (b * half) (a * half) ⟩
b * half - a * half
≡⟨ cong (λ z → b * half + z) (neg-distribˡ-* a half) ⟩
b * half + (- a) * half
≡⟨ sym (*-distribʳ-+ half b (- a)) ⟩
(b + (- a)) * half
≡⟨ refl ⟩
(b - a) * half
∎
where
merge : a * half + a * half ≡ a * 1ℚ
merge = trans (sym (*-distribˡ-+ a half half))
(cong (a *_) half+half≡1)
midpoint-u : ∀ a b → b - (a + b) * half ≡ (b - a) * half
midpoint-u a b = begin
b - (a + b) * half
≡⟨ cong (λ z → b - z) (*-distribʳ-+ half a b) ⟩
b - (a * half + b * half)
≡⟨ cong (λ z → z - (a * half + b * half)) (sym b-double) ⟩
(b * half + b * half) - (a * half + b * half)
≡⟨ cong (λ z → (b * half + b * half) - z)
(+-comm (a * half) (b * half)) ⟩
(b * half + b * half) - (b * half + a * half)
≡⟨ cancel-plus (b * half) (b * half) (a * half) ⟩
b * half - a * half
≡⟨ cong (λ z → b * half + z) (neg-distribˡ-* a half) ⟩
b * half + (- a) * half
≡⟨ sym (*-distribʳ-+ half b (- a)) ⟩
(b + (- a)) * half
≡⟨ refl ⟩
(b - a) * half
∎
where
b-double : b * half + b * half ≡ b
b-double =
trans (sym (*-distribˡ-+ b half half))
(trans (cong (b *_) half+half≡1) (*-identityʳ b))
dense : {x y : RealI} → x <ℝ y →
Σ ℚ (λ q → (x <ℝ embedℚ q) × (embedℚ q <ℝ y))
dense {x} {y} (k , uxk<lyk) = q , ((m , x<q) , (m , q<y))
where
d : ℚ
d = l y k - u x k
d>0 : 0ℚ < d
d>0 = pos-diff (u x k) (l y k) uxk<lyk
sel : Σ ℕ (λ m → (k ≤N m) × width (embedℚ 0ℚ) m < d)
sel = width-below-strict (embedℚ 0ℚ) d k d>0
m : ℕ
m = proj₁ sel
k≤m : k ≤N m
k≤m = proj₁ (proj₂ sel)
width<d : width (embedℚ 0ℚ) m < d
width<d = proj₂ (proj₂ sel)
2δ<d : δ m + δ m < d
2δ<d = subst (λ z → z < d) (width-0ℝ m) width<d
δm<half-d : δ m < d * half
δm<half-d = 2δ<d⇒δ<half-d 2δ<d
uxm : ℚ
uxm = u x m
lym : ℚ
lym = l y m
uxm≤uxk : u x m ≤ u x k
uxm≤uxk = u-mono x {n = k} {m = m} k≤m
lyk≤lym : l y k ≤ l y m
lyk≤lym = l-mono y {n = k} {m = m} k≤m
step1 : lym - uxm ≥ l y k - uxm
step1 = +-mono-≤ lyk≤lym (≤-refl { - uxm })
step2 : l y k - uxm ≥ l y k - u x k
step2 = +-mono-≤ (≤-refl { l y k }) (neg-antimono-≤ uxm≤uxk)
dm≥d : l y m - u x m ≥ d
dm≥d = ≤-trans step2 step1
q : ℚ
q = (uxm + lym) * half
q-uxm≡ : q - uxm ≡ (l y m - u x m) * half
q-uxm≡ = midpoint-l uxm lym
q-uxm≥half-d : q - uxm ≥ d * half
q-uxm≥half-d =
begin≤
d * half
≤⟨ *-monoʳ-≤-nonNeg half
{{pos⇒nonNeg half {{positive 0<half}}}} dm≥d ⟩
(l y m - u x m) * half
≈⟨ sym q-uxm≡ ⟩
q - uxm
≤∎
lym-q≡ : lym - q ≡ (l y m - u x m) * half
lym-q≡ = midpoint-u uxm lym
lym-q≥half-d : lym - q ≥ d * half
lym-q≥half-d =
begin≤
d * half
≤⟨ *-monoʳ-≤-nonNeg half
{{pos⇒nonNeg half {{positive 0<half}}}} dm≥d ⟩
(l y m - u x m) * half
≈⟨ sym lym-q≡ ⟩
lym - q
≤∎
q-uxm>δm : q - uxm > δ m
q-uxm>δm = <-≤-trans δm<half-d q-uxm≥half-d
lym-q>δm : lym - q > δ m
lym-q>δm = <-≤-trans δm<half-d lym-q≥half-d
cancel-a : uxm + (q - uxm) ≡ q
cancel-a = begin
uxm + (q - uxm)
≡⟨ cong (uxm +_) (+-comm q (- uxm)) ⟩
uxm + ((- uxm) + q)
≡⟨ sym (+-assoc uxm (- uxm) q) ⟩
(uxm + (- uxm)) + q
≡⟨ cong (λ z → z + q) (+-inverseʳ uxm) ⟩
0ℚ + q
≡⟨ +-identityˡ q ⟩
q
∎
cancel-l : (- δ m) + (uxm + δ m) ≡ uxm
cancel-l = begin
(- δ m) + (uxm + δ m)
≡⟨ sym (+-assoc (- δ m) uxm (δ m)) ⟩
((- δ m) + uxm) + δ m
≡⟨ cong (λ z → z + δ m) (+-comm (- δ m) uxm) ⟩
(uxm + (- δ m)) + δ m
≡⟨ +-assoc uxm (- δ m) (δ m) ⟩
uxm + ((- δ m) + δ m)
≡⟨ cong (uxm +_) (+-inverseˡ (δ m)) ⟩
uxm + 0ℚ
≡⟨ +-identityʳ uxm ⟩
uxm
∎
cancel-b : q + (lym - q) ≡ lym
cancel-b = begin
q + (lym - q)
≡⟨ cong (q +_) (+-comm lym (- q)) ⟩
q + ((- q) + lym)
≡⟨ sym (+-assoc q (- q) lym) ⟩
(q + (- q)) + lym
≡⟨ cong (λ z → z + lym) (+-inverseʳ q) ⟩
0ℚ + lym
≡⟨ +-identityˡ lym ⟩
lym
∎
inner : uxm + δ m < q
inner =
uxm + δ m
<⟨ +-monoʳ-< uxm q-uxm>δm ⟩≤[
≤-reflexive cancel-a ]
raw1 : uxm < q - δ m
raw1 =
≤-<-trans (≤-reflexive (sym cancel-l))
(<-≤-trans (+-monoʳ-< (- δ m) inner)
(≤-reflexive (+-comm (- δ m) q)))
x<q : u x m < l (embedℚ q) m
x<q =
subst (λ z → uxm < z) (sym (l-dyadic q m))
(subst (λ z → uxm < z) (+-comm q (- δ m)) raw1)
raw2 : q + δ m < lym
raw2 =
q + δ m
<⟨ +-monoʳ-< q lym-q>δm ⟩≤[
≤-reflexive cancel-b ]
q<y : u (embedℚ q) m < l y m
q<y =
subst (λ z → z < lym) (sym (u-dyadic q m))
(subst (λ z → z < lym) (+-comm q (δ m)) raw2)