{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.Infimum where
open import Data.Product using (Σ; _,_; proj₁; proj₂; _×_)
open import Data.Sum using (_⊎_; inj₁; inj₂)
open import Data.Rational using (ℚ; _<_) renaming (-_ to neg)
open import Data.Rational.Properties using (neg-antimono-<)
open import Function.Base using (case_of_)
open import Real.Interval using (RealI; embedℚ)
open import Real.Interval.Arith using (negℝ)
open import Real.Interval.Equiv using (_≈ℝ_; ≈ℝ-sym; ≈ℝ-refl; ≈ℝ-trans)
open import Real.Interval.Order using (_<ℝ_)
open import Real.Interval.OrderComplete.Base using
(Subset; Located; Upper; Occupied; ≤ℝ-trans; _≤ℝ_)
open import Real.Interval.OrderComplete using (order-complete)
open import Real.Interval.OrderLaws using (≈-<-resp; <-neg)
open import Real.Interval.Mul.Order using (≈-<-respʳ; ≈-neg)
open import Real.Interval.OrderLe using (≈⇒≤ℝ; ≤ℝ-resp-≈)
open import Real.Interval.ArithLaws using (negℝ-negℝ)
open import Real.Interval.Embed using (embedℚ-neg)
reflect : Subset → Subset
reflect P y = Σ RealI λ x → P x × (y ≈ℝ negℝ x)
reflect-member : {P : Subset} {x : RealI} → P x → reflect P (negℝ x)
reflect-member {P} {x} px = x , px , ≈ℝ-refl
Lower : Subset → ℚ → Set
Lower P a = (x : RealI) → P x → embedℚ a <ℝ x
OccupiedBelow : Subset → ℚ → Set
OccupiedBelow P b = Σ RealI λ x → P x × (x <ℝ embedℚ b)
LocatedBelow : Subset → Set
LocatedBelow P = ∀ (p q : ℚ) → p < q → Lower P p ⊎ OccupiedBelow P q
≤ℝ-neg : {x y : RealI} → x ≤ℝ y → negℝ y ≤ℝ negℝ x
≤ℝ-neg {x} {y} x≤y negx<negy =
let step : negℝ (negℝ y) <ℝ negℝ (negℝ x)
step = <-neg (negℝ x) (negℝ y) negx<negy
y<x : y <ℝ x
y<x =
let a : y <ℝ negℝ (negℝ x)
a = ≈-<-resp (negℝ-negℝ y) step
in ≈-<-respʳ (negℝ-negℝ x) a
in x≤y y<x
neg-emb-neg : (q : ℚ) → negℝ (embedℚ (neg q)) ≈ℝ embedℚ q
neg-emb-neg q = ≈ℝ-trans (≈-neg (embedℚ-neg q)) (negℝ-negℝ (embedℚ q))
lower→upper : {P : Subset} {q : ℚ} →
Lower P (neg q) → Upper (reflect P) q
lower→upper {P} {q} lw y (x , px , y≈negx) =
let base : embedℚ (neg q) <ℝ x
base = lw x px
flipped : negℝ x <ℝ negℝ (embedℚ (neg q))
flipped = <-neg (embedℚ (neg q)) x base
negx<embq : negℝ x <ℝ embedℚ q
negx<embq = ≈-<-respʳ (neg-emb-neg q) flipped
y<embq : y <ℝ embedℚ q
y<embq = ≈-<-resp (≈ℝ-sym y≈negx) negx<embq
in y<embq
occbelow→occ : {P : Subset} {p : ℚ} →
OccupiedBelow P (neg p) → Occupied (reflect P) p
occbelow→occ {P} {p} (x , px , x<enegp) =
let y = negℝ x
py : reflect P y
py = reflect-member px
flipped : negℝ (embedℚ (neg p)) <ℝ negℝ x
flipped = <-neg x (embedℚ (neg p)) x<enegp
embp<y : embedℚ p <ℝ y
embp<y = ≈-<-resp (neg-emb-neg p) flipped
in y , py , embp<y
located-below→located : {P : Subset} →
LocatedBelow P → Located (reflect P)
located-below→located {P} locb p q p<q =
let s = locb (neg q) (neg p) (neg-antimono-< p<q)
in case s of λ
{ (inj₁ lw) → inj₂ (lower→upper lw)
; (inj₂ ob) → inj₁ (occbelow→occ ob) }
module _ {P : Subset} (locb : LocatedBelow P)
{x₀ : RealI} (px₀ : P x₀)
{l₀ : RealI} (isLower : (x : RealI) → P x → l₀ ≤ℝ x) where
Q : Subset
Q = reflect P
locQ : Located Q
locQ = located-below→located locb
y₀ : RealI
y₀ = negℝ x₀
qy₀ : Q y₀
qy₀ = reflect-member px₀
u₀ : RealI
u₀ = negℝ l₀
upperQ : (y : RealI) → Q y → y ≤ℝ u₀
upperQ y (x , px , y≈negx) =
let l₀≤x : l₀ ≤ℝ x
l₀≤x = isLower x px
negx≤negl₀ : negℝ x ≤ℝ negℝ l₀
negx≤negl₀ = ≤ℝ-neg l₀≤x
y≤negx : y ≤ℝ negℝ x
y≤negx = ≈⇒≤ℝ y≈negx
in ≤ℝ-trans y≤negx negx≤negl₀
oc = order-complete {P = Q} locQ {y₀} qy₀ {u₀} upperQ
s : RealI
s = proj₁ oc
s-upper : (y : RealI) → Q y → y ≤ℝ s
s-upper = proj₁ (proj₂ oc)
s-least : (y : RealI) → ((z : RealI) → Q z → z ≤ℝ y) → s ≤ℝ y
s-least = proj₂ (proj₂ oc)
inf : RealI
inf = negℝ s
inf-lower : (x : RealI) → P x → inf ≤ℝ x
inf-lower x px =
let negx≤s : negℝ x ≤ℝ s
negx≤s = s-upper (negℝ x) (reflect-member px)
negs≤negnegx : negℝ s ≤ℝ negℝ (negℝ x)
negs≤negnegx = ≤ℝ-neg negx≤s
in ≤ℝ-resp-≈ (≈ℝ-refl) (negℝ-negℝ x) negs≤negnegx
inf-greatest : (y : RealI) →
((x : RealI) → P x → y ≤ℝ x) → y ≤ℝ inf
inf-greatest y lb =
let upper-negy : (z : RealI) → Q z → z ≤ℝ negℝ y
upper-negy z (x , px , z≈negx) =
let y≤x : y ≤ℝ x
y≤x = lb x px
negx≤negy : negℝ x ≤ℝ negℝ y
negx≤negy = ≤ℝ-neg y≤x
z≤negx : z ≤ℝ negℝ x
z≤negx = ≈⇒≤ℝ z≈negx
in ≤ℝ-trans z≤negx negx≤negy
s≤negy : s ≤ℝ negℝ y
s≤negy = s-least (negℝ y) upper-negy
negnegy≤negs : negℝ (negℝ y) ≤ℝ negℝ s
negnegy≤negs = ≤ℝ-neg s≤negy
in ≤ℝ-resp-≈ (negℝ-negℝ y) (≈ℝ-refl) negnegy≤negs
inf-complete : Σ RealI λ i →
(∀ x → P x → i ≤ℝ x)
× (∀ y → ((x : RealI) → P x → y ≤ℝ x) → y ≤ℝ i)
inf-complete = inf , inf-lower , inf-greatest