blob: 64248c6aa4cef8c34ba9db921f4c1d328450d1c6 [file]
/-
Copyright (c) 2025 Amazon.com, Inc. or its affiliates. All Rights Reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Leonardo de Moura
-/
module
prelude
public import Init.GrindInstances.ToInt
public import Init.Data.Nat.Div.Basic
import Init.ByCases
import Init.Data.Int.DivMod.Lemmas
import Init.Data.Int.LemmasAux
import Init.Data.Int.Pow
import Init.Omega
public section
namespace Nat.ToInt
theorem ofNat_toNat (a : Int) : (NatCast.natCast a.toNat : Int) = if a ≤ 0 then 0 else a := by simp [Int.max_def]
theorem toNat_nonneg (x : Nat) : (-1:Int) * (NatCast.natCast x) ≤ 0 := by simp
theorem natCast_ofNat (n : Nat) : (NatCast.natCast (OfNat.ofNat n : Nat) : Int) = OfNat.ofNat n := by rfl
theorem of_eq {a b : Nat} {a' b' : Int}
(h₁ : NatCast.natCast a = a') (h₂ : NatCast.natCast b = b') : a = b → a' = b' := by
intro h; replace h := congrArg (NatCast.natCast (R := Int)) h
rw [h₁, h₂] at h; assumption
theorem of_diseq {a b : Nat} {a' b' : Int}
(h₁ : NatCast.natCast a = a') (h₂ : NatCast.natCast b = b') : a ≠ b → a' ≠ b' := by
intro hne h; rw [← h₁, ← h₂] at h
replace h := Int.ofNat_inj.mp h; contradiction
theorem of_dvd (d a : Nat) (d' a' : Int)
(h₁ : NatCast.natCast d = d') (h₂ : NatCast.natCast a = a') : d ∣ a → d' ∣ a' := by
simp [← h₁, ←h₂, Int.ofNat_dvd]
theorem of_le {a b : Nat} {a' b' : Int}
(h₁ : NatCast.natCast a = a') (h₂ : NatCast.natCast b = b') : a ≤ b → a' ≤ b' := by
intro h; replace h := Int.ofNat_le |>.mpr h
rw [← h₁, ← h₂]; assumption
theorem of_not_le {a b : Nat} {a' b' : Int}
(h₁ : NatCast.natCast a = a') (h₂ : NatCast.natCast b = b') : ¬ (a ≤ b) → b' + 1 ≤ a' := by
intro h; rw [← Int.ofNat_le] at h
rw [← h₁, ← h₂]; show (↑b + 1 : Int) ≤ a; omega
theorem add_congr {a b : Nat} {a' b' : Int}
(h₁ : NatCast.natCast a = a') (h₂ : NatCast.natCast b = b') : NatCast.natCast (a + b) = a' + b' := by
simp_all [Int.natCast_add]
theorem mul_congr {a b : Nat} {a' b' : Int}
(h₁ : NatCast.natCast a = a') (h₂ : NatCast.natCast b = b') : NatCast.natCast (a * b) = a' * b' := by
simp_all [Int.natCast_mul]
theorem sub_congr {a b : Nat} {a' b' : Int}
(h₁ : NatCast.natCast a = a') (h₂ : NatCast.natCast b = b') : NatCast.natCast (a - b) = if b' + (-1)*a' ≤ 0 then a' - b' else 0 := by
rw [Int.neg_mul, ← Int.sub_eq_add_neg, Int.one_mul]
split
next h =>
have h := Int.le_of_sub_nonpos h
simp [← h₁, ← h₂, Int.ofNat_le] at h
simp [Int.ofNat_sub h]
rw [← h₁, ← h₂]
next h =>
have : ¬ (↑b : Int) ≤ ↑a := by
intro h
replace h := Int.sub_nonpos_of_le h
simp [h₁, h₂] at h
contradiction
rw [Int.ofNat_le] at this
simp [Lean.Omega.Int.ofNat_sub_eq_zero this]
theorem pow_congr {a : Nat} (k : Nat) (a' : Int)
(h₁ : NatCast.natCast a = a') : NatCast.natCast (a ^ k) = a' ^ k := by
simp_all [Int.natCast_pow]
theorem div_congr {a b : Nat} {a' b' : Int}
(h₁ : NatCast.natCast a = a') (h₂ : NatCast.natCast b = b') : NatCast.natCast (a / b) = a' / b' := by
simp_all [Int.natCast_ediv]
theorem mod_congr {a b : Nat} {a' b' : Int}
(h₁ : NatCast.natCast a = a') (h₂ : NatCast.natCast b = b') : NatCast.natCast (a % b) = a' % b' := by
simp_all [Int.natCast_emod]
theorem finVal {n : Nat} {a : Fin n} {a' : Int}
(h₁ : Lean.Grind.ToInt.toInt a = a') : NatCast.natCast (a.val) = a' := by
rw [← h₁, Lean.Grind.ToInt.toInt, Lean.Grind.instToIntFinCoOfNatIntCast]
theorem eq_eq {a b : Nat} {a' b' : Int}
(h₁ : NatCast.natCast a = a') (h₂ : NatCast.natCast b = b') : (a = b) = (a' = b') := by
simp [← h₁, ←h₂]; constructor
next => intro; subst a; rfl
next => simp [Int.natCast_inj]
theorem lt_eq {a b : Nat} {a' b' : Int}
(h₁ : NatCast.natCast a = a') (h₂ : NatCast.natCast b = b') : (a < b) = (a' < b') := by
simp only [← h₁, ← h₂, Int.ofNat_lt]
theorem le_eq {a b : Nat} {a' b' : Int}
(h₁ : NatCast.natCast a = a') (h₂ : NatCast.natCast b = b') : (a ≤ b) = (a' ≤ b') := by
simp only [← h₁, ← h₂, Int.ofNat_le]
end Nat.ToInt
namespace Int.Nonneg
@[expose] def num_cert (a : Int) : Bool := a ≥ 0
theorem num (a : Int) : num_cert a → a ≥ 0 := by simp [num_cert]
theorem add (a b : Int) (h₁ : a ≥ 0) (h₂ : b ≥ 0) : a + b ≥ 0 := by exact Int.add_nonneg h₁ h₂
theorem mul (a b : Int) (h₁ : a ≥ 0) (h₂ : b ≥ 0) : a * b ≥ 0 := by exact Int.mul_nonneg h₁ h₂
theorem div (a b : Int) (h₁ : a ≥ 0) (h₂ : b ≥ 0) : a / b ≥ 0 := by exact Int.ediv_nonneg h₁ h₂
theorem pow (a : Int) (k : Nat) (h₁ : a ≥ 0) : a ^ k ≥ 0 := by exact Int.pow_nonneg h₁
theorem mod (a b : Int) (h₁ : a ≥ 0) : a % b ≥ 0 := by
by_cases b = 0
next => simp [*]
next h => exact emod_nonneg a h
theorem natCast (a : Nat) : (NatCast.natCast a : Int) ≥ 0 := by simp
theorem toPoly (e : Int) : e ≥ 0 → -1 * e ≤ 0 := by omega
end Int.Nonneg