¿Qué es un buen diccionario de teoría de categorías-teoría de dominios?

10

Al tratar con las categorías teóricas de dominio (por ejemplo, CPO y CPO), con frecuencia deseo un diccionario para el lenguaje de la teoría de categorías en la teoría de dominios.ω

Es decir, dado un concepto, digamos flecha mónica, podría buscarlo en el diccionario y ver cuáles son sus caracterizaciones conocidas en las diferentes categorías de dominio.

Me doy cuenta de que este deseo es demasiado para esperar, pero ¿hay algún texto o recurso que lo aproxime?

ct.category-theory semantics denotational-semantics domain-theory Ohad Kammar
fuente

Respuestas:

6

El mejor recurso para esto es el capítulo del manual de Abramsky y Jung. Recuerdo que tenían una tabla que hacía referencias cruzadas de varias construcciones y categorías de dominios, con las entradas que decían si la construcción funcionaba en esa categoría y qué propiedades tenía. Sin embargo, las propiedades de las flechas, como ser un monic, tienden a no tener caracterizaciones terriblemente resbaladizas, porque la disponibilidad de dominios planos tiende a garantizar que a menudo no sean terriblemente diferentes de su contraparte teórica de conjuntos. OTOH, las propiedades que hacen algún uso de la estructura de orden (como ser un par de incrustación-proyección) tienden a tener caracterizaciones bastante bonitas.

¡Un punto menor a tener en cuenta es que en realidad hay dos definiciones de CPO de uso común! Los consumidores de la teoría de dominios (como yo) a menudo prefieren trabajar con cadenas omega, ya que las cadenas son objetos bastante concretos; mientras que los productores de teoría de dominios (como su asesor) tienden a preferir trabajar con conjuntos dirigidos, que son más generales y tienen mejores propiedades algebraicas. (De improviso, no estoy seguro de si restringir a conjuntos dirigidos que tienen una base contable es equivalente a la condición de la cadena omega).

Algo que encontré muy útil para construir este tipo de diccionario es trabajar a través de la solución de ecuaciones de dominio recursivas en alguna categoría de cosas que no son exactamente dominios. Dos buenas opciones son las categorías de PER (p. Ej., En modelos de polimorfismo) y preajustes (p. Ej., Para la asignación de nombres). Los espacios métricos son otra posibilidad, pero descubrí que son demasiado similares a los dominios para ayudarme a construir la intuición.

Neel Krishnaswami
fuente
Sí, estoy familiarizado con el capítulo de Abramsky et al., Y en particular con dicha tabla. Como dijiste, describen las estructuras fundamentales (productos, sumas, exponenciales, etc.), pero la lista está lejos de ser exhaustiva.
Ohad Kammar el
La pregunta surgió en mi mente cuando estaba discutiendo varias posibilidades para una definición, y necesitábamos comparar diferentes conceptos categóricos (varias nociones de flechas monicas, para ser exactos). Me sorprendió un poco cuando me di cuenta de que nuestra metodología era resolver rápidamente las caracterizaciones convenientes utilizando la intuición, los artículos antiguos y cualquier libro que se nos ocurriera, especialmente cuando las nociones no eran nociones categóricas tan oscuras. Por supuesto, este método se llama "experiencia" (que me falta), pero como programador sentí que podría haber una mejor manera de hacerlo.
Ohad Kammar el
λωω
Es posible que desee ver Smyth y Plotkin 1982, "Sobre la solución teórica de categoría de las ecuaciones de dominio recursivo", o algunos de los documentos de Paul Taylor (no recuerdo referencias exactas), o las "Propiedades relacionales de dominios" de 1996 de Andy Pitts. Todos estos documentos hacen cosas a través de caracterizaciones abstractas de arriba a abajo de las propiedades necesarias. Yo, encontré estos documentos demasiado abstractos para mí hasta que había trabajado en los detalles concretos en un par de ejemplos. ¡Entonces fueron claros!
Neel Krishnaswami
Markowsky 1977, Categorías de posets de cadena completa tiene una buena tabla para algunas variantes de CPO.
Ohad Kammar
5

No estoy seguro de que haya uno. Sin embargo, hay muchos buenos libros sobre teoría de categorías e incluso más conjuntos de apuntes de clase, de diferente calidad. Wikipedia también tiene bastante información confiable sobre teoría de categorías y teoría de dominios . Otro buen recurso de Internet es nCatLab , aunque deriva más hacia la teoría de categorías de dimensiones superiores.

Una buena referencia teórica de dominio es S. Abramsky, A. Jung (1994). "Teoría del dominio". En S. Abramsky, DM Gabbay, TSE Maibaum, editores, (PDF). Manual de Lógica en Informática. III. Prensa de la Universidad de Oxford. ISBN 0-19-853762-X.

Los libros sobre teoría de categorías que he visto son:

  • Awodey, Steve (2006). Teoría de la categoría (Oxford Logic Guides 49). Prensa de la Universidad de Oxford. 2ª edición, 2010. Una buena introducción reciente, inclinada hacia la informática.

  • Barr, Michael; Wells, Charles "Teoría de la categoría de ciencias de la computación". Es difícil de obtener, es decir, no está disponible en Amazon

  • Lawvere, William; Schanuel, Steve (1997). Matemática conceptual: una primera introducción a las categorías. Prensa de la Universidad de Cambridge. Introducción encantadora, quizás no lo suficientemente profunda

  • Mac Lane, Saunders (1998). Categorías para el matemático que trabaja. Textos de Posgrado en Matemáticas 5 (2ª ed.). Springer-Verlag. ISBN 0-387-98403-8. Quizás demasiado matemático

  • Pierce, Benjamin (1991). Teoría de la categoría básica para informáticos. MIT Press. Quizás demasiado básico

  • Taylor, Paul (1999). Fundamentos prácticos de las matemáticas. Prensa de la Universidad de Cambridge. Bastante completo; toma una perspectiva lógica

Otros libros están disponibles en línea, como Toposes, triples y teorías de Barr & Well , y Jiri Adámek, Horst Herrlich y Categorías abstractas y concretas de George E. Strecker : La alegría de los gatos . Es probable que contengan todas las definiciones que necesita, al menos desde el lado de la teoría de categorías.

Dave Clarke
fuente
Gracias por la respuesta integral. Sin embargo, como dijiste, es bastante fácil encontrar material sobre teoría de dominios y sobre teoría de categorías. Y, de hecho, bastante. Pero ese es el problema, el conocimiento se extiende a través de tantas páginas de libros, convenciones y anotaciones, que acceder a él (incluso con Google) no es trivial. Supongo que la diferencia es entre tener un estante lleno de libros de texto versus un buen libro de referencia que solo cita las relaciones y citas.
Ohad Kammar el
Un enfoque para resolver este problema para las generaciones futuras es escribir su propio diccionario de términos a medida que los encuentre.
Dave Clarke
1
¿Quizás desarrollar nuestra propia versión de ncatlab ?
Uday Reddy
3

¿Qué tal preguntarle a su asesor? Inventó una buena parte de la teoría de dominios.

Andrej Bauer
fuente
risas Como he dicho anteriormente, la idea vino a la mente cuando discutíamos algunas nociones teóricas categoría en diferentes dominios. Mi pensamiento exacto fue: seguramente debería haber una mejor manera que preguntarle a un experto que hojea toda la literatura o conjeturas ...
Ohad Kammar