Teoría de categorías

Una visión general con aplicaciones a la computación

Juan Marín Noguera
Julio de 2023

Tutor: Alberto del Valle Robles
Facultad de Matemáticas
Universidad de Murcia

Motivation

  • Known as abstract nonsense.
  • Common vocabulary
    • Isomorphisms
    • Products
    • Kernels
    • Quotients
    • etc.
  • Intuitive reasoning across fields
  • Rigorous transfer of knowledge across fields

Motivation

General results, appliable to a lot of fields

  • Abbreviate rutinary parts of proofs
  • Exploration of new areas
  • Diagram chasing

Bibliography

  • Adámek, Jiří & Herrlich, Horst & Strecker, George. Abstract and Concrete Categories: The Joy of Cats (1990).
  • Mac Lane, Saunders. Categories for the Working Mathematician (1971).
  • Riehl, Emily. Category Theory in Context (2014).
  • Some proofs and examples are mine.

Categories

  • Collections $\text{Ob}(\mathcal{C})$ and $\text{Mor}(\mathcal{C})$.
  • Functions $\text{dom},\text{cod}:\text{Mor}(\mathcal{C})\to\text{Ob}(\mathcal{C})$.
    • $f:a\to b$ means $\text{dom}\,f=a$ and $\text{cod}\,f=b$.
  • For $f:a\to b$ and $g:b\to c$, $g\circ f:a\to c$.
  • For every $a\in\text{Ob}(\mathcal{C})$, $1_a:a\to a$.
  • Construct: Category made up of sets and functions.

Monomorphisms and epimorphisms

  • Monomorphism: $f:a\rightarrowtail b$ such that for every $g,h:k\to a$, $f\circ g=f\circ h\implies g=h$.
  • Epimorphism: $f:a\twoheadrightarrow b$ such that for every $g,h:b\to q$, $g\circ f=h\circ f\implies g=h$.
  • Dual category: the same category but with direction of arrows (and composition) reversed.
  • Dual property: The same property in the dual category or categories.

Monomorphisms and epimorphisms

  • In constructs, these are usually the injective and surjective morphisms.
  • Not p.e. in $\mathbf{Rng}$.
    $\mathbb{Z}\overset{u}{\hookrightarrow}\mathbb{Q}\underset{h}{\overset{g}{\rightrightarrows}}A$
    • $g(\frac{p}{q})=\frac{g(p)}{g(q)}=\frac{(g\circ u)(p)}{(g\circ u)(q)}$, same for $h$.
    • Therefore $g\circ u=h\circ u\implies g=h$ and $u$ is an epimorphism.
  • Monomorphism + epimorphism $\neq$ isomorphism.

Funtores

Morfismos de categorías.

  • Función $T_0:\text{Ob}(\mathcal{C})\to\text{Ob}(\mathcal{D})$.
  • Para $a,b\in\text{Ob}(\mathcal{C})$, \[T_{a,b}:\hom(a,b)\to\hom(T_0a,T_0b).\]
  • $1_{T(a)}=T(1_a)$.
  • $T(g)\circ T(f)=T(g\circ f)$.
  • Categoría $\mathbf{Cat}$ de categorías pequeñas y funtores.

Transformaciones naturales

  • Sea $V$ un espacio vectorial de dimensión finita.
    • $V\cong V^*$, pero en general no hay un isomorfismo canónico.
    • $V\cong V^{**}$, isomorfismo natural $v\mapsto(f\mapsto f(v))$.
  • Morfismos que actúan siempre igual.
  • Dados dos funtores $S,T:\mathcal{C}\to\mathcal{D}$, función $\tau:\text{Ob}(\mathcal{C})\to\text{Mor}(\mathcal{D})$ tal que:

Flechas universales

Sean $U:\mathcal{C}\to\mathcal{B}$ un funtor y $b\in\text{Ob}(\mathcal{B})$.

  • $\mathbf{Mon}\to\mathbf{Set}$: $c=\left(\bigcup_nb^n,\bullet\right)$, $ux=(x)$.
  • $R\text{-}\mathbf{Mod}\to\mathbf{Set}$: $c=R^b$, $ux$ en la base.

Flechas universales

Sean $T:\mathcal{B}\to\mathcal{C}$ un funtor y $c\in\text{Ob}(\mathcal{C})$.

  • $\mathbf{Mon}\to\mathbf{Set}$: $c=\left(\bigcup_nb^n,\bullet\right)$, $ux=(x)$.
  • $R\text{-}\mathbf{Mod}\to\mathbf{Set}$: $c=R^b$, $ux$ en la base.

Adjunciones

Si todo objeto de $\mathcal{B}$ admite flecha universal hacia $G$...

\[(F,G,\eta,\varepsilon):\mathcal{B}\to\mathcal{C}\]
  • $G:\mathcal{C}\to\mathcal{B}$ suele ser un funtor olvidadizo.
  • $F:\mathcal{B}\to\mathcal{C}$ es el funtor libre.
  • $\eta:1_{\mathcal{B}}\to GF$ es la unidad.
  • $\varepsilon:FG\to 1_{\mathcal{C}}$ es la counidad.
  • $G\varepsilon\cdot\eta G=1_G$
  • $\varepsilon F\cdot F\eta=1_F$

Mónadas

  • $T:\mathcal{C}\to\mathcal{C}$
  • $\eta:1_{\mathcal{C}}\to T$
  • $\mu:T^2\to T$
  • $T=\mathcal{P}$
  • $\eta_X(x)=\{x\}$
  • $\mu_X(\mathcal{X})=\bigcup\mathcal{X}$
  • $T=GF$
  • $\eta=\eta$
  • $\mu=G\varepsilon F$

Categorías en programación

Programación imperativa Programación funcional
Estado accedido por variables. 
List<Item> list = new List<>();
int index;
 Variables que representan valores. 
let list = [item1, item2, ...]
Comandos que modifican el estado. 
list.insert(index, item1);
int sum = 0;
for (int i = 0; i < list.size(); i++)
    sum += list[i].price();
 Expresiones matemáticas. $\sum_{x\in\text{list}}\text{price}(x)\rightsquigarrow$
List.sum(List.map Item.price list)
Procedimientos. 
void printItem(Item item) {
    System.out.println(item.name().toString());
}
 Funciones puras. 
itemData item =
    Int.to_string (item.name)

Programación funcional

  • Cálculo lambda
    • $x$
    • $(\lambda x.M)$
    • $(M\,N)$
    • $(\lambda x.M[x])\to_\alpha(\lambda y.M[y])$
    • $((\lambda x.M)\,E)\to_\beta(M\{E/x\})$
    • $(\lambda x.M[x])\to_\eta M$
  • Teoría de categorías
    • Cada expresión tiene un tipo.
    • Las funciones (computables) de un tipo $a$ a un tipo $b$ tienen tipo $a\to b$.
    • Objetos: Tipos de dato.
    • Morfismos: Elementos de tipo $a\to b$.

Mónada IO

  • Las funciones puras no pueden, p. ej., mostrar datos por pantalla o interactuar con el usuario.
  • Para cada tipo $a$, un tipo $\mathtt{IO}\,a$ de las acciones que devuelven un elemento de tipo $a$.
  • Mónada $(\mathtt{IO},\eta,\mu)$.
    • Para $f:a\to b$, $(\mathtt{IO}\,f)(x)$ ejecuta $x$ y aplica $f$ al resultado.
    • $\eta_a(x)$ es una acción que no hace nada y devuelve $x$.
    • $\mu_a(x)$ ejecuta $x$ y ejecuta el resultado de $x$.

Mónada de manejo errores

  • Una función $f:a\to b\oplus e$ devuelve un valor de tipo $b$, o falla con un valor de tipo $e$.
  • Mónada $((\oplus\,e),\eta,\mu)$.
    • Para $f:a\to b$, $\,f\oplus e:x_a\rightsquigarrow f(x_a),x_e\rightsquigarrow x_e$.
    • $\eta_a:a\hookrightarrow a\oplus e$ es la inclusión en la unión disjunta.
    • $\mu_a:(a\oplus e)\oplus e\to a\oplus e$ identifica las dos copias de $e$.
  • Notación: Si $x:Ta$ y $f:a\to Tb$, $$(x\Rightarrow f)\coloneqq \mu_x(Tf(x)).$$