Benedikt Ahrens and RΓ©gis Spadotti— Terminal semantics for codata types in intensional Martin-Löf type theory
Table of contents
Index
Require Import Category.RComonad.
Require Import Category.RComod.
Require Import Category.RComonadWithCut.
Require Import Theory.Category.
Require Import Theory.Isomorphism.
Require Import Theory.Functor.
Require Import Theory.RelativeComonad.
Require Import Theory.RelativeComonadWithCut.
Require Import Theory.Comodule.
Require Import Theory.Product.
Require Import Theory.CartesianStrongMonoidal.
Require Import Theory.PrecompositionWithProduct.

Generalizable All Variables.

Pushforward comodule

Definition

Section Pushforward_construction.

  Context `{F : Functor π’ž π’Ÿ} {T S : RelativeComonad F}
           (Ο„ : T β‡’ S) `(M : Comodule T β„°).

  Program Definition pushforward : Comodule S β„° ≔
    Comodule.make⦃ M≔ M
    ; mcobind≔ Ξ» C D βˆ™ Ξ» f ↦ Mβ‹…mcobind (f ∘ Ο„(C)) ⦄.
  Show proof.
    solve_proper.
  Show proof.
    rewrite <- Ο„_counit. now rewrite mcobind_counit.
  Show proof.
    now rewrite compose_assoc,
                <- Ο„_commutes,
                mcobind_mcobind,
                <- compose_assoc.

End Pushforward_construction.

Functoriality of pushforward

Section Functoriality.

  Context `{F : Functor π’ž π’Ÿ} {T S : RelativeComonad F} {β„° : Category} {M N : Comodule S β„°}
          (Ο„ : S β‡’ T) (Ξ± : M β‡’ N).

  Infix "⁎" ≔ pushforward (at level 0).

  Program Definition pushforward_mor : ‡ Ο„βŽM β‡’ Ο„βŽN β€² ≔
    Comodule.make ⦃ Ξ± ≔ Ξ± ⦄.
  Show proof.
    now rewrite Ξ±_commutes.

End Functoriality.

Program Definition Pushforward
             `{F : Functor π’ž π’Ÿ} {T S : RelativeComonad F} (Ο„ : T β‡’ S) {β„°} : Functor (𝑹π‘ͺπ’π’Žπ’π’… T β„°) (𝑹π‘ͺπ’π’Žπ’π’… S β„°) ≔
  Functor.make⦃ F≔ pushforward Ο„
  ; map≔ Ξ» A B βˆ™ Ξ» f ↦ pushforward_mor Ο„ f ⦄.
Show proof.
  intros f g eq_fg x. simpl. now apply eq_fg.
Show proof.
  reflexivity.
Show proof.
  reflexivity.

Notation "Ο„ ⁎" ≔ (Pushforward Ο„) (at level 0).

Tautological comodule

Section tautological_comodule.

  Context `{F : Functor π’ž π’Ÿ} (T : RelativeComonad F).

  Program Definition tcomod : Comodule T π’Ÿ ≔
    Comodule.make⦃ M≔ T
    ; mcobind≔ Ξ» C D βˆ™ Tβ‹…cobind ⦄.
mcobind-counit
  Show proof.
    now rewrite cobind_counit.
mcobind-mcobind
  Show proof.
    now rewrite cobind_cobind.

End tautological_comodule.

Local Coercion tcomod : RelativeComonad >-> Comodule.
Notation "[ T ]" ≔ (tcomod T) (only parsing).

Induced morphism

Section induced_morphism.

  Context `{F : Functor π’ž π’Ÿ} {T S : RelativeComonad F}
          (Ο„ : T β‡’ S).

  Program Definition induced_morphism : ‡ Ο„βŽT β‡’ S β€² ≔
    Comodule.make ⦃ Ξ± ≔ Ξ» C βˆ™ Ο„(C) ⦄.
Ξ±-commutes
  Show proof.
    now rewrite Ο„_commutes.

End induced_morphism.

Notation "⟨ Ο„ ⟩" ≔ (induced_morphism Ο„) (at level 0).

Section Commutes.

  Context `{BinaryProduct π’ž} `{BinaryProduct π’Ÿ} {F : Functor π’ž π’Ÿ}
          {E : π’ž} `{!CartesianStrongMonoidal F} {T S : RelativeComonadWithCut F E}
          {Ο„ : T β‡’ S} `{M : Comodule T β„°}.

  Program Definition Ξ¦ : ‡ Ο„βŽ(M[E×─]) β‡’ (Ο„βŽM)[E×─] β€² ≔
    Comodule.make ⦃ Ξ± ≔ Ξ» X βˆ™ id[M (E Γ— X)] ⦄.
  Show proof.
    rewrite left_id, right_id.
    apply Ξ .cong.
    repeat rewrite compose_assoc.
    apply Ξ β‚‚.cong; [ reflexivity |].
    rewrite ∘-Γ—; apply Ξ β‚‚.cong.
    rewrite compose_assoc; apply Ξ β‚‚.cong; [ reflexivity |].
    apply Ο„_counit.
    rewrite compose_assoc. apply Ξ β‚‚.cong; [ reflexivity |].
    symmetry. apply Ο„_cut.

End Commutes.
Benedikt Ahrens and RΓ©gis Spadotti— Terminal semantics for codata types in intensional Martin-Löf type theory
Table of contents
Index