El uso de extremos para construir categórica puntos fijos

Question

Bajo el asesoramiento de Toby Bartels, estoy publicando aquí esta cuestión, cae bajo el rubro general de " la construcción de tipos de datos categóricamente como puntos fijos de functors.

La primera pregunta que tengo es un warm-up. Hay una manera de interpretar un número natural n en cualquier cartesiana cerrada en la categoría C, como dinatural transformación de la forma

c^c --> c^c

que intuitivamente se toma un elemento de f: c - > c a su n-ésima iteración f^(n): c --> c. Uno puede esperar que si C es "bonita", entonces cada uno de esos dinatural transformación será de esta forma, o mejor aún, que al final

\int_{c: C} (c^c)^(c^c)

(suponiendo que exista) se comporta como un números naturales objeto en C. por Lo tanto, en primer lugar, estoy interesado en lo "bonito" podría significar aquí: ¿cuáles son algunas de las condiciones generales en C, con el fin de poder construir un números naturales objeto como un fin en esta forma?

Segundo, este fin puede escribirse como

\int_{c: C} c^(c^(1 + c))

siempre que C ha co-productos, y la afirmación de que este se comporta como un números naturales objeto es equivalente a decir que es un álgebra inicial para la endofunctor F(c) = 1 + c (que es el álgebra para un endofunctor, no para una mónada), lo que es un "punto fijo" de F por un antiguo y famoso resultado de Lambek.

Esto sugiere una segunda pregunta más general: dado un endofunctor F: C - > C en cartesiana cerrada C con una fuerza (en esencia, una estructura de C-enriquecimiento), quiero saber que es lo "bonito" de las condiciones en C y/o F garantía de que el fin

e = int_{c: C} c^(c^F(c)),

si existe, es en principio una F-álgebra. No es difícil escribir una F-álgebra estructura para este fin e, y demostrar que es débilmente inicial, es decir, demostrar que si x es una F-álgebra, entonces hay al menos existe una F-álgebra de mapas e --> x. La cuestión es, entonces, sobre la singularidad de este mapa, o más bien, qué bonito condiciones de garantía.

Discusión de casos específicos como POR los modelos estaría bien, pero yo probablemente estaría mucho más emocionado si lleva a la consideración de más abstractos generales condiciones en C o F.

Answer 1

Hola Todd, tenía la esperanza de que alguien más sabio que yo iba a responder a esta pregunta, pero ya que aún no ha sucedido voy a publicar un par de comentarios.

Como usted probablemente ya sabe, su observación de que al final de los números naturales objeto puede ser escrito como $\int_{c:C} ((1 + c) \to c) \to c$ corresponde exactamente a la Iglesia de la codificación de los números naturales en el Sistema de F, el de segundo orden polimórficos cálculo lambda. Gordon Plotkin y John Reynolds escribió un artículo hace unos 20 años en la expresable functors de sistema de F, que se utiliza para explicar por qué no hubo conjunto teórico de los modelos de sistema de F (en el sentido de que no podemos interpretar el tipo de $A \to B$ en el sistema de F como una función del espacio a partir del significado de $A$ a el significado de $B$). "En Functors Expresable en el Polimórficos Escribió Cálculo Lambda" Esta no es exactamente la respuesta a su pregunta, desde la que se puede expresar functors (los definidos en el lenguaje interno de la categoría, básicamente) son sólo un subconjunto de los que usted desea considerar, pero esperamos que sea alimento para el pensamiento.

Sin embargo, esta Iglesia codificación no es un NSIN en cualquier modelo de Sistema F; para este tipo de ser números naturales objeto de la modelo tiene que ser un "paramétrico" del modelo. Lo que quiero decir con esto es que no es suficiente tener un modelo que valida solo el $\beta$ $\eta$ reglas del cálculo lambda -- necesitamos más ecuaciones que eso. (Si sólo tenemos estas dos reglas, entonces sólo podemos definir una débil NSIN.) Es un modelo paramétrico cuando el cuantificador universal conserva las relaciones. Es decir, si tenemos un plazo $M$ tipo $\forall \alpha. A(\alpha)$, y dos tipos de $\tau$$\sigma$, con una relación $R$ entre ellas, entonces la relación $R$ debe levantar a una relación entre el$A(\tau)$$B(\sigma)$, e $(M\;\tau, M\;\sigma)$ debe habitan en esa relación. POR los modelos en sí mismos no son paramétricos, pero pueden ser hechas paramétrico a través de la "paramétrico de finalización" proceso de Rosolini. Esencialmente, esta es una manera de cocinar un nuevo modelo a partir de una antigua, donde la cuantificación se limita a la gama de más de la relación que preservar, y consideramos sólo los elementos que preservar esa relación.

Una relacionada con el enfoque en la búsqueda de puntos fijos de functors surge en el trabajo de la denotational semántica. La idea básica es trabajar con enriquecido categorías, de modo que homsets han CPO o estructura de espacio métrico, y entonces usted puede utilizar un teorema de punto fijo para mostrar la existencia de menos puntos fijos de functors. Para dominios, este enfoque se da por primera vez una explicación categórica por Smyth y Plotkin en "La Categoría de la teoría de la Solución Recursiva de Dominio de Ecuaciones", y se explica en un buen artículo de Andy Pitts ("Relacional Propiedades de los Dominios"). Para la métrica enriquecido categorías, el mejor punto de entrada sé que es Kim Wagner tesis, "la Resolución Recursiva de Dominio Ecuaciones Enriquecido con las Categorías".

Answer 2

Me preguntó Marcelo Fiore acerca de esta última semana, y él reconoció al instante el tipo de problema --- a la derecha hasta el hecho de que uno normalmente tiene la existencia de un mapa de la supuesta inicial de álgebra a un arbitrario dado álgebra, pero no necesariamente singularidad. Esta respuesta consiste de mis mejores recuerdos de lo que Marcelo dijo.

La frase clave es "polimorfismo paramétrico". En la configuración general de polimorfismo, se tiene la existencia de la propiedad que acabamos de mencionar, pero no necesariamente singularidad. Con el fin de obtener la singularidad, se añade el ingrediente extra de parametricity. Si he entendido bien (y no estoy seguro de lo que hago), añadiendo en parametricity es algo así como pasar de una categoría de objetos y mapas a la resultante de la categoría de objetos y relaciones.

Uno de los papeles que encontró fue Marcelo Datos categóricos tipos de polimorfismo paramétrico por Ryu Hasegawa. Creo que no era exactamente lo que estaba buscando, que no contienen ninguna extremos. También hay documentos pertinentes por tanto Freyd y Rosolini, al parecer.

Lo siento, este es un poco confusa.