{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real where
open import Agda.Primitive using (lzero)
open import Data.Empty using (⊥-elim)
open import Data.Integer.Base using (+_; +<+; +≤+) renaming (_*_ to _ℤ*_; _+_ to _ℤ+_)
open import Data.Integer.Properties using (pos-+; pos-*)
renaming (*-identityʳ to ℤ*-identityʳ; ≤-<-trans to ℤ≤-<-trans
; ≤-trans to ℤ≤-trans; <-≤-trans to ℤ<-≤-trans; ≤-reflexive to ℤ≤-reflexive)
open import Data.Nat using (ℕ; zero; _≥_; _⊔_; suc; s≤s; z≤n)
renaming (_+_ to _+ℕ_; _*_ to _ℕ*_; _≤_ to _≤ℕ_; _<_ to _<ℕ_)
open import Data.Nat.Properties using (m≤m⊔n; m≤n⊔m; ≤-trans; *-suc)
open import Data.Nat.Coprimality using (1-coprimeTo)
renaming (sym to coprime-sym)
open import Data.Product using (Σ; _,_; _×_)
open import Data.Rational using
(ℚ; 0ℚ; 1ℚ; _+_; _-_; -_; _*_; _/_; _≤_; ∣_∣; _<_; NonZero; Positive)
open import Data.Rational.Base using (1/_; mkℚ; *<*; *≤*)
open import Data.Rational.Properties using
(0≤p⇒∣p∣≡p; +-inverseʳ; ≤-refl; ≤-reflexive; positive⁻¹; pos⇒nonZero
; normalize-coprime; /-cong; ≤-<-trans; +-mono-<; *-inverseʳ; *-assoc; *-comm
; *-identityˡ; *-identityʳ; *-distribʳ-+; mkℚ+-pos; 1/pos⇒pos; <⇒≤; <-irrefl)
open import Relation.Binary.Core using (Rel)
open import Relation.Binary.Structures using (IsEquivalence)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; cong; cong₂; subst; sym; module ≡-Reasoning)
open ≡-Reasoning
open import Base.RationalRing using (telescope)
embed : ℕ → ℚ
embed n = mkℚ (+ n) 0 (coprime-sym (1-coprimeTo n))
ε : ℕ → ℚ
ε k = 1/ embed (suc k)
embed-suc-pos : ∀ {n} → Positive (embed (suc n))
embed-suc-pos {n} =
mkℚ+-pos (suc n) 1 {c = coprime-sym (1-coprimeTo (suc n))}
instance
embed-suc-nonZero : ∀ {n} → NonZero (embed (suc n))
embed-suc-nonZero {n} = pos⇒nonZero (embed (suc n)) {{embed-suc-pos {n}}}
2ℚ : ℚ
2ℚ = embed 2
2ℚ≡1+1 : 2ℚ ≡ 1ℚ + 1ℚ
2ℚ≡1+1 = sym (normalize-coprime (coprime-sym (1-coprimeTo 2)))
num-2 : ∀ n → (+ 2) ℤ* (+ n) ≡ + (2 ℕ* n)
num-2 n = sym (pos-* 2 n)
2*embed : ∀ n → 2ℚ * embed n ≡ embed (2 ℕ* n)
2*embed n = begin
2ℚ * embed n
≡⟨⟩
(+ 2 ℤ* + n) / 1
≡⟨ /-cong (num-2 n) refl ⟩
(+ (2 ℕ* n)) / 1
≡⟨ normalize-coprime (coprime-sym (1-coprimeTo (2 ℕ* n))) ⟩
embed (2 ℕ* n)
∎
den-2 : ∀ k → suc (suc (2 ℕ* k)) ≡ 2 ℕ* suc k
den-2 k = sym (*-suc 2 k)
embed2-nonZero : NonZero (embed 2)
embed2-nonZero = embed-suc-nonZero {1}
half : ℚ
half = 1/_ (embed 2) {{embed2-nonZero}}
record CauchySeq : Set₁ where
field
f : ℕ → ℚ
μ : ℕ → ℕ
cauchy : ∀ k n m → n ≥ μ k → m ≥ μ k → ∣ f n - f m ∣ < ε k
open CauchySeq
_s≈_ : ℚ → ℚ → ℕ → Set
_s≈_ q1 q2 k = (q1 + (- q2)) < ε k × (q2 + (- q1)) < ε k
_≈_ : Rel CauchySeq lzero
_≈_ x y = ∀ k → Σ ℕ (λ N → ∀ n → n ≥ N → _s≈_ (f x n) (f y n) k)
0<ε : ∀ k → 0ℚ < ε k
0<ε k =
positive⁻¹ (ε k)
{{1/pos⇒pos (embed (suc k)) {{embed-suc-pos {k}}}}}
halve : ∀ m {{_ : NonZero m}} {{_ : NonZero (2ℚ * m)}} →
(1/ (2ℚ * m)) + (1/ (2ℚ * m)) ≡ 1/ m
halve m =
let t : ℚ
t = 1/ (2ℚ * m)
tt≡2t : t + t ≡ 2ℚ * t
tt≡2t = begin
t + t
≡⟨ cong (λ v → v + t) (sym (*-identityˡ t)) ⟩
1ℚ * t + t
≡⟨ cong (λ v → (1ℚ * t) + v) (sym (*-identityˡ t)) ⟩
1ℚ * t + 1ℚ * t
≡⟨ sym (*-distribʳ-+ t 1ℚ 1ℚ) ⟩
(1ℚ + 1ℚ) * t
≡⟨ cong (λ v → v * t) (sym 2ℚ≡1+1) ⟩
2ℚ * t
∎
2tm : (2ℚ * t) * m ≡ 1ℚ
2tm = begin
(2ℚ * t) * m
≡⟨ *-assoc 2ℚ t m ⟩
2ℚ * (t * m)
≡⟨ cong (2ℚ *_) (*-comm t m) ⟩
2ℚ * (m * t)
≡⟨ sym (*-assoc 2ℚ m t) ⟩
(2ℚ * m) * t
≡⟨ *-inverseʳ (2ℚ * m) ⟩
1ℚ
∎
2t≡1/m : 2ℚ * t ≡ 1/ m
2t≡1/m = begin
2ℚ * t
≡⟨ sym (*-identityʳ (2ℚ * t)) ⟩
(2ℚ * t) * 1ℚ
≡⟨ cong (λ v → (2ℚ * t) * v) (sym (*-inverseʳ m)) ⟩
(2ℚ * t) * (m * (1/ m))
≡⟨ sym (*-assoc (2ℚ * t) m (1/ m)) ⟩
((2ℚ * t) * m) * (1/ m)
≡⟨ cong (λ v → v * (1/ m)) 2tm ⟩
1ℚ * (1/ m)
≡⟨ *-identityˡ (1/ m) ⟩
1/ m
∎
in begin
t + t
≡⟨ tt≡2t ⟩
2ℚ * t
≡⟨ 2t≡1/m ⟩
1/ m
∎
reciprocal-cong : ∀ a b → .{{na : NonZero a}} → .{{nb : NonZero b}} →
a ≡ b → 1/_ a ≡ 1/_ b
reciprocal-cong a .a refl = refl
ε-half : ∀ k → ε (suc (2 ℕ* k)) + ε (suc (2 ℕ* k)) ≡ ε k
ε-half k =
let m = embed (suc k)
b = embed (suc (suc (2 ℕ* k)))
e2m : 2ℚ * m ≡ b
e2m = begin
2ℚ * m
≡⟨ 2*embed (suc k) ⟩
embed (2 ℕ* suc k)
≡⟨ cong embed (sym (den-2 k)) ⟩
b
∎
n2m : NonZero (2ℚ * m)
n2m = subst NonZero (sym e2m) (pos⇒nonZero b)
instance
_ = n2m
t : ℚ
t = 1/ (2ℚ * m)
l1 : t ≡ ε (suc (2 ℕ* k))
l1 = reciprocal-cong (2ℚ * m) b e2m
h : t + t ≡ 1/ m
h = halve m
in begin
ε (suc (2 ℕ* k)) + ε (suc (2 ℕ* k))
≡⟨ cong (λ r → r + r) (sym l1) ⟩
t + t
≡⟨ h ⟩
1/ m
∎
≈-refl : ∀ {x} → x ≈ x
≈-refl {x} k = μ x k , λ n n≥N →
let eq : f x n + (- f x n) ≡ 0ℚ
eq = +-inverseʳ (f x n)
d1 : (f x n + (- f x n)) < ε k
d1 = ≤-<-trans (≤-reflexive eq) (0<ε k)
in (d1 , d1)
≈-sym : ∀ {x y} → x ≈ y → y ≈ x
≈-sym {x} {y} x≈y k =
let N , witness = x≈y k
in N , λ n n≥N →
let (d1 , d2) = witness n n≥N
in (d2 , d1)
trans-one-dir : ∀ (a b c : ℚ) {k : ℕ}
→ (a + (- b)) < ε (suc (2 ℕ* k))
→ (b + (- c)) < ε (suc (2 ℕ* k))
→ (a + (- c)) < ε k
trans-one-dir a b c {k} d1 d2 =
let half = 2 ℕ* k
c' = ε (suc half)
cc : c' + c' ≡ ε k
cc = ε-half k
bound : (a + (- b)) + (b + (- c)) < c' + c'
bound = +-mono-< d1 d2
bound' : (a + (- b)) + (b + (- c)) < ε k
bound' = subst (λ r → (a + (- b)) + (b + (- c)) < r) cc bound
sum : (a + (- b)) + (b + (- c)) ≡ a + (- c)
sum = telescope a b c
in subst (λ r → r < ε k) sum bound'
≈-trans : ∀ {x y z} → x ≈ y → y ≈ z → x ≈ z
≈-trans {x} {y} {z} x≈y y≈z k =
let half = 2 ℕ* k
N1 , w1 = x≈y (suc half)
N2 , w2 = y≈z (suc half)
N = N1 ⊔ N2
in N , λ n n≥N →
let n≥N1 = ≤-trans (m≤m⊔n N1 N2) n≥N
n≥N2 = ≤-trans (m≤n⊔m N1 N2) n≥N
(d11 , d12) = w1 n n≥N1
(d21 , d22) = w2 n n≥N2
in trans-one-dir (f x n) (f y n) (f z n) d11 d21
, trans-one-dir (f z n) (f y n) (f x n) d22 d12
≈-isEquivalence : IsEquivalence {A = CauchySeq} _≈_
≈-isEquivalence = record
{ refl = λ {x} → ≈-refl {x}
; sym = λ {x y} → ≈-sym {x} {y}
; trans = λ {x y z} → ≈-trans {x} {y} {z}
}
const : ℚ → CauchySeq
const q = record
{ f = λ n → q
; μ = λ k → 0
; cauchy = λ k _ _ _ _ →
let eq0 : ∣ q - q ∣ ≡ 0ℚ
eq0 = begin
∣ q - q ∣
≡⟨ cong ∣_∣ (+-inverseʳ q) ⟩
∣ 0ℚ ∣
≡⟨ 0≤p⇒∣p∣≡p {0ℚ} (≤-refl {0ℚ}) ⟩
0ℚ
∎
in subst (λ z → z < ε k) (sym eq0) (0<ε k)
}
num-add : ∀ m n → (+ m ℤ* + 1 ℤ+ + n ℤ* + 1) ≡ + (m +ℕ n)
num-add m n = begin
(+ m ℤ* + 1 ℤ+ + n ℤ* + 1)
≡⟨ cong₂ _ℤ+_ (ℤ*-identityʳ (+ m)) (ℤ*-identityʳ (+ n)) ⟩
(+ m ℤ+ + n)
≡⟨ pos-+ m n ⟩
+ (m +ℕ n)
∎
embed-+-hom : ∀ m n → embed (m +ℕ n) ≡ embed m + embed n
embed-+-hom m n = begin
embed (m +ℕ n)
≡⟨ sym (normalize-coprime (coprime-sym (1-coprimeTo (m +ℕ n)))) ⟩
(+ (m +ℕ n) / 1)
≡⟨ sym (/-cong (num-add m n) refl) ⟩
((+ m ℤ* + 1 ℤ+ + n ℤ* + 1) / (1 ℕ* 1))
≡⟨⟩
embed m + embed n
∎
embed-*-hom : ∀ m n → embed (m ℕ* n) ≡ embed m * embed n
embed-*-hom m n = begin
embed (m ℕ* n)
≡⟨ sym (normalize-coprime (coprime-sym (1-coprimeTo (m ℕ* n)))) ⟩
(+ (m ℕ* n)) / 1
≡⟨ cong (λ x → x / 1) (pos-* m n) ⟩
(+ m ℤ* + n) / 1
≡⟨⟩
embed m * embed n
∎
embed-* : ∀ m n → embed m * embed n ≡ embed (m ℕ* n)
embed-* m n = sym (embed-*-hom m n)
0<embed : ∀ n → 0ℚ < embed (suc n)
0<embed n = positive⁻¹ (embed (suc n)) {{embed-suc-pos {n}}}
0≤embed : ∀ n → 0ℚ ≤ embed n
0≤embed zero = ≤-refl
0≤embed (suc n) = <⇒≤ (0<embed n)
embed-pos→≥1 : ∀ m → 0ℚ < embed m → m ≥ 1
embed-pos→≥1 zero pr = ⊥-elim (<-irrefl refl pr)
embed-pos→≥1 (suc m) _ = s≤s z≤n
embed-mono-< : ∀ {m n} → m <ℕ n → embed m < embed n
embed-mono-< {m} {n} h =
*<* (ℤ<-≤-trans
(ℤ≤-<-trans
(ℤ≤-reflexive
(ℤ*-identityʳ (+ m)))
(+<+ h))
(ℤ≤-reflexive
(sym (ℤ*-identityʳ (+ n)))))
embed-mono-≤ : ∀ {m n} → m ≤ℕ n → embed m ≤ embed n
embed-mono-≤ {m} {n} h =
*≤* (ℤ≤-trans
(ℤ≤-reflexive
(ℤ*-identityʳ (+ m)))
(ℤ≤-trans
(+≤+ h)
(ℤ≤-reflexive
(sym (ℤ*-identityʳ (+ n))))))