Documentation

Mathlib.Order.Monotone.Defs

Monotonicity #

This file defines (strictly) monotone/antitone functions. Contrary to standard mathematical usage, "monotone"/"mono" here means "increasing", not "increasing or decreasing". We use "antitone"/"anti" to mean "decreasing".

Definitions #

Implementation notes #

Some of these definitions used to only require LE α or LT α. The advantage of this is unclear and it led to slight elaboration issues. Now, everything requires Preorder α and seems to work fine. Related Zulip discussion: https://leanprover.zulipchat.com/#narrow/stream/113488-general/topic/Order.20diamond/near/254353352.

Tags #

monotone, strictly monotone, antitone, strictly antitone, increasing, strictly increasing, decreasing, strictly decreasing

def Monotone {α : Type u} {β : Type v} [Preorder α] [Preorder β] (f : αβ) :

A function f is monotone if a ≤ b implies f a ≤ f b.

Equations
Instances For
def Antitone {α : Type u} {β : Type v} [Preorder α] [Preorder β] (f : αβ) :

A function f is antitone if a ≤ b implies f b ≤ f a.

Equations
Instances For
def MonotoneOn {α : Type u} {β : Type v} [Preorder α] [Preorder β] (f : αβ) (s : Set α) :

A function f is monotone on s if, for all a, b ∈ s, a ≤ b implies f a ≤ f b.

Equations
Instances For
def AntitoneOn {α : Type u} {β : Type v} [Preorder α] [Preorder β] (f : αβ) (s : Set α) :

A function f is antitone on s if, for all a, b ∈ s, a ≤ b implies f b ≤ f a.

Equations
Instances For
def StrictMono {α : Type u} {β : Type v} [Preorder α] [Preorder β] (f : αβ) :

A function f is strictly monotone if a < b implies f a < f b.

Equations
Instances For
def StrictAnti {α : Type u} {β : Type v} [Preorder α] [Preorder β] (f : αβ) :

A function f is strictly antitone if a < b implies f b < f a.

Equations
Instances For
def StrictMonoOn {α : Type u} {β : Type v} [Preorder α] [Preorder β] (f : αβ) (s : Set α) :

A function f is strictly monotone on s if, for all a, b ∈ s, a < b implies f a < f b.

Equations
Instances For
def StrictAntiOn {α : Type u} {β : Type v} [Preorder α] [Preorder β] (f : αβ) (s : Set α) :

A function f is strictly antitone on s if, for all a, b ∈ s, a < b implies f b < f a.

Equations
Instances For
instance instDecidableMonotoneOfForallForallForallLe {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} [i : Decidable (∀ (a b : α), a bf a f b)] :
Equations
instance instDecidableAntitoneOfForallForallForallLe {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} [i : Decidable (∀ (a b : α), a bf b f a)] :
Equations
instance instDecidableMonotoneOnOfForallForallMemSetForallForallForallLe {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} {s : Set α} [i : Decidable (∀ (a : α), a s∀ (b : α), b sa bf a f b)] :
Equations
instance instDecidableAntitoneOnOfForallForallMemSetForallForallForallLe {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} {s : Set α} [i : Decidable (∀ (a : α), a s∀ (b : α), b sa bf b f a)] :
Equations
instance instDecidableStrictMonoOfForallForallForallLt {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} [i : Decidable (∀ (a b : α), a < bf a < f b)] :
Equations
instance instDecidableStrictAntiOfForallForallForallLt {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} [i : Decidable (∀ (a b : α), a < bf b < f a)] :
Equations
instance instDecidableStrictMonoOnOfForallForallMemSetForallForallForallLt {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} {s : Set α} [i : Decidable (∀ (a : α), a s∀ (b : α), b sa < bf a < f b)] :
Equations
instance instDecidableStrictAntiOnOfForallForallMemSetForallForallForallLt {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} {s : Set α} [i : Decidable (∀ (a : α), a s∀ (b : α), b sa < bf b < f a)] :
Equations

Monotonicity in function spaces #

theorem Monotone.comp_le_comp_left {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] {f : βα} {g h : γβ} (hf : Monotone f) (le_gh : g h) :
f g f h
theorem monotone_lam {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder γ] {f : αβγ} (hf : ∀ (b : β), Monotone fun (a : α) => f a b) :
theorem monotone_app {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder γ] (f : βαγ) (b : β) (hf : Monotone fun (a : α) (b : β) => f b a) :
Monotone (f b)
theorem antitone_lam {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder γ] {f : αβγ} (hf : ∀ (b : β), Antitone fun (a : α) => f a b) :
theorem antitone_app {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder γ] (f : βαγ) (b : β) (hf : Antitone fun (a : α) (b : β) => f b a) :
Antitone (f b)
theorem Function.monotone_eval {ι : Type u} {α : ιType v} [(i : ι) → Preorder (α i)] (i : ι) :

Monotonicity hierarchy #

These four lemmas are there to strip off the semi-implicit arguments ⦃a b : α⦄. This is useful when you do not want to apply a Monotone assumption (i.e. your goal is a ≤ b → f a ≤ f b). However if you find yourself writing hf.imp h, then you should have written hf h instead.

theorem Monotone.imp {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} {a b : α} (hf : Monotone f) (h : a b) :
f a f b
theorem Antitone.imp {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} {a b : α} (hf : Antitone f) (h : a b) :
f b f a
theorem StrictMono.imp {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} {a b : α} (hf : StrictMono f) (h : a < b) :
f a < f b
theorem StrictAnti.imp {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} {a b : α} (hf : StrictAnti f) (h : a < b) :
f b < f a
theorem Monotone.monotoneOn {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} (hf : Monotone f) (s : Set α) :
theorem Antitone.antitoneOn {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} (hf : Antitone f) (s : Set α) :
@[simp]
theorem monotoneOn_univ {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} :
@[simp]
theorem antitoneOn_univ {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} :
theorem StrictMono.strictMonoOn {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} (hf : StrictMono f) (s : Set α) :
theorem StrictAnti.strictAntiOn {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} (hf : StrictAnti f) (s : Set α) :
@[simp]
theorem strictMonoOn_univ {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} :
@[simp]
theorem strictAntiOn_univ {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} :
theorem Monotone.strictMono_of_injective {α : Type u} {β : Type v} [Preorder α] [PartialOrder β] {f : αβ} (h₁ : Monotone f) (h₂ : Function.Injective f) :
theorem Antitone.strictAnti_of_injective {α : Type u} {β : Type v} [Preorder α] [PartialOrder β] {f : αβ} (h₁ : Antitone f) (h₂ : Function.Injective f) :
theorem monotone_iff_forall_lt {α : Type u} {β : Type v} [PartialOrder α] [Preorder β] {f : αβ} :
Monotone f ∀ ⦃a b : α⦄, a < bf a f b
theorem antitone_iff_forall_lt {α : Type u} {β : Type v} [PartialOrder α] [Preorder β] {f : αβ} :
Antitone f ∀ ⦃a b : α⦄, a < bf b f a
theorem monotoneOn_iff_forall_lt {α : Type u} {β : Type v} [PartialOrder α] [Preorder β] {f : αβ} {s : Set α} :
MonotoneOn f s ∀ ⦃a : α⦄, a s∀ ⦃b : α⦄, b sa < bf a f b
theorem antitoneOn_iff_forall_lt {α : Type u} {β : Type v} [PartialOrder α] [Preorder β] {f : αβ} {s : Set α} :
AntitoneOn f s ∀ ⦃a : α⦄, a s∀ ⦃b : α⦄, b sa < bf b f a
theorem StrictMonoOn.monotoneOn {α : Type u} {β : Type v} [PartialOrder α] [Preorder β] {f : αβ} {s : Set α} (hf : StrictMonoOn f s) :
theorem StrictAntiOn.antitoneOn {α : Type u} {β : Type v} [PartialOrder α] [Preorder β] {f : αβ} {s : Set α} (hf : StrictAntiOn f s) :
theorem StrictMono.monotone {α : Type u} {β : Type v} [PartialOrder α] [Preorder β] {f : αβ} (hf : StrictMono f) :
theorem StrictAnti.antitone {α : Type u} {β : Type v} [PartialOrder α] [Preorder β] {f : αβ} (hf : StrictAnti f) :

Monotonicity from and to subsingletons #

theorem Subsingleton.monotone {α : Type u} {β : Type v} [Preorder α] [Preorder β] [Subsingleton α] (f : αβ) :
theorem Subsingleton.antitone {α : Type u} {β : Type v} [Preorder α] [Preorder β] [Subsingleton α] (f : αβ) :
theorem Subsingleton.monotone' {α : Type u} {β : Type v} [Preorder α] [Preorder β] [Subsingleton β] (f : αβ) :
theorem Subsingleton.antitone' {α : Type u} {β : Type v} [Preorder α] [Preorder β] [Subsingleton β] (f : αβ) :
theorem Subsingleton.strictMono {α : Type u} {β : Type v} [Preorder α] [Preorder β] [Subsingleton α] (f : αβ) :
theorem Subsingleton.strictAnti {α : Type u} {β : Type v} [Preorder α] [Preorder β] [Subsingleton α] (f : αβ) :

Miscellaneous monotonicity results #

theorem monotone_id {α : Type u} [Preorder α] :
theorem monotoneOn_id {α : Type u} [Preorder α] {s : Set α} :
theorem strictMonoOn_id {α : Type u} [Preorder α] {s : Set α} :
theorem monotone_const {α : Type u} {β : Type v} [Preorder α] [Preorder β] {c : β} :
Monotone fun (x : α) => c
theorem monotoneOn_const {α : Type u} {β : Type v} [Preorder α] [Preorder β] {c : β} {s : Set α} :
MonotoneOn (fun (x : α) => c) s
theorem antitone_const {α : Type u} {β : Type v} [Preorder α] [Preorder β] {c : β} :
Antitone fun (x : α) => c
theorem antitoneOn_const {α : Type u} {β : Type v} [Preorder α] [Preorder β] {c : β} {s : Set α} :
AntitoneOn (fun (x : α) => c) s
theorem strictMono_of_le_iff_le {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} (h : ∀ (x y : α), x y f x f y) :
theorem strictAnti_of_le_iff_le {α : Type u} {β : Type v} [Preorder α] [Preorder β] {f : αβ} (h : ∀ (x y : α), x y f y f x) :
theorem injective_of_lt_imp_ne {α : Type u} {β : Type v} [LinearOrder α] {f : αβ} (h : ∀ (x y : α), x < yf x f y) :
theorem injective_of_le_imp_le {α : Type u} {β : Type v} [PartialOrder α] [Preorder β] (f : αβ) (h : ∀ {x y : α}, f x f yx y) :

Monotonicity under composition #

theorem Monotone.comp {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} (hg : Monotone g) (hf : Monotone f) :
theorem Monotone.comp_antitone {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} (hg : Monotone g) (hf : Antitone f) :
theorem Antitone.comp {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} (hg : Antitone g) (hf : Antitone f) :
theorem Antitone.comp_monotone {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} (hg : Antitone g) (hf : Monotone f) :
theorem Monotone.iterate {α : Type u} [Preorder α] {f : αα} (hf : Monotone f) (n : ) :
theorem Monotone.comp_monotoneOn {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} {s : Set α} (hg : Monotone g) (hf : MonotoneOn f s) :
MonotoneOn (g f) s
theorem Monotone.comp_antitoneOn {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} {s : Set α} (hg : Monotone g) (hf : AntitoneOn f s) :
AntitoneOn (g f) s
theorem Antitone.comp_antitoneOn {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} {s : Set α} (hg : Antitone g) (hf : AntitoneOn f s) :
MonotoneOn (g f) s
theorem Antitone.comp_monotoneOn {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} {s : Set α} (hg : Antitone g) (hf : MonotoneOn f s) :
AntitoneOn (g f) s
theorem StrictMono.comp {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} (hg : StrictMono g) (hf : StrictMono f) :
theorem StrictMono.comp_strictAnti {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} (hg : StrictMono g) (hf : StrictAnti f) :
theorem StrictAnti.comp {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} (hg : StrictAnti g) (hf : StrictAnti f) :
theorem StrictAnti.comp_strictMono {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} (hg : StrictAnti g) (hf : StrictMono f) :
theorem StrictMono.iterate {α : Type u} [Preorder α] {f : αα} (hf : StrictMono f) (n : ) :
theorem StrictMono.comp_strictMonoOn {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} {s : Set α} (hg : StrictMono g) (hf : StrictMonoOn f s) :
theorem StrictMono.comp_strictAntiOn {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} {s : Set α} (hg : StrictMono g) (hf : StrictAntiOn f s) :
theorem StrictAnti.comp_strictAntiOn {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} {s : Set α} (hg : StrictAnti g) (hf : StrictAntiOn f s) :
theorem StrictAnti.comp_strictMonoOn {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {g : βγ} {f : αβ} {s : Set α} (hg : StrictAnti g) (hf : StrictMonoOn f s) :

Monotonicity in linear orders #

theorem Monotone.reflect_lt {α : Type u} {β : Type v} [LinearOrder α] [Preorder β] {f : αβ} (hf : Monotone f) {a b : α} (h : f a < f b) :
a < b
theorem Antitone.reflect_lt {α : Type u} {β : Type v} [LinearOrder α] [Preorder β] {f : αβ} (hf : Antitone f) {a b : α} (h : f a < f b) :
b < a
theorem MonotoneOn.reflect_lt {α : Type u} {β : Type v} [LinearOrder α] [Preorder β] {f : αβ} {s : Set α} (hf : MonotoneOn f s) {a b : α} (ha : a s) (hb : b s) (h : f a < f b) :
a < b
theorem AntitoneOn.reflect_lt {α : Type u} {β : Type v} [LinearOrder α] [Preorder β] {f : αβ} {s : Set α} (hf : AntitoneOn f s) {a b : α} (ha : a s) (hb : b s) (h : f a < f b) :
b < a
theorem Subtype.mono_coe {α : Type u} [Preorder α] (t : Set α) :
theorem monotone_fst {α : Type u} {β : Type v} [Preorder α] [Preorder β] :
theorem monotone_snd {α : Type u} {β : Type v} [Preorder α] [Preorder β] :
theorem Monotone.prod_map {α : Type u} {β : Type v} {γ : Type w} {δ : Type u_2} [Preorder α] [Preorder β] [Preorder γ] [Preorder δ] {f : αγ} {g : βδ} (hf : Monotone f) (hg : Monotone g) :
theorem Antitone.prod_map {α : Type u} {β : Type v} {γ : Type w} {δ : Type u_2} [Preorder α] [Preorder β] [Preorder γ] [Preorder δ] {f : αγ} {g : βδ} (hf : Antitone f) (hg : Antitone g) :
theorem monotone_prod_iff {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {h : α × βγ} :
Monotone h (∀ (a : α), Monotone fun (b : β) => h (a, b)) ∀ (b : β), Monotone fun (a : α) => h (a, b)
theorem antitone_prod_iff {α : Type u} {β : Type v} {γ : Type w} [Preorder α] [Preorder β] [Preorder γ] {h : α × βγ} :
Antitone h (∀ (a : α), Antitone fun (b : β) => h (a, b)) ∀ (b : β), Antitone fun (a : α) => h (a, b)
theorem StrictMono.prod_map {α : Type u} {β : Type v} {γ : Type w} {δ : Type u_2} [PartialOrder α] [PartialOrder β] [Preorder γ] [Preorder δ] {f : αγ} {g : βδ} (hf : StrictMono f) (hg : StrictMono g) :
theorem StrictAnti.prod_map {α : Type u} {β : Type v} {γ : Type w} {δ : Type u_2} [PartialOrder α] [PartialOrder β] [Preorder γ] [Preorder δ] {f : αγ} {g : βδ} (hf : StrictAnti f) (hg : StrictAnti g) :

Pi types #

theorem Function.update_mono {ι : Type u_1} {π : ιType u_3} [DecidableEq ι] [(i : ι) → Preorder (π i)] {f : (i : ι) → π i} {i : ι} :
theorem Function.update_strictMono {ι : Type u_1} {π : ιType u_3} [DecidableEq ι] [(i : ι) → Preorder (π i)] {f : (i : ι) → π i} {i : ι} :
theorem Function.const_mono {α : Type u} {β : Type v} [Preorder α] :
theorem Function.const_strictMono {α : Type u} {β : Type v} [Preorder α] [Nonempty β] :
theorem monotone_iff_apply₂ {ι : Type u_1} {α : Type u} {β : ιType u_4} [(i : ι) → Preorder (β i)] [Preorder α] {f : α(i : ι) → β i} :
Monotone f ∀ (i : ι), Monotone fun (x : α) => f x i
theorem antitone_iff_apply₂ {ι : Type u_1} {α : Type u} {β : ιType u_4} [(i : ι) → Preorder (β i)] [Preorder α] {f : α(i : ι) → β i} :
Antitone f ∀ (i : ι), Antitone fun (x : α) => f x i
theorem Monotone.apply₂ {ι : Type u_1} {α : Type u} {β : ιType u_4} [(i : ι) → Preorder (β i)] [Preorder α] {f : α(i : ι) → β i} :
Monotone f∀ (i : ι), Monotone fun (x : α) => f x i

Alias of the forward direction of monotone_iff_apply₂.

theorem Monotone.of_apply₂ {ι : Type u_1} {α : Type u} {β : ιType u_4} [(i : ι) → Preorder (β i)] [Preorder α] {f : α(i : ι) → β i} :
(∀ (i : ι), Monotone fun (x : α) => f x i)Monotone f

Alias of the reverse direction of monotone_iff_apply₂.

theorem Antitone.of_apply₂ {ι : Type u_1} {α : Type u} {β : ιType u_4} [(i : ι) → Preorder (β i)] [Preorder α] {f : α(i : ι) → β i} :
(∀ (i : ι), Antitone fun (x : α) => f x i)Antitone f

Alias of the reverse direction of antitone_iff_apply₂.

theorem Antitone.apply₂ {ι : Type u_1} {α : Type u} {β : ιType u_4} [(i : ι) → Preorder (β i)] [Preorder α] {f : α(i : ι) → β i} :
Antitone f∀ (i : ι), Antitone fun (x : α) => f x i

Alias of the forward direction of antitone_iff_apply₂.