Documentation

Mathlib.Order.Circular

Circular order hierarchy #

This file defines circular preorders, circular partial orders and circular orders.

Hierarchy #

The intuition is that a circular order is a circle and btw a b c means that going around clockwise from a you reach b before c (b is between a and c is meaningless on an unoriented circle). A circular partial order is several, potentially intersecting, circles. A circular preorder is like a circular partial order, but several points can coexist.

Note that the relations between CircularPreorder, CircularPartialOrder and CircularOrder are subtler than between Preorder, PartialOrder, LinearOrder. In particular, one cannot simply extend the Btw of a CircularPartialOrder to make it a CircularOrder.

One can translate from usual orders to circular ones by "closing the necklace at infinity". See LE.toBtw and LT.toSBtw. Going the other way involves "cutting the necklace" or "rolling the necklace open".

Examples #

Some concrete circular orders one encounters in the wild are ZMod n for 0 < n, Circle, Real.Angle...

Main definitions #

Notes #

There's an unsolved diamond on OrderDual α here. The instances LE α → Btw αᵒᵈ and LT α → SBtw αᵒᵈ can each be inferred in two ways:

TODO #

Antisymmetry is quite weak in the sense that there's no way to discriminate which two points are equal. This prevents defining closed-open intervals cIco and cIoc in the neat =-less way. We currently haven't defined them at all.

What is the correct generality of "rolling the necklace" open? At least, this works for α × β and β × α where α is a circular order and β is a linear order.

What's next is to define circular groups and provide instances for ZMod n, the usual circle group Circle, and RootsOfUnity M. What conditions do we need on M for this last one to work?

We should have circular order homomorphisms. The typical example is days_to_month : days_of_the_year →c months_of_the_year which relates the circular order of days and the circular order of months. Is α →c β a good notation?

References #

Tags #

circular order, cyclic order, circularly ordered set, cyclically ordered set

class Btw (α : Type u_1) :
Type u_1

Syntax typeclass for a betweenness relation.

  • btw : αααProp

    Betweenness for circular orders. btw a b c states that b is between a and c (in that order).

Instances
    class SBtw (α : Type u_1) :
    Type u_1

    Syntax typeclass for a strict betweenness relation.

    • sbtw : αααProp

      Strict betweenness for circular orders. sbtw a b c states that b is strictly between a and c (in that order).

    Instances
      class CircularPreorder (α : Type u_1) extends Btw , SBtw :
      Type u_1

      A circular preorder is the analogue of a preorder where you can loop around. and < are replaced by ternary relations btw and sbtw. btw is reflexive and cyclic. sbtw is transitive.

      • btw : αααProp
      • sbtw : αααProp
      • btw_refl : ∀ (a : α), btw a a a

        a is between a and a.

      • btw_cyclic_left : ∀ {a b c : α}, btw a b cbtw b c a

        If b is between a and c, then c is between b and a. This is motivated by imagining three points on a circle.

      • sbtw_iff_btw_not_btw : ∀ {a b c : α}, sbtw a b c btw a b c ¬btw c b a

        Strict betweenness is given by betweenness in one direction and non-betweenness in the other.

        I.e., if b is between a and c but not between c and a, then we say b is strictly between a and c.

      • sbtw_trans_left : ∀ {a b c d : α}, sbtw a b csbtw b d csbtw a d c

        For any fixed c, fun a b ↦ sbtw a b c is a transitive relation.

        I.e., given a b d c in that "order", if we have b strictly between a and c, and d strictly between b and c, then d is strictly between a and c.

      Instances
        theorem CircularPreorder.btw_refl {α : Type u_1} [self : CircularPreorder α] (a : α) :
        btw a a a

        a is between a and a.

        theorem CircularPreorder.btw_cyclic_left {α : Type u_1} [self : CircularPreorder α] {a : α} {b : α} {c : α} :
        btw a b cbtw b c a

        If b is between a and c, then c is between b and a. This is motivated by imagining three points on a circle.

        theorem CircularPreorder.sbtw_iff_btw_not_btw {α : Type u_1} [self : CircularPreorder α] {a : α} {b : α} {c : α} :
        sbtw a b c btw a b c ¬btw c b a

        Strict betweenness is given by betweenness in one direction and non-betweenness in the other.

        I.e., if b is between a and c but not between c and a, then we say b is strictly between a and c.

        theorem CircularPreorder.sbtw_trans_left {α : Type u_1} [self : CircularPreorder α] {a : α} {b : α} {c : α} {d : α} :
        sbtw a b csbtw b d csbtw a d c

        For any fixed c, fun a b ↦ sbtw a b c is a transitive relation.

        I.e., given a b d c in that "order", if we have b strictly between a and c, and d strictly between b and c, then d is strictly between a and c.

        class CircularPartialOrder (α : Type u_1) extends CircularPreorder :
        Type u_1

        A circular partial order is the analogue of a partial order where you can loop around. and < are replaced by ternary relations btw and sbtw. btw is reflexive, cyclic and antisymmetric. sbtw is transitive.

        • btw : αααProp
        • sbtw : αααProp
        • btw_refl : ∀ (a : α), btw a a a
        • btw_cyclic_left : ∀ {a b c : α}, btw a b cbtw b c a
        • sbtw_iff_btw_not_btw : ∀ {a b c : α}, sbtw a b c btw a b c ¬btw c b a
        • sbtw_trans_left : ∀ {a b c d : α}, sbtw a b csbtw b d csbtw a d c
        • btw_antisymm : ∀ {a b c : α}, btw a b cbtw c b aa = b b = c c = a

          If b is between a and c and also between c and a, then at least one pair of points among a, b, c are identical.

        Instances
          theorem CircularPartialOrder.btw_antisymm {α : Type u_1} [self : CircularPartialOrder α] {a : α} {b : α} {c : α} :
          btw a b cbtw c b aa = b b = c c = a

          If b is between a and c and also between c and a, then at least one pair of points among a, b, c are identical.

          class CircularOrder (α : Type u_1) extends CircularPartialOrder :
          Type u_1

          A circular order is the analogue of a linear order where you can loop around. and < are replaced by ternary relations btw and sbtw. btw is reflexive, cyclic, antisymmetric and total. sbtw is transitive.

          • btw : αααProp
          • sbtw : αααProp
          • btw_refl : ∀ (a : α), btw a a a
          • btw_cyclic_left : ∀ {a b c : α}, btw a b cbtw b c a
          • sbtw_iff_btw_not_btw : ∀ {a b c : α}, sbtw a b c btw a b c ¬btw c b a
          • sbtw_trans_left : ∀ {a b c d : α}, sbtw a b csbtw b d csbtw a d c
          • btw_antisymm : ∀ {a b c : α}, btw a b cbtw c b aa = b b = c c = a
          • btw_total : ∀ (a b c : α), btw a b c btw c b a

            For any triple of points, the second is between the other two one way or another.

          Instances
            theorem CircularOrder.btw_total {α : Type u_1} [self : CircularOrder α] (a : α) (b : α) (c : α) :
            btw a b c btw c b a

            For any triple of points, the second is between the other two one way or another.

            Circular preorders #

            theorem btw_rfl {α : Type u_1} [CircularPreorder α] {a : α} :
            btw a a a
            theorem Btw.btw.cyclic_left {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (h : btw a b c) :
            btw b c a
            theorem btw_cyclic_right {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (h : btw a b c) :
            btw c a b
            theorem Btw.btw.cyclic_right {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (h : btw a b c) :
            btw c a b

            Alias of btw_cyclic_right.

            theorem btw_cyclic {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} :
            btw a b c btw c a b

            The order of the has been chosen so that rw [btw_cyclic] cycles to the right while rw [← btw_cyclic] cycles to the left (thus following the prepended arrow).

            theorem sbtw_iff_btw_not_btw {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} :
            sbtw a b c btw a b c ¬btw c b a
            theorem btw_of_sbtw {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (h : sbtw a b c) :
            btw a b c
            theorem SBtw.sbtw.btw {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (h : sbtw a b c) :
            btw a b c

            Alias of btw_of_sbtw.

            theorem not_btw_of_sbtw {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (h : sbtw a b c) :
            ¬btw c b a
            theorem SBtw.sbtw.not_btw {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (h : sbtw a b c) :
            ¬btw c b a

            Alias of not_btw_of_sbtw.

            theorem not_sbtw_of_btw {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (h : btw a b c) :
            ¬sbtw c b a
            theorem Btw.btw.not_sbtw {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (h : btw a b c) :
            ¬sbtw c b a

            Alias of not_sbtw_of_btw.

            theorem sbtw_of_btw_not_btw {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (habc : btw a b c) (hcba : ¬btw c b a) :
            sbtw a b c
            theorem Btw.btw.sbtw_of_not_btw {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (habc : btw a b c) (hcba : ¬btw c b a) :
            sbtw a b c

            Alias of sbtw_of_btw_not_btw.

            theorem sbtw_cyclic_left {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (h : sbtw a b c) :
            sbtw b c a
            theorem SBtw.sbtw.cyclic_left {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (h : sbtw a b c) :
            sbtw b c a

            Alias of sbtw_cyclic_left.

            theorem sbtw_cyclic_right {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (h : sbtw a b c) :
            sbtw c a b
            theorem SBtw.sbtw.cyclic_right {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (h : sbtw a b c) :
            sbtw c a b

            Alias of sbtw_cyclic_right.

            theorem sbtw_cyclic {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} :
            sbtw a b c sbtw c a b

            The order of the has been chosen so that rw [sbtw_cyclic] cycles to the right while rw [← sbtw_cyclic] cycles to the left (thus following the prepended arrow).

            theorem SBtw.sbtw.trans_left {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} {d : α} (h : sbtw a b c) :
            sbtw b d csbtw a d c
            theorem sbtw_trans_right {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} {d : α} (hbc : sbtw a b c) (hcd : sbtw a c d) :
            sbtw a b d
            theorem SBtw.sbtw.trans_right {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} {d : α} (hbc : sbtw a b c) (hcd : sbtw a c d) :
            sbtw a b d

            Alias of sbtw_trans_right.

            theorem sbtw_asymm {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (h : sbtw a b c) :
            ¬sbtw c b a
            theorem SBtw.sbtw.not_sbtw {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {c : α} (h : sbtw a b c) :
            ¬sbtw c b a

            Alias of sbtw_asymm.

            theorem sbtw_irrefl_left_right {α : Type u_1} [CircularPreorder α] {a : α} {b : α} :
            ¬sbtw a b a
            theorem sbtw_irrefl_left {α : Type u_1} [CircularPreorder α] {a : α} {b : α} :
            ¬sbtw a a b
            theorem sbtw_irrefl_right {α : Type u_1} [CircularPreorder α] {a : α} {b : α} :
            ¬sbtw a b b
            theorem sbtw_irrefl {α : Type u_1} [CircularPreorder α] (a : α) :
            ¬sbtw a a a

            Circular partial orders #

            theorem Btw.btw.antisymm {α : Type u_1} [CircularPartialOrder α] {a : α} {b : α} {c : α} (h : btw a b c) :
            btw c b aa = b b = c c = a

            Circular orders #

            theorem btw_refl_left_right {α : Type u_1} [CircularOrder α] (a : α) (b : α) :
            btw a b a
            theorem btw_rfl_left_right {α : Type u_1} [CircularOrder α] {a : α} {b : α} :
            btw a b a
            theorem btw_refl_left {α : Type u_1} [CircularOrder α] (a : α) (b : α) :
            btw a a b
            theorem btw_rfl_left {α : Type u_1} [CircularOrder α] {a : α} {b : α} :
            btw a a b
            theorem btw_refl_right {α : Type u_1} [CircularOrder α] (a : α) (b : α) :
            btw a b b
            theorem btw_rfl_right {α : Type u_1} [CircularOrder α] {a : α} {b : α} :
            btw a b b
            theorem sbtw_iff_not_btw {α : Type u_1} [CircularOrder α] {a : α} {b : α} {c : α} :
            sbtw a b c ¬btw c b a
            theorem btw_iff_not_sbtw {α : Type u_1} [CircularOrder α] {a : α} {b : α} {c : α} :
            btw a b c ¬sbtw c b a

            Circular intervals #

            def Set.cIcc {α : Type u_1} [CircularPreorder α] (a : α) (b : α) :
            Set α

            Closed-closed circular interval

            Equations
            Instances For
              def Set.cIoo {α : Type u_1} [CircularPreorder α] (a : α) (b : α) :
              Set α

              Open-open circular interval

              Equations
              Instances For
                @[simp]
                theorem Set.mem_cIcc {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {x : α} :
                x Set.cIcc a b btw a x b
                @[simp]
                theorem Set.mem_cIoo {α : Type u_1} [CircularPreorder α] {a : α} {b : α} {x : α} :
                x Set.cIoo a b sbtw a x b
                theorem Set.left_mem_cIcc {α : Type u_1} [CircularOrder α] (a : α) (b : α) :
                theorem Set.right_mem_cIcc {α : Type u_1} [CircularOrder α] (a : α) (b : α) :
                theorem Set.compl_cIcc {α : Type u_1} [CircularOrder α] {a : α} {b : α} :
                theorem Set.compl_cIoo {α : Type u_1} [CircularOrder α] {a : α} {b : α} :

                Circularizing instances #

                @[reducible, inline]
                abbrev LE.toBtw (α : Type u_1) [LE α] :
                Btw α

                The betweenness relation obtained from "looping around" . See note [reducible non-instances].

                Equations
                Instances For
                  @[reducible, inline]
                  abbrev LT.toSBtw (α : Type u_1) [LT α] :
                  SBtw α

                  The strict betweenness relation obtained from "looping around" <. See note [reducible non-instances].

                  Equations
                  Instances For
                    @[reducible, inline]

                    The circular preorder obtained from "looping around" a preorder. See note [reducible non-instances].

                    Equations
                    Instances For
                      @[reducible, inline]

                      The circular partial order obtained from "looping around" a partial order. See note [reducible non-instances].

                      Equations
                      Instances For
                        @[reducible, inline]

                        The circular order obtained from "looping around" a linear order. See note [reducible non-instances].

                        Equations
                        Instances For

                          Dual constructions #

                          instance OrderDual.btw (α : Type u_1) [Btw α] :
                          Equations
                          instance OrderDual.sbtw (α : Type u_1) [SBtw α] :
                          Equations