blob: f240d8f69dafbff134f878a73b1f6409e6414b87 [file]
/-
Copyright (c) 2026 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Paul Reichert
-/
module
prelude
public import Init.Data.Order.Opposite
import Init.Data.Order.Lemmas
open Std
open scoped OppositeOrderInstances
/-! ## Definitions -/
/--
Returns either `x` or `y`, the one with the smaller value under `f`.
If `f x ≤ f y`, it returns `x`, and otherwise returns `y`.
-/
public def minOn [LE β] [DecidableLE β] (f : α → β) (x y : α) :=
if f x ≤ f y then x else y
/--
Returns either `x` or `y`, the one with the greater value under `f`.
If `f y ≤ f x`, it returns `x`, and otherwise returns `y`.
-/
public def maxOn [i : LE β] [DecidableLE β] (f : α → β) (x y : α) :=
letI := i.opposite
minOn f x y
/-! ## `minOn` Lemmas -/
public theorem minOn_id [Min α] [LE α] [DecidableLE α] [LawfulOrderLeftLeaningMin α] {x y : α} :
minOn id x y = min x y := by
simp [minOn, min_eq_if]
public theorem maxOn_id [Max α] [LE α] [DecidableLE α] [LawfulOrderLeftLeaningMax α] {x y : α} :
maxOn id x y = max x y := by
letI : LE α := (inferInstanceAs (LE α)).opposite
letI : Min α := (inferInstanceAs (Max α)).oppositeMin
simp [maxOn, minOn_id, Max.min_oppositeMin, this]
public theorem minOn_eq_or [LE β] [DecidableLE β] {f : α → β} {x y : α} :
minOn f x y = x ∨ minOn f x y = y := by
rw [minOn]
split
· exact Or.inl rfl
· exact Or.inr rfl
@[simp]
public theorem minOn_self [LE β] [DecidableLE β] {f : α → β} {x : α} :
minOn f x x = x := by
cases minOn_eq_or (f := f) (x := x) (y := x) <;> assumption
public theorem minOn_eq_left [LE β] [DecidableLE β] {f : α → β} {x y : α} (h : f x ≤ f y) :
minOn f x y = x := by
simp [minOn, h]
public theorem minOn_eq_right [LE β] [DecidableLE β] {f : α → β} {x y : α} (h : ¬ f x ≤ f y) :
minOn f x y = y := by
simp [minOn, h]
public theorem minOn_eq_right_of_lt
[LE β] [DecidableLE β] [LT β] [Total (α := β) (· ≤ ·)] [LawfulOrderLT β]
{f : α → β} {x y : α} (h : f y < f x) :
minOn f x y = y := by
apply minOn_eq_right
simpa [not_le] using h
public theorem apply_minOn_le_left [LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β}
{x y : α} : f (minOn f x y) ≤ f x := by
rw [minOn]
split
· apply le_refl
· exact le_of_not_ge ‹_›
public theorem apply_minOn_le_right [LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β}
{x y : α} : f (minOn f x y) ≤ f y := by
rw [minOn]
split
· assumption
· apply le_refl
public theorem le_apply_minOn_iff [LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β}
{x y : α} {b : β} :
b ≤ f (minOn f x y) ↔ b ≤ f x ∧ b ≤ f y := by
apply Iff.intro
· intro h
exact ⟨le_trans h apply_minOn_le_left, le_trans h apply_minOn_le_right⟩
· intro h
cases minOn_eq_or (f := f) (x := x) (y := y) <;> simp_all
public theorem minOn_assoc [LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β}
{x y z : α} : minOn f (minOn f x y) z = minOn f x (minOn f y z) := by
open scoped Classical.Order in
simp only [minOn]
split
· split
· split
· rfl
· rfl
· split
· have : ¬ f x ≤ f z := by assumption
have : f x ≤ f z := le_trans ‹f x ≤ f y› ‹f y ≤ f z›
contradiction
· rfl
· split
· rfl
· have : f z < f y := not_le.mp ‹¬ f y ≤ f z›
have : f y < f x := not_le.mp ‹¬ f x ≤ f y›
have : f z < f x := lt_trans ‹_› ‹_›
rw [if_neg]
exact not_le.mpr ‹_›
public instance [LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β} :
Associative (minOn f) where
assoc := by apply minOn_assoc
public theorem min_apply [LE β] [DecidableLE β] [Min β] [LawfulOrderLeftLeaningMin β]
{f : α → β} {x y : α} : min (f x) (f y) = f (minOn f x y) := by
rw [min_eq_if, minOn]
split <;> rfl
/-! ## `maxOn` Lemmas -/
public theorem maxOn_eq_minOn [le : LE β] [DecidableLE β] {f : α → β} {x y : α} :
maxOn f x y = (letI := le.opposite; minOn f x y) :=
(rfl)
public theorem maxOn_eq_or [LE β] [DecidableLE β] {f : α → β} {x y : α} :
maxOn f x y = x ∨ maxOn f x y = y :=
@minOn_eq_or ..
@[simp]
public theorem maxOn_self [LE β] [DecidableLE β] {f : α → β} {x : α} :
maxOn f x x = x :=
@minOn_self ..
public theorem maxOn_eq_left [le : LE β] [DecidableLE β] {f : α → β} {x y : α} (h : f y ≤ f x) :
maxOn f x y = x := by
simp only [maxOn_eq_minOn]
exact @minOn_eq_left (h := by simpa +instances [LE.opposite_def]) ..
public theorem maxOn_eq_right [LE β] [DecidableLE β] {f : α → β} {x y : α} (h : ¬ f y ≤ f x) :
maxOn f x y = y := by
simp only [maxOn_eq_minOn]
exact @minOn_eq_right (h := by simpa +instances [LE.opposite_def]) ..
public theorem maxOn_eq_right_of_lt
[LE β] [DecidableLE β] [LT β] [Total (α := β) (· ≤ ·)] [LawfulOrderLT β]
{f : α → β} {x y : α} (h : f x < f y) :
maxOn f x y = y :=
letI : LE β := (inferInstanceAs (LE β)).opposite
letI : LT β := (inferInstanceAs (LT β)).opposite
minOn_eq_right_of_lt (h := by simpa [LT.lt_opposite_iff] using h) ..
public theorem left_le_apply_maxOn [le : LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β}
{x y : α} : f x ≤ f (maxOn f x y) := by
rw [maxOn_eq_minOn]
letI : LE β := (inferInstanceAs (LE β)).opposite
simpa only [LE.le_opposite_iff] using apply_minOn_le_left (f := f) ..
public theorem right_le_apply_maxOn [LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β}
{x y : α} : f y ≤ f (maxOn f x y) := by
rw [maxOn_eq_minOn]
letI : LE β := (inferInstanceAs (LE β)).opposite
simpa only [LE.le_opposite_iff] using apply_minOn_le_right (f := f)
public theorem apply_maxOn_le_iff [LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β}
{x y : α} {b : β} :
f (maxOn f x y) ≤ b ↔ f x ≤ b ∧ f y ≤ b := by
rw [maxOn_eq_minOn]
letI : LE β := (inferInstanceAs (LE β)).opposite
simpa only [LE.le_opposite_iff] using le_apply_minOn_iff (f := f)
public theorem maxOn_assoc [LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β}
{x y z : α} : maxOn f (maxOn f x y) z = maxOn f x (maxOn f y z) :=
letI : LE β := (inferInstanceAs (LE β)).opposite
minOn_assoc (f := f)
public instance [LE β] [DecidableLE β] [IsLinearPreorder β] {f : α → β} :
Associative (maxOn f) where
assoc := by
apply maxOn_assoc
public theorem max_apply [LE β] [DecidableLE β] [Max β] [LawfulOrderLeftLeaningMax β]
{f : α → β} {x y : α} : max (f x) (f y) = f (maxOn f x y) := by
letI : LE β := (inferInstanceAs (LE β)).opposite
letI : Min β := (inferInstanceAs (Max β)).oppositeMin
simpa [Max.min_oppositeMin] using min_apply (f := f)
public theorem apply_maxOn [LE β] [DecidableLE β] [Max β] [LawfulOrderLeftLeaningMax β]
{f : α → β} {x y : α} : f (maxOn f x y) = max (f x) (f y) :=
max_apply.symm