{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.Sqrt.Laws where
open import Data.Nat using (ℕ; _⊔_)
open import Data.Nat.Properties using (m≤m⊔n; m≤n⊔m)
open import Data.Product using (Σ; _×_; _,_; proj₁; proj₂)
open import Data.Rational using (ℚ; 0ℚ; _*_; _<_; _≤_)
open import Data.Rational.Properties as ℚP using (≤-refl; *-zeroˡ)
open import Relation.Binary.PropositionalEquality using
(_≡_; sym; subst; refl; trans; cong)
open import Relation.Nullary.Negation using (¬_)
open import Real.IntervalEquiv using (l; u; l-mono; node)
open import Real.Interval using (RealI; embedℚ; δ-pos)
open import Real.Interval.Arith using (0ℝ)
open import Real.Interval.Continuity using (0<embedℚ; embedℚ-mono)
open import Real.Interval.DensityArch using (dense)
open import Real.Interval.Embed using (embedℚ-*)
open import Real.Interval.Equiv using (_≈ℝ_; ≈ℝ-sym; ≈ℝ-trans; ≈ℝ-refl)
open import Real.Interval.Kit using (n≤2n)
open import Real.Interval.Mul using (_*ℝ_)
open import Real.Interval.Mul.Laws using (*ℝ-comm; *ℝ-zeroˡ; *ℝ-assoc)
open import Real.Interval.Mul.Cong using (*ℝ-cong)
open import Real.Interval.Mul.Order using
(<-*mono; ≈-<-respʳ; u-prod-corner; ≤-resp-≈ʳ; l-prod-pos
; u-dyadic-0; *ℝ-≤-mono; ≤-resp-≈ˡ; *ℝ-nonNeg; pos*pos)
open import Real.Interval.Node using (node-*ℝ)
open import Real.Interval.Order using (_<ℝ_; <-trans; <-irrefl)
open import Real.Interval.OrderLe using
(≤ℝ-refl; <⇒≤ℝ; <-≤ℝ-trans; ≤ℝ-<trans; ≤ℝ-antisym)
open import Real.Interval.OrderLaws using (≈-<-resp)
open import Real.Interval.OrderComplete.Base using (_≤ℝ_; ≤ℝ-trans; Bracket)
open import Real.Interval.OrderComplete using (br-seq; u-sup; l-sup)
open import Real.Interval.Reasoning.Equiv using (beginℝ_; _≈ℝ⟨_⟩_; _∎ℝ)
open import Real.Interval.Recip using (recipℝ)
open import Real.Interval.RecipLaws using (recipℝ-pos; recipℝ-mul; recipℝ-cong)
open import Real.Interval.Sqrt.Located using (P; P-0; located)
open import Real.Interval.Sqrt.Bounds using
(sq-widen; embedℚ-reflect; l-layer-≤; u-layer-≤)
open import Real.Interval.Sqrt.Core using
(sqrtℝ; sqrt-upper; sqrt-least; sqrt-nonNeg; rq; isUpper)
sqrt-mono : (y z : RealI) (0y : 0ℝ <ℝ y) (0z : 0ℝ <ℝ z)
→ y ≤ℝ z → sqrtℝ y 0y ≤ℝ sqrtℝ z 0z
sqrt-mono y z 0y 0z y≤z = sqrt-least y 0y (sqrtℝ z 0z) step
where
step : (x : RealI) → P y 0y x → x ≤ℝ sqrtℝ z 0z
step x (x≥0 , xx<y) =
sqrt-upper z 0z x (x≥0 , <-≤ℝ-trans xx<y y≤z)
sqrt-pos : (y : RealI) (0y : 0ℝ <ℝ y) → 0ℝ <ℝ sqrtℝ y 0y
sqrt-pos y 0y =
let
probe : Σ ℚ (λ s → (0ℝ <ℝ embedℚ s) × (embedℚ s <ℝ y))
probe = dense {x = 0ℝ} {y = y} 0y
s : ℚ
s = proj₁ probe
0<es : 0ℝ <ℝ embedℚ s
0<es = proj₁ (proj₂ probe)
es<y : embedℚ s <ℝ y
es<y = proj₂ (proj₂ probe)
0<s : 0ℚ < s
0<s = embedℚ-reflect 0ℚ s 0<es
0*0<s : 0ℚ * 0ℚ < s
0*0<s = subst (λ z → z < s) (sym (*-zeroˡ 0ℚ)) 0<s
wid : Σ ℚ (λ r → 0ℚ < r × r * r < s)
wid = sq-widen 0ℚ s (≤-refl {0ℚ}) 0*0<s
r : ℚ
r = proj₁ wid
0<r : 0ℚ < r
0<r = proj₁ (proj₂ wid)
rr<s : r * r < s
rr<s = proj₂ (proj₂ wid)
x : RealI
x = embedℚ r
x≥0 : 0ℝ ≤ℝ x
x≥0 = <⇒≤ℝ (0<embedℚ r 0<r)
rr<y : embedℚ (r * r) <ℝ y
rr<y = <-trans (embedℚ-mono (r * r) s rr<s) es<y
xx<y : x *ℝ x <ℝ y
xx<y = ≈-<-resp (embedℚ-* r r) rr<y
px : P y 0y x
px = x≥0 , xx<y
x≤sqrt : x ≤ℝ sqrtℝ y 0y
x≤sqrt = sqrt-upper y 0y x px
0<x : 0ℝ <ℝ x
0<x = 0<embedℚ r 0<r
in
<-≤ℝ-trans 0<x x≤sqrt
sq-lt : (a b : RealI) → 0ℝ <ℝ a → a <ℝ b → a *ℝ a <ℝ b *ℝ b
sq-lt a b 0<a a<b =
let
0<b : 0ℝ <ℝ b
0<b = <-trans 0<a a<b
aa<ba : a *ℝ a <ℝ b *ℝ a
aa<ba = <-*mono a b a a<b 0<a
ab<bb : a *ℝ b <ℝ b *ℝ b
ab<bb = <-*mono a b b a<b 0<b
aa<ab : a *ℝ a <ℝ a *ℝ b
aa<ab = ≈-<-respʳ (≈ℝ-sym (*ℝ-comm a b)) aa<ba
in
<-trans aa<ab ab<bb
sq-of-member : (y : RealI) (0y : 0ℝ <ℝ y) (l x : RealI)
→ P y 0y x → l <ℝ x → 0ℝ <ℝ l
→ l *ℝ l <ℝ y
sq-of-member y 0y l x (_ , xx<y) l<x 0<l =
<-trans (sq-lt l x 0<l l<x) xx<y
sq-of-upper : (y : RealI) (0y : 0ℝ <ℝ y) (u : RealI)
→ 0ℝ ≤ℝ u → ((x : RealI) → P y 0y x → x <ℝ u)
→ y ≤ℝ u *ℝ u
sq-of-upper y 0y u 0≤u ub uu<y = <-irrefl u (ub u (0≤u , uu<y))
embedℚ-≤ : (p q : ℚ) → p ≤ q → embedℚ p ≤ℝ embedℚ q
embedℚ-≤ p q p≤q h =
ℚP.<-irrefl refl
(ℚP.≤-<-trans p≤q (embedℚ-reflect q p h))
sqrt-square-lower : (y : RealI) (0y : 0ℝ <ℝ y)
→ y ≤ℝ sqrtℝ y 0y *ℝ sqrtℝ y 0y
sqrt-square-lower y 0y sq<y =
let
sq : RealI
sq = sqrtℝ y 0y
k : ℕ
k = proj₁ sq<y
hk : u (sq *ℝ sq) k < l y k
hk = proj₂ sq<y
n : ℕ
n = Data.Nat._*_ 2 k
isUp : (z : RealI) → P y 0y z → z ≤ℝ rq y 0y
isUp = isUpper y 0y
br : ℕ → Bracket (P y 0y)
br = br-seq {P = P y 0y} (located y 0y) {x₀ = 0ℝ}
(P-0 y 0y) {u₀ = rq y 0y} isUp
b : ℚ
b = Bracket.b (br n)
b-ub : (z : RealI) → P y 0y z → z <ℝ embedℚ b
b-ub = Bracket.upper (br n)
0<eb : 0ℝ <ℝ embedℚ b
0<eb = b-ub 0ℝ (P-0 y 0y)
y≤eb² : y ≤ℝ embedℚ b *ℝ embedℚ b
y≤eb² = sq-of-upper y 0y (embedℚ b) (<⇒≤ℝ 0<eb) b-ub
y≤ebb : y ≤ℝ embedℚ (b * b)
y≤ebb = ≤-resp-≈ʳ y≤eb² (≈ℝ-sym (embedℚ-* b b))
ub : ℚ
ub = u (sq *ℝ sq) k
usq≡b : u sq n ≡ b
usq≡b = u-sup {P = P y 0y} (located y 0y) {x₀ = 0ℝ}
(P-0 y 0y) {u₀ = rq y 0y} isUp n
b≤ub : b * b ≤ ub
b≤ub = subst (λ z → z * z ≤ ub) usq≡b
(u-prod-corner sq sq k)
y≤eub : y ≤ℝ embedℚ ub
y≤eub = ≤ℝ-trans y≤ebb (embedℚ-≤ (b * b) ub b≤ub)
hkℝ : embedℚ ub <ℝ embedℚ (l y k)
hkℝ = embedℚ-mono ub (l y k) hk
eub<y : embedℚ ub <ℝ y
eub<y = <-≤ℝ-trans hkℝ (l-layer-≤ y k)
y<y : y <ℝ y
y<y = ≤ℝ-<trans y≤eub eub<y
in
<-irrefl y y<y
sqrt-square-upper : (y : RealI) (0y : 0ℝ <ℝ y)
→ sqrtℝ y 0y *ℝ sqrtℝ y 0y ≤ℝ y
sqrt-square-upper y 0y ys<ss =
let
s : RealI
s = sqrtℝ y 0y
isUp : (z : RealI) → P y 0y z → z ≤ℝ rq y 0y
isUp = isUpper y 0y
br : ℕ → Bracket (P y 0y)
br = br-seq {P = P y 0y} (located y 0y) {x₀ = 0ℝ}
(P-0 y 0y) {u₀ = rq y 0y} isUp
k : ℕ
k = proj₁ ys<ss
hk : u y k < l (s *ℝ s) k
hk = proj₂ ys<ss
ps : 0ℝ <ℝ s
ps = sqrt-pos y 0y
k₀ : ℕ
k₀ = proj₁ ps
h₀ : u 0ℝ k₀ < l s k₀
h₀ = proj₂ ps
0<lsk₀ : 0ℚ < l s k₀
0<lsk₀ = ℚP.<-trans (δ-pos k₀)
(subst (λ z → z < l s k₀) (u-dyadic-0 k₀) h₀)
K : ℕ
K = k ⊔ k₀
k≤K = m≤m⊔n k k₀
k₀≤K = m≤n⊔m k k₀
0<lsK : 0ℚ < l s K
0<lsK = ℚP.<-≤-trans 0<lsk₀ (l-mono s k₀≤K)
J : ℕ
J = Data.Nat._*_ 2 K
K≤J = n≤2n K
0<lsJ : 0ℚ < l s J
0<lsJ = ℚP.<-≤-trans 0<lsK (l-mono s K≤J)
lp : l (s *ℝ s) K ≡ l s J * l s J
lp = trans (cong RealI.l (node-*ℝ s s K))
(l-prod-pos (node s J) (node s J) 0<lsJ 0<lsJ)
occ : Σ RealI (λ x → P y 0y x × (embedℚ (Bracket.a (br J)) <ℝ x))
occ = Bracket.occ (br J)
x : RealI
x = proj₁ occ
px : P y 0y x
px = proj₁ (proj₂ occ)
a<x : embedℚ (Bracket.a (br J)) <ℝ x
a<x = proj₂ (proj₂ occ)
a≡lsJ : Bracket.a (br J) ≡ l s J
a≡lsJ = sym (l-sup {P = P y 0y} (located y 0y) {x₀ = 0ℝ}
(P-0 y 0y) {u₀ = rq y 0y} isUp J)
els<x : embedℚ (l s J) <ℝ x
els<x = subst (λ q → embedℚ q <ℝ x) a≡lsJ a<x
0<els : 0ℝ <ℝ embedℚ (l s J)
0<els = 0<embedℚ (l s J) 0<lsJ
els²<y : embedℚ (l s J) *ℝ embedℚ (l s J) <ℝ y
els²<y = <-trans (sq-lt (embedℚ (l s J)) x 0<els els<x)
(proj₂ px)
ells<y : embedℚ (l s J * l s J) <ℝ y
ells<y = ≈-<-resp (≈ℝ-sym (embedℚ-* (l s J) (l s J))) els²<y
eK<y : embedℚ (l (s *ℝ s) K) <ℝ y
eK<y = subst (λ z → embedℚ z <ℝ y) (sym lp) ells<y
ek≤K : l (s *ℝ s) k ≤ l (s *ℝ s) K
ek≤K = l-mono (s *ℝ s) k≤K
ek<y : embedℚ (l (s *ℝ s) k) <ℝ y
ek<y = ≤ℝ-<trans (embedℚ-≤ (l (s *ℝ s) k) (l (s *ℝ s) K) ek≤K)
eK<y
euy<y : embedℚ (u y k) <ℝ y
euy<y = <-trans (embedℚ-mono (u y k) (l (s *ℝ s) k) hk) ek<y
y≤euy : y ≤ℝ embedℚ (u y k)
y≤euy = u-layer-≤ y k
y<y : y <ℝ y
y<y = ≤ℝ-<trans y≤euy euy<y
in
<-irrefl y y<y
sqrt-square : (y : RealI) (0y : 0ℝ <ℝ y)
→ sqrtℝ y 0y *ℝ sqrtℝ y 0y ≈ℝ y
sqrt-square y 0y =
≤ℝ-antisym (sqrt-square-upper y 0y) (sqrt-square-lower y 0y)
sqrt-unique : (y : RealI) (0y : 0ℝ <ℝ y) (s : RealI)
→ 0ℝ ≤ℝ s → s *ℝ s ≈ℝ y
→ s ≈ℝ sqrtℝ y 0y
sqrt-unique y 0y s 0≤s ss≈y =
let
t : RealI
t = sqrtℝ y 0y
0<t : 0ℝ <ℝ t
0<t = sqrt-pos y 0y
tt≈y : t *ℝ t ≈ℝ y
tt≈y = sqrt-square y 0y
¬s<t : ¬ (s <ℝ t)
¬s<t s<t =
let
ss≤st : s *ℝ s ≤ℝ s *ℝ t
ss≤st = ≤-resp-≈ʳ
(*ℝ-≤-mono s t s (<⇒≤ℝ s<t) 0≤s)
(*ℝ-comm t s)
st<tt : s *ℝ t <ℝ t *ℝ t
st<tt = <-*mono s t t s<t 0<t
ss<tt : s *ℝ s <ℝ t *ℝ t
ss<tt = ≤ℝ-<trans ss≤st st<tt
ss<y : s *ℝ s <ℝ y
ss<y = ≈-<-respʳ tt≈y ss<tt
y<y : y <ℝ y
y<y = ≈-<-resp ss≈y ss<y
in
<-irrefl y y<y
¬t<s : ¬ (t <ℝ s)
¬t<s t<s =
let
tt<st : t *ℝ t <ℝ s *ℝ t
tt<st = <-*mono t s t t<s 0<t
st≤ss : s *ℝ t ≤ℝ s *ℝ s
st≤ss = ≤-resp-≈ˡ (*ℝ-comm t s)
(*ℝ-≤-mono t s s (<⇒≤ℝ t<s) 0≤s)
tt<ss : t *ℝ t <ℝ s *ℝ s
tt<ss = <-≤ℝ-trans tt<st st≤ss
tt<y : t *ℝ t <ℝ y
tt<y = ≈-<-respʳ ss≈y tt<ss
y<y : y <ℝ y
y<y = ≈-<-resp tt≈y tt<y
in
<-irrefl y y<y
s≤t : s ≤ℝ t
s≤t = ¬t<s
t≤s : t ≤ℝ s
t≤s = ¬s<t
in
≤ℝ-antisym s≤t t≤s
sqrt-of-mul : (y z : RealI) (0y : 0ℝ <ℝ y) (0z : 0ℝ <ℝ z)
(0yz : 0ℝ <ℝ y *ℝ z)
→ sqrtℝ (y *ℝ z) 0yz
≈ℝ sqrtℝ y 0y *ℝ sqrtℝ z 0z
sqrt-of-mul y z 0y 0z 0yz =
let
s : RealI
s = sqrtℝ y 0y
t : RealI
t = sqrtℝ z 0z
0st : 0ℝ ≤ℝ s *ℝ t
0st = *ℝ-nonNeg s t (sqrt-nonNeg y 0y) (sqrt-nonNeg z 0z)
square : (s *ℝ t) *ℝ (s *ℝ t) ≈ℝ y *ℝ z
square =
beginℝ
(s *ℝ t) *ℝ (s *ℝ t)
≈ℝ⟨ *ℝ-assoc s t (s *ℝ t) ⟩
s *ℝ (t *ℝ (s *ℝ t))
≈ℝ⟨ *ℝ-cong ≈ℝ-refl (≈ℝ-sym (*ℝ-assoc t s t)) ⟩
s *ℝ ((t *ℝ s) *ℝ t)
≈ℝ⟨ *ℝ-cong ≈ℝ-refl (*ℝ-cong (*ℝ-comm t s) ≈ℝ-refl) ⟩
s *ℝ ((s *ℝ t) *ℝ t)
≈ℝ⟨ *ℝ-cong ≈ℝ-refl (*ℝ-assoc s t t) ⟩
s *ℝ (s *ℝ (t *ℝ t))
≈ℝ⟨ ≈ℝ-sym (*ℝ-assoc s s (t *ℝ t)) ⟩
(s *ℝ s) *ℝ (t *ℝ t)
≈ℝ⟨ *ℝ-cong (sqrt-square y 0y) (sqrt-square z 0z) ⟩
y *ℝ z
∎ℝ
eq : s *ℝ t ≈ℝ sqrtℝ (y *ℝ z) 0yz
eq = sqrt-unique (y *ℝ z) 0yz (s *ℝ t) 0st square
in
≈ℝ-sym eq
sqrt-of-inv : (y : RealI) (0y : 0ℝ <ℝ y)
(0iy : 0ℝ <ℝ recipℝ y 0y) (0t : 0ℝ <ℝ sqrtℝ y 0y)
→ sqrtℝ (recipℝ y 0y) 0iy ≈ℝ recipℝ (sqrtℝ y 0y) 0t
sqrt-of-inv y 0y 0iy 0t =
let
t : RealI
t = sqrtℝ y 0y
r : RealI
r = recipℝ t 0t
0r : 0ℝ ≤ℝ r
0r = <⇒≤ℝ (recipℝ-pos t 0t)
0tt : 0ℝ <ℝ t *ℝ t
0tt = pos*pos t t 0t 0t
square : r *ℝ r ≈ℝ recipℝ y 0y
square =
≈ℝ-trans
(≈ℝ-sym (recipℝ-mul t t 0t 0t))
(recipℝ-cong (t *ℝ t) y 0tt 0y (sqrt-square y 0y))
eq : r ≈ℝ sqrtℝ (recipℝ y 0y) 0iy
eq = sqrt-unique (recipℝ y 0y) 0iy r 0r square
in
≈ℝ-sym eq
sqrt-of-zero : (y : RealI) → y ≈ℝ 0ℝ →
(0ℝ ≤ℝ 0ℝ) × (0ℝ *ℝ 0ℝ ≈ℝ y)
sqrt-of-zero y y≈0 =
≤ℝ-refl , ≈ℝ-trans (*ℝ-zeroˡ 0ℝ) (≈ℝ-sym y≈0)