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 #

• Monotone f: A function f between two preorders is monotone if a ≤ b implies f a ≤ f b.
• Antitone f: A function f between two preorders is antitone if a ≤ b implies f b ≤ f a.
• MonotoneOn f s: Same as Monotone f, but for all a, b ∈ s.
• AntitoneOn f s: Same as Antitone f, but for all a, b ∈ s.
• StrictMono f : A function f between two preorders is strictly monotone if a < b implies f a < f b.
• StrictAnti f : A function f between two preorders is strictly antitone if a < b implies f b < f a.
• StrictMonoOn f s: Same as StrictMono f, but for all a, b ∈ s.
• StrictAntiOn f s: Same as StrictAnti f, but for all a, b ∈ s.

Main theorems #

• monotone_nat_of_le_succ, monotone_int_of_le_succ: If f : ℕ → α or f : ℤ → α and f n ≤ f (n + 1) for all n, then f is monotone.
• antitone_nat_of_succ_le, antitone_int_of_succ_le: If f : ℕ → α or f : ℤ → α and f (n + 1) ≤ f n for all n, then f is antitone.
• strictMono_nat_of_lt_succ, strictMono_int_of_lt_succ: If f : ℕ → α or f : ℤ → α and f n < f (n + 1) for all n, then f is strictly monotone.
• strictAnti_nat_of_succ_lt, strictAnti_int_of_succ_lt: If f : ℕ → α or f : ℤ → α and f (n + 1) < f n for all n, then f is strictly antitone.

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.

TODO #

The above theorems are also true in ℕ+, Fin n... To make that work, we need SuccOrder α and IsSuccArchimedean α.

Tags #

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

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

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

Equations
• = ∀ ⦃a b : α⦄, a bf a f b
Instances For
def Antitone {α : Type u} {β : Type v} [] [] (f : αβ) :

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

Equations
• = ∀ ⦃a b : α⦄, a bf b f a
Instances For
def MonotoneOn {α : Type u} {β : Type v} [] [] (f : αβ) (s : Set α) :

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

Equations
• = ∀ ⦃a : α⦄, a s∀ ⦃b : α⦄, b sa bf a f b
Instances For
def AntitoneOn {α : Type u} {β : Type v} [] [] (f : αβ) (s : Set α) :

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

Equations
• = ∀ ⦃a : α⦄, a s∀ ⦃b : α⦄, b sa bf b f a
Instances For
def StrictMono {α : Type u} {β : Type v} [] [] (f : αβ) :

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

Equations
• = ∀ ⦃a b : α⦄, a < bf a < f b
Instances For
def StrictAnti {α : Type u} {β : Type v} [] [] (f : αβ) :

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

Equations
• = ∀ ⦃a b : α⦄, a < bf b < f a
Instances For
def StrictMonoOn {α : Type u} {β : Type v} [] [] (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
• = ∀ ⦃a : α⦄, a s∀ ⦃b : α⦄, b sa < bf a < f b
Instances For
def StrictAntiOn {α : Type u} {β : Type v} [] [] (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
• = ∀ ⦃a : α⦄, a s∀ ⦃b : α⦄, b sa < bf b < f a
Instances For
instance instDecidableMonotoneOfForallForallForallLe {α : Type u} {β : Type v} [] [] {f : αβ} [i : Decidable (∀ (a b : α), a bf a f b)] :
Equations
• instDecidableMonotoneOfForallForallForallLe = i
instance instDecidableAntitoneOfForallForallForallLe {α : Type u} {β : Type v} [] [] {f : αβ} [i : Decidable (∀ (a b : α), a bf b f a)] :
Equations
• instDecidableAntitoneOfForallForallForallLe = i
instance instDecidableMonotoneOnOfForallForallMemSetForallForallForallLe {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} [i : Decidable (∀ (a : α), a s∀ (b : α), b sa bf a f b)] :
Equations
• instDecidableMonotoneOnOfForallForallMemSetForallForallForallLe = i
instance instDecidableAntitoneOnOfForallForallMemSetForallForallForallLe {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} [i : Decidable (∀ (a : α), a s∀ (b : α), b sa bf b f a)] :
Equations
• instDecidableAntitoneOnOfForallForallMemSetForallForallForallLe = i
instance instDecidableStrictMonoOfForallForallForallLt {α : Type u} {β : Type v} [] [] {f : αβ} [i : Decidable (∀ (a b : α), a < bf a < f b)] :
Equations
• instDecidableStrictMonoOfForallForallForallLt = i
instance instDecidableStrictAntiOfForallForallForallLt {α : Type u} {β : Type v} [] [] {f : αβ} [i : Decidable (∀ (a b : α), a < bf b < f a)] :
Equations
• instDecidableStrictAntiOfForallForallForallLt = i
instance instDecidableStrictMonoOnOfForallForallMemSetForallForallForallLt {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} [i : Decidable (∀ (a : α), a s∀ (b : α), b sa < bf a < f b)] :
Equations
• instDecidableStrictMonoOnOfForallForallMemSetForallForallForallLt = i
instance instDecidableStrictAntiOnOfForallForallMemSetForallForallForallLt {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} [i : Decidable (∀ (a : α), a s∀ (b : α), b sa < bf b < f a)] :
Equations
• instDecidableStrictAntiOnOfForallForallMemSetForallForallForallLt = i
theorem monotone_inclusion_le_le_of_le {α : Type u} [] {k : α} {j : α} (hkj : k j) :
Monotone fun (x : { i : α // i k }) => match x with | i, hi => i,
theorem monotone_inclusion_lt_le_of_le {α : Type u} [] {k : α} {j : α} (hkj : k j) :
Monotone fun (x : { i : α // i < k }) => match x with | i, hi => i,
theorem monotone_inclusion_lt_lt_of_le {α : Type u} [] {k : α} {j : α} (hkj : k j) :
Monotone fun (x : { i : α // i < k }) => match x with | i, hi => i,

Monotonicity on the dual order #

Strictly, many of the *On.dual lemmas in this section should use ofDual ⁻¹' s instead of s, but right now this is not possible as Set.preimage is not defined yet, and importing it creates an import cycle.

Often, you should not need the rewriting lemmas. Instead, you probably want to add .dual, .dual_left or .dual_right to your Monotone/Antitone hypothesis.

@[simp]
theorem monotone_comp_ofDual_iff {α : Type u} {β : Type v} [] [] {f : αβ} :
Monotone (f OrderDual.ofDual)
@[simp]
theorem antitone_comp_ofDual_iff {α : Type u} {β : Type v} [] [] {f : αβ} :
Antitone (f OrderDual.ofDual)
@[simp]
theorem monotone_toDual_comp_iff {α : Type u} {β : Type v} [] [] {f : αβ} :
Monotone (OrderDual.toDual f)
@[simp]
theorem antitone_toDual_comp_iff {α : Type u} {β : Type v} [] [] {f : αβ} :
Antitone (OrderDual.toDual f)
@[simp]
theorem monotoneOn_comp_ofDual_iff {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
MonotoneOn (f OrderDual.ofDual) s
@[simp]
theorem antitoneOn_comp_ofDual_iff {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
AntitoneOn (f OrderDual.ofDual) s
@[simp]
theorem monotoneOn_toDual_comp_iff {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
MonotoneOn (OrderDual.toDual f) s
@[simp]
theorem antitoneOn_toDual_comp_iff {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
AntitoneOn (OrderDual.toDual f) s
@[simp]
theorem strictMono_comp_ofDual_iff {α : Type u} {β : Type v} [] [] {f : αβ} :
StrictMono (f OrderDual.ofDual)
@[simp]
theorem strictAnti_comp_ofDual_iff {α : Type u} {β : Type v} [] [] {f : αβ} :
StrictAnti (f OrderDual.ofDual)
@[simp]
theorem strictMono_toDual_comp_iff {α : Type u} {β : Type v} [] [] {f : αβ} :
StrictMono (OrderDual.toDual f)
@[simp]
theorem strictAnti_toDual_comp_iff {α : Type u} {β : Type v} [] [] {f : αβ} :
StrictAnti (OrderDual.toDual f)
@[simp]
theorem strictMonoOn_comp_ofDual_iff {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
StrictMonoOn (f OrderDual.ofDual) s
@[simp]
theorem strictAntiOn_comp_ofDual_iff {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
StrictAntiOn (f OrderDual.ofDual) s
@[simp]
theorem strictMonoOn_toDual_comp_iff {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
StrictMonoOn (OrderDual.toDual f) s
@[simp]
theorem strictAntiOn_toDual_comp_iff {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
StrictAntiOn (OrderDual.toDual f) s
theorem monotone_dual_iff {α : Type u} {β : Type v} [] [] {f : αβ} :
Monotone (OrderDual.toDual f OrderDual.ofDual)
theorem antitone_dual_iff {α : Type u} {β : Type v} [] [] {f : αβ} :
Antitone (OrderDual.toDual f OrderDual.ofDual)
theorem monotoneOn_dual_iff {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
MonotoneOn (OrderDual.toDual f OrderDual.ofDual) s
theorem antitoneOn_dual_iff {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
AntitoneOn (OrderDual.toDual f OrderDual.ofDual) s
theorem strictMono_dual_iff {α : Type u} {β : Type v} [] [] {f : αβ} :
StrictMono (OrderDual.toDual f OrderDual.ofDual)
theorem strictAnti_dual_iff {α : Type u} {β : Type v} [] [] {f : αβ} :
StrictAnti (OrderDual.toDual f OrderDual.ofDual)
theorem strictMonoOn_dual_iff {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
StrictMonoOn (OrderDual.toDual f OrderDual.ofDual) s
theorem strictAntiOn_dual_iff {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
StrictAntiOn (OrderDual.toDual f OrderDual.ofDual) s
theorem Monotone.dual_left {α : Type u} {β : Type v} [] [] {f : αβ} :
Antitone (f OrderDual.ofDual)

Alias of the reverse direction of antitone_comp_ofDual_iff.

theorem Antitone.dual_left {α : Type u} {β : Type v} [] [] {f : αβ} :
Monotone (f OrderDual.ofDual)

Alias of the reverse direction of monotone_comp_ofDual_iff.

theorem Monotone.dual_right {α : Type u} {β : Type v} [] [] {f : αβ} :
Antitone (OrderDual.toDual f)

Alias of the reverse direction of antitone_toDual_comp_iff.

theorem Antitone.dual_right {α : Type u} {β : Type v} [] [] {f : αβ} :
Monotone (OrderDual.toDual f)

Alias of the reverse direction of monotone_toDual_comp_iff.

theorem MonotoneOn.dual_left {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
AntitoneOn (f OrderDual.ofDual) s

Alias of the reverse direction of antitoneOn_comp_ofDual_iff.

theorem AntitoneOn.dual_left {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
MonotoneOn (f OrderDual.ofDual) s

Alias of the reverse direction of monotoneOn_comp_ofDual_iff.

theorem MonotoneOn.dual_right {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
AntitoneOn (OrderDual.toDual f) s

Alias of the reverse direction of antitoneOn_toDual_comp_iff.

theorem AntitoneOn.dual_right {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
MonotoneOn (OrderDual.toDual f) s

Alias of the reverse direction of monotoneOn_toDual_comp_iff.

theorem StrictMono.dual_left {α : Type u} {β : Type v} [] [] {f : αβ} :
StrictAnti (f OrderDual.ofDual)

Alias of the reverse direction of strictAnti_comp_ofDual_iff.

theorem StrictAnti.dual_left {α : Type u} {β : Type v} [] [] {f : αβ} :
StrictMono (f OrderDual.ofDual)

Alias of the reverse direction of strictMono_comp_ofDual_iff.

theorem StrictMono.dual_right {α : Type u} {β : Type v} [] [] {f : αβ} :
StrictAnti (OrderDual.toDual f)

Alias of the reverse direction of strictAnti_toDual_comp_iff.

theorem StrictAnti.dual_right {α : Type u} {β : Type v} [] [] {f : αβ} :
StrictMono (OrderDual.toDual f)

Alias of the reverse direction of strictMono_toDual_comp_iff.

theorem StrictMonoOn.dual_left {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
StrictAntiOn (f OrderDual.ofDual) s

Alias of the reverse direction of strictAntiOn_comp_ofDual_iff.

theorem StrictAntiOn.dual_left {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
StrictMonoOn (f OrderDual.ofDual) s

Alias of the reverse direction of strictMonoOn_comp_ofDual_iff.

theorem StrictMonoOn.dual_right {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
StrictAntiOn (OrderDual.toDual f) s

Alias of the reverse direction of strictAntiOn_toDual_comp_iff.

theorem StrictAntiOn.dual_right {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
StrictMonoOn (OrderDual.toDual f) s

Alias of the reverse direction of strictMonoOn_toDual_comp_iff.

theorem Monotone.dual {α : Type u} {β : Type v} [] [] {f : αβ} :
Monotone (OrderDual.toDual f OrderDual.ofDual)

Alias of the reverse direction of monotone_dual_iff.

theorem Antitone.dual {α : Type u} {β : Type v} [] [] {f : αβ} :
Antitone (OrderDual.toDual f OrderDual.ofDual)

Alias of the reverse direction of antitone_dual_iff.

theorem MonotoneOn.dual {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
MonotoneOn (OrderDual.toDual f OrderDual.ofDual) s

Alias of the reverse direction of monotoneOn_dual_iff.

theorem AntitoneOn.dual {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
AntitoneOn (OrderDual.toDual f OrderDual.ofDual) s

Alias of the reverse direction of antitoneOn_dual_iff.

theorem StrictMono.dual {α : Type u} {β : Type v} [] [] {f : αβ} :
StrictMono (OrderDual.toDual f OrderDual.ofDual)

Alias of the reverse direction of strictMono_dual_iff.

theorem StrictAnti.dual {α : Type u} {β : Type v} [] [] {f : αβ} :
StrictAnti (OrderDual.toDual f OrderDual.ofDual)

Alias of the reverse direction of strictAnti_dual_iff.

theorem StrictMonoOn.dual {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
StrictMonoOn (OrderDual.toDual f OrderDual.ofDual) s

Alias of the reverse direction of strictMonoOn_dual_iff.

theorem StrictAntiOn.dual {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
StrictAntiOn (OrderDual.toDual f OrderDual.ofDual) s

Alias of the reverse direction of strictAntiOn_dual_iff.

Monotonicity in function spaces #

theorem Monotone.comp_le_comp_left {α : Type u} {β : Type v} {γ : Type w} [] [] {f : βα} {g : γβ} {h : γβ} (hf : ) (le_gh : g h) :
f g f h
theorem monotone_lam {α : Type u} {β : Type v} {γ : Type w} [] [] {f : αβγ} (hf : ∀ (b : β), Monotone fun (a : α) => f a b) :
theorem monotone_app {α : Type u} {β : Type v} {γ : Type w} [] [] (f : βαγ) (b : β) (hf : Monotone fun (a : α) (b : β) => f b a) :
Monotone (f b)
theorem antitone_lam {α : Type u} {β : Type v} {γ : Type w} [] [] {f : αβγ} (hf : ∀ (b : β), Antitone fun (a : α) => f a b) :
theorem antitone_app {α : Type u} {β : Type v} {γ : Type w} [] [] (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} [] [] {f : αβ} {a : α} {b : α} (hf : ) (h : a b) :
f a f b
theorem Antitone.imp {α : Type u} {β : Type v} [] [] {f : αβ} {a : α} {b : α} (hf : ) (h : a b) :
f b f a
theorem StrictMono.imp {α : Type u} {β : Type v} [] [] {f : αβ} {a : α} {b : α} (hf : ) (h : a < b) :
f a < f b
theorem StrictAnti.imp {α : Type u} {β : Type v} [] [] {f : αβ} {a : α} {b : α} (hf : ) (h : a < b) :
f b < f a
theorem Monotone.monotoneOn {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) (s : Set α) :
theorem Antitone.antitoneOn {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) (s : Set α) :
@[simp]
theorem monotoneOn_univ {α : Type u} {β : Type v} [] [] {f : αβ} :
MonotoneOn f Set.univ
@[simp]
theorem antitoneOn_univ {α : Type u} {β : Type v} [] [] {f : αβ} :
AntitoneOn f Set.univ
theorem StrictMono.strictMonoOn {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) (s : Set α) :
theorem StrictAnti.strictAntiOn {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) (s : Set α) :
@[simp]
theorem strictMonoOn_univ {α : Type u} {β : Type v} [] [] {f : αβ} :
StrictMonoOn f Set.univ
@[simp]
theorem strictAntiOn_univ {α : Type u} {β : Type v} [] [] {f : αβ} :
StrictAntiOn f Set.univ
theorem Monotone.strictMono_of_injective {α : Type u} {β : Type v} [] [] {f : αβ} (h₁ : ) (h₂ : ) :
theorem Antitone.strictAnti_of_injective {α : Type u} {β : Type v} [] [] {f : αβ} (h₁ : ) (h₂ : ) :
theorem monotone_iff_forall_lt {α : Type u} {β : Type v} [] [] {f : αβ} :
∀ ⦃a b : α⦄, a < bf a f b
theorem antitone_iff_forall_lt {α : Type u} {β : Type v} [] [] {f : αβ} :
∀ ⦃a b : α⦄, a < bf b f a
theorem monotoneOn_iff_forall_lt {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
∀ ⦃a : α⦄, a s∀ ⦃b : α⦄, b sa < bf a f b
theorem antitoneOn_iff_forall_lt {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} :
∀ ⦃a : α⦄, a s∀ ⦃b : α⦄, b sa < bf b f a
theorem StrictMonoOn.monotoneOn {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} (hf : ) :
theorem StrictAntiOn.antitoneOn {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} (hf : ) :
theorem StrictMono.monotone {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) :
theorem StrictAnti.antitone {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) :

Monotonicity from and to subsingletons #

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

Miscellaneous monotonicity results #

theorem monotone_id {α : Type u} [] :
theorem monotoneOn_id {α : Type u} [] {s : Set α} :
theorem strictMono_id {α : Type u} [] :
theorem strictMonoOn_id {α : Type u} [] {s : Set α} :
theorem monotone_const {α : Type u} {β : Type v} [] [] {c : β} :
Monotone fun (x : α) => c
theorem monotoneOn_const {α : Type u} {β : Type v} [] [] {c : β} {s : Set α} :
MonotoneOn (fun (x : α) => c) s
theorem antitone_const {α : Type u} {β : Type v} [] [] {c : β} :
Antitone fun (x : α) => c
theorem antitoneOn_const {α : Type u} {β : Type v} [] [] {c : β} {s : Set α} :
AntitoneOn (fun (x : α) => c) s
theorem strictMono_of_le_iff_le {α : Type u} {β : Type v} [] [] {f : αβ} (h : ∀ (x y : α), x y f x f y) :
theorem strictAnti_of_le_iff_le {α : Type u} {β : Type v} [] [] {f : αβ} (h : ∀ (x y : α), x y f y f x) :
theorem injective_of_lt_imp_ne {α : Type u} {β : Type v} [] {f : αβ} (h : ∀ (x y : α), x < yf x f y) :
theorem injective_of_le_imp_le {α : Type u} {β : Type v} [] [] (f : αβ) (h : ∀ {x y : α}, f x f yx y) :
theorem StrictMono.isMax_of_apply {α : Type u} {β : Type v} [] [] {f : αβ} {a : α} (hf : ) (ha : IsMax (f a)) :
theorem StrictMono.isMin_of_apply {α : Type u} {β : Type v} [] [] {f : αβ} {a : α} (hf : ) (ha : IsMin (f a)) :
theorem StrictAnti.isMax_of_apply {α : Type u} {β : Type v} [] [] {f : αβ} {a : α} (hf : ) (ha : IsMin (f a)) :
theorem StrictAnti.isMin_of_apply {α : Type u} {β : Type v} [] [] {f : αβ} {a : α} (hf : ) (ha : IsMax (f a)) :
theorem StrictMono.add_le_nat {f : } (hf : ) (m : ) (n : ) :
m + f n f (m + n)
theorem StrictMono.ite' {α : Type u} {β : Type v} [] [] {f : αβ} {g : αβ} (hf : ) (hg : ) {p : αProp} [] (hp : ∀ ⦃x y : α⦄, x < yp yp x) (hfg : ∀ ⦃x y : α⦄, p x¬p yx < yf x < g y) :
StrictMono fun (x : α) => if p x then f x else g x
theorem StrictMono.ite {α : Type u} {β : Type v} [] [] {f : αβ} {g : αβ} (hf : ) (hg : ) {p : αProp} [] (hp : ∀ ⦃x y : α⦄, x < yp yp x) (hfg : ∀ (x : α), f x g x) :
StrictMono fun (x : α) => if p x then f x else g x
theorem StrictAnti.ite' {α : Type u} {β : Type v} [] [] {f : αβ} {g : αβ} (hf : ) (hg : ) {p : αProp} [] (hp : ∀ ⦃x y : α⦄, x < yp yp x) (hfg : ∀ ⦃x y : α⦄, p x¬p yx < yg y < f x) :
StrictAnti fun (x : α) => if p x then f x else g x
theorem StrictAnti.ite {α : Type u} {β : Type v} [] [] {f : αβ} {g : αβ} (hf : ) (hg : ) {p : αProp} [] (hp : ∀ ⦃x y : α⦄, x < yp yp x) (hfg : ∀ (x : α), g x f x) :
StrictAnti fun (x : α) => if p x then f x else g x

Monotonicity under composition #

theorem Monotone.comp {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} (hg : ) (hf : ) :
theorem Monotone.comp_antitone {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} (hg : ) (hf : ) :
theorem Antitone.comp {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} (hg : ) (hf : ) :
theorem Antitone.comp_monotone {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} (hg : ) (hf : ) :
theorem Monotone.iterate {α : Type u} [] {f : αα} (hf : ) (n : ) :
theorem Monotone.comp_monotoneOn {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} {s : Set α} (hg : ) (hf : ) :
MonotoneOn (g f) s
theorem Monotone.comp_antitoneOn {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} {s : Set α} (hg : ) (hf : ) :
AntitoneOn (g f) s
theorem Antitone.comp_antitoneOn {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} {s : Set α} (hg : ) (hf : ) :
MonotoneOn (g f) s
theorem Antitone.comp_monotoneOn {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} {s : Set α} (hg : ) (hf : ) :
AntitoneOn (g f) s
theorem StrictMono.comp {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} (hg : ) (hf : ) :
theorem StrictMono.comp_strictAnti {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} (hg : ) (hf : ) :
theorem StrictAnti.comp {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} (hg : ) (hf : ) :
theorem StrictAnti.comp_strictMono {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} (hg : ) (hf : ) :
theorem StrictMono.iterate {α : Type u} [] {f : αα} (hf : ) (n : ) :
theorem StrictMono.comp_strictMonoOn {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} {s : Set α} (hg : ) (hf : ) :
theorem StrictMono.comp_strictAntiOn {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} {s : Set α} (hg : ) (hf : ) :
theorem StrictAnti.comp_strictAntiOn {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} {s : Set α} (hg : ) (hf : ) :
theorem StrictAnti.comp_strictMonoOn {α : Type u} {β : Type v} {γ : Type w} [] [] [] {g : βγ} {f : αβ} {s : Set α} (hg : ) (hf : ) :
theorem List.foldl_monotone {α : Type u} {β : Type v} [] {f : αβα} (H : ∀ (b : β), Monotone fun (a : α) => f a b) (l : List β) :
Monotone fun (a : α) => List.foldl f a l
theorem List.foldr_monotone {α : Type u} {β : Type v} [] {f : αββ} (H : ∀ (a : α), Monotone (f a)) (l : List α) :
Monotone fun (b : β) => List.foldr f b l
theorem List.foldl_strictMono {α : Type u} {β : Type v} [] {f : αβα} (H : ∀ (b : β), StrictMono fun (a : α) => f a b) (l : List β) :
StrictMono fun (a : α) => List.foldl f a l
theorem List.foldr_strictMono {α : Type u} {β : Type v} [] {f : αββ} (H : ∀ (a : α), StrictMono (f a)) (l : List α) :
StrictMono fun (b : β) => List.foldr f b l

Monotonicity in linear orders #

theorem Monotone.reflect_lt {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) {a : α} {b : α} (h : f a < f b) :
a < b
theorem Antitone.reflect_lt {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) {a : α} {b : α} (h : f a < f b) :
b < a
theorem MonotoneOn.reflect_lt {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} (hf : ) {a : α} {b : α} (ha : a s) (hb : b s) (h : f a < f b) :
a < b
theorem AntitoneOn.reflect_lt {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} (hf : ) {a : α} {b : α} (ha : a s) (hb : b s) (h : f a < f b) :
b < a
theorem StrictMonoOn.le_iff_le {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} (hf : ) {a : α} {b : α} (ha : a s) (hb : b s) :
f a f b a b
theorem StrictAntiOn.le_iff_le {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} (hf : ) {a : α} {b : α} (ha : a s) (hb : b s) :
f a f b b a
theorem StrictMonoOn.eq_iff_eq {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} (hf : ) {a : α} {b : α} (ha : a s) (hb : b s) :
f a = f b a = b
theorem StrictAntiOn.eq_iff_eq {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} (hf : ) {a : α} {b : α} (ha : a s) (hb : b s) :
f a = f b b = a
theorem StrictMonoOn.lt_iff_lt {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} (hf : ) {a : α} {b : α} (ha : a s) (hb : b s) :
f a < f b a < b
theorem StrictAntiOn.lt_iff_lt {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} (hf : ) {a : α} {b : α} (ha : a s) (hb : b s) :
f a < f b b < a
theorem StrictMono.le_iff_le {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) {a : α} {b : α} :
f a f b a b
theorem StrictAnti.le_iff_le {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) {a : α} {b : α} :
f a f b b a
theorem StrictMono.lt_iff_lt {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) {a : α} {b : α} :
f a < f b a < b
theorem StrictAnti.lt_iff_lt {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) {a : α} {b : α} :
f a < f b b < a
theorem StrictMonoOn.compares {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} (hf : ) {a : α} {b : α} (ha : a s) (hb : b s) {o : Ordering} :
o.Compares (f a) (f b) o.Compares a b
theorem StrictAntiOn.compares {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} (hf : ) {a : α} {b : α} (ha : a s) (hb : b s) {o : Ordering} :
o.Compares (f a) (f b) o.Compares b a
theorem StrictMono.compares {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) {a : α} {b : α} {o : Ordering} :
o.Compares (f a) (f b) o.Compares a b
theorem StrictAnti.compares {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) {a : α} {b : α} {o : Ordering} :
o.Compares (f a) (f b) o.Compares b a
theorem StrictMono.injective {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) :
theorem StrictAnti.injective {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) :
theorem StrictMono.maximal_of_maximal_image {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) {a : α} (hmax : ∀ (p : β), p f a) (x : α) :
x a
theorem StrictMono.minimal_of_minimal_image {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) {a : α} (hmin : ∀ (p : β), f a p) (x : α) :
a x
theorem StrictAnti.minimal_of_maximal_image {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) {a : α} (hmax : ∀ (p : β), p f a) (x : α) :
a x
theorem StrictAnti.maximal_of_minimal_image {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) {a : α} (hmin : ∀ (p : β), f a p) (x : α) :
x a
theorem Monotone.strictMono_iff_injective {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) :
theorem Antitone.strictAnti_iff_injective {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) :
theorem Monotone.eq_of_le_of_le {α : Type u} {β : Type v} [] [] {f : αβ} {a₁ : α} {a₂ : α} (h_mon : ) (h_fa : f a₁ = f a₂) {i : α} (h₁ : a₁ i) (h₂ : i a₂) :
f i = f a₁

If a monotone function is equal at two points, it is equal between all of them

theorem Antitone.eq_of_le_of_le {α : Type u} {β : Type v} [] [] {f : αβ} {a₁ : α} {a₂ : α} (h_anti : ) (h_fa : f a₁ = f a₂) {i : α} (h₁ : a₁ i) (h₂ : i a₂) :
f i = f a₁

If an antitone function is equal at two points, it is equal between all of them

theorem not_monotone_not_antitone_iff_exists_le_le {α : Type u} {β : Type v} [] [] {f : αβ} :
∃ (a : α), ∃ (b : α), ∃ (c : α), a b b c (f a < f b f c < f b f b < f a f b < f c)

A function between linear orders which is neither monotone nor antitone makes a dent upright or downright.

theorem not_monotone_not_antitone_iff_exists_lt_lt {α : Type u} {β : Type v} [] [] {f : αβ} :
∃ (a : α), ∃ (b : α), ∃ (c : α), a < b b < c (f a < f b f c < f b f b < f a f b < f c)

A function between linear orders which is neither monotone nor antitone makes a dent upright or downright.

Strictly monotone functions and cmp#

theorem StrictMonoOn.cmp_map_eq {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} {x : α} {y : α} (hf : ) (hx : x s) (hy : y s) :
cmp (f x) (f y) = cmp x y
theorem StrictMono.cmp_map_eq {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) (x : α) (y : α) :
cmp (f x) (f y) = cmp x y
theorem StrictAntiOn.cmp_map_eq {α : Type u} {β : Type v} [] [] {f : αβ} {s : Set α} {x : α} {y : α} (hf : ) (hx : x s) (hy : y s) :
cmp (f x) (f y) = cmp y x
theorem StrictAnti.cmp_map_eq {α : Type u} {β : Type v} [] [] {f : αβ} (hf : ) (x : α) (y : α) :
cmp (f x) (f y) = cmp y x

Monotonicity in ℕ and ℤ#

theorem Nat.rel_of_forall_rel_succ_of_le_of_lt {β : Type v} (r : ββProp) [IsTrans β r] {f : β} {a : } (h : ∀ (n : ), a nr (f n) (f (n + 1))) ⦃b : ⦃c : (hab : a b) (hbc : b < c) :
r (f b) (f c)
theorem Nat.rel_of_forall_rel_succ_of_le_of_le {β : Type v} (r : ββProp) [IsRefl β r] [IsTrans β r] {f : β} {a : } (h : ∀ (n : ), a nr (f n) (f (n + 1))) ⦃b : ⦃c : (hab : a b) (hbc : b c) :
r (f b) (f c)
theorem Nat.rel_of_forall_rel_succ_of_lt {β : Type v} (r : ββProp) [IsTrans β r] {f : β} (h : ∀ (n : ), r (f n) (f (n + 1))) ⦃a : ⦃b : (hab : a < b) :
r (f a) (f b)
theorem Nat.rel_of_forall_rel_succ_of_le {β : Type v} (r : ββProp) [IsRefl β r] [IsTrans β r] {f : β} (h : ∀ (n : ), r (f n) (f (n + 1))) ⦃a : ⦃b : (hab : a b) :
r (f a) (f b)
theorem monotone_nat_of_le_succ {α : Type u} [] {f : α} (hf : ∀ (n : ), f n f (n + 1)) :
theorem antitone_nat_of_succ_le {α : Type u} [] {f : α} (hf : ∀ (n : ), f (n + 1) f n) :
theorem strictMono_nat_of_lt_succ {α : Type u} [] {f : α} (hf : ∀ (n : ), f n < f (n + 1)) :
theorem strictAnti_nat_of_succ_lt {α : Type u} [] {f : α} (hf : ∀ (n : ), f (n + 1) < f n) :
theorem Nat.exists_strictMono' {α : Type u} [] [] (a : α) :
∃ (f : α), f 0 = a

If α is a preorder with no maximal elements, then there exists a strictly monotone function ℕ → α with any prescribed value of f 0.

theorem Nat.exists_strictAnti' {α : Type u} [] [] (a : α) :
∃ (f : α), f 0 = a

If α is a preorder with no maximal elements, then there exists a strictly antitone function ℕ → α with any prescribed value of f 0.

theorem Nat.exists_strictMono (α : Type u) [] [] [] :
∃ (f : α),

If α is a nonempty preorder with no maximal elements, then there exists a strictly monotone function ℕ → α.

theorem Nat.exists_strictAnti (α : Type u) [] [] [] :
∃ (f : α),

If α is a nonempty preorder with no minimal elements, then there exists a strictly antitone function ℕ → α.

theorem Int.rel_of_forall_rel_succ_of_lt {β : Type v} (r : ββProp) [IsTrans β r] {f : β} (h : ∀ (n : ), r (f n) (f (n + 1))) ⦃a : ⦃b : (hab : a < b) :
r (f a) (f b)
theorem Int.rel_of_forall_rel_succ_of_le {β : Type v} (r : ββProp) [IsRefl β r] [IsTrans β r] {f : β} (h : ∀ (n : ), r (f n) (f (n + 1))) ⦃a : ⦃b : (hab : a b) :
r (f a) (f b)
theorem monotone_int_of_le_succ {α : Type u} [] {f : α} (hf : ∀ (n : ), f n f (n + 1)) :
theorem antitone_int_of_succ_le {α : Type u} [] {f : α} (hf : ∀ (n : ), f (n + 1) f n) :
theorem strictMono_int_of_lt_succ {α : Type u} [] {f : α} (hf : ∀ (n : ), f n < f (n + 1)) :
theorem strictAnti_int_of_succ_lt {α : Type u} [] {f : α} (hf : ∀ (n : ), f (n + 1) < f n) :
theorem Int.exists_strictMono (α : Type u) [] [] [] [] :
∃ (f : α),

If α is a nonempty preorder with no minimal or maximal elements, then there exists a strictly monotone function f : ℤ → α.

theorem Int.exists_strictAnti (α : Type u) [] [] [] [] :
∃ (f : α),

If α is a nonempty preorder with no minimal or maximal elements, then there exists a strictly antitone function f : ℤ → α.

theorem Monotone.ne_of_lt_of_lt_nat {α : Type u} [] {f : α} (hf : ) (n : ) {x : α} (h1 : f n < x) (h2 : x < f (n + 1)) (a : ) :
f a x

If f is a monotone function from ℕ to a preorder such that x lies between f n and f (n + 1), then x doesn't lie in the range of f.

theorem Antitone.ne_of_lt_of_lt_nat {α : Type u} [] {f : α} (hf : ) (n : ) {x : α} (h1 : f (n + 1) < x) (h2 : x < f n) (a : ) :
f a x

If f is an antitone function from ℕ to a preorder such that x lies between f (n + 1) and f n, then x doesn't lie in the range of f.

theorem Monotone.ne_of_lt_of_lt_int {α : Type u} [] {f : α} (hf : ) (n : ) {x : α} (h1 : f n < x) (h2 : x < f (n + 1)) (a : ) :
f a x

If f is a monotone function from ℤ to a preorder and x lies between f n and f (n + 1), then x doesn't lie in the range of f.

theorem Antitone.ne_of_lt_of_lt_int {α : Type u} [] {f : α} (hf : ) (n : ) {x : α} (h1 : f (n + 1) < x) (h2 : x < f n) (a : ) :
f a x

If f is an antitone function from ℤ to a preorder and x lies between f (n + 1) and f n, then x doesn't lie in the range of f.

theorem Subtype.mono_coe {α : Type u} [] (t : Set α) :
Monotone Subtype.val
theorem Subtype.strictMono_coe {α : Type u} [] (t : Set α) :
StrictMono Subtype.val
theorem monotone_fst {α : Type u} {β : Type v} [] [] :
Monotone Prod.fst
theorem monotone_snd {α : Type u} {β : Type v} [] [] :
Monotone Prod.snd
theorem Monotone.prod_map {α : Type u} {β : Type v} {γ : Type w} {δ : Type u_2} [] [] [] [] {f : αγ} {g : βδ} (hf : ) (hg : ) :
theorem Antitone.prod_map {α : Type u} {β : Type v} {γ : Type w} {δ : Type u_2} [] [] [] [] {f : αγ} {g : βδ} (hf : ) (hg : ) :
theorem StrictMono.prod_map {α : Type u} {β : Type v} {γ : Type w} {δ : Type u_2} [] [] [] [] {f : αγ} {g : βδ} (hf : ) (hg : ) :
theorem StrictAnti.prod_map {α : Type u} {β : Type v} {γ : Type w} {δ : Type u_2} [] [] [] [] {f : αγ} {g : βδ} (hf : ) (hg : ) :

Pi types #

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

Alias of the forward direction of monotone_iff_apply₂.

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

Alias of the reverse direction of monotone_iff_apply₂.

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

Alias of the reverse direction of antitone_iff_apply₂.

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

Alias of the forward direction of antitone_iff_apply₂.