[The University of Leicester]

Department of Mathematics & Computer Science



Next: Rewriting for Kan Extensions Up: paper10 Previous: Introduction

Presentations of Kan Extensions

Let $ \mathsf{A}$ be a category. A category action $ X$ of $ \mathsf{A}$ is a functor $ X:\mathsf{A}\to \mathsf{Sets}$. Let $ \mathsf{B}$ be a second category and let $ F:\mathsf{A}\to \mathsf{B}$ be a functor. Then an extension of the action $ X$ along $ F$ is a pair $ (K,\varepsilon )$ where $ K:\mathsf{B}\to \mathsf{Sets}$ is a functor and $ \varepsilon :X \to K \circ F$ is a natural transformation. The Kan extension of the action $ X$ along $ F$ is an extension of the action $ (K,\varepsilon )$ with the universal property that for any other extension of the action $ (K',\varepsilon ')$ there exists a unique natural transformation $ \alpha:K \to K'$ such that $ \varepsilon '=\alpha \circ \varepsilon $.

The problem that has been introduced is that of ``computing a Kan extension''. In order to keep the analogy with computation and rewriting for presentations of monoids we propose a definition of a presentation of a Kan extension. The papers [2,4,5,7] were very influential on the current work.

A Kan extension data $ (X',F')$ consists of small categories $ \mathsf{A}$, $ \mathsf{B}$ and functors $ X':\mathsf{A}\to \mathsf{Sets}$ and $ F':\mathsf{A}\to \mathsf{B}$. A Kan extension presentation is a quintuple $ \mathcal{P}:=kan \langle \Gamma \vert \Delta \vert RelB \vert X \vert F \rangle $ where

  1. $ \Gamma$ and $ \Delta$ are (directed) graphs;
  2. $ X: \Gamma \to \mathsf{Sets}$ and $ F: \Gamma \to P \Delta$ are graph morphisms to the category of sets and the free category on $ \Delta$ respectively;
  3. and $ RelB$ is a set of relations on the free category $ P\Delta$.

We say $ \mathcal{P}$ presents the Kan extension $ (K,\varepsilon )$ of the Kan extension data $ (X',F')$ where $ X':\mathsf{A}\to \mathsf{Sets}$ and $ F':\mathsf{A}\to \mathsf{B}$ if

  1. $ \Gamma$ is a generating graph for $ \mathsf{A}$ and $ X: \Gamma \to \mathsf{Sets}$ is the restriction of $ X':\mathsf{A}\to \mathsf{Sets}$
  2. $ cat \langle \Delta \vert RelB \rangle $ is a category presentation for $ \mathsf{B}$.
  3. $ F: \Gamma \to P \Delta$ induces $ F':\mathsf{A}\to \mathsf{B}$.

We expect that a Kan extension $ (K,\varepsilon )$ is given by a set $ KB$ for each $ B \in {\mathrm{ Ob}}\Delta$ and a function $ Kb: KB_1 \to KB_2$ for each $ b:B_1 \to B_2 \in \mathsf{B}$ (defining the functor $ K$) together with a function $ \varepsilon _A: XA \to KFA$ for each $ A \in {\mathrm{ Ob}}\mathsf{A}$ (the natural transformation). This information can be given in four parts:

Here $ \bigsqcup_B KB$ and $ \bigsqcup_A XA$ are the disjoint unions of the sets $ KB$, $ XA$ over $ {\mathrm{ Ob}}\mathsf{B}$, $ {\mathrm{ Ob}}\mathsf{A}$ respectively; if $ z \in KB$ then $ \overline {\tau}(z)=B$ and if further $ src(p)=B$ for $ p \in \mathrm{Arr}\mathsf{P}$ then $ z \cdot p$ is defined.

Next: Rewriting for Kan Extensions Up: paper10 Previous: Introduction

[University Home] [MCS Home] [University Index A-Z] [University Search] [University Help]

Author: A. Heyworth, tel: +44 (0)116 252 3884
Last updated: 2000-11-24
MCS Web Maintainer
This document has been approved by the Head of Department.
© University of Leicester.