Documentation

Mathlib.Order.ConditionallyCompleteLattice.Basic

Theory of conditionally complete lattices #

A conditionally complete lattice is a lattice in which every non-empty bounded subset s has a least upper bound and a greatest lower bound, denoted below by sSup s and sInf s. Typical examples are , , and with their usual orders.

The theory is very comparable to the theory of complete lattices, except that suitable boundedness and nonemptiness assumptions have to be added to most statements. We express these using the BddAbove and BddBelow predicates, which we use to prove most useful properties of sSup and sInf in conditionally complete lattices.

To differentiate the statements between complete lattices and conditionally complete lattices, we prefix sInf and sSup in the statements by c, giving csInf and csSup. For instance, sInf_le is a statement in complete lattices ensuring sInf s ≤ x, while csInf_le is the same statement in conditionally complete lattices with an additional assumption that s is bounded below.

Extension of sSup and sInf from a preorder α to WithTop α and WithBot α

noncomputable instance WithTop.instSupSet {α : Type u_1} [Preorder α] [SupSet α] :
Equations
noncomputable instance WithTop.instInfSet {α : Type u_1} [Preorder α] [InfSet α] :
Equations
noncomputable instance WithBot.instSupSet {α : Type u_1} [Preorder α] [SupSet α] :
Equations
  • WithBot.instSupSet = { sSup := sInf }
noncomputable instance WithBot.instInfSet {α : Type u_1} [Preorder α] [InfSet α] :
Equations
  • WithBot.instInfSet = { sInf := sSup }
theorem WithTop.sSup_eq {α : Type u_1} [Preorder α] [SupSet α] {s : Set (WithTop α)} (hs : s) (hs' : BddAbove (WithTop.some ⁻¹' s)) :
sSup s = (sSup (WithTop.some ⁻¹' s))
theorem WithTop.sInf_eq {α : Type u_1} [Preorder α] [InfSet α] {s : Set (WithTop α)} (hs : ¬s {}) (h's : BddBelow s) :
sInf s = (sInf (WithTop.some ⁻¹' s))
theorem WithBot.sInf_eq {α : Type u_1} [Preorder α] [InfSet α] {s : Set (WithBot α)} (hs : s) (hs' : BddBelow (WithBot.some ⁻¹' s)) :
sInf s = (sInf (WithBot.some ⁻¹' s))
theorem WithBot.sSup_eq {α : Type u_1} [Preorder α] [SupSet α] {s : Set (WithBot α)} (hs : ¬s {}) (h's : BddAbove s) :
sSup s = (sSup (WithBot.some ⁻¹' s))
@[simp]
theorem WithTop.sInf_empty {α : Type u_1} [Preorder α] [InfSet α] :
theorem WithTop.coe_sInf' {α : Type u_1} [Preorder α] [InfSet α] {s : Set α} (hs : s.Nonempty) (h's : BddBelow s) :
(sInf s) = sInf ((fun (a : α) => a) '' s)
theorem WithTop.coe_sSup' {α : Type u_1} [Preorder α] [SupSet α] {s : Set α} (hs : BddAbove s) :
(sSup s) = sSup ((fun (a : α) => a) '' s)
@[simp]
theorem WithBot.sSup_empty {α : Type u_1} [Preorder α] [SupSet α] :
@[deprecated WithBot.sSup_empty]
theorem WithBot.csSup_empty {α : Type u_1} [Preorder α] [SupSet α] :

Alias of WithBot.sSup_empty.

theorem WithBot.coe_sSup' {α : Type u_1} [Preorder α] [SupSet α] {s : Set α} (hs : s.Nonempty) (h's : BddAbove s) :
(sSup s) = sSup ((fun (a : α) => a) '' s)
theorem WithBot.coe_sInf' {α : Type u_1} [Preorder α] [InfSet α] {s : Set α} (hs : BddBelow s) :
(sInf s) = sInf ((fun (a : α) => a) '' s)

A conditionally complete lattice is a lattice in which every nonempty subset which is bounded above has a supremum, and every nonempty subset which is bounded below has an infimum. Typical examples are real numbers or natural numbers.

To differentiate the statements from the corresponding statements in (unconditional) complete lattices, we prefix sInf and sSup by a c everywhere. The same statements should hold in both worlds, sometimes with additional assumptions of nonemptiness or boundedness.

    Instances
      theorem ConditionallyCompleteLattice.le_csSup {α : Type u_5} [self : ConditionallyCompleteLattice α] (s : Set α) (a : α) :
      BddAbove sa sa sSup s

      a ≤ sSup s for all a ∈ s.

      theorem ConditionallyCompleteLattice.csSup_le {α : Type u_5} [self : ConditionallyCompleteLattice α] (s : Set α) (a : α) :
      s.Nonemptya upperBounds ssSup s a

      sSup s ≤ a for all a ∈ upperBounds s.

      theorem ConditionallyCompleteLattice.csInf_le {α : Type u_5} [self : ConditionallyCompleteLattice α] (s : Set α) (a : α) :
      BddBelow sa ssInf s a

      sInf s ≤ a for all a ∈ s.

      theorem ConditionallyCompleteLattice.le_csInf {α : Type u_5} [self : ConditionallyCompleteLattice α] (s : Set α) (a : α) :
      s.Nonemptya lowerBounds sa sInf s

      a ≤ sInf s for all a ∈ lowerBounds s.

      A conditionally complete linear order is a linear order in which every nonempty subset which is bounded above has a supremum, and every nonempty subset which is bounded below has an infimum. Typical examples are real numbers or natural numbers.

      To differentiate the statements from the corresponding statements in (unconditional) complete linear orders, we prefix sInf and sSup by a c everywhere. The same statements should hold in both worlds, sometimes with additional assumptions of nonemptiness or boundedness.

        Instances

          If a set is not bounded above, its supremum is by convention sSup ∅.

          If a set is not bounded below, its infimum is by convention sInf ∅.

          Equations
          • One or more equations did not get rendered due to their size.

          A conditionally complete linear order with Bot is a linear order with least element, in which every nonempty subset which is bounded above has a supremum, and every nonempty subset (necessarily bounded below) has an infimum. A typical example is the natural numbers.

          To differentiate the statements from the corresponding statements in (unconditional) complete linear orders, we prefix sInf and sSup by a c everywhere. The same statements should hold in both worlds, sometimes with additional assumptions of nonemptiness or boundedness.

            Instances

              The supremum of the empty set is special-cased to

              @[instance 100]

              A complete lattice is a conditionally complete lattice, as there are no restrictions on the properties of sInf and sSup in a complete lattice.

              Equations
              @[instance 100]
              Equations
              @[reducible, inline]

              A well founded linear order is conditionally complete, with a bottom element.

              Equations
              Instances For
                def conditionallyCompleteLatticeOfsSup (α : Type u_5) [H1 : PartialOrder α] [H2 : SupSet α] (bddAbove_pair : ∀ (a b : α), BddAbove {a, b}) (bddBelow_pair : ∀ (a b : α), BddBelow {a, b}) (isLUB_sSup : ∀ (s : Set α), BddAbove ss.NonemptyIsLUB s (sSup s)) :

                Create a ConditionallyCompleteLattice from a PartialOrder and sup function that returns the least upper bound of a nonempty set which is bounded above. Usually this constructor provides poor definitional equalities. If other fields are known explicitly, they should be provided; for example, if inf is known explicitly, construct the ConditionallyCompleteLattice instance as

                instance : ConditionallyCompleteLattice my_T :=
                  { inf := better_inf,
                    le_inf := ...,
                    inf_le_right := ...,
                    inf_le_left := ...
                    -- don't care to fix sup, sInf
                    ..conditionallyCompleteLatticeOfsSup my_T _ }
                
                Equations
                Instances For
                  def conditionallyCompleteLatticeOfsInf (α : Type u_5) [H1 : PartialOrder α] [H2 : InfSet α] (bddAbove_pair : ∀ (a b : α), BddAbove {a, b}) (bddBelow_pair : ∀ (a b : α), BddBelow {a, b}) (isGLB_sInf : ∀ (s : Set α), BddBelow ss.NonemptyIsGLB s (sInf s)) :

                  Create a ConditionallyCompleteLattice from a PartialOrder and inf function that returns the greatest lower bound of a nonempty set which is bounded below. Usually this constructor provides poor definitional equalities. If other fields are known explicitly, they should be provided; for example, if inf is known explicitly, construct the ConditionallyCompleteLattice instance as

                  instance : ConditionallyCompleteLattice my_T :=
                    { inf := better_inf,
                      le_inf := ...,
                      inf_le_right := ...,
                      inf_le_left := ...
                      -- don't care to fix sup, sSup
                      ..conditionallyCompleteLatticeOfsInf my_T _ }
                  
                  Equations
                  Instances For
                    def conditionallyCompleteLatticeOfLatticeOfsSup (α : Type u_5) [H1 : Lattice α] [SupSet α] (isLUB_sSup : ∀ (s : Set α), BddAbove ss.NonemptyIsLUB s (sSup s)) :

                    A version of conditionallyCompleteLatticeOfsSup when we already know that α is a lattice.

                    This should only be used when it is both hard and unnecessary to provide inf explicitly.

                    Equations
                    Instances For
                      def conditionallyCompleteLatticeOfLatticeOfsInf (α : Type u_5) [H1 : Lattice α] [InfSet α] (isGLB_sInf : ∀ (s : Set α), BddBelow ss.NonemptyIsGLB s (sInf s)) :

                      A version of conditionallyCompleteLatticeOfsInf when we already know that α is a lattice.

                      This should only be used when it is both hard and unnecessary to provide sup explicitly.

                      Equations
                      Instances For
                        theorem le_csSup {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (h₁ : BddAbove s) (h₂ : a s) :
                        a sSup s
                        theorem csSup_le {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (h₁ : s.Nonempty) (h₂ : bs, b a) :
                        sSup s a
                        theorem csInf_le {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (h₁ : BddBelow s) (h₂ : a s) :
                        sInf s a
                        theorem le_csInf {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (h₁ : s.Nonempty) (h₂ : bs, a b) :
                        a sInf s
                        theorem le_csSup_of_le {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} {b : α} (hs : BddAbove s) (hb : b s) (h : a b) :
                        a sSup s
                        theorem csInf_le_of_le {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} {b : α} (hs : BddBelow s) (hb : b s) (h : b a) :
                        sInf s a
                        theorem csSup_le_csSup {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {t : Set α} (ht : BddAbove t) (hs : s.Nonempty) (h : s t) :
                        theorem csInf_le_csInf {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {t : Set α} (ht : BddBelow t) (hs : s.Nonempty) (h : s t) :
                        theorem le_csSup_iff {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (h : BddAbove s) (hs : s.Nonempty) :
                        a sSup s bupperBounds s, a b
                        theorem csInf_le_iff {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (h : BddBelow s) (hs : s.Nonempty) :
                        sInf s a blowerBounds s, b a
                        theorem isLUB_csSup {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} (ne : s.Nonempty) (H : BddAbove s) :
                        IsLUB s (sSup s)
                        theorem isGLB_csInf {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} (ne : s.Nonempty) (H : BddBelow s) :
                        IsGLB s (sInf s)
                        theorem IsLUB.csSup_eq {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (H : IsLUB s a) (ne : s.Nonempty) :
                        sSup s = a
                        theorem IsGreatest.csSup_eq {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (H : IsGreatest s a) :
                        sSup s = a

                        A greatest element of a set is the supremum of this set.

                        theorem IsGreatest.csSup_mem {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (H : IsGreatest s a) :
                        sSup s s
                        theorem IsGLB.csInf_eq {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (H : IsGLB s a) (ne : s.Nonempty) :
                        sInf s = a
                        theorem IsLeast.csInf_eq {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (H : IsLeast s a) :
                        sInf s = a

                        A least element of a set is the infimum of this set.

                        theorem IsLeast.csInf_mem {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (H : IsLeast s a) :
                        sInf s s
                        theorem subset_Icc_csInf_csSup {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} (hb : BddBelow s) (ha : BddAbove s) :
                        s Set.Icc (sInf s) (sSup s)
                        theorem csSup_le_iff {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (hb : BddAbove s) (hs : s.Nonempty) :
                        sSup s a bs, b a
                        theorem le_csInf_iff {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (hb : BddBelow s) (hs : s.Nonempty) :
                        a sInf s bs, a b
                        theorem csSup_lowerBounds_eq_csInf {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} (h : BddBelow s) (hs : s.Nonempty) :
                        theorem csInf_upperBounds_eq_csSup {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} (h : BddAbove s) (hs : s.Nonempty) :
                        @[deprecated csSup_lowerBounds_eq_csInf]
                        theorem csSup_lower_bounds_eq_csInf {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} (h : BddBelow s) (hs : s.Nonempty) :

                        Alias of csSup_lowerBounds_eq_csInf.

                        @[deprecated csInf_upperBounds_eq_csSup]
                        theorem csInf_upper_bounds_eq_csSup {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} (h : BddAbove s) (hs : s.Nonempty) :

                        Alias of csInf_upperBounds_eq_csSup.

                        theorem csSup_lowerBounds_range {α : Type u_1} {β : Type u_2} [ConditionallyCompleteLattice α] [Nonempty β] {f : βα} (hf : BddBelow (Set.range f)) :
                        sSup (lowerBounds (Set.range f)) = ⨅ (i : β), f i
                        theorem csInf_upperBounds_range {α : Type u_1} {β : Type u_2} [ConditionallyCompleteLattice α] [Nonempty β] {f : βα} (hf : BddAbove (Set.range f)) :
                        sInf (upperBounds (Set.range f)) = ⨆ (i : β), f i
                        theorem not_mem_of_lt_csInf {α : Type u_1} [ConditionallyCompleteLattice α] {x : α} {s : Set α} (h : x < sInf s) (hs : BddBelow s) :
                        xs
                        theorem not_mem_of_csSup_lt {α : Type u_1} [ConditionallyCompleteLattice α] {x : α} {s : Set α} (h : sSup s < x) (hs : BddAbove s) :
                        xs
                        theorem csSup_eq_of_forall_le_of_forall_lt_exists_gt {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {b : α} (hs : s.Nonempty) (H : as, a b) (H' : w < b, as, w < a) :
                        sSup s = b

                        Introduction rule to prove that b is the supremum of s: it suffices to check that b is larger than all elements of s, and that this is not the case of any w<b. See sSup_eq_of_forall_le_of_forall_lt_exists_gt for a version in complete lattices.

                        theorem csInf_eq_of_forall_ge_of_forall_gt_exists_lt {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {b : α} :
                        s.Nonempty(∀ as, b a)(∀ (w : α), b < was, a < w)sInf s = b

                        Introduction rule to prove that b is the infimum of s: it suffices to check that b is smaller than all elements of s, and that this is not the case of any w>b. See sInf_eq_of_forall_ge_of_forall_gt_exists_lt for a version in complete lattices.

                        theorem lt_csSup_of_lt {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} {b : α} (hs : BddAbove s) (ha : a s) (h : b < a) :
                        b < sSup s

                        b < sSup s when there is an element a in s with b < a, when s is bounded above. This is essentially an iff, except that the assumptions for the two implications are slightly different (one needs boundedness above for one direction, nonemptiness and linear order for the other one), so we formulate separately the two implications, contrary to the CompleteLattice case.

                        theorem csInf_lt_of_lt {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} {b : α} :
                        BddBelow sa sa < bsInf s < b

                        sInf s < b when there is an element a in s with a < b, when s is bounded below. This is essentially an iff, except that the assumptions for the two implications are slightly different (one needs boundedness below for one direction, nonemptiness and linear order for the other one), so we formulate separately the two implications, contrary to the CompleteLattice case.

                        theorem exists_between_of_forall_le {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {t : Set α} (sne : s.Nonempty) (tne : t.Nonempty) (hst : xs, yt, x y) :
                        (upperBounds s lowerBounds t).Nonempty

                        If all elements of a nonempty set s are less than or equal to all elements of a nonempty set t, then there exists an element between these sets.

                        @[simp]
                        theorem csSup_singleton {α : Type u_1} [ConditionallyCompleteLattice α] (a : α) :
                        sSup {a} = a

                        The supremum of a singleton is the element of the singleton

                        @[simp]
                        theorem csInf_singleton {α : Type u_1} [ConditionallyCompleteLattice α] (a : α) :
                        sInf {a} = a

                        The infimum of a singleton is the element of the singleton

                        @[simp]
                        theorem csSup_pair {α : Type u_1} [ConditionallyCompleteLattice α] (a : α) (b : α) :
                        sSup {a, b} = a b
                        @[simp]
                        theorem csInf_pair {α : Type u_1} [ConditionallyCompleteLattice α] (a : α) (b : α) :
                        sInf {a, b} = a b
                        theorem csInf_le_csSup {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} (hb : BddBelow s) (ha : BddAbove s) (ne : s.Nonempty) :

                        If a set is bounded below and above, and nonempty, its infimum is less than or equal to its supremum.

                        theorem csSup_union {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {t : Set α} (hs : BddAbove s) (sne : s.Nonempty) (ht : BddAbove t) (tne : t.Nonempty) :
                        sSup (s t) = sSup s sSup t

                        The sSup of a union of two sets is the max of the suprema of each subset, under the assumptions that all sets are bounded above and nonempty.

                        theorem csInf_union {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {t : Set α} (hs : BddBelow s) (sne : s.Nonempty) (ht : BddBelow t) (tne : t.Nonempty) :
                        sInf (s t) = sInf s sInf t

                        The sInf of a union of two sets is the min of the infima of each subset, under the assumptions that all sets are bounded below and nonempty.

                        theorem csSup_inter_le {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {t : Set α} (hs : BddAbove s) (ht : BddAbove t) (hst : (s t).Nonempty) :
                        sSup (s t) sSup s sSup t

                        The supremum of an intersection of two sets is bounded by the minimum of the suprema of each set, if all sets are bounded above and nonempty.

                        theorem le_csInf_inter {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {t : Set α} :
                        BddBelow sBddBelow t(s t).NonemptysInf s sInf t sInf (s t)

                        The infimum of an intersection of two sets is bounded below by the maximum of the infima of each set, if all sets are bounded below and nonempty.

                        theorem csSup_insert {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (hs : BddAbove s) (sne : s.Nonempty) :
                        sSup (insert a s) = a sSup s

                        The supremum of insert a s is the maximum of a and the supremum of s, if s is nonempty and bounded above.

                        theorem csInf_insert {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {a : α} (hs : BddBelow s) (sne : s.Nonempty) :
                        sInf (insert a s) = a sInf s

                        The infimum of insert a s is the minimum of a and the infimum of s, if s is nonempty and bounded below.

                        @[simp]
                        theorem csInf_Icc {α : Type u_1} [ConditionallyCompleteLattice α] {a : α} {b : α} (h : a b) :
                        sInf (Set.Icc a b) = a
                        @[simp]
                        theorem csInf_Ici {α : Type u_1} [ConditionallyCompleteLattice α] {a : α} :
                        sInf (Set.Ici a) = a
                        @[simp]
                        theorem csInf_Ico {α : Type u_1} [ConditionallyCompleteLattice α] {a : α} {b : α} (h : a < b) :
                        sInf (Set.Ico a b) = a
                        @[simp]
                        theorem csInf_Ioc {α : Type u_1} [ConditionallyCompleteLattice α] {a : α} {b : α} [DenselyOrdered α] (h : a < b) :
                        sInf (Set.Ioc a b) = a
                        @[simp]
                        theorem csInf_Ioi {α : Type u_1} [ConditionallyCompleteLattice α] {a : α} [NoMaxOrder α] [DenselyOrdered α] :
                        sInf (Set.Ioi a) = a
                        @[simp]
                        theorem csInf_Ioo {α : Type u_1} [ConditionallyCompleteLattice α] {a : α} {b : α} [DenselyOrdered α] (h : a < b) :
                        sInf (Set.Ioo a b) = a
                        @[simp]
                        theorem csSup_Icc {α : Type u_1} [ConditionallyCompleteLattice α] {a : α} {b : α} (h : a b) :
                        sSup (Set.Icc a b) = b
                        @[simp]
                        theorem csSup_Ico {α : Type u_1} [ConditionallyCompleteLattice α] {a : α} {b : α} [DenselyOrdered α] (h : a < b) :
                        sSup (Set.Ico a b) = b
                        @[simp]
                        theorem csSup_Iic {α : Type u_1} [ConditionallyCompleteLattice α] {a : α} :
                        sSup (Set.Iic a) = a
                        @[simp]
                        theorem csSup_Iio {α : Type u_1} [ConditionallyCompleteLattice α] {a : α} [NoMinOrder α] [DenselyOrdered α] :
                        sSup (Set.Iio a) = a
                        @[simp]
                        theorem csSup_Ioc {α : Type u_1} [ConditionallyCompleteLattice α] {a : α} {b : α} (h : a < b) :
                        sSup (Set.Ioc a b) = b
                        @[simp]
                        theorem csSup_Ioo {α : Type u_1} [ConditionallyCompleteLattice α] {a : α} {b : α} [DenselyOrdered α] (h : a < b) :
                        sSup (Set.Ioo a b) = b
                        theorem csSup_eq_of_is_forall_le_of_forall_le_imp_ge {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} {b : α} (hs : s.Nonempty) (h_is_ub : as, a b) (h_b_le_ub : ∀ (ub : α), (∀ as, a ub)b ub) :
                        sSup s = b

                        Introduction rule to prove that b is the supremum of s: it suffices to check that

                        1. b is an upper bound
                        2. every other upper bound b' satisfies b ≤ b'.
                        theorem sup_eq_top_of_top_mem {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} [OrderTop α] (h : s) :
                        theorem inf_eq_bot_of_bot_mem {α : Type u_1} [ConditionallyCompleteLattice α] {s : Set α} [OrderBot α] (h : s) :
                        instance Pi.conditionallyCompleteLattice {ι : Type u_5} {α : ιType u_6} [(i : ι) → ConditionallyCompleteLattice (α i)] :
                        ConditionallyCompleteLattice ((i : ι) → α i)
                        Equations
                        theorem exists_lt_of_lt_csSup {α : Type u_1} [ConditionallyCompleteLinearOrder α] {s : Set α} {b : α} (hs : s.Nonempty) (hb : b < sSup s) :
                        as, b < a

                        When b < sSup s, there is an element a in s with b < a, if s is nonempty and the order is a linear order.

                        theorem exists_lt_of_csInf_lt {α : Type u_1} [ConditionallyCompleteLinearOrder α] {s : Set α} {b : α} (hs : s.Nonempty) (hb : sInf s < b) :
                        as, a < b

                        When sInf s < b, there is an element a in s with a < b, if s is nonempty and the order is a linear order.

                        theorem lt_csSup_iff {α : Type u_1} [ConditionallyCompleteLinearOrder α] {s : Set α} {a : α} (hb : BddAbove s) (hs : s.Nonempty) :
                        a < sSup s bs, a < b
                        theorem csInf_lt_iff {α : Type u_1} [ConditionallyCompleteLinearOrder α] {s : Set α} {a : α} (hb : BddBelow s) (hs : s.Nonempty) :
                        sInf s < a bs, b < a
                        theorem csSup_eq_csSup_of_forall_exists_le {α : Type u_1} [ConditionallyCompleteLinearOrder α] {s : Set α} {t : Set α} (hs : xs, yt, x y) (ht : yt, xs, y x) :
                        sSup s = sSup t

                        When every element of a set s is bounded by an element of a set t, and conversely, then s and t have the same supremum. This holds even when the sets may be empty or unbounded.

                        theorem csInf_eq_csInf_of_forall_exists_le {α : Type u_1} [ConditionallyCompleteLinearOrder α] {s : Set α} {t : Set α} (hs : xs, yt, y x) (ht : yt, xs, x y) :
                        sInf s = sInf t

                        When every element of a set s is bounded by an element of a set t, and conversely, then s and t have the same infimum. This holds even when the sets may be empty or unbounded.

                        theorem sSup_iUnion_Iic {α : Type u_1} {ι : Sort u_4} [ConditionallyCompleteLinearOrder α] (f : ια) :
                        sSup (⋃ (i : ι), Set.Iic (f i)) = ⨆ (i : ι), f i
                        theorem sInf_iUnion_Ici {α : Type u_1} {ι : Sort u_4} [ConditionallyCompleteLinearOrder α] (f : ια) :
                        sInf (⋃ (i : ι), Set.Ici (f i)) = ⨅ (i : ι), f i
                        theorem sInf_eq_argmin_on {α : Type u_1} [ConditionallyCompleteLinearOrder α] {s : Set α} [WellFoundedLT α] (hs : s.Nonempty) :
                        sInf s = Function.argminOn id s hs
                        theorem isLeast_csInf {α : Type u_1} [ConditionallyCompleteLinearOrder α] {s : Set α} [WellFoundedLT α] (hs : s.Nonempty) :
                        theorem le_csInf_iff' {α : Type u_1} [ConditionallyCompleteLinearOrder α] {s : Set α} {b : α} [WellFoundedLT α] (hs : s.Nonempty) :
                        theorem csInf_mem {α : Type u_1} [ConditionallyCompleteLinearOrder α] {s : Set α} [WellFoundedLT α] (hs : s.Nonempty) :
                        sInf s s
                        theorem MonotoneOn.map_csInf {α : Type u_1} [ConditionallyCompleteLinearOrder α] {s : Set α} [WellFoundedLT α] {β : Type u_5} [ConditionallyCompleteLattice β] {f : αβ} (hf : MonotoneOn f s) (hs : s.Nonempty) :
                        f (sInf s) = sInf (f '' s)
                        theorem Monotone.map_csInf {α : Type u_1} [ConditionallyCompleteLinearOrder α] {s : Set α} [WellFoundedLT α] {β : Type u_5} [ConditionallyCompleteLattice β] {f : αβ} (hf : Monotone f) (hs : s.Nonempty) :
                        f (sInf s) = sInf (f '' s)

                        Lemmas about a conditionally complete linear order with bottom element #

                        In this case we have Sup ∅ = ⊥, so we can drop some Nonempty/Set.Nonempty assumptions.

                        @[simp]
                        theorem csInf_univ {α : Type u_1} [ConditionallyCompleteLinearOrder α] [OrderBot α] :
                        sInf Set.univ =
                        theorem isLUB_csSup' {α : Type u_1} [ConditionallyCompleteLinearOrderBot α] {s : Set α} (hs : BddAbove s) :
                        IsLUB s (sSup s)
                        theorem csSup_le_iff' {α : Type u_1} [ConditionallyCompleteLinearOrderBot α] {s : Set α} (hs : BddAbove s) {a : α} :
                        sSup s a xs, x a

                        In conditionally complete orders with a bottom element, the nonempty condition can be omitted from csSup_le_iff.

                        theorem csSup_le' {α : Type u_1} [ConditionallyCompleteLinearOrderBot α] {s : Set α} {a : α} (h : a upperBounds s) :
                        sSup s a
                        theorem lt_csSup_iff' {α : Type u_1} [ConditionallyCompleteLinearOrderBot α] {s : Set α} {a : α} (hb : BddAbove s) :
                        a < sSup s bs, a < b

                        In conditionally complete orders with a bottom element, the nonempty condition can be omitted from lt_csSup_iff.

                        theorem le_csSup_iff' {α : Type u_1} [ConditionallyCompleteLinearOrderBot α] {s : Set α} {a : α} (h : BddAbove s) :
                        a sSup s bupperBounds s, a b
                        theorem le_csInf_iff'' {α : Type u_1} [ConditionallyCompleteLinearOrderBot α] {s : Set α} {a : α} (ne : s.Nonempty) :
                        a sInf s bs, a b
                        theorem csInf_le' {α : Type u_1} [ConditionallyCompleteLinearOrderBot α] {s : Set α} {a : α} (h : a s) :
                        sInf s a
                        theorem exists_lt_of_lt_csSup' {α : Type u_1} [ConditionallyCompleteLinearOrderBot α] {s : Set α} {a : α} (h : a < sSup s) :
                        bs, a < b
                        theorem not_mem_of_lt_csInf' {α : Type u_1} [ConditionallyCompleteLinearOrderBot α] {x : α} {s : Set α} (h : x < sInf s) :
                        xs
                        theorem csInf_le_csInf' {α : Type u_1} [ConditionallyCompleteLinearOrderBot α] {s : Set α} {t : Set α} (h₁ : t.Nonempty) (h₂ : t s) :
                        theorem csSup_le_csSup' {α : Type u_1} [ConditionallyCompleteLinearOrderBot α] {s : Set α} {t : Set α} (h₁ : BddAbove t) (h₂ : s t) :
                        theorem WithTop.isLUB_sSup' {β : Type u_5} [ConditionallyCompleteLattice β] {s : Set (WithTop β)} (hs : s.Nonempty) :
                        IsLUB s (sSup s)

                        The sSup of a non-empty set is its least upper bound for a conditionally complete lattice with a top.

                        theorem WithTop.isGLB_sInf' {β : Type u_5} [ConditionallyCompleteLattice β] {s : Set (WithTop β)} (hs : BddBelow s) :
                        IsGLB s (sInf s)

                        The sInf of a bounded-below set is its greatest lower bound for a conditionally complete lattice with a top.

                        Equations
                        • WithTop.instCompleteLinearOrder = CompleteLinearOrder.mk LinearOrder.decidableLE LinearOrder.decidableEq LinearOrder.decidableLT
                        theorem WithTop.coe_sSup {α : Type u_1} [ConditionallyCompleteLinearOrderBot α] {s : Set α} (hb : BddAbove s) :
                        (sSup s) = as, a

                        A version of WithTop.coe_sSup' with a more convenient but less general statement.

                        theorem WithTop.coe_sInf {α : Type u_1} [ConditionallyCompleteLinearOrderBot α] {s : Set α} (hs : s.Nonempty) (h's : BddBelow s) :
                        (sInf s) = as, a

                        A version of WithTop.coe_sInf' with a more convenient but less general statement.

                        A monotone function into a conditionally complete lattice preserves the ordering properties of sSup and sInf.

                        theorem Monotone.le_csSup_image {α : Type u_1} {β : Type u_2} [Preorder α] [ConditionallyCompleteLattice β] {f : αβ} (h_mono : Monotone f) {s : Set α} {c : α} (hcs : c s) (h_bdd : BddAbove s) :
                        f c sSup (f '' s)
                        theorem Monotone.csSup_image_le {α : Type u_1} {β : Type u_2} [Preorder α] [ConditionallyCompleteLattice β] {f : αβ} (h_mono : Monotone f) {s : Set α} (hs : s.Nonempty) {B : α} (hB : B upperBounds s) :
                        sSup (f '' s) f B
                        theorem Monotone.csInf_image_le {α : Type u_1} {β : Type u_2} [Preorder α] [ConditionallyCompleteLattice β] {f : αβ} (h_mono : Monotone f) {s : Set α} {c : α} (hcs : c s) (h_bdd : BddBelow s) :
                        sInf (f '' s) f c
                        theorem Monotone.le_csInf_image {α : Type u_1} {β : Type u_2} [Preorder α] [ConditionallyCompleteLattice β] {f : αβ} (h_mono : Monotone f) {s : Set α} (hs : s.Nonempty) {B : α} (hB : B lowerBounds s) :
                        f B sInf (f '' s)

                        Supremum/infimum of Set.image2 #

                        A collection of lemmas showing what happens to the suprema/infima of s and t when mapped under a binary function whose partial evaluations are lower/upper adjoints of Galois connections.

                        theorem csSup_image2_eq_csSup_csSup {α : Type u_1} {β : Type u_2} {γ : Type u_3} [ConditionallyCompleteLattice α] [ConditionallyCompleteLattice β] [ConditionallyCompleteLattice γ] {s : Set α} {t : Set β} {l : αβγ} {u₁ : βγα} {u₂ : αγβ} (h₁ : ∀ (b : β), GaloisConnection (Function.swap l b) (u₁ b)) (h₂ : ∀ (a : α), GaloisConnection (l a) (u₂ a)) (hs₀ : s.Nonempty) (hs₁ : BddAbove s) (ht₀ : t.Nonempty) (ht₁ : BddAbove t) :
                        sSup (Set.image2 l s t) = l (sSup s) (sSup t)
                        theorem csSup_image2_eq_csSup_csInf {α : Type u_1} {β : Type u_2} {γ : Type u_3} [ConditionallyCompleteLattice α] [ConditionallyCompleteLattice β] [ConditionallyCompleteLattice γ] {s : Set α} {t : Set β} {l : αβγ} {u₁ : βγα} {u₂ : αγβ} (h₁ : ∀ (b : β), GaloisConnection (Function.swap l b) (u₁ b)) (h₂ : ∀ (a : α), GaloisConnection (l a OrderDual.ofDual) (OrderDual.toDual u₂ a)) :
                        s.NonemptyBddAbove st.NonemptyBddBelow tsSup (Set.image2 l s t) = l (sSup s) (sInf t)
                        theorem csSup_image2_eq_csInf_csSup {α : Type u_1} {β : Type u_2} {γ : Type u_3} [ConditionallyCompleteLattice α] [ConditionallyCompleteLattice β] [ConditionallyCompleteLattice γ] {s : Set α} {t : Set β} {l : αβγ} {u₁ : βγα} {u₂ : αγβ} (h₁ : ∀ (b : β), GaloisConnection (Function.swap l b OrderDual.ofDual) (OrderDual.toDual u₁ b)) (h₂ : ∀ (a : α), GaloisConnection (l a) (u₂ a)) :
                        s.NonemptyBddBelow st.NonemptyBddAbove tsSup (Set.image2 l s t) = l (sInf s) (sSup t)
                        theorem csSup_image2_eq_csInf_csInf {α : Type u_1} {β : Type u_2} {γ : Type u_3} [ConditionallyCompleteLattice α] [ConditionallyCompleteLattice β] [ConditionallyCompleteLattice γ] {s : Set α} {t : Set β} {l : αβγ} {u₁ : βγα} {u₂ : αγβ} (h₁ : ∀ (b : β), GaloisConnection (Function.swap l b OrderDual.ofDual) (OrderDual.toDual u₁ b)) (h₂ : ∀ (a : α), GaloisConnection (l a OrderDual.ofDual) (OrderDual.toDual u₂ a)) :
                        s.NonemptyBddBelow st.NonemptyBddBelow tsSup (Set.image2 l s t) = l (sInf s) (sInf t)
                        theorem csInf_image2_eq_csInf_csInf {α : Type u_1} {β : Type u_2} {γ : Type u_3} [ConditionallyCompleteLattice α] [ConditionallyCompleteLattice β] [ConditionallyCompleteLattice γ] {s : Set α} {t : Set β} {u : αβγ} {l₁ : βγα} {l₂ : αγβ} (h₁ : ∀ (b : β), GaloisConnection (l₁ b) (Function.swap u b)) (h₂ : ∀ (a : α), GaloisConnection (l₂ a) (u a)) :
                        s.NonemptyBddBelow st.NonemptyBddBelow tsInf (Set.image2 u s t) = u (sInf s) (sInf t)
                        theorem csInf_image2_eq_csInf_csSup {α : Type u_1} {β : Type u_2} {γ : Type u_3} [ConditionallyCompleteLattice α] [ConditionallyCompleteLattice β] [ConditionallyCompleteLattice γ] {s : Set α} {t : Set β} {u : αβγ} {l₁ : βγα} {l₂ : αγβ} (h₁ : ∀ (b : β), GaloisConnection (l₁ b) (Function.swap u b)) (h₂ : ∀ (a : α), GaloisConnection (OrderDual.toDual l₂ a) (u a OrderDual.ofDual)) :
                        s.NonemptyBddBelow st.NonemptyBddAbove tsInf (Set.image2 u s t) = u (sInf s) (sSup t)
                        theorem csInf_image2_eq_csSup_csInf {α : Type u_1} {β : Type u_2} {γ : Type u_3} [ConditionallyCompleteLattice α] [ConditionallyCompleteLattice β] [ConditionallyCompleteLattice γ] {s : Set α} {t : Set β} {u : αβγ} {l₁ : βγα} {l₂ : αγβ} (h₁ : ∀ (b : β), GaloisConnection (OrderDual.toDual l₁ b) (Function.swap u b OrderDual.ofDual)) (h₂ : ∀ (a : α), GaloisConnection (l₂ a) (u a)) :
                        s.NonemptyBddAbove st.NonemptyBddBelow tsInf (Set.image2 u s t) = u (sSup s) (sInf t)
                        theorem csInf_image2_eq_csSup_csSup {α : Type u_1} {β : Type u_2} {γ : Type u_3} [ConditionallyCompleteLattice α] [ConditionallyCompleteLattice β] [ConditionallyCompleteLattice γ] {s : Set α} {t : Set β} {u : αβγ} {l₁ : βγα} {l₂ : αγβ} (h₁ : ∀ (b : β), GaloisConnection (OrderDual.toDual l₁ b) (Function.swap u b OrderDual.ofDual)) (h₂ : ∀ (a : α), GaloisConnection (OrderDual.toDual l₂ a) (u a OrderDual.ofDual)) :
                        s.NonemptyBddAbove st.NonemptyBddAbove tsInf (Set.image2 u s t) = u (sSup s) (sSup t)

                        Complete lattice structure on WithTop (WithBot α) #

                        If α is a ConditionallyCompleteLattice, then we show that WithTop α and WithBot α also inherit the structure of conditionally complete lattices. Furthermore, we show that WithTop (WithBot α) and WithBot (WithTop α) naturally inherit the structure of a complete lattice. Note that for α a conditionally complete lattice, sSup and sInf both return junk values for sets which are empty or unbounded. The extension of sSup to WithTop α fixes the unboundedness problem and the extension to WithBot α fixes the problem with the empty set.

                        This result can be used to show that the extended reals [-∞, ∞] are a complete linear order.

                        Adding a top element to a conditionally complete lattice gives a conditionally complete lattice

                        Equations

                        Adding a bottom element to a conditionally complete lattice gives a conditionally complete lattice

                        Equations
                        Equations
                        Equations
                        • WithTop.WithBot.completeLinearOrder = CompleteLinearOrder.mk LinearOrder.decidableLE LinearOrder.decidableEq LinearOrder.decidableLT
                        Equations
                        Equations
                        • WithBot.WithTop.completeLinearOrder = CompleteLinearOrder.mk LinearOrder.decidableLE LinearOrder.decidableEq LinearOrder.decidableLT