------------------------------------------------------------------------
-- Constructive Cauchy reals
--
-- 构造性柯西实数
------------------------------------------------------------------------

{-# 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)

------------------------------------------------------------------------
-- Precision level
--
-- ε k = 1 / (k + 1). The k-th Cauchy level demands approximation
-- within 1/(k+1).
--
-- Embedding ℕ → ℚ as the normalised fraction n/1, built directly
-- with the raw constructor so the reciprocal 1/(suc n) reduces
-- definitionally (no gcd decision term).
--
-- 精度层
--
-- 第 k 层柯西条件要求逼近到 1/(k+1) 以内。
--
-- 将 ℕ 嵌入 ℚ 为规范化分数 n/1,直接用底层构造器构造,
-- 使倒数 1/(suc n) 可定义性归约(无 gcd 判定项)。

embed : ℕ → ℚ
embed n = mkℚ (+ n) 0 (coprime-sym (1-coprimeTo n))

-- The k-th Cauchy precision.
--
-- 第 k 层柯西精度。
ε : ℕ → ℚ
ε k = 1/ embed (suc k)

-- The embedding of a successor is positive, hence nonzero.
--
-- 后继的嵌入为正,故非零。
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}}}

-- The rational 2, built directly via the raw constructor so that
-- 2ℚ * embed n reduces via the fraction congruence (no sign
-- wrapper). It equals 1 + 1.
--
-- 有理数 2,直接用底层构造器构造,使乘法经分数同余归约;
-- 它等于 1 + 1。
2ℚ : ℚ
2ℚ = embed 2

2ℚ≡1+1 : 2ℚ ≡ 1ℚ + 1ℚ
2ℚ≡1+1 = sym (normalize-coprime (coprime-sym (1-coprimeTo 2)))

-- Numerator arithmetic for doubling.
--
-- 分子层面的加倍算术。
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)
  ∎

-- The denominator at the half index is twice the denominator at the
-- current index.
--
-- 半索引处的分母是当前索引处分母的两倍。
den-2 : ∀ k → suc (suc (2 ℕ* k)) ≡ 2 ℕ* suc k
den-2 k = sym (*-suc 2 k)

------------------------------------------------------------------------
-- Half and its NonZero instance
--
-- 二分之一及其非零实例

embed2-nonZero : NonZero (embed 2)
embed2-nonZero = embed-suc-nonZero {1}

half : ℚ
half = 1/_ (embed 2) {{embed2-nonZero}}

------------------------------------------------------------------------
-- Cauchy sequence record
--
-- A Cauchy sequence carries its own convergence modulus μ: for every
-- precision k, all terms from position μ k onward agree within ε k.
--
-- 柯西序列记录
--
-- 柯西序列携带自己的收敛模数 μ:对每个精度 k,从位置 μ k 起的所有项
-- 在 ε k 以内一致。

record CauchySeq : Set₁ where
  field
    f : ℕ → ℚ
    μ : ℕ → ℕ
    cauchy : ∀ k n m → n ≥ μ k → m ≥ μ k → ∣ f n - f m ∣ < ε k

open CauchySeq

------------------------------------------------------------------------
-- Symmetric close relation
--
-- q1 ≈[k] q2 iff both directions are within ε k:
--   (q1 - q2) < ε k  AND  (q2 - q1) < ε k
-- This is symmetric by construction — no absolute value, no subst.
--
-- 对称接近关系
--
-- 当且仅当两个方向都在 ε k 以内时,称两点在第 k 层对称接近。
-- 这按构造就是对称的——无绝对值、无 subst。

_s≈_ : ℚ → ℚ → ℕ → Set
_s≈_ q1 q2 k = (q1 + (- q2)) < ε k × (q2 + (- q1)) < ε k

------------------------------------------------------------------------
-- Setoid equivalence
--
-- x ≈ y iff for every k, eventually x n and y n are symmetrically
-- close within ε k.
--
-- setoid 等价
--
-- x 与 y 等价当且仅当对每个 k,最终 x n 与 y n 在 ε k 内对称接近。

_≈_ : Rel CauchySeq lzero
_≈_ x y = ∀ k → Σ ℕ (λ N → ∀ n → n ≥ N → _s≈_ (f x n) (f y n) k)

------------------------------------------------------------------------
-- Positivity of the k-th precision
--
-- 第 k 层精度的正性

0<ε : ∀ k → 0ℚ < ε k
0<ε k =
  positive⁻¹ (ε k)
    {{1/pos⇒pos (embed (suc k)) {{embed-suc-pos {k}}}}}

------------------------------------------------------------------------
-- Halving lemma
--
-- Two copies of the half-denominator reciprocal add to the
-- full-denominator reciprocal. Pure field algebra over ℚ.
--
-- 折半引理
--
-- 两份半精度容差相加即全精度容差;纯 ℚ 域代数。

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 respects propositional equality.
--
-- 倒数保持命题相等。
reciprocal-cong : ∀ a b → .{{na : NonZero a}} → .{{nb : NonZero b}} →
                  a ≡ b → 1/_ a ≡ 1/_ b
reciprocal-cong a .a refl = refl

------------------------------------------------------------------------
-- ε halving
--
-- Two successor-level precisions at the halved index add to the
-- current level's precision.
--
-- ε 折半
--
-- 在半索引处的两份后继精度相加,回到当前精度。

ε-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
    ∎

------------------------------------------------------------------------
-- Reflexivity
--
-- Take N = μ x k. For n ≥ μ x k, the Cauchy condition implies both
-- directions of the symmetric close relation.
--
-- 自反性
--
-- 取 N = μ x k。n ≥ μ x k 时,由柯西条件即得对称接近的两个方向。

≈-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)

------------------------------------------------------------------------
-- Symmetry
--
-- Swap the two components of the symmetric close relation.
-- No subst, no absolute-value lemma.
--
-- 对称性
--
-- 交换对称接近关系的两个分量。无 subst、无绝对值引理。

≈-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)

------------------------------------------------------------------------
-- One-direction triangle step
--
-- 单向三角步

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'

------------------------------------------------------------------------
-- Transitivity
--
-- 传递性

≈-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

------------------------------------------------------------------------
-- Setoid instance
--
-- setoid 实例

≈-isEquivalence : IsEquivalence {A = CauchySeq} _≈_
≈-isEquivalence = record
  { refl  = λ {x} → ≈-refl {x}
  ; sym   = λ {x y} → ≈-sym {x} {y}
  ; trans = λ {x y z} → ≈-trans {x} {y} {z}
  }

------------------------------------------------------------------------
-- ℚ embedding
--
-- Embed a rational as the constant Cauchy sequence, with modulus
-- everywhere zero (all terms are identical).
--
-- ℚ 嵌入
--
-- 将有理数嵌入为常柯西序列,模数处处为零(所有项相同)。

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)
  }

------------------------------------------------------------------------
-- Arithmetic homomorphism of embed
--
-- embed 的算术同态

-- Numerator addition: the sum of two positive numerators corresponds
-- to the natural-number sum.
--
-- 分子加法:分子层面的加法同态。
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)
  ∎

-- The embedding preserves addition.
--
-- 嵌入保持加法。
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
  ∎

-- The embedding preserves multiplication.
--
-- 嵌入保持乘法。
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)

------------------------------------------------------------------------
-- Positivity and monotonicity of embed
--
-- embed 的正性与单调性

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)

-- A natural number whose embedding is positive is at least one.
--
-- 嵌入为正的自然数至少为 1。
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

-- Monotonicity of the embedding for strict and non-strict order.
--
-- 嵌入对严格序与非严格序单调。
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))))))