{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Base.RationalRing where
open import Algebra.Properties.Group using (⁻¹-involutive)
open import Algebra.Properties.CommutativeMonoid using (medial)
open import Algebra.Properties.Ring using ([-x][-y]≈xy; [y-z]x≈yx-zx; x[y-z]≈xy-xz)
open import Data.Rational using (ℚ; 0ℚ; 1ℚ; _+_; _*_; _-_; -_; _<_; _≤_)
open import Data.Rational.Properties using
(+-assoc; +-comm; +-identityˡ; +-identityʳ; +-inverseˡ; *-assoc; *-comm
; *-identityˡ; *-zeroˡ; *-distribˡ-+; *-distribʳ-+; neg-distrib-+; positive⁻¹
; neg-distribʳ-*; <⇒≤; +-0-group; +-*-ring; +-0-commutativeMonoid
; *-1-commutativeMonoid; +-monoˡ-<; +-monoˡ-≤; neg-antimono-<; +-inverseʳ
; +-monoʳ-<; <-trans)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; sym; trans; cong; cong₂; subst; module ≡-Reasoning)
open ≡-Reasoning
0<1 : 0ℚ < 1ℚ
0<1 = positive⁻¹ 1ℚ
0≤1 : 0ℚ ≤ 1ℚ
0≤1 = <⇒≤ 0<1
+interchange : ∀ a b c d → (a + b) + (c + d) ≡ (a + c) + (b + d)
+interchange = medial +-0-commutativeMonoid
swap-mid : ∀ a b c d → (a * b) * (c * d) ≡ (a * c) * (b * d)
swap-mid = medial *-1-commutativeMonoid
neg-involutive : ∀ x → - (- x) ≡ x
neg-involutive = ⁻¹-involutive +-0-group
neg-0 : - 0ℚ ≡ 0ℚ
neg-0 = refl
neg-neg-mul : ∀ x y → (- x) * (- y) ≡ x * y
neg-neg-mul = [-x][-y]≈xy +-*-ring
flat4 : ∀ p q r s → ((p + q) + r) + s ≡ p + (q + (r + s))
flat4 p q r s = begin
((p + q) + r) + s
≡⟨ +-assoc (p + q) r s ⟩
(p + q) + (r + s)
≡⟨ +-assoc p q (r + s) ⟩
p + (q + (r + s)) ∎
cancel-pair : ∀ t → (- t + - t) + (t + t) ≡ 0ℚ
cancel-pair t = begin
(- t + - t) + (t + t)
≡⟨ cong (_+ (t + t)) (sym (neg-distrib-+ t t)) ⟩
(- (t + t)) + (t + t)
≡⟨ +-inverseˡ (t + t) ⟩
0ℚ ∎
telescope : ∀ a b c → (a + (- b)) + (b + (- c)) ≡ a + (- c)
telescope a b c = begin
(a + (- b)) + (b + (- c))
≡⟨ +-assoc a (- b) (b + (- c)) ⟩
a + ((- b) + (b + (- c)))
≡⟨ cong (a +_) (sym (+-assoc (- b) b (- c))) ⟩
a + (((- b) + b) + (- c))
≡⟨ cong (a +_) (cong (_+ (- c)) (+-inverseˡ b)) ⟩
a + (0ℚ + (- c))
≡⟨ cong (a +_) (+-identityˡ (- c)) ⟩
a + (- c) ∎
sq+ : ∀ x y → (x + y) * (x + y) ≡
x * x + (y * y + (x * y + x * y))
sq+ x y = begin
(x + y) * (x + y)
≡⟨ *-distribʳ-+ (x + y) x y ⟩
x * (x + y) + y * (x + y)
≡⟨ cong₂ _+_ (*-distribˡ-+ x x y) (*-distribˡ-+ y x y) ⟩
(x * x + x * y) + (y * x + y * y)
≡⟨ cong (λ t → (x * x + x * y) + (t + y * y)) (*-comm y x) ⟩
(x * x + x * y) + (x * y + y * y)
≡⟨ +-assoc (x * x) (x * y) (x * y + y * y) ⟩
x * x + (x * y + (x * y + y * y))
≡⟨ cong (x * x +_) (sym (+-assoc (x * y) (x * y) (y * y))) ⟩
x * x + ((x * y + x * y) + y * y)
≡⟨ cong (x * x +_) (+-comm (x * y + x * y) (y * y)) ⟩
x * x + (y * y + (x * y + x * y)) ∎
sq- : ∀ x y → (x - y) * (x - y) ≡
x * x + (y * y + (- (x * y) + - (x * y)))
sq- x y = begin
(x - y) * (x - y)
≡⟨ refl ⟩
(x + (- y)) * (x + (- y))
≡⟨ sq+ x (- y) ⟩
x * x + ((- y) * (- y) + (x * (- y) + x * (- y)))
≡⟨ cong (x * x +_)
(cong₂ (λ u v → u + (v + v))
(neg-neg-mul y y)
(sym (neg-distribʳ-* x y))) ⟩
x * x + (y * y + (- (x * y) + - (x * y))) ∎
cross-eq : ∀ a b c d → (a * c) * (b * d) ≡ (a * d) * (b * c)
cross-eq a b c d = begin
(a * c) * (b * d)
≡⟨ swap-mid a c b d ⟩
(a * b) * (c * d)
≡⟨ cong ((a * b) *_) (*-comm c d) ⟩
(a * b) * (d * c)
≡⟨ sym (swap-mid a d b c) ⟩
(a * d) * (b * c) ∎
flip3 : ∀ s x y → (s * x) * y ≡ (s * y) * x
flip3 s x y = begin
(s * x) * y
≡⟨ *-assoc s x y ⟩
s * (x * y)
≡⟨ cong (s *_) (*-comm x y) ⟩
s * (y * x)
≡⟨ sym (*-assoc s y x) ⟩
(s * y) * x ∎
*ʳ-sub : ∀ x y z → (x - y) * z ≡ x * z - y * z
*ʳ-sub x y z = [y-z]x≈yx-zx +-*-ring z x y
*ˡ-sub : ∀ x y z → x * (y - z) ≡ x * y - x * z
*ˡ-sub = x[y-z]≈xy-xz +-*-ring
sub-+-assoc : ∀ X Y Z → X - (Y + Z) ≡ (X - Y) - Z
sub-+-assoc X Y Z = begin
X - (Y + Z)
≡⟨ cong (X +_) (neg-distrib-+ Y Z) ⟩
X + (- Y + - Z)
≡⟨ sym (+-assoc X (- Y) (- Z)) ⟩
(X - Y) - Z ∎
pairs4 : ∀ x₁ x₂ x₃ x₄ y₁ y₂ y₃ y₄ →
(((x₁ + y₁) + (x₂ + y₂)) + ((x₃ + y₃) + (x₄ + y₄)))
≡ ((((x₁ + x₂) + x₃) + x₄) + (((y₁ + y₂) + y₃) + y₄))
pairs4 x₁ x₂ x₃ x₄ y₁ y₂ y₃ y₄ = begin
(((x₁ + y₁) + (x₂ + y₂)) + ((x₃ + y₃) + (x₄ + y₄)))
≡⟨ cong₂ _+_ (+interchange x₁ y₁ x₂ y₂)
(+interchange x₃ y₃ x₄ y₄) ⟩
(((x₁ + x₂) + (y₁ + y₂)) + ((x₃ + x₄) + (y₃ + y₄)))
≡⟨ +interchange (x₁ + x₂) (y₁ + y₂) (x₃ + x₄) (y₃ + y₄) ⟩
(((x₁ + x₂) + (x₃ + x₄)) + ((y₁ + y₂) + (y₃ + y₄)))
≡⟨ cong₂ _+_ (sym (+-assoc (x₁ + x₂) x₃ x₄))
(sym (+-assoc (y₁ + y₂) y₃ y₄)) ⟩
((((x₁ + x₂) + x₃) + x₄) + (((y₁ + y₂) + y₃) + y₄)) ∎
rot4 : ∀ X Y U V → ((X + Y) + U) + V ≡ ((U + V) + X) + Y
rot4 X Y U V = begin
((X + Y) + U) + V
≡⟨ +-assoc (X + Y) U V ⟩
(X + Y) + (U + V)
≡⟨ +-comm (X + Y) (U + V) ⟩
(U + V) + (X + Y)
≡⟨ sym (+-assoc (U + V) X Y) ⟩
((U + V) + X) + Y ∎
rev4 : ∀ X Y U V → ((X + Y) + U) + V ≡ ((V + U) + Y) + X
rev4 X Y U V = begin
((X + Y) + U) + V
≡⟨ +-assoc (X + Y) U V ⟩
(X + Y) + (U + V)
≡⟨ +-comm (X + Y) (U + V) ⟩
(U + V) + (X + Y)
≡⟨ cong₂ _+_ (+-comm U V) (+-comm X Y) ⟩
(V + U) + (Y + X)
≡⟨ sym (+-assoc (V + U) Y X) ⟩
((V + U) + Y) + X ∎
neg4 : ∀ a b c d →
- (((a + b) + - c) + - d) ≡ ((- a + - b) + c) + d
neg4 a b c d = begin
- (((a + b) + - c) + - d)
≡⟨ neg-distrib-+ ((a + b) + - c) (- d) ⟩
- ((a + b) + - c) + - (- d)
≡⟨ cong₂ _+_ (inner a b c) (neg-involutive d) ⟩
((- a + - b) + c) + d ∎
where
inner : ∀ a b c → - ((a + b) + - c) ≡ (- a + - b) + c
inner a b c = begin
- ((a + b) + - c)
≡⟨ neg-distrib-+ (a + b) (- c) ⟩
- (a + b) + - (- c)
≡⟨ cong (λ t → - (a + b) + t) (neg-involutive c) ⟩
- (a + b) + c
≡⟨ cong (λ t → t + c) (neg-distrib-+ a b) ⟩
(- a + - b) + c ∎
foldNeg : ∀ x y → - (x + - y) ≡ - x + y
foldNeg x y = begin
- (x + - y)
≡⟨ neg-distrib-+ x (- y) ⟩
- x + - (- y)
≡⟨ cong (- x +_) (neg-involutive y) ⟩
- x + y ∎
swap-scalar : ∀ {r} s x → (s * (r * x)) ≡ r * (s * x)
swap-scalar {r} s x = begin
s * (r * x)
≡⟨ sym (*-assoc s r x) ⟩
(s * r) * x
≡⟨ cong (λ z → z * x) (*-comm s r) ⟩
(r * s) * x
≡⟨ *-assoc r s x ⟩
r * (s * x) ∎
frontS : ∀ {r} s z x → (s * (r * x)) * z ≡ r * ((s * x) * z)
frontS {r} s z x = begin
(s * (r * x)) * z
≡⟨ cong (λ t → t * z) (swap-scalar {r} s x) ⟩
(r * (s * x)) * z
≡⟨ *-assoc r (s * x) z ⟩
r * ((s * x) * z) ∎
front-negS : ∀ {r} s z x →
- ((s * (r * x)) * z) ≡ r * (- ((s * x) * z))
front-negS {r} s z x = begin
- ((s * (r * x)) * z)
≡⟨ cong -_ (frontS {r} s z x) ⟩
- (r * ((s * x) * z))
≡⟨ neg-distribʳ-* r ((s * x) * z) ⟩
r * (- ((s * x) * z)) ∎
factor4 : ∀ {r} x y z w →
(((r * x + r * y) + r * (- z)) + r * (- w))
≡ r * (((x + y) + - z) + - w)
factor4 {r} x y z w = begin
(((r * x + r * y) + r * (- z)) + r * (- w))
≡⟨ cong (λ t → (t + r * (- z)) + r * (- w))
(sym (*-distribˡ-+ r x y)) ⟩
((r * (x + y) + r * (- z)) + r * (- w))
≡⟨ cong (λ t → t + r * (- w))
(sym (*-distribˡ-+ r (x + y) (- z))) ⟩
r * ((x + y) + - z) + r * (- w)
≡⟨ sym (*-distribˡ-+ r ((x + y) + - z) (- w)) ⟩
r * (((x + y) + - z) + - w) ∎
norm1 : ∀ k → 1ℚ * k + - (0ℚ * k) ≡ k
norm1 k = begin
1ℚ * k + - (0ℚ * k)
≡⟨ cong (λ x → 1ℚ * k + - x) (*-zeroˡ k) ⟩
1ℚ * k + - 0ℚ
≡⟨ cong (λ x → x + - 0ℚ) (*-identityˡ k) ⟩
k + - 0ℚ
≡⟨ +-identityʳ k ⟩
k ∎
norm-tail : ∀ k → 0ℚ + (0ℚ + (0ℚ + k)) ≡ k
norm-tail k = begin
0ℚ + (0ℚ + (0ℚ + k))
≡⟨ +-identityˡ (0ℚ + (0ℚ + k)) ⟩
0ℚ + (0ℚ + k)
≡⟨ +-identityˡ (0ℚ + k) ⟩
0ℚ + k
≡⟨ +-identityˡ k ⟩
k ∎
cancel-add : (x y : ℚ) → (x + y) + -_ y ≡ x
cancel-add x y =
trans (+-assoc x y (-_ y))
(trans (cong (x +_) (+-inverseʳ y)) (+-identityʳ x))
sub-cancel-common : (a x y : ℚ) → (a + x) - (a + y) ≡ x - y
sub-cancel-common a x y =
begin
(a + x) - (a + y)
≡⟨ cong (λ z → (a + x) + z) (neg-distrib-+ a y) ⟩
(a + x) + (-_ a + -_ y)
≡⟨ sym (+-assoc (a + x) (-_ a) (-_ y)) ⟩
((a + x) + -_ a) + -_ y
≡⟨ cong (λ z → z + -_ y) red ⟩
x + -_ y
∎
where
red : (a + x) + -_ a ≡ x
red =
begin
(a + x) + -_ a
≡⟨ +-assoc a x (-_ a) ⟩
a + (x + -_ a)
≡⟨ cong (λ z → a + z) (+-comm x (-_ a)) ⟩
a + (-_ a + x)
≡⟨ sym (+-assoc a (-_ a) x) ⟩
(a + -_ a) + x
≡⟨ cong (λ z → z + x) (+-inverseʳ a) ⟩
0ℚ + x
≡⟨ +-identityˡ x ⟩
x
∎
sub-add-split : (a b c d : ℚ) → (a + c) - (b + d) ≡ (a - b) + (c - d)
sub-add-split a b c d =
begin
(a + c) - (b + d)
≡⟨ cong (λ z → (a + c) + z) (neg-distrib-+ b d) ⟩
(a + c) + (-_ b + -_ d)
≡⟨ sym (+-assoc (a + c) (-_ b) (-_ d)) ⟩
((a + c) + -_ b) + -_ d
≡⟨ cong (λ z → z + -_ d) mid ⟩
((a - b) + c) + -_ d
≡⟨ +-assoc (a - b) c (-_ d) ⟩
(a - b) + (c + -_ d)
∎
where
mid : (a + c) + -_ b ≡ (a - b) + c
mid =
begin
(a + c) + -_ b
≡⟨ cong (λ z → z + -_ b) (+-comm a c) ⟩
(c + a) + -_ b
≡⟨ +-assoc c a (-_ b) ⟩
c + (a + -_ b)
≡⟨ +-comm c (a + -_ b) ⟩
(a - b) + c
∎
sub-shift-cancel : (x e : ℚ) → (x - e) + e ≡ x
sub-shift-cancel x e =
begin
(x - e) + e
≡⟨ +-assoc x (-_ e) e ⟩
x + (-_ e + e)
≡⟨ cong (λ z → x + z) (+-comm (-_ e) e) ⟩
x + (e + -_ e)
≡⟨ cong (λ z → x + z) (+-inverseʳ e) ⟩
x + 0ℚ
≡⟨ +-identityʳ x ⟩
x
∎
lt-sub : (x y e : ℚ) → x < y + e → x - e < y
lt-sub x y e h =
subst (λ z → x + -_ e < z) (cancel-add y e) (+-monoˡ-< (-_ e) h)
lt-add : (x y e : ℚ) → x - e < y → x < y + e
lt-add x y e h =
subst (λ z → z < y + e) (sub-shift-cancel x e) (+-monoˡ-< e h)
lt-shift : (x y e : ℚ) → x + e < y → x < y - e
lt-shift x y e h =
subst (λ z → z < y + -_ e) (cancel-add x e) (+-monoˡ-< (-_ e) h)
sub-sum-swap : (b c : ℚ) → (b + c) + -_ b ≡ c
sub-sum-swap b c =
begin
(b + c) + -_ b
≡⟨ cong (λ z → z + -_ b) (+-comm b c) ⟩
(c + b) + -_ b
≡⟨ +-assoc c b (-_ b) ⟩
c + (b + -_ b)
≡⟨ cong (c +_) (+-inverseʳ b) ⟩
c + 0ℚ
≡⟨ +-identityʳ c ⟩
c
∎
le-sub-shift : (a b c : ℚ) → b + c ≤ a → c ≤ a - b
le-sub-shift a b c h =
subst (λ z → z ≤ a + -_ b) (sub-sum-swap b c) (+-monoˡ-≤ (-_ b) h)
sub-lt : (a b c d : ℚ) → a < b → c < d → a - d < b - c
sub-lt a b c d h k =
let s1 : a + -_ d < b + -_ d
s1 = +-monoˡ-< (-_ d) h
nd< : -_ d < -_ c
nd< = neg-antimono-< k
s2 : b + -_ d < b + -_ c
s2 = +-monoʳ-< b nd<
in <-trans s1 s2
sub-sub : (a b c d : ℚ) → (a - c) - (b + d) ≡ (a - b) - (c + d)
sub-sub a b c d =
trans (cong (λ z → (a - c) + z) (neg-distrib-+ b d))
(trans (+interchange a (-_ c) (-_ b) (-_ d))
(cong (λ z → (a - b) + z) (sym (neg-distrib-+ c d))))
rotate-sum : (a x y z : ℚ) → ((a + x) + y) + z ≡ (a + z) + (x + y)
rotate-sum a x y z =
let axz : (a + x) + z ≡ (a + z) + x
axz = trans (+-assoc a x z)
(trans (cong (a +_) (+-comm x z)) (sym (+-assoc a z x)))
s1 : ((a + x) + y) + z ≡ (a + x) + (y + z)
s1 = +-assoc (a + x) y z
s2 : (a + x) + (y + z) ≡ (a + x) + (z + y)
s2 = cong ((a + x) +_) (+-comm y z)
s3 : (a + x) + (z + y) ≡ ((a + x) + z) + y
s3 = sym (+-assoc (a + x) z y)
s4 : ((a + x) + z) + y ≡ ((a + z) + x) + y
s4 = cong (_+ y) axz
s5 : ((a + z) + x) + y ≡ (a + z) + (x + y)
s5 = +-assoc (a + z) x y
in trans s1 (trans s2 (trans s3 (trans s4 s5)))
neg-sub : (p q : ℚ) → -_ (p - q) ≡ q - p
neg-sub p q =
trans (neg-distrib-+ p (-_ q))
(trans (cong (-_ p +_) (neg-involutive q)) (+-comm (-_ p) q))