open import 1Lab.Path

open import Cat.Base

module Cat.Reasoning {o β„“} (C : Precategory o β„“) where

open import Cat.Morphism C public

Reasoning Combinators for CategoriesπŸ”—

When doing category theory, we often have to perform many β€œtrivial” algebraic manipulations like reassociation, insertion of identity morphisms, etc. On paper we can omit these steps, but Agda is a bit more picky! We could just do these steps in our proofs one after another, but this clutters things up. Instead, we provide a series of reasoning combinators to make writing (and reading) proofs easier.

Most of these helpers were taken from agda-categories.

Identity MorphismsπŸ”—

id-comm : βˆ€ {a b} {f : Hom a b} β†’ f ∘ id ≑ id ∘ f
id-comm {f = f} = idr f βˆ™ sym (idl f)

id-comm-sym : βˆ€ {a b} {f : Hom a b} β†’ id ∘ f ≑ f ∘ id
id-comm-sym {f = f} = idl f βˆ™ sym (idr f)

module _ (a≑id : a ≑ id) where

  eliml : a ∘ f ≑ f
  eliml {f = f} =
    a ∘ f β‰‘βŸ¨ ap (_∘ f) a≑id βŸ©β‰‘
    id ∘ f β‰‘βŸ¨ idl f βŸ©β‰‘
    f ∎

  elimr : f ∘ a ≑ f
  elimr {f = f} =
    f ∘ a β‰‘βŸ¨ ap (f ∘_) a≑id βŸ©β‰‘
    f ∘ id β‰‘βŸ¨ idr f βŸ©β‰‘
    f ∎

  introl : f ≑ a ∘ f
  introl = sym eliml

  intror : f ≑ f ∘ a
  intror = sym elimr

ReassocationsπŸ”—

We often find ourselves in situations where we have an equality involving the composition of 2 morphisms, but the association is a bit off. These combinators aim to address that situation.

module _ (ab≑c : a ∘ b ≑ c) where

  pulll : a ∘ (b ∘ f) ≑ c ∘ f
  pulll {f = f} =
    a ∘ b ∘ f   β‰‘βŸ¨ assoc a b f βŸ©β‰‘
    (a ∘ b) ∘ f β‰‘βŸ¨ ap (_∘ f) ab≑c βŸ©β‰‘
    c ∘ f ∎

  pullr : (f ∘ a) ∘ b ≑ f ∘ c
  pullr {f = f} =
    (f ∘ a) ∘ b β‰‘Λ˜βŸ¨ assoc f a b βŸ©β‰‘Λ˜
    f ∘ (a ∘ b) β‰‘βŸ¨ ap (f ∘_) ab≑c βŸ©β‰‘
    f ∘ c ∎

module _ (c≑ab : c ≑ a ∘ b) where

  pushl : c ∘ f ≑ a ∘ (b ∘ f)
  pushl = sym (pulll (sym c≑ab))

  pushr : f ∘ c ≑ (f ∘ a) ∘ b
  pushr = sym (pullr (sym c≑ab))

module _ (p : f ∘ h ≑ g ∘ i) where
  extendl : f ∘ (h ∘ b) ≑ g ∘ (i ∘ b)
  extendl {b = b} =
    f ∘ (h ∘ b) β‰‘βŸ¨ assoc f h b βŸ©β‰‘
    (f ∘ h) ∘ b β‰‘βŸ¨ ap (_∘ b) p βŸ©β‰‘
    (g ∘ i) ∘ b β‰‘Λ˜βŸ¨ assoc g i b βŸ©β‰‘Λ˜
    g ∘ (i ∘ b) ∎

  extendr : (a ∘ f) ∘ h ≑ (a ∘ g) ∘ i
  extendr {a = a} =
    (a ∘ f) ∘ h β‰‘Λ˜βŸ¨ assoc a f h βŸ©β‰‘Λ˜
    a ∘ (f ∘ h) β‰‘βŸ¨ ap (a ∘_) p βŸ©β‰‘
    a ∘ (g ∘ i) β‰‘βŸ¨ assoc a g i βŸ©β‰‘
    (a ∘ g) ∘ i ∎

  extend-inner : a ∘ f ∘ h ∘ b ≑ a ∘ g ∘ i ∘ b
  extend-inner {a = a} = ap (a ∘_) extendl

CancellationπŸ”—

These lemmas do 2 things at once: rearrange parenthesis, and also remove things that are equal to id.

module _ (inv : h ∘ i ≑ id) where

  cancell : h ∘ (i ∘ f) ≑ f
  cancell {f = f} =
    h ∘ (i ∘ f) β‰‘βŸ¨ pulll inv βŸ©β‰‘
    id ∘ f β‰‘βŸ¨ idl f βŸ©β‰‘
    f ∎

  cancelr : (f ∘ h) ∘ i ≑ f
  cancelr {f = f} =
    (f ∘ h) ∘ i β‰‘βŸ¨ pullr inv βŸ©β‰‘
    f ∘ id β‰‘βŸ¨ idr f βŸ©β‰‘
    f ∎

  insertl : f ≑ h ∘ (i ∘ f)
  insertl = sym cancell

  insertr : f ≑ (f ∘ h) ∘ i
  insertr = sym cancelr

  cancel-inner : (f ∘ h) ∘ (i ∘ g) ≑ f ∘ g
  cancel-inner = pulll cancelr

IsomorphismsπŸ”—

These lemmas are useful for proving that partial inverses to an isomorphism are unique. There’s a helper for proving uniqueness of left inverses, of right inverses, and for proving that any left inverse must match any right inverse.

module _ {y z} (f : y β‰… z) where
  open _β‰…_

  left-inv-unique
    : βˆ€ {g h}
    β†’ g ∘ f .to ≑ id β†’ h ∘ f .to ≑ id
    β†’ g ≑ h
  left-inv-unique {g = g} {h = h} p q =
    g                   β‰‘βŸ¨ intror (f .invl) βŸ©β‰‘
    g ∘ f .to ∘ f .from β‰‘βŸ¨ extendl (p βˆ™ sym q) βŸ©β‰‘
    h ∘ f .to ∘ f .from β‰‘βŸ¨ elimr (f .invl) βŸ©β‰‘
    h                   ∎

  left-right-inv-unique
    : βˆ€ {g h}
    β†’ g ∘ f .to ≑ id β†’ f .to ∘ h ≑ id
    β†’ g ≑ h
  left-right-inv-unique {g = g} {h = h} p q =
    g                    β‰‘βŸ¨ intror (f .invl) βŸ©β‰‘
    g ∘ f .to ∘ f .from  β‰‘βŸ¨ cancell p βŸ©β‰‘
    f .from              β‰‘βŸ¨ intror q βŸ©β‰‘
    f .from ∘ f .to ∘ h  β‰‘βŸ¨ cancell (f .invr) βŸ©β‰‘
    h                    ∎

  right-inv-unique
    : βˆ€ {g h}
    β†’ f .to ∘ g ≑ id β†’ f .to ∘ h ≑ id
    β†’ g ≑ h
  right-inv-unique {g = g} {h} p q =
    g                     β‰‘βŸ¨ introl (f .invr) βŸ©β‰‘
    (f .from ∘ f .to) ∘ g β‰‘βŸ¨ pullr (p βˆ™ sym q) βŸ©β‰‘
    f .from ∘ f .to ∘ h   β‰‘βŸ¨ cancell (f .invr) βŸ©β‰‘
    h                     ∎

NotationπŸ”—

When doing equational reasoning, it’s often somewhat clumsy to have to write ap (f ∘_) p when proving that f ∘ g ≑ f ∘ h. To fix this, we define steal some cute mixfix notation from agda-categories which allows us to write β‰‘βŸ¨ refl⟩∘⟨ p ⟩ instead, which is much more aesthetically pleasing!

_⟩∘⟨_ : f ≑ h β†’ g ≑ i β†’ f ∘ g ≑ h ∘ i
_⟩∘⟨_ = apβ‚‚ _∘_

refl⟩∘⟨_ : g ≑ h β†’ f ∘ g ≑ f ∘ h
refl⟩∘⟨_ {f = f} p = ap (f ∘_) p

_⟩∘⟨refl : f ≑ h β†’ f ∘ g ≑ h ∘ g
_⟩∘⟨refl {g = g} p = ap (_∘ g) p