Skip to content

整数

module integer where

open import apartness-relation
open import bottom-type
open import commutative-monoid
open import commutative-monoid-equation CommutativeMonoidℕ
open import equivalence-relation
open import identity-type
open import natural-number
open import negation
open import relation
open import sigma-type
open import sum-type
open import vector
abstract
  ℤ : Set
  ℤ = ℕ × ℕ

open Equiv ⦃ ... ⦄

instance abstract
  Equivℤ : Equiv ℤ
  _≈_ ⦃ Equivℤ ⦄ m n = fst m +ℕ snd n = fst n +ℕ snd m
  refl-≈ ⦃ Equivℤ ⦄ x = refl
  sym-≈ ⦃ Equivℤ ⦄ e = sym e
  trans-≈ ⦃ Equivℤ ⦄ {x = x} {y = y} {z = z} e₁ e₂ = cancel-right-+ℕ (snd y)
    (
      (fst x +ℕ snd z) +ℕ snd y
          =⟨ swap-right-+ℕ (fst x) (snd z) (snd y) ⟩
      (fst x +ℕ snd y) +ℕ snd z
          =⟨ cong (_+ℕ snd z) e₁ ⟩
      (fst y +ℕ snd x) +ℕ snd z
          =⟨ swap-right-+ℕ (fst y) (snd x) (snd z) ⟩
      (fst y +ℕ snd z) +ℕ snd x
          =⟨ cong (_+ℕ snd x) e₂ ⟩
      (fst z +ℕ snd y) +ℕ snd x
          =⟨ swap-right-+ℕ (fst z) (snd y) (snd x) ⟩
      (fst z +ℕ snd x) +ℕ snd y
          ∎
    )
abstract
  ℕ→ℤ : ℕ → ℤ
  ℕ→ℤ n = (n , 0)

  pos : ℕ → ℤ
  pos n = (suc n , 0)

  neg : ℕ → ℤ
  neg n = (0 , suc n)

  negate : ℤ → ℤ
  negate (m , n) = (n , m)

  decideℤ-≈ : ∀ (x y : ℤ) → Decidable (x ≈ y)
  decideℤ-≈ x y = Discrete-ℕ (fst x +ℕ snd y) (fst y +ℕ snd x)
data canonicalℤ : Set where
  zero     : canonicalℤ
  positive : ℕ → canonicalℤ
  negative : ℕ → canonicalℤ

abstract
  from-canonicalℤ : canonicalℤ → ℤ
  from-canonicalℤ zero         = 0 , 0
  from-canonicalℤ (positive n) = pos n
  from-canonicalℤ (negative n) = neg n

  to-canonicalℤ : ℤ → canonicalℤ
  to-canonicalℤ (m , n) with trichotomy-ℕ m n
  ... | Eq _   = zero
  ... | Lt m<n = negative (subℕ m<n .fst)
  ... | Gt m>n = positive (subℕ m>n .fst)

  helper1 : ∀ m → to-canonicalℤ (from-canonicalℤ m) = m
  helper1 zero         = refl
  helper1 (positive _) = refl
  helper1 (negative _) = refl

  helper2 : ∀ m → from-canonicalℤ (to-canonicalℤ m) ≈ m
  helper2 (a , b) with trichotomy-ℕ a b
  ... | Lt x = sym (trans (+ℕ-suc a (subℕ x .fst)) (subℕ x .snd))
  ... | Eq e rewrite e = sym (right-unit-+ℕ b)
  ... | Gt x =
    trans
      (trans (comm-+ℕ _ b) (trans (+ℕ-suc _ _) (subℕ x .snd)))
      (sym (right-unit-+ℕ a))

  to-canonicalℤ-respect-≈′ :
    ∀ m n →
    from-canonicalℤ m ≈ from-canonicalℤ n →
    to-canonicalℤ (from-canonicalℤ m) = to-canonicalℤ (from-canonicalℤ n)
  to-canonicalℤ-respect-≈′ zero zero e = refl
  to-canonicalℤ-respect-≈′ (positive x) (positive y) e =
    cong positive (suc-injective e')
    where
      e' : suc x = suc y
      e' = trans (sym (right-unit-+ℕ (suc x))) (trans e (right-unit-+ℕ (suc y)))
  to-canonicalℤ-respect-≈′ (negative x) (negative y) e =
    cong negative (suc-injective e')
    where
      e' : suc x = suc y
      e' = sym e

to-canonicalℤ-respect-≈ :
  ∀ (m n : ℤ) →
  m ≈ n →
  to-canonicalℤ m = to-canonicalℤ n
to-canonicalℤ-respect-≈ m n e =
  to-canonicalℤ m
    =⟨ sym (helper1 (to-canonicalℤ m)) ⟩
  to-canonicalℤ (from-canonicalℤ (to-canonicalℤ m))
    =⟨ to-canonicalℤ-respect-≈′ (to-canonicalℤ m) (to-canonicalℤ n) e' ⟩
  to-canonicalℤ (from-canonicalℤ (to-canonicalℤ n))
    =⟨ helper1 (to-canonicalℤ n) ⟩
  to-canonicalℤ n
  ∎
  where
    e' : from-canonicalℤ (to-canonicalℤ m) ≈ from-canonicalℤ (to-canonicalℤ n)
    e' = trans-≈ {z = from-canonicalℤ (to-canonicalℤ n)}
          (helper2 m) (trans-≈ {x = m} e (sym-≈ {y = n} (helper2 n)))
infixl 60 _+ℤ_

abstract
  _+ℤ_ : ℤ → ℤ → ℤ
  m +ℤ n = (fst m +ℕ fst n , snd m +ℕ snd n)

  +ℤ-resp-≈ : ∀ m n p q → m ≈ p → n ≈ q → m +ℤ n ≈ p +ℤ q
  +ℤ-resp-≈ (x , x₁) (x₂ , x₃) (x₄ , x₅) (x₆ , x₇) m≈p n≈q =
    (x +ℕ x₂) +ℕ (x₅ +ℕ x₇)
        =⟨ swap-center-+ℕ x x₂ x₅ x₇ ⟩
    (x +ℕ x₅) +ℕ (x₂ +ℕ x₇)
        =⟨ cong₂ _+ℕ_ m≈p n≈q ⟩
    (x₄ +ℕ x₁) +ℕ (x₆ +ℕ x₃)
        =⟨ swap-center-+ℕ x₄ x₁ x₆ x₃ ⟩
    (x₄ +ℕ x₆) +ℕ (x₁ +ℕ x₃)
        ∎

整数の0を定義する:

abstract
  0ℤ : ℤ
  0ℤ = zero , zero

0ℤは+ℤの単位元となる:

abstract
  left-unit-+ℤ : ∀ n → 0ℤ +ℤ n ≈ n
  left-unit-+ℤ n = refl

  right-unit-+ℤ : ∀ n → n +ℤ 0ℤ ≈ n
  right-unit-+ℤ (a , b) =
    (a +ℕ zero) +ℕ b
        =⟨ assoc-+ℕ a _ _ ⟩
    a +ℕ (zero +ℕ b)
        =⟨ cong (a +ℕ_) (comm-+ℕ zero _) ⟩
    a +ℕ (b +ℕ zero)
        ∎
infix 60 _-ℤ_
_-ℤ_ : ℤ → ℤ → ℤ
x -ℤ y = x +ℤ negate y

TODO: +ℤ-resp-≈を使う:

abstract
  rinv-+ℤ : ∀ {x y}
    → x -ℤ y ≈ 0ℤ
    → x ≈ y
  rinv-+ℤ {x = x} {y} e =
    fst x +ℕ snd y
      =⟨ sym (right-unit-+ℕ (fst (x -ℤ y))) ⟩
    (fst x +ℕ snd y) +ℕ 0
      =⟨ e ⟩
    snd x +ℕ fst y
      =⟨ comm-+ℕ (snd x) (fst y) ⟩
    fst y +ℕ snd x
      ∎

  -- helper1 : ∀ {x}
  --   → x -ℤ x ≈ 0ℤ
  -- helper1 = ?

  helper : ∀ {x y}
    → x ≈ y
    → x -ℤ y ≈ 0ℤ
  helper {x = x} {y} e =
    fst (x -ℤ y) +ℕ snd 0ℤ
      =⟨ right-unit-+ℕ _ ⟩
    fst (x -ℤ y)
      =⟨ e ⟩
    fst y +ℕ snd x
      =⟨ comm-+ℕ (fst y) _ ⟩
    snd x +ℕ fst y
      =⟨ sym (left-unit-+ℕ _) ⟩
    fst 0ℤ +ℕ snd (x -ℤ y)
      ∎
infixl 70 _*ℤ_

abstract
  _*ℤ_ : ℤ → ℤ → ℤ
  m *ℤ n = (fst m *ℕ fst n +ℕ snd m *ℕ snd n)
         , (snd m *ℕ fst n +ℕ fst m *ℕ snd n)

  *ℤ-resp-≈ : ∀ m n p q → m ≈ p → n ≈ q → m *ℤ n ≈ p *ℤ q
  *ℤ-resp-≈ (m₁ , m₂) (n₁ , n₂) (p₁ , p₂) (q₁ , q₂) m≈p n≈q = cancel-right-+ℕ (p₂ *ℕ n₂ +ℕ p₁ *ℕ n₁) (cancel-left-+ℕ (p₂ *ℕ n₁ +ℕ p₁ *ℕ n₂) (
    (p₂ *ℕ n₁ +ℕ p₁ *ℕ n₂) +ℕ (((m₁ *ℕ n₁ +ℕ m₂ *ℕ n₂) +ℕ (p₂ *ℕ q₁ +ℕ p₁ *ℕ q₂)) +ℕ (p₂ *ℕ n₂ +ℕ p₁ *ℕ n₁))
        =⟨ cong (p₂ *ℕ n₁ +ℕ p₁ *ℕ n₂ +ℕ_) (assoc-+ℕ (m₁ *ℕ n₁ +ℕ m₂ *ℕ n₂) _ _) ⟩
    (p₂ *ℕ n₁ +ℕ p₁ *ℕ n₂) +ℕ ((m₁ *ℕ n₁ +ℕ m₂ *ℕ n₂) +ℕ ((p₂ *ℕ q₁ +ℕ p₁ *ℕ q₂) +ℕ (p₂ *ℕ n₂ +ℕ p₁ *ℕ n₁)))
        =⟨ cong (p₂ *ℕ n₁ +ℕ p₁ *ℕ n₂ +ℕ_) (cong (m₁ *ℕ n₁ +ℕ m₂ *ℕ n₂ +ℕ_) (swap-center-+ℕ (p₂ *ℕ q₁) _ _ _)) ⟩
    (p₂ *ℕ n₁ +ℕ p₁ *ℕ n₂) +ℕ ((m₁ *ℕ n₁ +ℕ m₂ *ℕ n₂) +ℕ ((p₂ *ℕ q₁ +ℕ p₂ *ℕ n₂) +ℕ (p₁ *ℕ q₂ +ℕ p₁ *ℕ n₁)))
        =⟨ cong (p₂ *ℕ n₁ +ℕ p₁ *ℕ n₂ +ℕ_) (cong (m₁ *ℕ n₁ +ℕ m₂ *ℕ n₂ +ℕ_) (sym (cong₂ _+ℕ_ (*ℕ-distrib-left-+ℕ p₂ q₁ n₂) (*ℕ-distrib-left-+ℕ p₁ q₂ n₁)))) ⟩
    (p₂ *ℕ n₁ +ℕ p₁ *ℕ n₂) +ℕ ((m₁ *ℕ n₁ +ℕ m₂ *ℕ n₂) +ℕ ((p₂ *ℕ (q₁ +ℕ n₂)) +ℕ (p₁ *ℕ (q₂ +ℕ n₁))))
        =⟨ cong (p₂ *ℕ n₁ +ℕ p₁ *ℕ n₂ +ℕ_) (cong (m₁ *ℕ n₁ +ℕ m₂ *ℕ n₂ +ℕ_) (sym (cong₂ _+ℕ_ (cong (p₂ *ℕ_) n≈q) (cong (p₁ *ℕ_) (sym n≈q ∙ (comm-+ℕ n₁ _)))))) ⟩
    (p₂ *ℕ n₁ +ℕ p₁ *ℕ n₂) +ℕ ((m₁ *ℕ n₁ +ℕ m₂ *ℕ n₂) +ℕ ((p₂ *ℕ (n₁ +ℕ q₂)) +ℕ (p₁ *ℕ (q₁ +ℕ n₂))))
        =⟨ sym (assoc-+ℕ (p₂ *ℕ n₁ +ℕ p₁ *ℕ n₂) _ _) ⟩
    ((p₂ *ℕ n₁ +ℕ p₁ *ℕ n₂) +ℕ (m₁ *ℕ n₁ +ℕ m₂ *ℕ n₂)) +ℕ ((p₂ *ℕ (n₁ +ℕ q₂)) +ℕ (p₁ *ℕ (q₁ +ℕ n₂)))
        =⟨ cong (_+ℕ (p₂ *ℕ (n₁ +ℕ q₂) +ℕ p₁ *ℕ (q₁ +ℕ n₂))) (swap-center-+ℕ (p₂ *ℕ n₁) _ _ _) ⟩
    ((p₂ *ℕ n₁ +ℕ m₁ *ℕ n₁) +ℕ (p₁ *ℕ n₂ +ℕ m₂ *ℕ n₂)) +ℕ ((p₂ *ℕ (n₁ +ℕ q₂)) +ℕ (p₁ *ℕ (q₁ +ℕ n₂)))
        =⟨ cong (_+ℕ (p₂ *ℕ (n₁ +ℕ q₂) +ℕ p₁ *ℕ (q₁ +ℕ n₂))) (sym (cong₂ _+ℕ_ (*ℕ-distrib-right-+ℕ n₁ p₂ m₁) (*ℕ-distrib-right-+ℕ n₂ p₁ m₂))) ⟩
    (((p₂ +ℕ m₁) *ℕ n₁) +ℕ ((p₁ +ℕ m₂) *ℕ n₂)) +ℕ ((p₂ *ℕ (n₁ +ℕ q₂)) +ℕ (p₁ *ℕ (q₁ +ℕ n₂)))
        =⟨ cong (_+ℕ (p₂ *ℕ (n₁ +ℕ q₂) +ℕ p₁ *ℕ (q₁ +ℕ n₂))) (cong₂ _+ℕ_ (cong (_*ℕ n₁) (comm-+ℕ p₂ m₁ ∙ m≈p)) (cong (_*ℕ n₂) (sym m≈p))) ⟩
    (((p₁ +ℕ m₂) *ℕ n₁) +ℕ ((m₁ +ℕ p₂) *ℕ n₂)) +ℕ ((p₂ *ℕ (n₁ +ℕ q₂)) +ℕ (p₁ *ℕ (q₁ +ℕ n₂)))
        =⟨ cong (_+ℕ (p₂ *ℕ (n₁ +ℕ q₂) +ℕ p₁ *ℕ (q₁ +ℕ n₂))) (cong₂ _+ℕ_ (*ℕ-distrib-right-+ℕ n₁ p₁ m₂) (*ℕ-distrib-right-+ℕ n₂ m₁ p₂)) ⟩
    ((p₁ *ℕ n₁ +ℕ m₂ *ℕ n₁) +ℕ (m₁ *ℕ n₂ +ℕ p₂ *ℕ n₂)) +ℕ ((p₂ *ℕ (n₁ +ℕ q₂)) +ℕ (p₁ *ℕ (q₁ +ℕ n₂)))
        =⟨ cong (p₁ *ℕ n₁ +ℕ m₂ *ℕ n₁ +ℕ (m₁ *ℕ n₂ +ℕ p₂ *ℕ n₂) +ℕ_) (cong₂ _+ℕ_ (*ℕ-distrib-left-+ℕ p₂ n₁ q₂) (*ℕ-distrib-left-+ℕ p₁ q₁ n₂)) ⟩
    ((p₁ *ℕ n₁ +ℕ m₂ *ℕ n₁) +ℕ (m₁ *ℕ n₂ +ℕ p₂ *ℕ n₂)) +ℕ ((p₂ *ℕ n₁ +ℕ p₂ *ℕ q₂) +ℕ (p₁ *ℕ q₁ +ℕ p₁ *ℕ n₂))
        =⟨ eval-equality expr1 expr2 env refl ⟩
    (p₂ *ℕ n₁ +ℕ p₁ *ℕ n₂) +ℕ (((p₁ *ℕ q₁ +ℕ p₂ *ℕ q₂) +ℕ (m₂ *ℕ n₁ +ℕ m₁ *ℕ n₂)) +ℕ (p₂ *ℕ n₂ +ℕ p₁ *ℕ n₁))
        ∎))
    where
      env : Vec ℕ 8
      env =
        p₁ *ℕ n₁ ∷ m₂ *ℕ n₁ ∷ m₁ *ℕ n₂ ∷ p₂ *ℕ n₂ ∷
        p₂ *ℕ n₁ ∷ p₂ *ℕ q₂ ∷ p₁ *ℕ q₁ ∷ p₁ *ℕ n₂ ∷ []

      expr1 : Expr 8
      expr1 =
        ((varLit 0 □ varLit 1) □ (varLit 2 □ varLit 3)) □
        ((varLit 4 □ varLit 5) □ (varLit 6 □ varLit 7))

      expr2 : Expr 8
      expr2 =
        varLit 4 □ varLit 7 □ (
          (varLit 6 □ varLit 5) □
          (varLit 1 □ varLit 2) □
          (varLit 3 □ varLit 0)
        )
abstract
  no-zero-divisor-ℕ' : ∀ x y → x *ℤ y ≈ 0ℤ → ¬ (x ≈ 0ℤ) → y ≈ 0ℤ
  no-zero-divisor-ℕ' (a , b) (c , d) e f
    rewrite right-unit-+ℕ (fst ((a , b) *ℤ (c , d)))
    rewrite right-unit-+ℕ a
    rewrite right-unit-+ℕ c
    = ?

  no-zero-divisor-ℕ : ∀ x y → x *ℤ y ≈ 0ℤ → (x ≈ 0ℤ) + (y ≈ 0ℤ)
  no-zero-divisor-ℕ x y e with decideℤ-≈ x 0ℤ
  ... | inl e' = inl e'
  ... | inr f  = inr (no-zero-divisor-ℕ' x y e f)
*ℤ-distrib-left-+ℤ : ∀ x a b → x *ℤ (a +ℤ b) ≈ x *ℤ a +ℤ x *ℤ b
*ℤ-distrib-left-+ℤ x a b = ?

*ℤ-distrib-left--ℤ : ∀ x a b → x *ℤ (a -ℤ b) ≈ x *ℤ a -ℤ x *ℤ b
*ℤ-distrib-left--ℤ x a b = ?
cancel-left-*ℤ : ∀ x {a b : ℤ}
  → ¬ (x ≈ 0ℤ)
  → x *ℤ a ≈ x *ℤ b
  → a ≈ b
cancel-left-*ℤ x {a = a} {b = b} f e =
  let e1 = helper e
      e2 = *ℤ-distrib-left--ℤ x a b
      z = no-zero-divisor-ℕ' _ _ (trans-≈ e2 e1) f in
  rinv-+ℤ z

cancel-right-*ℤ : ∀ x {a b : ℤ}
  → ¬ (x ≈ 0ℤ)
  → a *ℤ x ≈ b *ℤ x
  → a ≈ b
cancel-right-*ℤ x f e = ?
ApartedSetℤ : ApartedSet
ApartedSetℤ = DiscreteSetoid→ApartedSet record
  { X = ℤ
  ; equiv = Equivℤ
  }
  decideℤ-≈