Categoría cerrada cartesiana

Tipo de categoría en la teoría de categorías.

En teoría de categorías , una categoría es cartesiana cerrada si, en términos generales, cualquier morfismo definido en un producto de dos objetos puede identificarse naturalmente con un morfismo definido en uno de los factores. Estas categorías son particularmente importantes en la lógica matemática y la teoría de la programación, ya que su lenguaje interno es el cálculo lambda simplemente tipificado . Se generalizan mediante categorías monoidales cerradas , cuyo lenguaje interno, los sistemas de tipo lineal , son adecuados tanto para la computación cuántica como para la clásica. ^[1]

Etimología

Debe su nombre a René Descartes (1596-1650), filósofo, matemático y científico francés, cuya formulación de la geometría analítica dio origen al concepto de producto cartesiano , que luego se generalizó a la noción de producto categórico .

Definición

La categoría C se llama cartesiana cerrada ^[2] si y sólo si satisface las siguientes tres propiedades:

• Tiene un objeto terminal .
• Dos objetos cualesquiera X e Y de C tienen un producto X  × Y en C.
• Dos objetos cualesquiera Y y Z de C tienen una Z ^Y exponencial en C.

Las dos primeras condiciones se pueden combinar con el único requisito de que cualquier familia finita (posiblemente vacía) de objetos de C admita un producto en C , debido a la asociatividad natural del producto categórico y porque el producto vacío en una categoría es el objeto terminal. de esa categoría.

La tercera condición es equivalente al requisito de que el funtor – × Y (es decir, el funtor de C a C que asigna objetos X a X  × Y y morfismos φ a φ × id _Y ) tenga un adjunto derecho , generalmente denotado –Y ^, por todos los objetos Y en C . Para categorías localmente pequeñas , esto se puede expresar mediante la existencia de una biyección entre los hom-sets.

${\displaystyle \mathrm {Hom} (X\times Y,Z)\cong \mathrm {Hom} (X,Z^{Y})}$

que es natural en X , Y y Z . ^[3]

Tenga en cuenta que una categoría cerrada cartesiana no necesita tener límites finitos; Sólo se garantizan productos finitos.

Si una categoría tiene la propiedad de que todas sus categorías de sectores son cartesianas cerradas, entonces se denomina localmente cartesiana cerrada . ^[4] Tenga en cuenta que si C es localmente cerrado cartesiano, en realidad no necesita ser cerrado cartesiano; eso sucede si y sólo si C tiene un objeto terminal.

Construcciones basicas

Evaluación

Para cada objeto Y , la unidad de la conjunción exponencial es una transformación natural

${\displaystyle \mathrm {ev} _{Y,Z}:Z^{Y}\times Y\to Z}$

llamado mapa de evaluación (interno) . De manera más general, podemos construir el mapa de aplicación parcial como el mapa compuesto.

${\displaystyle \mathrm {papply} _{X,Y,Z}:Z^{X\times Y}\times X\cong (Z^{Y})^{X}\times X{\xrightarrow {\mathrm {ev} _{X,Z^{Y}}}}Z^{Y}.}$

En el caso particular de la categoría Conjunto , estas se reducen a las operaciones ordinarias:

${\displaystyle \mathrm {ev} _{Y,Z}(f,y)=f(y).}$

Composición

Evaluar el exponencial en un argumento en un morfismo p  : X → Y da morfismos

${\displaystyle p^{Z}:X^{Z}\to Y^{Z},}$

${\displaystyle Z^{p}:Z^{Y}\to Z^{X},}$

correspondiente a la operación de composición con p . Las notaciones alternativas para la operación p ^Z incluyen p _* y p∘- . Las notaciones alternativas para la operación Z ^p incluyen p ^* y -∘p .

Los mapas de evaluación se pueden encadenar como

${\displaystyle Z^{Y}\times Y^{X}\times X{\xrightarrow {\mathrm {id} \times \mathrm {ev} _{X,Y}}}Z^{Y}\times Y{\xrightarrow {\mathrm {ev} _{Y,Z}}}Z}$

la flecha correspondiente debajo de la conjunción exponencial

${\displaystyle c_{X,Y,Z}:Z^{Y}\times Y^{X}\to Z^{X}}$

se llama mapa de composición (interno) .

En el caso particular de la categoría Set , esta es la operación de composición ordinaria:

${\displaystyle c_{X,Y,Z}(g,f)=g\circ f.}$

Secciones

Para un morfismo p : X → Y , supongamos que existe el siguiente cuadrado de retroceso, que define el subobjeto de X ^Y correspondiente a mapas cuyo compuesto con p es la identidad:

${\displaystyle {\begin{array}{ccc}\Gamma _{Y}(p)&\to &X^{Y}\\\downarrow &&\downarrow \\1&\to &Y^{Y}\end{array}}}$

donde la flecha de la derecha es p ^Y y la flecha de abajo corresponde a la identidad en Y . Entonces Γ _Y ( p ) se llama objeto de secciones de p . A menudo se abrevia como Γ _Y ( X ).

Si Γ _Y ( p ) existe para cada morfismo p con codominio Y , entonces se puede ensamblar en un funtor Γ _Y  : C / Y → C en la categoría de sector, que está junto a una variante del funtor de producto:

${\displaystyle \hom _{C/Y}(X\times Y{\xrightarrow {\pi _{2}}}Y,Z{\xrightarrow {p}}Y)\cong \hom _{C}(X,\Gamma _{Y}(p)).}$

La exponencial de Y se puede expresar en términos de secciones:

${\displaystyle Z^{Y}\cong \Gamma _{Y}(Z\times Y{\xrightarrow {\pi _{2}}}Y).}$

Ejemplos

Ejemplos de categorías cerradas cartesianas incluyen:

• La categoría Conjunto de todos los conjuntos , con funciones como morfismos, es cartesiana cerrada. El producto X × Y es el producto cartesiano de X e Y , y Z ^Y es el conjunto de todas las funciones de Y a Z. La adjunción se expresa por el siguiente hecho: la función f  : X × Y → Z se identifica naturalmente con la función curry g  : X → Z ^Y definida por g ( x )( y ) = f ( x , y ) para todo x en X y y en Y.​
• La categoría de conjuntos finitos , con funciones como morfismos, es cartesiana cerrada por la misma razón.
• Si G es un grupo , entonces la categoría de todos los conjuntos G es cartesiana cerrada. Si Y y Z son dos conjuntos G , entonces Z ^Y es el conjunto de todas las funciones de Y a Z con acción G definida por ( g . F )( y ) = g .F( g ⁻¹ .y) para todo g en GRAMO , F : Y → Z y y en Y.​
• La categoría de conjuntos G finitos también es cartesiana cerrada.
• La categoría Cat de todas las categorías pequeñas (con functores como morfismos) es cartesiana cerrada; el C ^D exponencial viene dado por la categoría de funtores que consta de todos los funtores de D a C , con transformaciones naturales como morfismos.
• Si C es una categoría pequeña , entonces el conjunto de categorías de funtores ^C que consta de todos los funtores covariantes de C en la categoría de conjuntos, con transformaciones naturales como morfismos, es cartesiano cerrado. Si F y G son dos funtores de C a Set , entonces el exponencial F ^G es el funtor cuyo valor en el objeto X de C viene dado por el conjunto de todas las transformaciones naturales de ( X ,−) ×  G a F.
  • El ejemplo anterior de conjuntos G puede verse como un caso especial de categorías de funtores: cada grupo puede considerarse como una categoría de un solo objeto, y los conjuntos G no son más que funtores de esta categoría a Conjunto.
  • La categoría de todos los gráficos dirigidos es cartesiana cerrada; esta es una categoría de funtor como se explica en categoría de funtor.
  • En particular, la categoría de conjuntos simpliciales (que son functores X  : Δ ^op → Set ) es cartesiana cerrada.
• De manera aún más general, todo topos elemental es cartesiano cerrado.
• En topología algebraica , es particularmente fácil trabajar con categorías cerradas cartesianas. Ni la categoría de espacios topológicos con mapas continuos ni la categoría de variedades suaves con mapas suaves son cartesianas cerradas. Por lo tanto, se han considerado categorías sustitutas: la categoría de espacios de Hausdorff generados de forma compacta es cartesiana cerrada, al igual que la categoría de espacios de Frölicher .
• En la teoría del orden , los órdenes parciales completos ( cpo s) tienen una topología natural, la topología de Scott , cuyos mapas continuos sí forman una categoría cerrada cartesiana (es decir, los objetos son los cpos y los morfismos son los mapas continuos de Scott ). Tanto currying como apply son funciones continuas en la topología de Scott, y currying, junto con apply, proporcionan el adjunto. ^[5]
• Un álgebra de Heyting es una red cartesiana cerrada (acotada) . Un ejemplo importante surge de los espacios topológicos. Si X es un espacio topológico, entonces los conjuntos abiertos en X forman los objetos de una categoría O( X ) para la cual existe un morfismo único de U a V si U es un subconjunto de V y ningún morfismo en caso contrario. Este poset es una categoría cerrada cartesiana: el "producto" de U y V es la intersección de U y V y el exponencial U ^V es el interior de U ∪( X \ V ) .
• Una categoría con un objeto cero es cartesiana cerrada si y solo si es equivalente a una categoría con un solo objeto y un morfismo de identidad. De hecho, si 0 es un objeto inicial y 1 es un objeto final y tenemos , entonces tiene un solo elemento. ^[6] ${\displaystyle 0\cong 1}$ ${\displaystyle \mathrm {Hom} (X,Y)\cong \mathrm {Hom} (1,Y^{X})\cong \mathrm {Hom} (0,Y^{X})\cong 1}$
  • En particular, cualquier categoría no trivial con un objeto cero, como una categoría abeliana , no es cartesiana cerrada. Entonces la categoría de módulos sobre un anillo no es cartesiana cerrada. Sin embargo, el producto tensorial funtor con módulo fijo tiene un adjunto derecho . El producto tensorial no es un producto categórico, por lo que esto no contradice lo anterior. Obtenemos en cambio que la categoría de módulos es monoidal cerrada . ${\displaystyle -\otimes M}$

Ejemplos de categorías cerradas localmente cartesianas incluyen:

• Todo topos elemental es localmente cartesiano cerrado. Este ejemplo incluye Set , FinSet , G -sets para un grupo G , así como Set ^C para categorías pequeñas C .
• La categoría LH cuyos objetos son espacios topológicos y cuyos morfismos son homeomorfismos locales es localmente cartesiana cerrada, ya que LH/X equivale a la categoría de gavillas . Sin embargo, LH no tiene un objeto terminal y, por tanto, no es cartesiano cerrado. ${\displaystyle Sh(X)}$
• Si C tiene retrocesos y para cada flecha p  : X → Y , el funtor p ^*  : C/Y → C/X dado al tomar retrocesos tiene un adjunto derecho, entonces C es localmente cartesiano cerrado.
• Si C es localmente cartesiano cerrado, entonces todas sus categorías de sectores C/X también son localmente cartesiano cerrado.

Los no ejemplos de categorías cerradas localmente cartesianas incluyen:

• Cat no es localmente cartesiano cerrado.

Aplicaciones

En categorías cerradas cartesianas, una "función de dos variables" (un morfismo f  : X × Y → Z ) siempre se puede representar como una "función de una variable" (el morfismo λ f  : X → Z ^Y ). En aplicaciones informáticas , esto se conoce como curry ; ha llevado a la comprensión de que el cálculo lambda de tipo simple se puede interpretar en cualquier categoría cerrada cartesiana.

La correspondencia Curry-Howard-Lambek proporciona un profundo isomorfismo entre la lógica intuicionista, el cálculo lambda de tipo simple y las categorías cerradas cartesianas.

Ciertas categorías cerradas cartesianas, los topoi , han sido propuestas como marco general para las matemáticas, en lugar de la tradicional teoría de conjuntos .

El informático John Backus ha abogado por una notación libre de variables, o programación a nivel de función , que en retrospectiva guarda cierta similitud con el lenguaje interno de las categorías cerradas cartesianas. ^[7] CAML se modela más conscientemente en categorías cerradas cartesianas.

Suma y producto dependientes

Sea C una categoría cerrada localmente cartesiana. Entonces C tiene todos los retrocesos, porque el retroceso de dos flechas con codominio Z viene dado por el producto en C/Z .

Para cada flecha p  : X → Y , sea P el objeto correspondiente de C/Y . Al realizar retrocesos a lo largo de p se obtiene un funtor p ^*  : C/Y → C/X que tiene un adjunto izquierdo y otro derecho.

El adjunto izquierdo se llama suma dependiente y está dado por la composición . ${\displaystyle \Sigma _{p}:C/X\to C/Y}$ ${\displaystyle p\circ (-)}$

El adjunto derecho se llama producto dependiente . ${\displaystyle \Pi _{p}:C/X\to C/Y}$

La exponencial de P en C/Y se puede expresar en términos del producto dependiente mediante la fórmula . ${\displaystyle Q^{P}\cong \Pi _{p}(p^{*}(Q))}$

El motivo de estos nombres es que, al interpretar P como un tipo dependiente , los functores y corresponden a las formaciones de tipo y respectivamente. ${\displaystyle y:Y\vdash P(y):\mathrm {Type} }$ ${\displaystyle \Sigma _{p}}$ ${\displaystyle \Pi _{p}}$ ${\displaystyle \Sigma _{x:P(y)}}$ ${\displaystyle \Pi _{x:P(y)}}$

Teoría ecuacional

En cada categoría cerrada cartesiana (usando notación exponencial), ( X ^Y ) ^Z y ( X ^Z ) ^Y son isomórficos para todos los objetos X , Y y Z . Escribimos esto como la "ecuación"

( x ^y ) ^z = ( x ^z ) ^y .

Cabe preguntarse qué otras ecuaciones similares son válidas en todas las categorías cerradas cartesianas. Resulta que todos ellos se derivan lógicamente de los siguientes axiomas: ^[8]

• x ×( y × z ) = ( x × y )× z
• x × y = y × x
• x ×1 = x (aquí 1 denota el objeto terminal de C )
• 1 ^x = 1
• x1 = x^​
• ( x × y ) ^z = x ^z × y ^z
• ( x ^y ) ^z = x ^{( y × z )}

Categorías cerradas bicartesianas

Las categorías cerradas bicartesianas amplían las categorías cerradas cartesianas con coproductos binarios y un objeto inicial , con productos distribuyéndose sobre los coproductos. Su teoría ecuacional se amplía con los siguientes axiomas, lo que produce algo similar a los axiomas de la escuela secundaria de Tarski pero con un cero:

• x + y = y + x
• ( x + y ) + z = x + ( y + z )
• x ×( y + z ) = x × y + x × z
• x ^{( y + z )} = x ^y ×x ^z
• 0 + x = x
• x ×0 = 0
• x0 ⁼ 1

Sin embargo, tenga en cuenta que la lista anterior no está completa; El isomorfismo de tipos en el BCCC libre no es finitamente axiomatizable y su decidibilidad sigue siendo un problema abierto. ^[9]

Referencias

1. Báez, John C .; Quédate, Mike (2011). "Física, topología, lógica y computación: una piedra de Rosetta" (PDF) . En Coecke, Bob (ed.). Nuevas estructuras para la física . Apuntes de conferencias de física. vol. 813. Saltador. págs. 95-174. arXiv : 0903.0340 . CiteSeerX  10.1.1.296.1044 . doi :10.1007/978-3-642-12821-9_2. ISBN 978-3-642-12821-9. S2CID  115169297.
2. Saunders, Mac Lane (1978). Categorías para el matemático que trabaja (2ª ed.). Saltador. ISBN 1441931236. OCLC  851741862.
3. "categoría cerrada cartesiana en nLab". ncatlab.org . Consultado el 17 de septiembre de 2017 .
4. Categoría cerrada localmente cartesiana en el n Lab
5. Barendregt, HP (1984). "Teorema 1.2.16". El cálculo Lambda . Holanda del Norte. ISBN 0-444-87508-5.
6. "Teoría de la categoría Ct: ¿está cerrada la categoría monoide conmutativa cartesiana?".
7. Backus, John (1981). Programas a nivel de función como objetos matemáticos . Nueva York, Nueva York, Estados Unidos: ACM Press. doi :10.1145/800223.806757.
8. Solov'ev, SV (1983). "La categoría de conjuntos finitos y categorías cerradas cartesianas". J Matemáticas Ciencias . 22 (3): 1387-1400. doi :10.1007/BF01084396. S2CID  122693163.
9. Fiore, M.; Cosmo, R. Di; Balat, V. (2006). "Observaciones sobre isomorfismos en cálculos lambda mecanografiados con tipos vacíos y de suma" (PDF) . Anales de lógica pura y aplicada . 141 (1–2): 35–50. doi :10.1016/j.apal.2005.09.001.

• Seely, TRAPO (1984). "Categorías cerradas localmente cartesianas y teoría de tipos". Actas matemáticas de la Sociedad Filosófica de Cambridge . 95 (1): 33–48. doi :10.1017/S0305004100061284. ISSN  1469-8064. S2CID  15115721.

enlaces externos

• Categoría cerrada cartesiana en el n Lab
• Báez, John (2006). "CCC y el cálculo λ". The n-Category Café: un blog grupal sobre matemáticas, física y filosofía . Universidad de Texas.