Documentation

Provenance.Semirings.Interval

Intervals over linear orders #

This file defines closed/open intervals over a linear order and the operations needed to build the interval-union semiring.

Main definitions #

Main results #

structure Endpoint (α : Type) :

An endpoint of an interval: a value together with a boolean flag indicating whether the endpoint is included (closed = true) or excluded (closed = false).

  • val : α
  • closed : Bool
Instances For
    Dependency graph
    theorem Endpoint.ext_iff {α : Type} {x y : Endpoint α} :
    x = y ↔ x.val = y.val ∧ x.closed = y.closed
    Dependency graph
    theorem Endpoint.ext {α : Type} {x y : Endpoint α} (val : x.val = y.val) (closed : x.closed = y.closed) :
    x = y
    Dependency graph
    @[instance_reducible]
    Equations
    • One or more equations did not get rendered due to their size.
    Dependency graph
    def Endpoint.minLo {α : Type} [LinearOrder α] (a b : Endpoint α) :
    Equations
    Instances For
      Dependency graph
      def Endpoint.maxHi {α : Type} [LinearOrder α] (a b : Endpoint α) :
      Equations
      Instances For
        Dependency graph
        def Endpoint.below {α : Type} [LinearOrder α] (x : α) (hi : Endpoint α) :

        below x hi holds when x is on the correct side of the upper endpoint hi, respecting its closedness: x ≤ hi.val if closed, x < hi.val if open.

        Equations
        Instances For
          def Endpoint.above {α : Type} [LinearOrder α] (x : α) (lo : Endpoint α) :

          above x lo holds when x is on the correct side of the lower endpoint lo, respecting its closedness: lo.val ≤ x if closed, lo.val < x if open.

          Equations
          Instances For
            Dependency graph

            Endpoint operations for intersection and difference #

            def Endpoint.maxLo {α : Type} [LinearOrder α] (a b : Endpoint α) :

            Most restrictive (largest) lower endpoint: above x (maxLo a b) ↔ above x a ∧ above x b.

            Equations
            Instances For
              Dependency graph
              def Endpoint.minHi {α : Type} [LinearOrder α] (a b : Endpoint α) :

              Most restrictive (smallest) upper endpoint: below x (minHi a b) ↔ below x a ∧ below x b.

              Equations
              Instances For
                Dependency graph
                structure Interval (α : Type) [LinearOrder α] :

                An interval over a linear order, given by a lower endpoint lo and an upper endpoint hi satisfying lo.val < hi.val (strict) or lo.val = hi.val with both endpoints closed (degenerate point interval).

                Instances For
                  Dependency graph
                  theorem Interval.ext {α : Type} {inst✝ : LinearOrder α} {x y : Interval α} (lo : x.lo = y.lo) (hi : x.hi = y.hi) :
                  x = y
                  Dependency graph
                  theorem Interval.ext_iff {α : Type} {inst✝ : LinearOrder α} {x y : Interval α} :
                  x = y ↔ x.lo = y.lo ∧ x.hi = y.hi
                  Dependency graph
                  @[simp]
                  theorem Interval.le_lo_hi {α : Type} [LinearOrder α] (I : Interval α) :
                  Dependency graph
                  def Interval.toSet {α : Type} [LinearOrder α] (I : Interval α) :
                  Set α

                  The set of points belonging to an interval: those x that are above lo and below hi according to their respective closedness flags.

                  Equations
                  Instances For
                    Dependency graph
                    theorem Interval.toSet_not_empty {α : Type} [LinearOrder α] [DenselyOrdered α] (I : Interval α) :
                    ∃ (x : α), x ∈ I.toSet
                    Dependency graph
                    theorem Interval.ext_toSet {α : Type} [LinearOrder α] [DenselyOrdered α] {I J : Interval α} (h : I.toSet = J.toSet) :
                    I = J
                    Dependency graph
                    theorem Interval.ext_toSet_iff {α : Type} [LinearOrder α] [DenselyOrdered α] {I J : Interval α} :
                    I = J ↔ I.toSet = J.toSet
                    Dependency graph
                    @[simp]
                    theorem Interval.mem {α : Type} [LinearOrder α] (x : α) (I : Interval α) :
                    Dependency graph
                    def Interval.disjoint {α : Type} [LinearOrder α] (I J : Interval α) :

                    Two intervals are disjoint when their point sets have empty intersection.

                    Equations
                    Instances For
                      Dependency graph
                      @[instance_reducible]
                      Equations
                      • One or more equations did not get rendered due to their size.
                      Dependency graph
                      def Interval.before {α : Type} [LinearOrder α] (I J : Interval α) :

                      I.before J means the intervals are strictly separated and cannot be merged: either I.hi.val < J.lo.val, or the endpoints meet at the same value but both are open.

                      Equations
                      Instances For
                        Dependency graph
                        theorem Interval.disjoint_of_before {α : Type} [LinearOrder α] {I J : Interval α} :
                        I.before J → I.disjoint J
                        Dependency graph
                        @[instance_reducible]
                        Equations
                        • One or more equations did not get rendered due to their size.
                        Dependency graph

                        Interval intersection #

                        def Interval.inter {α : Type} [LinearOrder α] (I J : Interval α) :

                        Intersection of two intervals: empty or a single interval.

                        Equations
                        • One or more equations did not get rendered due to their size.
                        Instances For
                          Dependency graph
                          theorem Interval.mem_inter {α : Type} [LinearOrder α] (I J : Interval α) (x : α) :
                          (∃ K ∈ I.inter J, x ∈ K.toSet) ↔ x ∈ I.toSet ∧ x ∈ J.toSet
                          Dependency graph

                          Interval difference #

                          def Interval.diff {α : Type} [LinearOrder α] (I J : Interval α) :

                          Difference I \ J: the left piece (below J) and right piece (above J) of I.

                          Equations
                          • One or more equations did not get rendered due to their size.
                          Instances For
                            Dependency graph
                            theorem Interval.mem_diff {α : Type} [LinearOrder α] (I J : Interval α) (x : α) :
                            (∃ K ∈ I.diff J, x ∈ K.toSet) ↔ x ∈ I.toSet ∧ x ∉ J.toSet
                            Dependency graph