LeanMachineLearning exposition

1.6. ForMathlib.MeasureTheory.Order.MeasurableArg🔗

Argmax and argmin functions on finite sets

We prove in particular that those functions are measurable.

Module LeanMachineLearning.ForMathlib.MeasureTheory.Order.MeasurableArg contains 17 exposed declarations.

max🔗

DefinitionFunction.max
Details

The maximum value of a tuple.

🔗def
Function.max.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : α
Function.max.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : α

Code

abbrev max : α := univ.sup' univ_nonempty f
Used by (8)

Actions: Source · Open Issue

min🔗

DefinitionFunction.min
Details

The minimum value of a tuple.

🔗def
Function.min.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : α
Function.min.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : α

Code

def min : {ι : Type u_1} → {α : Type u_2} → [LinearOrder α] → [Fintype ι] → [Nonempty ι] → (ι → α) → α
Used by (8)

Actions: Source · Open Issue

le_max🔗

LemmaFunction.le_max
Details

No docstring.

🔗theorem
Function.le_max.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) (x : ι) : f x ≤ max f
Function.le_max.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α)
  (x : ι) : f x ≤ max f

Code

lemma le_max (x : ι) : f x ≤ max f
Type uses (1)
Used by (1)

Actions: Source · Open Issue

Proof
le_sup' _ (by simp)

min_le🔗

TheoremFunction.min_le
Details

No docstring.

🔗theorem
Function.min_le.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) (x : ι) : min f ≤ f x
Function.min_le.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α)
  (x : ι) : min f ≤ f x

Code

theorem min_le : ∀ {ι : Type u_1} {α : Type u_2} [inst : LinearOrder α] [inst_1 : Fintype ι] [inst_2 : Nonempty ι] (f : ι → α) (x : ι),
  Function.min f ≤ f x
Type uses (1)
Used by (1)

Actions: Source · Open Issue

Proof
@[to_dual min_le]

exists_argmax🔗

Lemmaexists_argmax
Details

No docstring.

🔗theorem
exists_argmax.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : ∃ i, f i = Function.max f
exists_argmax.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) :
  ∃ i, f i = Function.max f

Code

lemma exists_argmax : ∃ i, f i = f.max
Type uses (1)
Used by (3)

Actions: Source · Open Issue

Proof
by
  obtain ⟨i, -, hi⟩ := Finset.exists_mem_eq_sup' (by simp : Finset.univ.Nonempty) f
  exact ⟨i, hi.symm⟩

exists_argmin🔗

Theoremexists_argmin
Details

No docstring.

🔗theorem
exists_argmin.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : ∃ i, f i = Function.min f
exists_argmin.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) :
  ∃ i, f i = Function.min f

Code

theorem exists_argmin : ∀ {ι : Type u_1} {α : Type u_2} [inst : LinearOrder α] [inst_1 : Fintype ι] [inst_2 : Nonempty ι] (f : ι → α),
  ∃ i, f i = Function.min f
Type uses (1)
Used by (3)

Actions: Source · Open Issue

Proof
@[to_dual exists_argmin]

argmax🔗

Definitionargmax
Details

The index of the maximum value of a tuple.

🔗def
argmax.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : ι
argmax.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : ι

Code

noncomputable def argmax := (exists_argmax f).choose
Body uses (2)
Used by (17)

Actions: Source · Open Issue

argmin🔗

Definitionargmin
Details

The index of the minimum value of a tuple.

🔗def
argmin.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : ι
argmin.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : ι

Code

def argmin : {ι : Type u_1} → {α : Type u_2} → [LinearOrder α] → [Fintype ι] → [Nonempty ι] → (ι → α) → ι
Body uses (2)
Used by (3)

Actions: Source · Open Issue

argmax_spec🔗

Lemmaargmax_spec
Details

No docstring.

🔗theorem
argmax_spec.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : f (argmax f) = Function.max f
argmax_spec.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) :
  f (argmax f) = Function.max f

Code

lemma argmax_spec : f (argmax f) = f.max
Type uses (2)
Body uses (1)
Used by (1)

Actions: Source · Open Issue

Proof
(exists_argmax f).choose_spec

argmin_spec🔗

Theoremargmin_spec
Details

No docstring.

🔗theorem
argmin_spec.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) : f (argmin f) = Function.min f
argmin_spec.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) :
  f (argmin f) = Function.min f

Code

theorem argmin_spec : ∀ {ι : Type u_1} {α : Type u_2} [inst : LinearOrder α] [inst_1 : Fintype ι] [inst_2 : Nonempty ι] (f : ι → α),
  f (argmin f) = Function.min f
Type uses (2)
Body uses (1)
Used by (1)

Actions: Source · Open Issue

Proof
@[to_dual argmin_spec]

isMaxOn_argmax🔗

LemmaisMaxOn_argmax
Details

No docstring.

🔗theorem
isMaxOn_argmax.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) (x : ι) : f x ≤ f (argmax f)
isMaxOn_argmax.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α)
  (x : ι) : f x ≤ f (argmax f)

Code

lemma isMaxOn_argmax (x : ι) : f x ≤ f (argmax f)
Type uses (1)
Body uses (3)
Used by (4)

Actions: Source · Open Issue

Proof
by
  rw [argmax_spec f]
  exact f.le_max x

isMinOn_argmin🔗

TheoremisMinOn_argmin
Details

No docstring.

🔗theorem
isMinOn_argmin.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α) (x : ι) : f (argmin f) ≤ f x
isMinOn_argmin.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] (f : ι → α)
  (x : ι) : f (argmin f) ≤ f x

Code

theorem isMinOn_argmin : ∀ {ι : Type u_1} {α : Type u_2} [inst : LinearOrder α] [inst_1 : Fintype ι] [inst_2 : Nonempty ι] (f : ι → α) (x : ι),
  f (argmin f) ≤ f x
Type uses (1)
Body uses (3)

Actions: Source · Open Issue

Proof
@[to_dual isMinOn_argmin]

measurable_max🔗

Lemmameasurable_max
Details

No docstring.

🔗theorem
measurable_max.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] [MeasurableSpace α] [MeasurableSup₂ α] :
  Measurable fun t => Function.max t
measurable_max.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι]
  [MeasurableSpace α] [MeasurableSup₂ α] :
  Measurable fun t => Function.max t

Code

lemma measurable_max [MeasurableSup₂ α] : Measurable (fun (t : ι → α) => t.max)
Type uses (1)
Used by (1)

Actions: Source · Open Issue

Proof
fun_prop)]
lemma measurable_max [MeasurableSup₂ α] : Measurable (fun (t : ι → α) => t.max) := by
  suffices (fun f : ι → α ↦ f.max) = (univ.sup' univ_nonempty fun i f => f i) by
    rw [this]
    exact measurable_sup' univ_nonempty (fun i _ => measurable_pi_apply i)
  ext
  simp [Function.max]

measurable_min🔗

Theoremmeasurable_min
Details

No docstring.

🔗theorem
measurable_min.{u_1, u_2} {ι : Type u_1} {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι] [MeasurableSpace α] [MeasurableInf₂ α] :
  Measurable fun t => Function.min t
measurable_min.{u_1, u_2} {ι : Type u_1}
  {α : Type u_2} [LinearOrder α]
  [Fintype ι] [Nonempty ι]
  [MeasurableSpace α] [MeasurableInf₂ α] :
  Measurable fun t => Function.min t

Code

theorem measurable_min : ∀ {ι : Type u_1} {α : Type u_2} [inst : LinearOrder α] [inst_1 : Fintype ι] [inst_2 : Nonempty ι]
  [inst_3 : MeasurableSpace α] [MeasurableInf₂ α], Measurable fun t => Function.min t
Type uses (1)
Body uses (1)
Used by (1)

Actions: Source · Open Issue

Proof
fun_prop)]

measurable_argmax🔗

Lemmameasurable_argmax
Details

No docstring.

🔗theorem
measurable_argmax.{u_1, u_2} {ι : Type u_1} {α : Type u_2}
  [LinearOrder α] [Fintype ι] [Nonempty ι] [MeasurableSpace α]
  [MeasurableSpace ι] [MeasurableEq α] [MeasurableSup₂ α] :
  Measurable fun f => argmax f
measurable_argmax.{u_1, u_2}
  {ι : Type u_1} {α : Type u_2}
  [LinearOrder α] [Fintype ι] [Nonempty ι]
  [MeasurableSpace α] [MeasurableSpace ι]
  [MeasurableEq α] [MeasurableSup₂ α] :
  Measurable fun f => argmax f

Code

lemma measurable_argmax [MeasurableSpace ι] [MeasurableEq α] [MeasurableSup₂ α] :
    Measurable fun f : ι → α ↦ argmax f
Type uses (1)
Body uses (3)
Used by (3)

Actions: Source · Open Issue

Proof
fun_prop) measurable_argmin]
lemma measurable_argmax [MeasurableSpace ι] [MeasurableEq α] [MeasurableSup₂ α] :
    Measurable fun f : ι → α ↦ argmax f := by
  refine measurable_to_countable' fun i ↦ ?_
  simp only [Set.preimage, Set.mem_singleton_iff]
  let Maximizers (f : ι → α) : Set ι := {i | f i = f.max}
  suffices {f : ι → α | argmax f = i} = ⋃ (S)
      (hS : ∀ x, Maximizers x = S → argmax x = i), {f | Maximizers f = S} by
    rw [this]
    refine MeasurableSet.iUnion fun S ↦ (.iUnion fun hS ↦ ?_)
    exact measurableSet_eq_fun (by fun_prop) measurable_const
  ext f
  simp only [Set.mem_setOf_eq, Set.mem_iUnion, exists_prop, exists_eq_right']
  constructor
  · intro hf x hx
    rw [← hf]
    exact Classical.choose.congr_simp hx (exists_argmax x)
  · intro h
    exact h f rfl

measurable_argmin🔗

Theoremmeasurable_argmin
Details

No docstring.

🔗theorem
measurable_argmin.{u_1, u_2} {ι : Type u_1} {α : Type u_2}
  [LinearOrder α] [Fintype ι] [Nonempty ι] [MeasurableSpace α]
  [MeasurableSpace ι] [MeasurableEq α] [MeasurableInf₂ α] :
  Measurable fun f => argmin f
measurable_argmin.{u_1, u_2}
  {ι : Type u_1} {α : Type u_2}
  [LinearOrder α] [Fintype ι] [Nonempty ι]
  [MeasurableSpace α] [MeasurableSpace ι]
  [MeasurableEq α] [MeasurableInf₂ α] :
  Measurable fun f => argmin f

Code

theorem measurable_argmin : ∀ {ι : Type u_1} {α : Type u_2} [inst : LinearOrder α] [inst_1 : Fintype ι] [inst_2 : Nonempty ι]
  [inst_3 : MeasurableSpace α] [inst_4 : MeasurableSpace ι] [MeasurableEq α] [MeasurableInf₂ α],
  Measurable fun f => argmin f
Type uses (1)
Body uses (3)

Actions: Source · Open Issue

Proof
fun_prop) measurable_argmin]

neg_max_eq_min_neg🔗

Lemmaneg_max_eq_min_neg
Details

No docstring.

🔗theorem
neg_max_eq_min_neg.{u_1, u_2} {ι : Type u_1} {α : Type u_2}
  [LinearOrder α] [Fintype ι] [Nonempty ι] (f : ι → α) [AddGroup α]
  [AddLeftMono α] [AddRightMono α] : -Function.max f = Function.min (-f)
neg_max_eq_min_neg.{u_1, u_2}
  {ι : Type u_1} {α : Type u_2}
  [LinearOrder α] [Fintype ι] [Nonempty ι]
  (f : ι → α) [AddGroup α] [AddLeftMono α]
  [AddRightMono α] :
  -Function.max f = Function.min (-f)

Code

lemma neg_max_eq_min_neg [AddGroup α] [AddLeftMono α] [AddRightMono α] : -f.max = (-f).min
Type uses (2)
Body uses (2)

Actions: Source · Open Issue

Proof
by
  refine le_antisymm ?_ ?_
  · simp; grind
  · simp only [inf'_le_iff, mem_univ, Pi.neg_apply, neg_le_neg_iff, sup'_le_iff, forall_const,
      true_and]
    exact ⟨argmax f, isMaxOn_argmax f⟩
  1. Function.max
  2. Function.min
  3. Function.le_max
  4. Function.min_le
  5. exists_argmax
  6. exists_argmin
  7. argmax
  8. argmin
  9. argmax_spec
  10. argmin_spec
  11. isMaxOn_argmax
  12. isMinOn_argmin
  13. measurable_max
  14. measurable_min
  15. measurable_argmax
  16. measurable_argmin
  17. neg_max_eq_min_neg