{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Archimedean where
open import Data.Empty using (⊥-elim)
open import Data.Integer using (+_; -[1+_]) renaming (+<+ to ℤ+<+)
open import Data.Integer.Properties using (<-irrefl; *-identityˡ)
open import Data.Nat using (ℕ; suc; _*_; _+_; s≤s)
open import Data.Nat.Properties as Nat using (≤-refl; m≤m+n)
open import Data.Product using (Σ; _,_)
open import Data.Rational using (ℚ; 0ℚ; _<_; *<*)
open import Data.Rational.Base using (↥_; ↧_; ↧ₙ_)
open import Relation.Binary.PropositionalEquality using
(_≡_; sym; cong; refl; subst; subst₂; inspect; [_])
open import Relation.Nullary.Negation using (¬_)
open import Real using (ε)
den-eq : ∀ k → ↧ (ε k) ≡ + (suc k)
den-eq k = refl
cross : ∀ d n → d Data.Nat.< (suc n) * (suc d)
cross d n =
let base : d Data.Nat.< suc d
base = s≤s ≤-refl
mult : suc d Data.Nat.≤ (suc n) * (suc d)
mult = m≤m+n (suc d) (n * suc d)
in Nat.<-≤-trans base mult
num-of : ℚ → Data.Integer.ℤ
num-of x = ↥ x
no-zero : ¬_ (+ 0 Data.Integer.< + 0 Data.Integer.* + 1)
no-zero = <-irrefl refl
no-neg : ∀ n → ¬_ (+ 0 Data.Integer.< (-[1+ n ]) Data.Integer.* + 1)
no-neg n ()
build : (e : ℚ) → 0ℚ < e → ε (↧ₙ e) < e
build e (*<* w) with num-of e | inspect num-of e
build e (*<* w) | + (suc n) | [ num-eq ] =
let num = num-of e
den = ↧ₙ e
sd = + (suc den)
all< = ℤ+<+ (cross den n)
all<′ = subst (λ x → + den Data.Integer.< x Data.Integer.* sd)
(sym num-eq) all<
lhs-eq = sym (*-identityˡ (↧ e))
rhs-eq = cong (num Data.Integer.*_) (sym (den-eq den))
aligned = subst₂ (λ a b → a Data.Integer.< b)
lhs-eq rhs-eq all<′
in *<* aligned
build e (*<* w) | + 0 | _ = ⊥-elim (no-zero w)
build e (*<* w) | -[1+ n ] | _ = ⊥-elim (no-neg n w)
ε-archimedean : (e : ℚ) → 0ℚ < e → Σ ℕ (λ k → ε k < e)
ε-archimedean e pos = ↧ₙ e , build e pos