blob: ff58ca244f0daa66d1226351d929fec371144a51 [file]
/-
Copyright (c) 2025 Lean FRO, LLC. or its affiliates. All Rights Reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kim Morrison
-/
module
prelude
import Init.Data.Int.Order
import Init.Grind.ToInt
namespace Lean.Grind
/--
A type where addition is right-cancellative, i.e. `a + c = b + c` implies `a = b`.
-/
class AddRightCancel (M : Type u) [Add M] where
/-- Addition is right-cancellative. -/
add_right_cancel : ∀ a b c : M, a + c = b + c → a = b
/--
A module over the natural numbers, i.e. a type with zero, addition, and scalar multiplication by natural numbers,
satisfying appropriate compatibilities.
Equivalently, an additive commutative monoid.
Use `IntModule` if the type has negation.
-/
class NatModule (M : Type u) extends Zero M, Add M, HMul Nat M M where
/-- Zero is the right identity for addition. -/
add_zero : ∀ a : M, a + 0 = a
/-- Addition is commutative. -/
add_comm : ∀ a b : M, a + b = b + a
/-- Addition is associative. -/
add_assoc : ∀ a b c : M, a + b + c = a + (b + c)
/-- Scalar multiplication by zero is zero. -/
zero_hmul : ∀ a : M, 0 * a = 0
/-- Scalar multiplication by one is the identity. -/
one_hmul : ∀ a : M, 1 * a = a
/-- Scalar multiplication is distributive over addition in the natural numbers. -/
add_hmul : ∀ n m : Nat, ∀ a : M, (n + m) * a = n * a + m * a
/-- Scalar multiplication of zero is zero. -/
hmul_zero : ∀ n : Nat, n * (0 : M) = 0
/-- Scalar multiplication is distributive over addition in the module. -/
hmul_add : ∀ n : Nat, ∀ a b : M, n * (a + b) = n * a + n * b
attribute [instance 100] NatModule.toZero NatModule.toAdd NatModule.toHMul
/--
A module over the integers, i.e. a type with zero, addition, negation, subtraction, and scalar multiplication by integers,
satisfying appropriate compatibilities.
Equivalently, an additive commutative group.
-/
class IntModule (M : Type u) extends Zero M, Add M, Neg M, Sub M where
/-- Scalar multiplication by natural numbers. -/
[hmulNat : HMul Nat M M]
/-- Scalar multiplication by integers. -/
[hmulInt : HMul Int M M]
/-- Zero is the right identity for addition. -/
add_zero : ∀ a : M, a + 0 = a
/-- Addition is commutative. -/
add_comm : ∀ a b : M, a + b = b + a
/-- Addition is associative. -/
add_assoc : ∀ a b c : M, a + b + c = a + (b + c)
/-- Scalar multiplication by zero is zero. -/
zero_hmul : ∀ a : M, (0 : Int) * a = 0
/-- Scalar multiplication by one is the identity. -/
one_hmul : ∀ a : M, (1 : Int) * a = a
/-- Scalar multiplication is distributive over addition in the integers. -/
add_hmul : ∀ n m : Int, ∀ a : M, (n + m) * a = n * a + m * a
/-- Scalar multiplication of zero is zero. -/
hmul_zero : ∀ n : Int, n * (0 : M) = 0
/-- Scalar multiplication is distributive over addition in the module. -/
hmul_add : ∀ n : Int, ∀ a b : M, n * (a + b) = n * a + n * b
/-- Negation is the left inverse of addition. -/
neg_add_cancel : ∀ a : M, -a + a = 0
/-- Subtraction is addition of the negative. -/
sub_eq_add_neg : ∀ a b : M, a - b = a + -b
/-- Scalar multiplication by natural numbers is consistent with scalar multiplication by integers. -/
hmul_nat : ∀ n : Nat, ∀ a : M, (n : Int) * a = n * a
namespace NatModule
variable {M : Type u} [NatModule M]
theorem zero_add (a : M) : 0 + a = a := by
rw [add_comm, add_zero]
theorem mul_hmul (n m : Nat) (a : M) : (n * m) * a = n * (m * a) := by
induction n with
| zero => simp [zero_hmul]
| succ n ih =>
rw [Nat.add_one_mul, add_hmul, ih, add_hmul, one_hmul]
instance (priority := 100) (M : Type u) [NatModule M] : SMul Nat M where
smul a x := a * x
end NatModule
namespace IntModule
attribute [instance 100] IntModule.toZero IntModule.toAdd IntModule.toNeg IntModule.toSub
IntModule.hmulNat IntModule.hmulInt
instance toNatModule (M : Type u) [i : IntModule M] : NatModule M :=
{ i with
hMul := i.hmulNat.hMul
zero_hmul := by simp [← hmul_nat, zero_hmul]
one_hmul := by simp [← hmul_nat, one_hmul]
hmul_zero := by simp [← hmul_nat, hmul_zero]
add_hmul := by simp [← hmul_nat, add_hmul]
hmul_add := by simp [← hmul_nat, hmul_add] }
instance (priority := 100) (M : Type u) [IntModule M] : SMul Nat M where
smul a x := a * x
instance (priority := 100) (M : Type u) [IntModule M] : SMul Int M where
smul a x := a * x
variable {M : Type u} [IntModule M]
theorem zero_add (a : M) : 0 + a = a := by
rw [add_comm, add_zero]
theorem add_neg_cancel (a : M) : a + -a = 0 := by
rw [add_comm, neg_add_cancel]
theorem add_left_comm (a b c : M) : a + (b + c) = b + (a + c) := by
rw [← add_assoc, ← add_assoc, add_comm a]
theorem add_left_inj {a b : M} (c : M) : a + c = b + c ↔ a = b :=
⟨fun h => by simpa [add_assoc, add_neg_cancel, add_zero] using (congrArg (· + -c) h),
fun g => congrArg (· + c) g⟩
theorem add_right_inj (a b c : M) : a + b = a + c ↔ b = c := by
rw [add_comm a b, add_comm a c, add_left_inj]
theorem neg_zero : (-0 : M) = 0 := by
rw [← add_left_inj 0, neg_add_cancel, add_zero]
theorem neg_neg (a : M) : -(-a) = a := by
rw [← add_left_inj (-a), neg_add_cancel, add_neg_cancel]
theorem neg_eq_zero (a : M) : -a = 0 ↔ a = 0 :=
⟨fun h => by
replace h := congrArg (-·) h
simpa [neg_neg, neg_zero] using h,
fun h => by rw [h, neg_zero]⟩
theorem neg_add (a b : M) : -(a + b) = -a + -b := by
rw [← add_left_inj (a + b), neg_add_cancel, add_assoc (-a), add_comm a b, ← add_assoc (-b),
neg_add_cancel, zero_add, neg_add_cancel]
theorem neg_sub (a b : M) : -(a - b) = b - a := by
rw [sub_eq_add_neg, neg_add, neg_neg, sub_eq_add_neg, add_comm]
theorem sub_self (a : M) : a - a = 0 := by
rw [sub_eq_add_neg, add_neg_cancel]
theorem sub_eq_iff {a b c : M} : a - b = c ↔ a = c + b := by
rw [sub_eq_add_neg]
constructor
next => intro; subst c; rw [add_assoc, neg_add_cancel, add_zero]
next => intro; subst a; rw [add_assoc, add_comm b, neg_add_cancel, add_zero]
theorem sub_eq_zero_iff {a b : M} : a - b = 0 ↔ a = b := by
simp [sub_eq_iff, zero_add]
theorem add_sub_cancel {a b : M} : a + b - b = a := by
rw [sub_eq_add_neg, add_assoc, add_neg_cancel, add_zero]
theorem sub_add_cancel {a b : M} : a - b + b = a := by
rw [sub_eq_add_neg, add_assoc, neg_add_cancel, add_zero]
theorem neg_hmul (n : Int) (a : M) : (-n) * a = - (n * a) := by
apply (add_left_inj (n * a)).mp
rw [← add_hmul, Int.add_left_neg, zero_hmul, neg_add_cancel]
theorem hmul_neg (n : Int) (a : M) : n * (-a) = - (n * a) := by
apply (add_left_inj (n * a)).mp
rw [← hmul_add, neg_add_cancel, neg_add_cancel, hmul_zero]
theorem hmul_sub (k : Int) (a b : M) : k * (a - b) = k * a - k * b := by
rw [sub_eq_add_neg, hmul_add, hmul_neg, ← sub_eq_add_neg]
theorem sub_hmul (k₁ k₂ : Int) (a : M) : (k₁ - k₂) * a = k₁ * a - k₂ * a := by
rw [Int.sub_eq_add_neg, add_hmul, neg_hmul, ← sub_eq_add_neg]
theorem nat_zero_hmul (a : M) : (0 : Nat) * a = 0 := by
rw [← hmul_nat, Int.natCast_zero, zero_hmul]
private theorem nat_mul_hmul (n : Nat) (m : Int) (a : M) :
((n : Int) * m) * a = (n : Int) * (m * a) := by
induction n with
| zero => simp [zero_hmul]
| succ n ih =>
rw [Int.natCast_add, Int.add_mul, add_hmul, Int.natCast_one,
Int.one_mul, add_hmul, one_hmul, ih]
theorem mul_hmul (n m : Int) (a : M) : (n * m) * a = n * (m * a) := by
match n with
| (n : Nat) => exact nat_mul_hmul n m a
| -(n + 1 : Nat) => rw [Int.neg_mul, neg_hmul, nat_mul_hmul, neg_hmul]
end IntModule
/--
We say a module has no natural number zero divisors if
`k ≠ 0` and `k * a = k * b` implies `a = b` (here `k` is a natural number and `a` and `b` are element of the module).
For a module over the integersm this is equivalent to
`k ≠ 0` and `k * a = 0` implies `a = 0`.
(See the alternative constructor `NoNatZeroDivisors.mk'`,
and the theorem `eq_zero_of_mul_eq_zero`.)
-/
class NoNatZeroDivisors (α : Type u) [HMul Nat α α] where
/-- If `k * a ≠ k * b` then `k ≠ 0` or `a ≠ b`.-/
no_nat_zero_divisors : ∀ (k : Nat) (a b : α), k ≠ 0 → k * a = k * b → a = b
export NoNatZeroDivisors (no_nat_zero_divisors)
namespace NoNatZeroDivisors
/-- Alternative constructor for `NoNatZeroDivisors` when we have an `IntModule`. -/
def mk' {α} [IntModule α] (eq_zero_of_mul_eq_zero : ∀ (k : Nat) (a : α), k ≠ 0 → k * a = 0 → a = 0) : NoNatZeroDivisors α where
no_nat_zero_divisors k a b h₁ h₂ := by
rw [← IntModule.sub_eq_zero_iff, ← IntModule.hmul_nat, ← IntModule.hmul_nat, ← IntModule.hmul_sub, IntModule.hmul_nat] at h₂
rw [← IntModule.sub_eq_zero_iff]
apply eq_zero_of_mul_eq_zero k (a - b) h₁ h₂
theorem eq_zero_of_mul_eq_zero {α : Type u} [NatModule α] [NoNatZeroDivisors α] {k : Nat} {a : α}
: k ≠ 0 → k * a = 0 → a = 0 := by
intro h₁ h₂
replace h₁ : k ≠ 0 := by intro h; simp [h] at h₁
exact no_nat_zero_divisors k a 0 h₁ (by rwa [NatModule.hmul_zero])
end NoNatZeroDivisors
instance [ToInt α (some lo) (some hi)] [IntModule α] [ToInt.Zero α (some lo) (some hi)] [ToInt.Add α (some lo) (some hi)] : ToInt.Neg α (some lo) (some hi) where
toInt_neg x := by
have := (ToInt.Add.toInt_add (-x) x).symm
rw [IntModule.neg_add_cancel, ToInt.Zero.toInt_zero, ← ToInt.Zero.wrap_zero (α := α)] at this
rw [ToInt.wrap_eq_wrap_iff] at this
simp at this
rw [← ToInt.wrap_toInt]
rw [ToInt.wrap_eq_wrap_iff]
simpa
instance [ToInt α (some lo) (some hi)] [IntModule α] [ToInt.Add α (some lo) (some hi)] [ToInt.Neg α (some lo) (some hi)] : ToInt.Sub α (some lo) (some hi) :=
ToInt.Sub.of_sub_eq_add_neg IntModule.sub_eq_add_neg
end Lean.Grind