整数
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ℤ-≈