module Order.Instances.LexicalSum where

Lexicographic sum of posetsπŸ”—

Let be a partial order and be a family of partial orders indexed by the underlying set of We can equip the with a lexicographic partial order:


We avoid the more traditional formulation that uses the strict order:

The reason is that naturally involves when we take the non-strict order as the primitive notion. Negated types carry less information and usually work less well in constructive settings.

Given the dependency of on the comparison between and only makes sense when they lie in the same fibre, that is, when there is evidence We can then transport across to obtain a value in which can then be compared against

The concerns of defining the ordering in each fibre, and then defining the ordering on the entire total space, are mostly orthogonal. Indeed, these can be handled in a modular way: the construction we’re interested in naturally arises as the total (thin) category of a particular displayed order over the base poset

  Lexical-sum-over : Displayed _ _ I
  Lexical-sum-over .D.Ob[_]                = ⌞F⌟
  Lexical-sum-over .D.Rel[_] {i} {j} _ x y = (p : i ≑ᡒ j) β†’ substα΅’ ⌞F⌟ p x F.≀ y
  Lexical-sum : Poset _ _
  Lexical-sum = ∫ Lexical-sum-over

The fibre in a lexical sum over is essentially In fact, their underlying types are judgementally equal in the current construction. We do not express the sameness using isomorphisms in the category of posets (Posets) due to technical reasons: their universe levels do not match and we would need ugly lifting to compensate for the differences.

    : (i : ⌞ I ⌟) β†’ ⌞ Fibre (Lexical-sum-over I F) i ⌟ ≃ ⌞ F i ⌟
  lexical-sum-fibre-equiv i = _ , id-equiv

    : βˆ€ i β†’ is-order-embedding (Fibre (Lexical-sum-over I F) i) (F i) (Ξ» x β†’ x)
  lexical-sum-fibre-equiv-is-order-embedding i =
      (Ξ» x≀y β†’ x≀y reflα΅’)
      (Ξ» x≀y p β†’ subst (F._≀ _) (substα΅’-filler-set ⌞F⌟ (hlevel 2) p _) x≀y)

We can also define injections from which are the generic injections fibre-injα΅– (for general displayed posets) precomposed with the inverse of the above equivalence lexical-sum-fibre-equiv.

  lexical-sum-injα΅– : (i : ⌞ I ⌟) β†’ Monotone (F i) (Lexical-sum I F)
  lexical-sum-injα΅– i .hom    x   = i , x
  lexical-sum-injα΅– i .pres-≀ x≀y = I.≀-refl , Ξ» p β†’
    subst (F._≀ _) (substα΅’-filler-set ⌞F⌟ (hlevel 2) p _) x≀y

    : βˆ€ i β†’ is-order-embedding (F i) (Lexical-sum I F) (apply (lexical-sum-injα΅– i))
  lexical-sum-injα΅–-is-order-embedding i =
    prop-ext! (lexical-sum-injα΅– i .pres-≀) Ξ» (_ , q) β†’ q reflα΅’

The name Lexical-sum is justified by the observation that it is the maximum poset with the given index and fibres Its mapping-in universal property is: given another poset displayed over and a collection a fibrewise map there exists a (unique!) index-preserving map from the total space of into the lexical sum such that it commutes with

    : βˆ€ {o β„“} (G : Displayed o β„“ I)
    β†’ (βˆ€ i β†’ Monotone (Fibre G i) (F i))
    β†’ Monotone (∫ G) (Lexical-sum I F)
  splitα΅– G cases .hom    (i , x)     = i , cases i # x
  splitα΅– G cases .pres-≀ (i≀j , x≀y) = i≀j , Ξ» i=α΅’j β†’ lemma-pres-≀ i=α΅’j i≀j x≀y

The categorical definition of lexicographic sums is given by Reinhard BΓΆrger, Walter Tholen and Anna Tozzi in their paper Lexicographic sums and fibre-faithful maps.