module Order.Base where

Partially ordered setsπŸ”—

A poset is a set equipped with a relation called a partial order, which is reflexive, transitive, and antisymmetric. Put another way, a poset is a univalent category which has at most one morphism between each pair of its objects: a thin category.

Posets are a simultaneous generalisation of many naturally occurring notions of β€œorder” in mathematics:

  • The β€œusual” ordering relations on familiar number systems like the natural numbers, the integers, the rationals, or the reals.

    When ordering the naturals, the integers, and the rationals, we can say more: they are linear orders. That is, in addition to the properties of required to be a poset, we have, for any pair of elements and

  • The divisibility order on the natural numbers is also a poset, as detailed in that page. More than just a poset, it’s actually a lattice: the meet of a pair of numbers is their greatest common divisor, and the join is their least common multiple.

    The divisibility ordering is also interesting as a counterexample: even though it is decidable, it fails to be a linear order: any pair of coprime numbers is unrelated by the divisibility order.

  • Moving away from numbers, partial orders are also intimately connected with the study of logic.

    To each theory in a given fragment of propositional logic, we can build a set of sentences in the language of The entailment (or provability) relation is almost a partial order: we certainly have and the transitivity requirement is the β€œcut” rule,

    However, this fails to be a poset, because inter-provable formulas and need not be syntactically equal. However, if we quotient the set by the inter-provability relation, then we do obtain a poset: the Lindenbaum-Tarski algebra of

    This poset will inherit order-theoretic structure from the logical structure of For example, if is expressed in a fragment of logic which has conjunction, then will be a meet-semilattice; if it also has infinitary disjunction, then its Lindenbaum-Tarski algebra is a frame.

  • As mentioned in the opening paragraph, the notion of poset specialises that of univalent category.

    In particular, to every univalent category we can universally associate a poset: Its set of elements is the set truncation of groupoid of objects, and the relation is the propositional truncation

    This process can actually be extended to any precategory: however, instead of merely truncating the space of objects, we must instead take its set-quotient by the relation

With the motivating examples out of the way, we can finally move onto the formalised definition of poset, which is a straightforward translation.

record Poset o β„“ : Type (lsuc (o βŠ” β„“)) where
  no-eta-equality
  field
    Ob        : Type o
    _≀_       : Ob β†’ Ob β†’ Type β„“
    ≀-thin    : βˆ€ {x y} β†’ is-prop (x ≀ y)

We note, as usual, that each fibre of the order relation should be a proposition: this is precisely the formalisation of having at most one element. The reflexivity, transitivity, and antisymmetry properties are literal:

    ≀-refl    : βˆ€ {x}     β†’ x ≀ x
    ≀-trans   : βˆ€ {x y z} β†’ x ≀ y β†’ y ≀ z β†’ x ≀ z
    ≀-antisym : βˆ€ {x y}   β†’ x ≀ y β†’ y ≀ x β†’ x ≑ y

Note that the type of ≀-antisym ends in a path in Ob, which, a priori, might not be a proposition: we have not included the assumption that Ob is actually a set. Therefore, it might be the case that an identification between posets does not correspond to an identification of the underlying types and one of the relation. However, since the β€œsymmetric part” of the relation iff.

is a reflexive mere relation which implies identity, the type of objects is automatically a set.

  abstract
    Ob-is-set : is-set Ob
    Ob-is-set =
      identity-system→hlevel 1
        {r = Ξ» _ β†’ ≀-refl , ≀-refl}
        (set-identity-system
          (Ξ» a b β†’ Γ—-is-hlevel 1 ≀-thin ≀-thin)
          (Ξ» {a} {b} (p , q) β†’ ≀-antisym {a} {b} p q))
        (Ξ» a b β†’ Γ—-is-hlevel 1 ≀-thin ≀-thin)

Monotone mapsπŸ”—

Since we are considering posets to be categories satisfying a property, it follows that the category of posets should be a full subcategory of i.e., the maps should be precisely the functors However, since there is at most one inhabitant of each we are free to drop the functoriality assumptions, and consider instead the monotone maps:

record
  Monotone {o o' β„“ β„“'} (P : Poset o β„“) (Q : Poset o' β„“')
    : Type (o βŠ” o' βŠ” β„“ βŠ” β„“') where
  no-eta-equality
  field
    hom    : P.Ob β†’ Q.Ob
    pres-≀ : βˆ€ {x y} β†’ x P.≀ y β†’ hom x Q.≀ hom y

A monotone map between posets is a map between their underlying sets which preserves the order relation. This is the most natural choice: for example, the monotone functions are precisely nondecreasing sequences of elements in

open Monotone public

private variable
  o β„“ o' β„“' o'' β„“'' : Level
  P Q R : Poset o β„“

unquoteDecl H-Level-Monotone = declare-record-hlevel 2 H-Level-Monotone (quote Monotone)

instance
  Funlike-Monotone : Funlike (Monotone P Q) ⌞ P ⌟ Ξ» _ β†’ ⌞ Q ⌟
  Funlike-Monotone = record { _#_ = hom }

  Membership-Monotone : ⦃ _ : Underlying ⌞ Q ⌟ ⦄ β†’ Membership ⌞ P ⌟ (Monotone P Q) _
  Membership-Monotone = record { _∈_ = Ξ» x S β†’ ⌞ S #Β x ⌟ }

Monotone-pathp
  : βˆ€ {o β„“ o' β„“'} {P : I β†’ Poset o β„“} {Q : I β†’ Poset o' β„“'}
  β†’ {f : Monotone (P i0) (Q i0)} {g : Monotone (P i1) (Q i1)}
  β†’ PathP (Ξ» i β†’ ⌞ P i ⌟ β†’ ⌞ Q i ⌟) (apply f) (apply g)
  β†’ PathP (Ξ» i β†’ Monotone (P i) (Q i)) f g
Monotone-pathp q i .hom a = q i a
Monotone-pathp {P = P} {Q} {f} {g} q i .Monotone.pres-≀ {x} {y} Ξ± =
  is-prop→pathp
    (Ξ» i β†’ Ξ -is-hlevelΒ³ {A = ⌞ P i ⌟} {B = Ξ» _ β†’ ⌞ P i ⌟} {C = Ξ» x y β†’ P i .Poset._≀_ x y} 1
      Ξ» x y _ β†’ Q i .Poset.≀-thin {q i x} {q i y})
    (Ξ» _ _ Ξ± β†’ f .Monotone.pres-≀ Ξ±)
    (Ξ» _ _ Ξ± β†’ g .Monotone.pres-≀ Ξ±) i x y Ξ±

instance
  Extensional-Monotone
    : βˆ€ {o β„“ o' β„“' β„“r} {P : Poset o β„“} {Q : Poset o' β„“'}
    β†’ ⦃ sa : Extensional (⌞ P ⌟ β†’ ⌞ Q ⌟) β„“r ⦄
    β†’ Extensional (Monotone P Q) β„“r
  Extensional-Monotone {Q = Q} ⦃ sa ⦄ =
    injection→extensional! Monotone-pathp sa

It’s immediate to see that the identity function is monotone, and that monotone maps are closed under composition. Since identity of monotone maps is given by identity of the underlying functions, there is a set of monotone maps and the laws of a category are trivial.

idβ‚˜ : Monotone P P
idβ‚˜ .hom    x   = x
idβ‚˜ .pres-≀ x≀y = x≀y

_βˆ˜β‚˜_ : Monotone Q R β†’ Monotone P Q β†’ Monotone P R
(f βˆ˜β‚˜ g) .hom    x   = f # (g # x)
(f βˆ˜β‚˜ g) .pres-≀ x≀y = f .pres-≀ (g .pres-≀ x≀y)

Posets : βˆ€ (o β„“ : Level) β†’ Precategory (lsuc o βŠ” lsuc β„“) (o βŠ” β„“)
Posets o β„“ .Precategory.Ob          = Poset o β„“
Posets o β„“ .Precategory.Hom         = Monotone
Posets o β„“ .Precategory.Hom-set _ _ = hlevel 2

Posets o β„“ .Precategory.id  = idβ‚˜
Posets o β„“ .Precategory._∘_ = _βˆ˜β‚˜_

Posets o β„“ .Precategory.idr f       = trivial!
Posets o β„“ .Precategory.idl f       = trivial!
Posets o β„“ .Precategory.assoc f g h = trivial!

Simple constructionsπŸ”—

The simplest thing we can do to a poset is to forget the order. This evidently extends to a faithful functor

Posetsβ†ͺSets : βˆ€ {o β„“} β†’ Functor (Posets o β„“) (Sets o)
Posetsβ†ͺSets .Functor.Fβ‚€ P .∣_∣    = ⌞ P ⌟
Posetsβ†ͺSets .Functor.Fβ‚€ P .is-tr = hlevel 2
Posetsβ†ͺSets .Functor.F₁ = hom
Posetsβ†ͺSets .Functor.F-id    = refl
Posetsβ†ͺSets .Functor.F-∘ _ _ = refl

Slightly less trivial, we can extend the opposite category construction to posets as well, by transposing the order relation and making sure to flip the direction of transitivity:

_^opp : βˆ€ {β„“ β„“'} β†’ Poset β„“ β„“' β†’ Poset β„“ β„“'
(P ^opp) .Poset.Ob      = Poset.Ob P
(P ^opp) .Poset._≀_ x y = Poset._≀_ P y x

(P ^opp) .Poset.≀-thin = Poset.≀-thin P
(P ^opp) .Poset.≀-refl = Poset.≀-refl P
(P ^opp) .Poset.≀-trans   xβ‰₯y yβ‰₯z = Poset.≀-trans P yβ‰₯z xβ‰₯y
(P ^opp) .Poset.≀-antisym xβ‰₯y yβ‰₯x = Poset.≀-antisym P yβ‰₯x xβ‰₯y

We can construct the trivial posets with one and zero (object(s), ordering(s)) respectively

πŸ™α΅– : βˆ€ {o β„“} β†’ Poset o β„“
πŸ™α΅– .Poset.Ob = Lift _ ⊀
πŸ™α΅– .Poset._≀_ _ _ = Lift _ ⊀
πŸ™α΅– .Poset.≀-thin = hlevel 1
πŸ™α΅– .Poset.≀-refl = lift tt
πŸ™α΅– .Poset.≀-trans = Ξ» _ _ β†’ lift tt
πŸ™α΅– .Poset.≀-antisym = Ξ» _ _ β†’ refl

πŸ˜α΅– : βˆ€ {o β„“} β†’ Poset o β„“
πŸ˜α΅– .Poset.Ob = Lift _ βŠ₯
πŸ˜α΅– .Poset._≀_ _ _ = Lift _ βŠ₯
πŸ˜α΅– .Poset.≀-thin ()
πŸ˜α΅– .Poset.≀-refl {()}
πŸ˜α΅– .Poset.≀-trans ()
πŸ˜α΅– .Poset.≀-antisym ()