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₂.