From 1fd2213192d22880706440e7f724bdc6db966ee0 Mon Sep 17 00:00:00 2001 From: Juan Marin Noguera Date: Tue, 22 Aug 2023 17:56:56 +0200 Subject: Añadida presentación MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- present/index.html | 409 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 409 insertions(+) create mode 100644 present/index.html (limited to 'present/index.html') diff --git a/present/index.html b/present/index.html new file mode 100644 index 0000000..7eecb66 --- /dev/null +++ b/present/index.html @@ -0,0 +1,409 @@ + + + + + + + reveal.js + + + + + + + + + + +
+
+
+

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 routine 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.
    • +
+
+
+
+
+

Monomorfismos y epimorfismos

+
    +
  • Monomorfismo: + $f:a\rightarrowtail b$ tal que para cada $g,h:k\to a$, $f\circ + g=f\circ h\implies g=h$.
    • +
  • Epimorfismo: $f:a\twoheadrightarrow + b$ tal que para cada $g,h:b\to q$, $g\circ f=h\circ f\implies + g=h$.
    • +
  • Categoría dual: la misma pero con + el sentido de las flechas (y la composición) invertido.
    • +
  • Propiedad dual: La + misma propiedad en la categoría dual.
    • +
+
+
+

Monomorfismos y epimorfismos

+
    +
  • En constructos suelen ser los morfismos inyectivos y suprayectivos.
    • +
  • No es el caso, por ejemplo, en $\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)}$, e igualmente para $h$.
      • +
    • Por tanto $g\circ u=h\circ u\implies g=h$ y $u$ es un epimorfismo.
      • +
    +
    • +
  • Monomorfismo + epimorfismo $\neq$ isomorfismo.
    • +
+
+
+
+

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 imperativaProgramació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_b(Tf(x)).$$
    • +
+
+
+

Preguntas

+
+
+
+ + + + + + + + + -- cgit v1.2.3