{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.IntervalEquiv where
open import Data.Integer using (+_; -[1+_]; +≤+)
import Data.Integer.Properties as ℤP
open import Data.Nat using (ℕ; zero; suc; _≥_; _^_; _∸_; z≤n; s≤s; ≢-nonZero)
renaming (_+_ to _+N_; _≤_ to _≤N_; _<_ to _<N_; _*_ to _ℕ*_; NonZero to ℕNonZero)
open import Data.Nat.Properties using (*-suc; n≤1+n; *-mono-≤; ^-monoʳ-≤)
renaming (≤-trans to ≤ℕ-trans; ≤-refl to ≤ℕ-refl)
import Data.Nat.Properties as ℕP
open import Data.Nat.Coprimality using (Coprime; 1-coprimeTo)
open import Data.Product using (Σ; _,_; proj₁; proj₂)
open import Data.Sum.Base using (inj₁; inj₂)
open import Data.Rational using
(ℚ; 0ℚ; 1ℚ; _<_; _≤_; _+_; _-_; _*_; ∣_∣; NonZero; Positive; nonNegative
; NonNegative; fromℚᵘ) renaming (-_ to neg)
open import Data.Rational.Base using (mkℚ; _÷_; 1/_; normalize; positive; *≤*)
open import Data.Rational.Properties using
(≤-reflexive; ≤-refl; ≤-trans; <⇒≤; <-≤-trans; ≤-<-trans; +-inverseʳ
; +-mono-≤; *-assoc; *-comm; *-identityˡ; *-identityʳ; *-inverseˡ; *-inverseʳ
; *-distribʳ-+; *-monoˡ-≤-nonNeg; *-monoʳ-≤-nonNeg; pos⇒nonZero; pos⇒nonNeg
; pos*pos⇒pos; 1/pos⇒pos; neg-antimono-≤; ∣p∣≡p∨∣p∣≡-p; /-cong
; normalize-coprime; mkℚ-cong; module ≤-Reasoning)
open import Data.Rational.Unnormalised.Base using (ℚᵘ; mkℚᵘ)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; trans; sym; cong; subst; ≢-sym; module ≡-Reasoning)
open import Base.RationalRing using (0<1)
open import Real using
(CauchySeq; ε; embed; 2ℚ≡1+1; 2*embed; embed-suc-pos; embed-pos→≥1
; embed-mono-<; reciprocal-cong)
open CauchySeq
open import Real.Interval using (RealI; pos-pow)
open import Real.Interval.Rational using
(rawR; suc∸1; 0<2^t; negsub; pos-diff; recip-*-hom; combFrac; comb-strict)
node : RealI → ℕ → RealI
node r zero = r
node r (suc n) = RealI.next (node r n)
node-suc : (r : RealI) (n : ℕ) → node r (suc n) ≡ node (RealI.next r) n
node-suc r zero = refl
node-suc r (suc n) = cong RealI.next (node-suc r n)
l u : RealI → ℕ → ℚ
l r n = RealI.l (node r n)
u r n = RealI.u (node r n)
width : RealI → ℕ → ℚ
width r n = u r n - l r n
width-step : (r : RealI) → width r 1 ≤ width r 0 ÷ embed 2
width-step r = proj₂ (proj₂ (RealI.nest r))
centre : RealI → ℕ → ℚ
centre r n = (l r n + u r n) ÷ embed 2
width-1step : (r : RealI) (n : ℕ) → width r (suc n) ≤ width r n ÷ embed 2
width-1step r n = proj₂ (proj₂ (RealI.nest (node r n)))
mono-half : ∀ {a b} → a ≤ b → a ÷ embed 2 ≤ b ÷ embed 2
mono-half {a} {b} a≤b =
let half = 1/_ (embed 2) {{pos⇒nonZero (embed 2) {{pos-pow 0}}}}
halfPos : Positive half
halfPos = 1/pos⇒pos (embed 2) {{pos-pow 0}}
in *-monoʳ-≤-nonNeg half {{pos⇒nonNeg half {{halfPos}}}} a≤b
recip-prod≤ : (a b : ℚ) → (pa : Positive a) → (pb : Positive b) →
1/_ a {{pos⇒nonZero a {{pa}}}}
* 1/_ b {{pos⇒nonZero b {{pb}}}}
≤ 1/_ (a * b)
{{pos⇒nonZero (a * b) {{pos*pos⇒pos a {{pa}} b {{pb}}}}}}
recip-prod≤ a b pa pb =
≤-reflexive (sym (recip-*-hom a b
⦃ pos⇒nonZero a {{pa}} ⦄
⦃ pos⇒nonZero b {{pb}} ⦄
⦃ pos⇒nonZero (a * b) {{pos*pos⇒pos a {{pa}} b {{pb}}}} ⦄))
pow2 : ℕ → ℚ
pow2 n = embed (2 ^ n)
posPow2 : (n : ℕ) → Positive (pow2 n)
posPow2 zero = embed-suc-pos {0}
posPow2 (suc n) = pos-pow n
denom-eq : (n : ℕ) → pow2 n * pow2 1 ≡ pow2 (suc n)
denom-eq n =
trans (*-comm (pow2 n) (embed 2))
(2*embed (2 ^ n))
recipPow2 : ℕ → ℚ
recipPow2 n =
let d = 2 ^ n ∸ 1
in 1/_ (embed (suc d))
⦃ pos⇒nonZero (embed (suc d)) ⦃ embed-suc-pos ⦄ ⦄
width-nV : RealI → ℕ → ℚ
width-nV r n = width r 0 * recipPow2 n
width-n : (r : RealI) (n : ℕ) →
width r n ≤ width-nV r n
width-n r zero =
≤-reflexive (sym (*-identityʳ (width r 0)))
width-n r (suc n) =
let open ≡-Reasoning
w0 = width r 0
an = 2 ^ n ∸ 1
a1 = 2 ^ 1 ∸ 1
as = 2 ^ suc n ∸ 1
A = embed (suc an)
B = embed (suc a1)
S = embed (suc as)
hn = recipPow2 n
h1 = recipPow2 1
hs = recipPow2 (suc n)
w0nn : NonNegative w0
w0nn = nonNegative
(≤-trans (≤-reflexive (sym (+-inverseʳ (l r 0))))
(+-mono-≤ (<⇒≤ (RealI.lo r)) (≤-refl)))
h1nn : NonNegative h1
h1nn = pos⇒nonNeg h1 {{1/pos⇒pos B {{embed-suc-pos}}}}
step1 : width r (suc n) ≤ width r n * h1
step1 = width-1step r n
step2 : width r n * h1 ≤ (w0 * hn) * h1
step2 = *-monoʳ-≤-nonNeg h1 {{h1nn}} (width-n r n)
step3 : (w0 * hn) * h1 ≤ w0 * (hn * h1)
step3 = ≤-reflexive (*-assoc w0 hn h1)
step4 : w0 * (hn * h1) ≤ w0 * hs
step4 =
let prod = A * B
prodPos : Positive prod
prodPos = pos*pos⇒pos A {{embed-suc-pos}} B {{embed-suc-pos}}
invprod = 1/_ prod {{pos⇒nonZero prod {{prodPos}}}}
s41 : w0 * (hn * h1) ≤ w0 * invprod
s41 = *-monoˡ-≤-nonNeg w0 {{w0nn}}
(recip-prod≤ A B embed-suc-pos embed-suc-pos)
A≡ : A ≡ pow2 n
A≡ = cong embed (suc∸1 (0<2^t n))
B≡ : B ≡ pow2 1
B≡ = cong embed (suc∸1 (0<2^t 1))
S≡ : S ≡ pow2 (suc n)
S≡ = cong embed (suc∸1 (0<2^t (suc n)))
prod≡S : prod ≡ S
prod≡S = begin
A * B ≡⟨ cong (A *_) B≡ ⟩
A * pow2 1 ≡⟨ cong (_* pow2 1) A≡ ⟩
pow2 n * pow2 1 ≡⟨ denom-eq n ⟩
pow2 (suc n) ≡⟨ sym S≡ ⟩
S ∎
inv-eq : invprod ≡ hs
inv-eq = reciprocal-cong prod S
{{pos⇒nonZero prod {{prodPos}}}}
{{pos⇒nonZero S {{embed-suc-pos}}}}
prod≡S
s42 : w0 * invprod ≡ w0 * hs
s42 = cong (λ z → w0 * z) inv-eq
in ≤-trans s41 (≤-reflexive s42)
in ≤-trans step1 (≤-trans step2 (≤-trans step3 step4))
centre-l : (r : RealI) (n : ℕ) → l r n ≤ centre r n
centre-l r n =
let open ≡-Reasoning
l′ = l r n; u′ = u r n
half = 1/_ (embed 2) {{pos⇒nonZero (embed 2) {{pos-pow 0}}}}
2h : embed 2 * half ≡ 1ℚ
2h = *-inverseʳ (embed 2) {{pos⇒nonZero (embed 2) {{pos-pow 0}}}}
2l : embed 2 * l′ ≡ l′ + l′
2l = begin
embed 2 * l′
≡⟨ cong (λ z → z * l′) (sym 2ℚ≡1+1) ⟩
(1ℚ + 1ℚ) * l′
≡⟨ *-distribʳ-+ l′ 1ℚ 1ℚ ⟩
1ℚ * l′ + 1ℚ * l′
≡⟨ cong (λ z → z + 1ℚ * l′) (*-identityˡ l′) ⟩
l′ + 1ℚ * l′
≡⟨ cong (λ z → l′ + z) (*-identityˡ l′) ⟩
l′ + l′
∎
l≤u : l′ ≤ u′
l≤u = <⇒≤ (RealI.lo (node r n))
ineq : embed 2 * l′ ≤ l′ + u′
ineq =
≤-trans (≤-reflexive 2l)
(+-mono-≤ (≤-refl {l′}) l≤u)
mono : (embed 2 * l′) * half ≤ (l′ + u′) * half
mono = *-monoʳ-≤-nonNeg half
{{pos⇒nonNeg half {{1/pos⇒pos (embed 2) {{pos-pow 0}}}}}} ineq
chain : (embed 2 * l′) * half ≡ l′
chain = begin
(embed 2 * l′) * half
≡⟨ *-assoc (embed 2) l′ half ⟩
embed 2 * (l′ * half)
≡⟨ cong (λ z → embed 2 * z) (*-comm l′ half) ⟩
embed 2 * (half * l′)
≡⟨ sym (*-assoc (embed 2) half l′) ⟩
(embed 2 * half) * l′
≡⟨ cong (λ z → z * l′) 2h ⟩
1ℚ * l′
≡⟨ *-identityˡ l′ ⟩
l′
∎
lhs : l′ ≡ (embed 2 * l′) * half
lhs = sym chain
in ≤-trans (≤-reflexive lhs) mono
centre-u : (r : RealI) (n : ℕ) → centre r n ≤ u r n
centre-u r n =
let open ≡-Reasoning
l′ = l r n; u′ = u r n
half = 1/_ (embed 2) {{pos⇒nonZero (embed 2) {{pos-pow 0}}}}
2h : embed 2 * half ≡ 1ℚ
2h = *-inverseʳ (embed 2) {{pos⇒nonZero (embed 2) {{pos-pow 0}}}}
2u : embed 2 * u′ ≡ u′ + u′
2u = begin
embed 2 * u′
≡⟨ cong (λ z → z * u′) (sym 2ℚ≡1+1) ⟩
(1ℚ + 1ℚ) * u′
≡⟨ *-distribʳ-+ u′ 1ℚ 1ℚ ⟩
1ℚ * u′ + 1ℚ * u′
≡⟨ cong (λ z → z + 1ℚ * u′) (*-identityˡ u′) ⟩
u′ + 1ℚ * u′
≡⟨ cong (λ z → u′ + z) (*-identityˡ u′) ⟩
u′ + u′
∎
l≤u : l′ ≤ u′
l≤u = <⇒≤ (RealI.lo (node r n))
ineq : l′ + u′ ≤ embed 2 * u′
ineq =
≤-trans (+-mono-≤ l≤u (≤-refl {u′}))
(≤-reflexive (sym 2u))
mono : (l′ + u′) * half ≤ (embed 2 * u′) * half
mono = *-monoʳ-≤-nonNeg half
{{pos⇒nonNeg half {{1/pos⇒pos (embed 2) {{pos-pow 0}}}}}} ineq
chain : (embed 2 * u′) * half ≡ u′
chain = begin
(embed 2 * u′) * half
≡⟨ *-assoc (embed 2) u′ half ⟩
embed 2 * (u′ * half)
≡⟨ cong (λ z → embed 2 * z) (*-comm u′ half) ⟩
embed 2 * (half * u′)
≡⟨ sym (*-assoc (embed 2) half u′) ⟩
(embed 2 * half) * u′
≡⟨ cong (λ z → z * u′) 2h ⟩
1ℚ * u′
≡⟨ *-identityˡ u′ ⟩
u′
∎
final : (l′ + u′) * half ≤ u′
final = ≤-trans mono (≤-reflexive chain)
in final
l-nest : (r : RealI) → l r 0 ≤ l (RealI.next r) 0
l-nest r = proj₁ (RealI.nest r)
u-nest : (r : RealI) → u (RealI.next r) 0 ≤ u r 0
u-nest r = proj₁ (proj₂ (RealI.nest r))
l-mono0 : (r : RealI) (m : ℕ) → RealI.l r ≤ RealI.l (node r m)
l-mono0 r zero = ≤-refl
l-mono0 r (suc m) = ≤-trans (l-mono0 r m) (l-nest (node r m))
l-mono : (r : RealI) → {n m : ℕ} → n ≤N m →
RealI.l (node r n) ≤ RealI.l (node r m)
l-mono r {m = m} z≤n = l-mono0 r m
l-mono r {suc n} {suc m} (s≤s p) =
≤-trans (≤-reflexive (cong RealI.l (node-suc r n)))
(≤-trans (l-mono (RealI.next r) p)
(≤-reflexive (cong RealI.l (sym (node-suc r m)))))
u-mono0 : (r : RealI) (m : ℕ) → RealI.u (node r m) ≤ RealI.u r
u-mono0 r zero = ≤-refl
u-mono0 r (suc m) = ≤-trans (u-nest (node r m)) (u-mono0 r m)
u-mono : (r : RealI) → {n m : ℕ} → n ≤N m →
RealI.u (node r m) ≤ RealI.u (node r n)
u-mono r {m = m} z≤n = u-mono0 r m
u-mono r {suc n} {suc m} (s≤s p) =
≤-trans (≤-reflexive (cong RealI.u (node-suc r m)))
(≤-trans (u-mono (RealI.next r) p)
(≤-reflexive (cong RealI.u (sym (node-suc r n)))))
centre-in-l : (r : RealI) {n m : ℕ} → n ≤N m → l r n ≤ centre r m
centre-in-l r {n} {m} p = ≤-trans (l-mono r p) (centre-l r m)
centre-in-u : (r : RealI) {n m : ℕ} → n ≤N m → centre r m ≤ u r n
centre-in-u r {n} {m} p = ≤-trans (centre-u r m) (u-mono r p)
diff+ : {x y l u : ℚ} →
l ≤ x → x ≤ u → l ≤ y → y ≤ u → (x - y) ≤ (u - l)
diff+ {x} {y} {l} {u} lx xu ly yu =
≤-trans (+-mono-≤ xu (≤-refl { neg y }))
(+-mono-≤ (≤-refl {u}) (neg-antimono-≤ ly))
diff- : {x y l u : ℚ} →
l ≤ x → x ≤ u → l ≤ y → y ≤ u → neg (x - y) ≤ (u - l)
diff- {x} {y} {l} {u} lx xu ly yu =
≤-trans (≤-reflexive (negsub x y))
(≤-trans (+-mono-≤ yu (≤-refl { neg x }))
(+-mono-≤ (≤-refl {u}) (neg-antimono-≤ lx)))
bounded-diff : {x y l u : ℚ} →
l ≤ x → x ≤ u → l ≤ y → y ≤ u → ∣ x - y ∣ ≤ u - l
bounded-diff {x} {y} {l} {u} lx xu ly yu
with ∣p∣≡p∨∣p∣≡-p (x - y)
... | inj₁ abs≡ =
≤-trans (≤-reflexive abs≡) (diff+ lx xu ly yu)
... | inj₂ abs≡ =
≤-trans (≤-reflexive abs≡) (diff- lx xu ly yu)
centre-diff : (r : RealI) (t a b : ℕ) →
t ≤N a → t ≤N b → ∣ centre r a - centre r b ∣ ≤ width r t
centre-diff r t a b ta tb =
bounded-diff (centre-in-l r ta) (centre-in-u r ta)
(centre-in-l r tb) (centre-in-u r tb)
centre-diff≤ : (r : RealI) (t a b : ℕ) →
t ≤N a → t ≤N b → ∣ centre r a - centre r b ∣ ≤ width-nV r t
centre-diff≤ r t a b ta tb =
≤-trans (centre-diff r t a b ta tb) (width-n r t)
2m : ∀ m → 2 ℕ* m ≡ m +N m
2m m = begin
2 ℕ* m
≡⟨ ℕP.*-comm 2 m ⟩
m ℕ* 2
≡⟨ *-suc m 1 ⟩
m +N (m ℕ* 1)
≡⟨ cong (m +N_) (ℕP.*-identityʳ m) ⟩
m +N m
∎
where open ≡-Reasoning
pp : ∀ n → 2 ^ suc n ≡ 2 ℕ* (2 ^ n)
pp n = refl
qq : ∀ n → 2 ^ n +N 2 ^ n ≡ 2 ^ suc n
qq n = begin
2 ^ n +N 2 ^ n
≡⟨ sym (2m (2 ^ n)) ⟩
2 ℕ* (2 ^ n)
≡⟨ sym (pp n) ⟩
2 ^ suc n
∎
where open ≡-Reasoning
pow≤ : ∀ n → 2 ^ n ≤N 2 ^ suc n
pow≤ n = ^-monoʳ-≤ 2 (n≤1+n n)
1≤2^n : ∀ n → 1 ≤N 2 ^ n
1≤2^n n = ^-monoʳ-≤ 2 (z≤n {n})
1≤⇒Positive : (q : ℚ) → 1ℚ ≤ q → Positive q
1≤⇒Positive q 1≤q =
positive (<-≤-trans (0<1) 1≤q)
recip≤1 : (q : ℚ) → 1ℚ ≤ q → (nz : NonZero q) →
1/_ q {{nz}} ≤ 1ℚ
recip≤1 q 1≤q nz =
let r = 1/_ q {{nz}}
pq : Positive q
pq = 1≤⇒Positive q 1≤q
in
begin
r
≡⟨ sym (*-identityʳ r) ⟩
r * 1ℚ
≤⟨ *-monoˡ-≤-nonNeg r
{{pos⇒nonNeg r {{1/pos⇒pos q {{pq}}}}}} 1≤q ⟩
r * q
≡⟨ *-inverseˡ q {{nz}} ⟩
1ℚ
∎
where open ≤-Reasoning
1≤embed-suc : (d : ℕ) → 1ℚ ≤ embed (suc d)
1≤embed-suc d =
*≤* (+≤+ (s≤s z≤n))
nonNeg-embed : (M : ℕ) → NonNegative (embed M)
nonNeg-embed zero = nonNegative (≤-refl)
nonNeg-embed (suc n) =
pos⇒nonNeg (embed (suc n)) {{embed-suc-pos}}
frac≤ : (M d : ℕ) →
let p = embed M
q = embed (suc d)
pq : Positive q
pq = embed-suc-pos
nz : NonZero q
nz = pos⇒nonZero q {{pq}}
in
p * 1/_ q {{nz}} ≤ p
frac≤ M d =
let p = embed M
q = embed (suc d)
pq : Positive q
pq = embed-suc-pos
in
begin
p * 1/_ q {{pos⇒nonZero q {{pq}}}}
≤⟨ *-monoˡ-≤-nonNeg p
{{nonNeg-embed M}} (recip≤1 q (1≤embed-suc d) (pos⇒nonZero q {{pq}})) ⟩
p * 1ℚ
≡⟨ *-identityʳ p ⟩
p
∎
where open ≤-Reasoning
prod-eq : (M d : ℕ) →
embed M * 1/_ (embed (suc d))
{{pos⇒nonZero (embed (suc d)) {{embed-suc-pos}}}}
≡ normalize M (suc d)
prod-eq M d =
/-cong
(ℤP.*-identityʳ (+ M))
(ℕP.*-identityˡ (suc d))
frac-term-eq : (M d : ℕ) → .(c : Coprime M (suc d)) →
mkℚ (+ M) d c
≡ embed M * 1/_ (embed (suc d))
{{pos⇒nonZero (embed (suc d)) {{embed-suc-pos}}}}
frac-term-eq M d c =
trans (sym (normalize-coprime c)) (sym (prod-eq M d))
bound-w : (w : ℚ) → 0ℚ ≤ w → Σ ℕ (λ M → w ≤ embed M)
bound-w (mkℚ (+ M) d c) _ =
M , (≤-trans (≤-reflexive (frac-term-eq M d c)) (frac≤ M d))
bound-w (mkℚ -[1+ n ] d c) (*≤* le) with le
... | ()
pow< : (n : ℕ) → 2 ^ n <N 2 ^ suc n
pow< n =
ℕP.<-≤-trans
(ℕP.m<n+m (2 ^ n) {n = 2 ^ n} (0<2^t n))
(ℕP.≤-reflexive (qq n))
n<2^n : (n : ℕ) → n <N 2 ^ n
n<2^n zero = s≤s z≤n
n<2^n (suc n) =
ℕP.≤-<-trans (n<2^n n) (pow< n)
B<2^sucB : (B : ℕ) → B <N 2 ^ suc B
B<2^sucB B =
ℕP.<-trans (n<2^n B) (pow< B)
pos-2^t : (t : ℕ) → Positive (embed (2 ^ t))
pos-2^t t = positive (embed-mono-< (0<2^t t))
recip2^t : (t : ℕ) → ℚ
recip2^t = recipPow2
rawL : (M t : ℕ) → ℚᵘ
rawL M t = mkℚᵘ (+ M) (2 ^ t ∸ 1)
recip-suc : (k : ℕ) → ℚ
recip-suc k = ε k
nz-2^t : (t : ℕ) → ℕNonZero (2 ^ t)
nz-2^t t =
≢-nonZero
(≢-sym
(ℕP.<⇒≢ (0<2^t t)))
fracL : (M t : ℕ) → ℚ
fracL M t = fromℚᵘ (rawL M t)
prod≡fracL : (M t : ℕ) → embed M * recip2^t t ≡ fracL M t
prod≡fracL M t = prod-eq M (2 ^ t ∸ 1)
fracL≡combFrac : (M t : ℕ) → fracL M t ≡ combFrac M 0 t
fracL≡combFrac M t =
cong (λ z → fromℚᵘ (mkℚᵘ (+ M) z))
(cong (_∸ 1) (sym (ℕP.+-identityʳ (2 ^ t))))
fromℚᵘ-rawR≡recip-suc : (k : ℕ) → fromℚᵘ (rawR k) ≡ recip-suc k
fromℚᵘ-rawR≡recip-suc k =
trans (normalize-coprime (1-coprimeTo (suc k)))
(mkℚ-cong refl refl)
frac-strict : (M k t : ℕ) →
(M ℕ* suc k) <N 2 ^ t →
embed M * recip2^t t < recip-suc k
frac-strict M k t h =
≤-<-trans
(≤-reflexive (trans (prod≡fracL M t) (fracL≡combFrac M t)))
(<-≤-trans
(comb-strict M 0 k t h')
(≤-reflexive (fromℚᵘ-rawR≡recip-suc k)))
where
h' = subst (λ z → M ℕ* suc k <N z)
(sym (ℕP.+-identityʳ (2 ^ t))) h
0<width : (r : RealI) → 0ℚ < width r 0
0<width r = pos-diff (RealI.l r) (RealI.u r) (RealI.lo r)
realI→cauchy : RealI → CauchySeq
realI→cauchy r = record
{ f = centre r
; μ = modulus
; cauchy = cauchy-proof
}
where
w0 = width r 0
0≤w0 : 0ℚ ≤ w0
0≤w0 = <⇒≤ (0<width r)
M = proj₁ (bound-w w0 0≤w0)
w0≤M : w0 ≤ embed M
w0≤M = proj₂ (bound-w w0 0≤w0)
modulus : ℕ → ℕ
modulus k = suc (M ℕ* suc k)
recip2^t-pos : (t : ℕ) → Positive (recip2^t t)
recip2^t-pos t =
let d = 2 ^ t ∸ 1
in 1/pos⇒pos (embed (suc d))
⦃ embed-suc-pos ⦄
step2 : (t : ℕ) → width-nV r t ≤ embed M * recip2^t t
step2 t =
*-monoʳ-≤-nonNeg
(recip2^t t)
{{pos⇒nonNeg (recip2^t t) {{recip2^t-pos t}}}}
w0≤M
cauchy-proof : ∀ k n m → n ≥ modulus k → m ≥ modulus k →
∣ centre r n - centre r m ∣ < ε k
cauchy-proof k n m n≥μ m≥μ =
let t = modulus k in
≤-<-trans
(centre-diff≤ r t n m n≥μ m≥μ)
(≤-<-trans
(step2 t)
(frac-strict M k t (B<2^sucB (M ℕ* suc k))))
μx-dom : (r : RealI) (k : ℕ) → μ (realI→cauchy r) k ≥ k
μx-dom r zero = z≤n
μx-dom r (suc k) = s≤s (≤ℕ-trans mid monoA)
where
w0 = width r 0
0≤w0 = <⇒≤ (0<width r)
Mx = proj₁ (bound-w w0 0≤w0)
w0≤Mx = proj₂ (bound-w w0 0≤w0)
0<eMx = <-≤-trans (0<width r) w0≤Mx
Mx≥1 : 1 ≤N Mx
Mx≥1 = embed-pos→≥1 Mx 0<eMx
mid : k ≤N suc (suc k)
mid = ≤ℕ-trans (n≤1+n k) (s≤s (n≤1+n k))
monoA : suc (suc k) ≤N Mx ℕ* suc (suc k)
monoA =
≤ℕ-trans (ℕP.≤-reflexive (sym (ℕP.*-identityˡ (suc (suc k)))))
(*-mono-≤ Mx≥1 (≤ℕ-refl {suc (suc k)}))