Ciencias de la Computación FAMAF

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== Teoría de Categorías ======

===== Generalidades =====

  * Docente: Daniel Fridlender.
  * Dictado: 2 clases teóricas semanales de 2 horas (lunes y miércoles de 14 a 16 hs en el aula 15) + horario de consulta para resolución de ejercicios (lunes y miércoles de 16 a 17 hs en el aula 15).
  * Regularidad: entrega de resolución de ejercicios seleccionados: {{:categorias:parcial1.pdf| Primera selección}} y {{:categorias:parcial2.pdf|segunda selección}}.
  * Examen: examen final integrador que incluirá la defensa de las resoluciones de los ejercicios seleccionados.
  * Programa: El {{:categorias:programacategorias.pdf |programa}} fue tomado de los contenidos de [1].  El curso contará con más material, en particular se utilizará también [2] y quizá [3]. Además de los ejemplos tradicionales tomados de la matemática, se considerarán ejemplos de computación. También [4] refleja el enfoque adoptado, al menos en las primeras clases.

===== Contenidos, clase por clase =====

Abajo están los apuntes de c/u de las clases, o {{:categorias:categorias.pdf|todo junto.}}

  * Primera clase (8/8): Diferentes definiciones de grafos, grafos finitos e infinitos, grafos localmente finitos. Funciones. Categorías, definición, primeras observaciones. Demostración gráfica, demostración ecuacional. Ejemplos de categorías. Con grafos: las categorías 0, 1 y 2. Con funciones: las categorías Set, Set_fin, Inj, Surj, algunas variantes y Pfn. Con programas: las categorías lambda flecha, y de estados. {{:categorias:clase1.pdf|Apuntes.}}

  * Segunda clase (10/8): Categorías concretas. Semigrupo, monoide y grupo. Ejemplos habituales (números, cadenas y permutaciones). El monoide Hom_C(A,A). Propiedades elementales de estas estructuras. Homomorfismo de semigrupo, monoide y grupo. Ejemplos. Categorías Semi, Mon y Grp. Generalización (categoría (Omega,E)-Alg). Conjunto parcialmente ordenado y función monótona. La categoría Poset. Homomorfismo de grafos. La categoría Graph. Funtores. Ejemplos. La categoría Cat. Categorías pequeñas y grandes. Categorías localmente pequeñas. {{:categorias:clase2.pdf|Apuntes.}}

  * Tercera clase (15/8): Isomorfismo. Objetos isomorfos. Objetos inicial y terminal. Unicidad (salvo isomorfismo). Objetos iniciales y terminales de las categorías vistas. Categoría 3 y n. Conjuntos parcialmente ordenados o preordenados vistos como categorías, sus objetos iniciales y terminales y sus isomorfismos. Construcción de una categoría a partir de un grafo sin y con ciclos. Las categorías Path_G y Rel. {{:categorias:clase3.pdf|Apuntes.}}

  * Cuarta clase (17/8): Subcategoría. Equivalencia con funtores inyectivos. Categoría opuesta. Principio de dualidad. Producto Cartesiano, definición, unicidad (salvo isomorfismo), ecuaciones, ejemplos. Producto de categorías. Producto cartesiano. {{:categorias:clase4.pdf|Apuntes.}}

  * Quinta clase (24/8): Ejemplo de producto: en Set, en categorías discretas, en un preorden, en el cálculo lambda, en rel. Definición de producto usando hom-sets. Co-producto, definición, ejemplo, ejercicios. {{:categorias:clase5.pdf|Apuntes.}}

  * Sexta clase (29/8): Prueba de asociatividad del producto. La categoría Set* de los conjuntos punteados. Monomorfismos y epimorfismos. Ecualizadores. {{:categorias:clase6.pdf|Apuntes.}}

  * Séptima clase (31/8): Coecualizadores. Pullbacks. Equivalencia entre: (pullbacks + 1) y (productos finitos + ecualizadores). {{:categorias:clase7.pdf|Apuntes.}}

  * Octava clase (5/9): Categorías de flechas (Categoría Slice, Coslice y Flecha). Funtores dom y cod. Funtores representables covariantes. Funtores producto y pullback. {{:categorias:clase8.pdf|Apuntes.}}

  * Novena clase (7/9): Definición de Diagrama, Cono y Límite. Equivalencia entre (productos finitos + ecualizadores) y límites finitos. Generalización al caso infinito. Cocono y Colímite. {{:categorias:clase9.pdf|Apuntes.}}

  * Décima clase (12/9): Exponenciales: motivación, definición, categorías cartesianas cerradas. Ejemplos. Propiedades.{{:categorias:clase10.pdf|Apuntes.}}

  * Undécima clase (14/9): Ejemplos de exponenciales de lógica y computación: Álgebras de Heyting. Lógica proposicional intuicionista. Cálculo lambda. Álgebras de Heyting como modelo de la lógica proposicional intuicionista. Categorías cartesianas cerradas como modelo del cálculo lambda. Comparación entre estas dos correspondencias.  {{:categorias:clase11.pdf|Apuntes.}}

  * Duodécima clase (26/9): Límites y colímites en Cat. La categoría de funtores entre dos categorías. Transformaciones naturales. Isomorfismos naturales. Ejemplos.  {{:categorias:clase12.pdf|Apuntes.}}

  * Decimotercera clase (28/9): Límites y colimites de la categoría D^C. Funtores representables contravariantes. Definición alternativa de producto cartesiano en una categoría localmente pequeña.   {{:categorias:clase13.pdf|Apuntes.}}

  * Decimocuarta clase (3/10): Lema bifuntor. La categoría D^C es el exponencial de la categoría Cat. Ejemplos.   {{:categorias:clase14.pdf|Apuntes.}}

  * Decimoquinta clase (5/10): Categorías funtoriales. Funtores full y faithful. Equivalencia entre categorías. Ejemplos.   {{:categorias:clase15.pdf|Apuntes.}}

  * Decimosexta clase (12/10): Equivalencia entre categorías. Proposición. Ejemplo. Embedding Yoneda. {{:categorias:clase16.pdf|Apuntes.}}

  * Decimoséptima clase (17/10): Lema de Yoneda. Prueba y aplicaciones. {{:categorias:clase17.pdf|Apuntes.}}

  * Decimooctava clase (19/10): Aplicaciones del lema de Yoneda. El embedding es full y faithfull. Límites, más abstractos. {{:categorias:clase18.pdf|Apuntes.}}

  * Decimonovena clase (24/10): Adjunciones. Monoide libre y funtor de olvido. Definición. Funtor diagonal y producto binario. Hacia una definición simétrica. {{:categorias:clase19.pdf|Apuntes.}}

  * Vigésima clase (26/10): Definición simétrica de adjunciones. Ejemplos. Categorías equivalentes implica existencia de adjunciones. Unicidad del adjunto. {{:categorias:clase20.pdf|Apuntes.}}

  * Vigesimoprimera clase (31/10): Ejemplos de adjunción. Adjunciones, límites y colímites. Órdenes y conexiones de Galois. Cuantificadores. Secuencias de adjunciones. Adjunciones preservan límites o colímites. {{:categorias:clase21.pdf|Apuntes.}}

  * Vigesimosegunda clase (2/11): Mónadas. Adjunciones son mónadas. Ejemplos. {{:categorias:clase22.pdf|Apuntes.}}

  * Vigesimotercera clase (7/11): Mónadas en la programación funcional. Ejemplos. {{:categorias:clase23.pdf|Apuntes.}} Archivos con los ejemplos en Haskell: [[sin monadas]] y [[con monadas]].

  * Vigesimocuarta clase (9/11): Las mónadas son adjunciones. Categoría de T-álgebras. Comónadas, coálgebras. {{:categorias:clase24.pdf|Apuntes.}}

  * Vigesimoquinta clase (16/11): Tipos inductivos y coinductivos. Categorías de álgebras y de coálgebras. {{:categorias:clase25.pdf|Apuntes.}}


===== Bibliografía =====

  * [1] Steve Awodey. Category Theory, 2006, 2010.
  * [2] Benjamin C. Pierce. Basic Category Theory for Computer Scientist, 1991.
  * [3] Andrea Asperti y Giuseppe Longo. Categories, Types and Structures: An Introduction to Category Theory for the Working Computer Scientist, 1991.
  * [4] Michael Barr y Charles Wells. Category Theory, 1999.
  * Jirí Adámek, Horst Herrlich y George E. Strecker. Abstract and Concrete Categories: The Joy of Cats, 1990, 2004.
  * F. William Lawvere, Stephen H. Schanuel. Conceptual Mathematics: A First Introduction to Categories, 1991.
  * Saunders Mac Lane. Categories for the Working Mathematician, 1971.
  * Jaap van Oosten. Basic Category Theory, 1995.
  * A. Schalk y H. Simmons. An Introduction to Category Theory in four easy movements, 2005.