{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.Log.Core where
open import Data.Empty using (⊥-elim)
open import Data.Nat using (ℕ; zero; suc)
open import Data.Product using (Σ; _×_; _,_; proj₁; proj₂)
open import Data.Rational using (ℚ; 0ℚ; 1ℚ; _+_; _<_; _≤_) renaming (-_ to neg)
open import Data.Rational.Properties using
(≤-refl; ≤-trans; <⇒≤; <-≤-trans; <-trans; <-asym; +-monoʳ-<; +-monoˡ-≤; <-cmp
; +-comm; +-assoc; +-identityˡ; +-identityʳ; +-inverseʳ; neg-antimono-<; ≮⇒≥)
open import Data.Sum.Base using (_⊎_; inj₁; inj₂; [_,_])
open import Relation.Binary.Definitions using (tri<; tri≈; tri>)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; sym; trans; cong; subst; subst₂)
open import Relation.Nullary using (¬_)
open import Real using (embed; 0<embed; 0<ε; ε; _≈_)
open import Real.CauchyToInterval using (M)
open import Real.IntervalEquiv using (l; u)
open import Real.Interval using (RealI; embedℚ; δ; δ-pos)
open import Real.Interval.Arith using (1ℝ)
open import Real.Interval.Continuity using (embedℚ-mono)
open import Real.Interval.DensityArch using (archimedean)
open import Base.RationalRing using (0<1)
open import Real.Interval.Exp.Core using (expPartial; expSeq; expq)
open import Real.Interval.Exp.Order using (expq-zero; expq-mono; expq-strict-mono)
open import Real.Interval.Exp.Step using (expq-u; expq-step-up; M-lower)
open import Real.Interval.Equiv using (_≈ℝ_; ≈ℝ-sym; ≈ℝ-refl)
open import Real.Interval.Mul.Order using (≈-<-respʳ)
open import Real.Interval.Node using (l-dyadic; u-dyadic)
open import Real.Interval.Order as Ord using (_<ℝ_; <-cotrans)
open import Real.Interval.OrderLe using
(<-≤ℝ-trans; ≤ℝ-<trans; ≤ℝ-resp-≈; ≈⇒≤ℝ∧)
open import Real.Interval.OrderLaws using (≈-<-resp)
open import Real.Interval.OrderComplete.Base using
(Subset; Upper; Occupied; Located; _≤ℝ_)
open import Real.Interval.OrderComplete using (sup; sup-upper; sup-least)
open import Real.Interval.RetractCauchy using (cauchy→realI-cong)
expSeq-irrel : (q : ℚ) (p p' : 0ℚ ≤ q) → expSeq q p ≈ expSeq q p'
expSeq-irrel q p p' k = 0 , λ n _ →
let c : expPartial q n + neg (expPartial q n) < ε k
c = subst (λ z → z < ε k) (sym (+-inverseʳ (expPartial q n))) (0<ε k)
in c , c
expq-irrel : (q : ℚ) (p p' : 0ℚ ≤ q) → expq q p ≈ℝ expq q p'
expq-irrel q p p' = cauchy→realI-cong (expSeq-irrel q p p')
expq-mono-any : (p q : ℚ) (0≤p : 0ℚ ≤ p) (0≤q : 0ℚ ≤ q)
→ p ≤ q → expq p 0≤p ≤ℝ expq q 0≤q
expq-mono-any p q 0≤p 0≤q p≤q =
≤ℝ-resp-≈ ≈ℝ-refl (expq-irrel q (≤-trans 0≤p p≤q) 0≤q)
(expq-mono p q 0≤p p≤q)
expq-strict-any : (p q : ℚ) (0≤p : 0ℚ ≤ p) (0≤q : 0ℚ ≤ q)
→ p < q → expq p 0≤p <ℝ expq q 0≤q
expq-strict-any p q 0≤p 0≤q p<q =
let step : expq p 0≤p <ℝ expq q (≤-trans 0≤p (<⇒≤ p<q))
step = expq-strict-mono p q 0≤p p<q
le : expq q (≤-trans 0≤p (<⇒≤ p<q)) ≤ℝ expq q 0≤q
le = proj₁ (≈⇒≤ℝ∧ (expq-irrel q (≤-trans 0≤p (<⇒≤ p<q)) 0≤q))
in <-≤ℝ-trans step le
module _ (y : RealI) (1<y : 1ℝ <ℝ y) where
P : Subset
P x = Σ ℚ (λ q → Σ (0ℚ ≤ q) (λ 0≤q → (x ≈ℝ embedℚ q) × (expq q 0≤q <ℝ y)))
P-0 : P (embedℚ 0ℚ)
P-0 = 0ℚ , (≤-refl , (≈ℝ-refl , ≈-<-resp (≈ℝ-sym expq-zero) 1<y))
embed-below-zero : (p : ℚ) → p < 0ℚ → embedℚ p <ℝ embedℚ 0ℚ
embed-below-zero p p<0 = embedℚ-mono p 0ℚ p<0
not-≤⇒< : (r q : ℚ) → ¬ (q ≤ r) → r < q
not-≤⇒< r q nle with <-cmp r q
... | tri< lt _ _ = lt
... | tri≈ _ eq _ = ⊥-elim (nle (subst (λ z → q ≤ z) (sym eq) ≤-refl))
... | tri> _ _ q<r = ⊥-elim (nle (<⇒≤ q<r))
0<1ℚ : 0ℚ < 1ℚ
0<1ℚ = 0<1
neg-δ<0 : (k : ℕ) → neg (δ k) < 0ℚ
neg-δ<0 k = neg-antimono-< {0ℚ} {δ k} (δ-pos k)
m<1+m : (m : ℚ) → m < 1ℚ + m
m<1+m m =
subst₂ _<_
(trans (+-comm m 0ℚ) (+-identityˡ m))
(+-comm m 1ℚ)
(+-monoʳ-< m 0<1ℚ)
m<δ+m : (k : ℕ) (m : ℚ) → m < δ k + m
m<δ+m k m =
subst₂ _<_
(+-identityʳ m)
(+-comm m (δ k))
(+-monoʳ-< m (δ-pos k))
neg-δ+m<m : (k : ℕ) (m : ℚ) → neg (δ k) + m < m
neg-δ+m<m k m =
subst₂ _<_
(+-comm m (neg (δ k)))
(+-identityʳ m)
(+-monoʳ-< m (neg-δ<0 k))
δ-triple : (e : ℚ) (k : ℕ)
→ (e + (δ k + δ k)) + neg (δ k) ≡ e + δ k
δ-triple e k =
trans (+-assoc e (δ k + δ k) (neg (δ k)))
(trans (cong (e +_) cancel) refl)
where
cancel : (δ k + δ k) + neg (δ k) ≡ δ k
cancel = trans (+-assoc (δ k) (δ k) (neg (δ k)))
(trans (cong (δ k +_) (+-inverseʳ (δ k)))
(+-identityʳ (δ k)))
embed≤exp : (m : ℚ) (0≤m : 0ℚ ≤ m) → embedℚ m ≤ℝ expq m 0≤m
embed≤exp m 0≤m (k , h) =
let
Mk : ℕ
Mk = M (expSeq m 0≤m) k
lower : 1ℚ + m ≤ expPartial m Mk + (δ k + δ k)
lower = M-lower m 0≤m k
add-negδ : (1ℚ + m) + neg (δ k)
≤ (expPartial m Mk + (δ k + δ k)) + neg (δ k)
add-negδ = +-monoˡ-≤ (neg (δ k)) lower
lower' : (1ℚ + m) + neg (δ k) ≤ expPartial m Mk + δ k
lower' = subst (λ z → (1ℚ + m) + neg (δ k) ≤ z)
(δ-triple (expPartial m Mk) k) add-negδ
strict : neg (δ k) + m < (1ℚ + m) + neg (δ k)
strict = subst (λ z → neg (δ k) + m < z)
(+-comm (neg (δ k)) (1ℚ + m))
(+-monoʳ-< (neg (δ k)) (m<1+m m))
gt : neg (δ k) + m < expPartial m Mk + δ k
gt = <-≤-trans strict lower'
uP≡ : u (expq m 0≤m) k ≡ expPartial m Mk + δ k
uP≡ = expq-u m 0≤m k
lE : l (embedℚ m) k ≡ neg (δ k) + m
lE = l-dyadic m k
lt : l (embedℚ m) k < u (expq m 0≤m) k
lt = subst (λ z → z < u (expq m 0≤m) k) (sym lE)
(subst (λ z → neg (δ k) + m < z) (sym uP≡) gt)
in
<-asym lt h
occupied-up : (p : ℚ) (0≤p : 0ℚ ≤ p) (k₀ : ℕ)
→ u (expq p 0≤p) k₀ < l y k₀ → Occupied P p
occupied-up p 0≤p k₀ hlt =
let
st = expq-step-up p 0≤p y k₀ hlt
h = proj₁ st
0<h = proj₁ (proj₂ st)
0≤ph = proj₁ (proj₂ (proj₂ st))
k₂ = proj₁ (proj₂ (proj₂ (proj₂ st)))
hlt₂ = proj₂ (proj₂ (proj₂ (proj₂ st)))
p<ph : p < p + h
p<ph = subst₂ _<_
(+-identityʳ p)
refl
(+-monoʳ-< p 0<h)
x : RealI
x = embedℚ (p + h)
member : P x
member = p + h , (0≤ph , (≈ℝ-refl , (k₂ , hlt₂)))
in
x , (member , embedℚ-mono p (p + h) p<ph)
upper-above : (q : ℚ) (0≤q : 0ℚ ≤ q) (y<eq : y <ℝ expq q 0≤q) → Upper P q
upper-above q 0≤q y<eq x (r , (0≤r , (x≈ , er<y))) =
let
not-q≤r : ¬ (q ≤ r)
not-q≤r q≤r =
let mono : expq q 0≤q ≤ℝ expq r 0≤r
mono = expq-mono-any q r 0≤q 0≤r q≤r
eq<y : expq q 0≤q <ℝ y
eq<y = ≤ℝ-<trans mono er<y
in Ord.<-irrefl (expq q 0≤q) (Ord.<-trans eq<y y<eq)
r<q : r < q
r<q = not-≤⇒< r q not-q≤r
in
≈-<-resp (≈ℝ-sym x≈) (embedℚ-mono r q r<q)
decide : (p q : ℚ) → p < q → 0ℚ ≤ p → Occupied P p ⊎ Upper P q
decide p q p<q 0≤p =
let
0≤q : 0ℚ ≤ q
0≤q = ≤-trans 0≤p (<⇒≤ p<q)
mono : expq p 0≤p <ℝ expq q 0≤q
mono = expq-strict-mono p q 0≤p p<q
br : (expq p 0≤p <ℝ y) ⊎ (y <ℝ expq q 0≤q)
br = <-cotrans {x = expq p 0≤p} {y = y} {z = expq q 0≤q} mono
in
[ (λ lt → inj₁ (occupied-up p 0≤p (proj₁ lt) (proj₂ lt)))
, (λ gt → inj₂ (upper-above q 0≤q gt))
] br
located : Located P
located p q p<q with <-cmp p 0ℚ
... | tri< p<0 _ _ = inj₁ (embedℚ 0ℚ , (P-0 , embed-below-zero p p<0))
... | tri≈ ¬p<0 _ _ = decide p q p<q (≮⇒≥ ¬p<0)
... | tri> ¬p<0 _ _ = decide p q p<q (≮⇒≥ ¬p<0)
n : ℕ
n = proj₁ (archimedean y)
m : ℚ
m = embed n
y<m : y <ℝ embedℚ m
y<m = proj₂ (archimedean y)
0≤m : 0ℚ ≤ m
0≤m with n
... | zero = ≤-refl
... | suc j = <⇒≤ (0<embed j)
isUpper : (x : RealI) → P x → x ≤ℝ embedℚ m
isUpper x (r , (0≤r , (x≈ , er<y))) h =
let
em<er : embedℚ m <ℝ embedℚ r
em<er = ≈-<-respʳ x≈ h
k : ℕ
k = proj₁ em<er
hlt : u (embedℚ m) k < l (embedℚ r) k
hlt = proj₂ em<er
s1 : m < u (embedℚ m) k
s1 = subst (λ z → m < z) (sym (u-dyadic m k)) (m<δ+m k m)
s2 : u (embedℚ m) k < r
s2 = <-trans (subst (λ z → u (embedℚ m) k < z) (l-dyadic r k) hlt)
(neg-δ+m<m k r)
m<r : m < r
m<r = <-trans s1 s2
em<exp : embedℚ m <ℝ expq r 0≤r
em<exp = <-≤ℝ-trans (embedℚ-mono m r m<r) (embed≤exp r 0≤r)
exp<em : expq r 0≤r <ℝ embedℚ m
exp<em = Ord.<-trans er<y y<m
in
Ord.<-irrefl (embedℚ m) (Ord.<-trans em<exp exp<em)
logℝ : RealI
logℝ = sup {P = P} located {x₀ = embedℚ 0ℚ} P-0 {u₀ = embedℚ m} isUpper
log-upper : (x : RealI) → P x → x ≤ℝ logℝ
log-upper = sup-upper {P = P} located {x₀ = embedℚ 0ℚ} P-0
{u₀ = embedℚ m} isUpper
log-least : (u₀ : RealI) → ((x : RealI) → P x → x ≤ℝ u₀)
→ logℝ ≤ℝ u₀
log-least = sup-least {P = P} located {x₀ = embedℚ 0ℚ} P-0
{u₀ = embedℚ m} isUpper
log-member : (q : ℚ) (0≤q : 0ℚ ≤ q) → expq q 0≤q <ℝ y
→ P (embedℚ q)
log-member q 0≤q q<y = q , (0≤q , (≈ℝ-refl , q<y))