blob: e02093737fa9780e0309d12e6c993a0eac973950 [file]
/-
Copyright (c) 2025 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Leonardo de Moura, Jeremy Avigad, Mario Carneiro, Paul Reichert
-/
prelude
import Init.Data.Ord
import Init.Data.Int.Order
/-! # Basic lemmas about comparing integers
This file introduces some basic lemmas about `compare` as applied to integers.
Import `Std.Classes.Ord` in order to obtain the `TransOrd` and `LawfulEqOrd` instances for `Int`.
-/
namespace Int
protected theorem lt_or_eq_of_le {n m : Int} (h : n ≤ m) : n < m ∨ n = m := by
omega
theorem compare_eq_ite_lt (a b : Int) :
compare a b = if a < b then .lt else if b < a then .gt else .eq := by
simp only [compare, compareOfLessAndEq]
split
· rfl
· next h =>
match Int.lt_or_eq_of_le (Int.not_lt.1 h) with
| .inl h => simp [h, Int.ne_of_gt h]
| .inr rfl => simp
theorem compare_eq_ite_le (a b : Int) :
compare a b = if a ≤ b then if b ≤ a then .eq else .lt else .gt := by
rw [compare_eq_ite_lt]
split
· next hlt => simp [Int.le_of_lt hlt, Int.not_le.2 hlt]
· next hge =>
split
· next hgt => simp [Int.le_of_lt hgt, Int.not_le.2 hgt]
· next hle => simp [Int.not_lt.1 hge, Int.not_lt.1 hle]
protected theorem compare_swap (a b : Int) : (compare a b).swap = compare b a := by
simp only [compare_eq_ite_le]; (repeat' split) <;> try rfl
next h1 h2 => cases h1 (Int.le_of_not_le h2)
protected theorem compare_eq_eq {a b : Int} : compare a b = .eq ↔ a = b := by
rw [compare_eq_ite_lt]; (repeat' split) <;> simp [Int.ne_of_lt, Int.ne_of_gt, *]
next hlt hgt => exact Int.le_antisymm (Int.not_lt.1 hgt) (Int.not_lt.1 hlt)
protected theorem compare_eq_lt {a b : Int} : compare a b = .lt ↔ a < b := by
rw [compare_eq_ite_lt]; (repeat' split) <;> simp [*]
protected theorem compare_eq_gt {a b : Int} : compare a b = .gt ↔ b < a := by
rw [compare_eq_ite_lt]; (repeat' split) <;> simp [Int.le_of_lt, *]
protected theorem compare_ne_gt {a b : Int} : compare a b ≠ .gt ↔ a ≤ b := by
rw [compare_eq_ite_le]; (repeat' split) <;> simp [*]
protected theorem compare_ne_lt {a b : Int} : compare a b ≠ .lt ↔ b ≤ a := by
rw [compare_eq_ite_le]; (repeat' split) <;> simp [Int.le_of_not_le, *]
protected theorem isLE_compare {a b : Int} :
(compare a b).isLE ↔ a ≤ b := by
simp only [Int.compare_eq_ite_le]
repeat' split <;> simp_all
protected theorem isGE_compare {a b : Int} :
(compare a b).isGE ↔ b ≤ a := by
rw [← Int.compare_swap, Ordering.isGE_swap]
exact Int.isLE_compare
end Int