Was ist ein gutes Wörterbuch für Kategorietheorie und Domänentheorie?

Wenn ich mich mit domänentheoretischen Kategorien befasse (z. B. CPO und CPO), wünsche ich mir häufig ein Wörterbuch für die Sprache der Kategorietheorie in der Domänentheorie. $\omega$

Das heißt, wenn ein Konzept gegeben ist, sagen wir monischer Pfeil, könnte ich es im Wörterbuch nachschlagen und sehen, welche Charakteristika es in den verschiedenen Domänenkategorien kennt.

Mir ist klar, dass dieser Wunsch zu viel ist, um darauf zu hoffen, aber gibt es einen Text oder eine Ressource, die sich ihm annähern?

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

Antworten:

Die beste Quelle dafür ist das Handbuchkapitel von Abramsky und Jung. Ich erinnere mich, dass sie eine Tabelle hatten, in der verschiedene Konstruktionen und Kategorien von Domänen referenziert wurden, wobei die Einträge besagten, ob die Konstruktion in dieser Kategorie funktionierte und welche Eigenschaften sie hatte. Die Eigenschaften von Pfeilen wie Monics hatten jedoch tendenziell keine besonders raffinierten Charakterisierungen, da die Verfügbarkeit von flachen Domänen dazu neigt, sicherzustellen, dass sie sich häufig nicht wesentlich von ihrem satztheoretischen Gegenstück unterscheiden. OTOH, Eigenschaften, die die Ordnungsstruktur etwas nutzen (wie ein Einbettungs-Projektions-Paar), haben tendenziell ziemlich hübsche Charakterisierungen.

Ein kleiner Punkt, auf den Sie achten sollten, ist, dass tatsächlich zwei Definitionen von CPO gebräuchlich sind! Verbraucher der Domänentheorie (wie ich) bevorzugen es oft, mit Omega-Ketten zu arbeiten, da Ketten ziemlich konkrete Objekte sind; Während Produzenten der Domänentheorie (wie z. B. Ihr Berater) es vorziehen, mit gerichteten Mengen zu arbeiten, die allgemeiner sind und bessere algebraische Eigenschaften haben. (Auf Anhieb bin ich mir nicht sicher, ob die Beschränkung auf gerichtete Mengen mit zählbarer Basis der Omega-Ketten-Bedingung entspricht.)

Etwas, das ich beim Erstellen dieser Art von Wörterbuch sehr hilfreich fand, ist das Durcharbeiten der Lösung rekursiver Domänengleichungen in einer Kategorie von Dingen, die nicht genau Domänen sind. Zwei gute Möglichkeiten sind Kategorien von PERs (z. B. in Modellen des Polymorphismus) und Presheaves (z. B. für die Namenszuweisung). Metrische Räume sind eine weitere Möglichkeit, aber ich fand, dass sie Domänen zu ähnlich sind, um mir beim Aufbau der Intuition zu helfen.

Neel Krishnaswami
quelle

Ja, ich kenne das Kapitel von Abramsky et al. Und insbesondere die Tabelle. Wie Sie sagten, beschreiben sie die grundlegenden Strukturen (Produkte, Summen, Exponentiale usw.), aber die Liste ist alles andere als umfassend.

Ohad Kammar

Die Frage stellte sich in meinem Kopf, als ich verschiedene Möglichkeiten für eine Definition diskutierte, und wir mussten verschiedene kategoriale Konzepte vergleichen (um genau zu sein mehrere Begriffe von monischen Pfeilen). Ich war ein bisschen überrascht, als mir klar wurde, dass unsere Methodik entweder darin bestand, schnell bequeme Charakterisierungen unter Verwendung von Intuition, alten Artikeln und jedem Buch zu erarbeiten, das uns in den Sinn kam, insbesondere wenn die Begriffe keine so obskuren kategorischen Begriffe waren. Natürlich nennt man diese Methode "Fachwissen" (was mir fehlt), aber als Programmierer hatte ich das Gefühl, dass es einen besseren Weg geben könnte, dies zu tun.

Ohad Kammar

λ

$\lambda$

ω

$\omega$

ω

$\omega$

Vielleicht möchten Sie sich Smyth und Plotkin 1982, "Über die kategorietheoretische Lösung rekursiver Domänengleichungen", oder einige von Paul Taylors Arbeiten (ich vergesse genaue Referenzen) oder Andy Pitts '1996 "Relational Properties of Domains" ansehen. Diese Artikel erledigen alles über abstrakte Top-Down-Charakterisierungen der benötigten Eigenschaften. Ich fand diese Papiere etwas zu abstrakt für mich, bis ich die konkreten Details in einigen Beispielen durchgearbeitet hatte. Dann waren sie klar!

Neel Krishnaswami

Markowsky 1977, Categories of Chain-Complete Posets hat eine schöne Tabelle für einige Varianten von CPOs.

Ohad Kammar

Ich bin mir nicht sicher, ob es einen gibt. Es gibt jedoch viele gute Bücher über Kategorietheorie und noch mehr Sätze von Vorlesungsskripten unterschiedlicher Qualität. Wikipedia hat auch ziemlich viele verlässliche Informationen über Kategorietheorie und Domänentheorie . Eine weitere gute Internetressource ist nCatLab , obwohl es mehr in die höherdimensionale Kategorietheorie übergeht .

Eine gute Referenz zur Domänentheorie ist S. Abramsky, A. Jung (1994). "Domänentheorie". In S. Abramsky, DM Gabbay, TSE Maibaum, Herausgeber (PDF). Handbuch der Logik in der Informatik. III. Oxford University Press. ISBN 0-19-853762-X.

Bücher über Kategorietheorie, die ich mir tatsächlich angesehen habe, sind:

Awodey, Steve (2006). Kategorietheorie (Oxford Logic Guides 49). Oxford University Press. 2. Auflage, 2010. Eine gute Einführung in die Informatik
Barr, Michael; Wells, Charles "Kategorietheorie für Informatik." Schwer zu bekommen, das heißt nicht bei Amazon erhältlich
Lawvere, William; Schanuel, Steve (1997). Konzeptmathematik: eine erste Einführung in Kategorien. Cambridge University Press. Herrliche Einführung, vielleicht nicht tief genug
Mac Lane, Saunders (1998). Kategorien für den Arbeitsmathematiker. Diplomtexte in Mathematik 5 (2. Aufl.). Springer-Verlag. ISBN 0-387-98403-8. Vielleicht zu mathematisch
Pierce, Benjamin (1991). Grundlegende Kategorietheorie für Informatiker. MIT Press. Vielleicht zu einfach
Taylor, Paul (1999). Praktische Grundlagen der Mathematik. Cambridge University Press. Ganz umfassend; nimmt eine logische Perspektive

Andere Bücher sind online verfügbar, wie Barr & Wells Toposes, Triples and Theories und Jiri Adámek, Horst Herrlich und George E. Streckers abstrakte und konkrete Kategorien - Die Freude an Katzen . Diese enthalten wahrscheinlich alle Definitionen, die Sie benötigen, zumindest von der Seite der Kategorietheorie.

Dave Clarke
quelle

Vielen Dank für die umfassende Antwort. Wie Sie sagten, ist es jedoch leicht genug, Material zur Domänentheorie und zur Kategorietheorie zu finden. Und in der Tat ziemlich viel davon. Aber das ist das Problem, das Wissen ist auf so viele Seiten mit Büchern, Konventionen und Notationen verteilt, dass der Zugriff darauf (auch mit Google) nicht trivial wird. Ich denke, dass der Unterschied zwischen einem Regal voller Lehrbücher und einem guten Nachschlagewerk besteht, in dem nur die Beziehungen und Zitate zitiert werden.

Ohad Kammar

Ein Ansatz zur Lösung dieses Problems für zukünftige Generationen besteht darin, ein eigenes Wörterbuch mit Begriffen zu schreiben, auf die Sie stoßen.

Dave Clarke

Vielleicht unsere eigene Version von ncatlab entwickeln ?

Uday Reddy

Wie wäre es, wenn Sie Ihren Berater fragen? Er erfand einen guten Teil der Domänentheorie.

Andrej Bauer
quelle

lacht Wie ich oben sagte, kam mir der Gedanke, als wir einige kategorietheoretische Begriffe in verschiedenen Bereichen diskutierten. Mein genauer Gedanke war: Sicherlich sollte es einen besseren Weg geben, als einen Experten zu bitten, die gesamte Literatur

durchzublättern