Natürliche Transformationen und Parametrizität

11

In Theorems kostenlos! Wadler sagt, dass die Charakterisierung der Parametrizität in Form von laxen natürlichen Transformationen wieder ausgedrückt werden kann, und dies wird Gegenstand einer weiteren Arbeit sein. Auf welches Papier bezieht er sich?

Die kategorische Herangehensweise an die Paramterizität, die ich kenne, verwendet dinaturale Transformationen wie im Functorial Polymorphism von Bainbridge, Freyd, Scedrov und PJ Scott. Was ist der Zusammenhang zwischen laxer natürlicher Transformation und dinaturalen Transformationsformulierungen der Parametrizität?

reference-request ct.category-theory parametricity Sonat
quelle
2
Ich habe fast Angst, diesen Kommentar abzugeben, aber ich werde gestehen, dass ich in dieser Frage kein technisches Wort verstehe. Könnte es möglich sein, einige Links zu Definitionen für diesen (schrecklich) Nicht-Experten hinzuzufügen?
Suresh Venkat
1
Sieht aus wie ein Job für @UdayReddy.
Dave Clarke
5
Soweit ich weiß, ist das in Theorems for Free! wurde (leider) nie geschrieben. Ich bin mir ziemlich sicher, dass das aktuelle Verständnis der Parametrizität in Bezug auf die Kategorietheorie am besten von Scones und Kommakategorien erfasst wird . Siehe z. B. Mitchell & Scedrov und diesen n-Category Café-Beitrag.
Cody
Suresh, entschuldigen Sie, dass Sie die entsprechenden Links nicht angegeben haben. Cody, danke, dass du den Beitrag bearbeitet und Scones und Kommakategorien erwähnt hast.
Sonat

Antworten:

8

Leider ist die Bemerkung von Wadler zu kryptisch, als dass ich sagen könnte, welchen Nutzen er aus "laxen natürlichen Transformationen" ziehen wollte. Hier ist eine Vermutung. Beziehungserhaltungsquadrate können oft als laxe kommutative Quadrate umformuliert werden. So wurden sie früher in alten automatentheoretischen Papieren / Büchern geschrieben. Siehe Abschnitt 1.2 in meinen Anmerkungen zu Halbgruppen . Um so etwas zu tun, muss man Beziehungen und Morphismen verwechseln und so tun, als wären sie gleich. Ich bin mir auch nicht sicher, ob es dir etwas Neues kauft. Es ist nur eine hässlichere Notation, das Gleiche wie Beziehungserhaltung zu sagen.

Bitte zögern Sie nicht, die Verbindung zu erkunden, aber ich bin nicht sicher, ob Sie dadurch etwas Neues finden werden.

Uday Reddy
quelle
Vielen Dank für den Link. Die Formulierung in Absatz 1.2 ist für mich immer noch theoretisch festgelegt. Wie redest du über Inklusion? Nehmen Sie an, dass die Kategorie eine Allegorie ist oder toposähnliche Eigenschaften hat? Wenn dies eine Reform der laxen natürlichen Transformationen ist, welche ist die zugrunde liegende 2-Kategorie? Ich habe auch den Teil "Kategorisierung" gelesen, konnte aber nichts über laxe natürliche Transformationen finden.
Sonat
x→yx≤yf→gf≤gR⊆S:Rel(A,B)
Oh, also die Kategorie ist festgelegt! Ich dachte, Wadler beziehe sich auf eine allgemeinere und abstraktere Formulierung, die in einer bestimmten Klasse von Kategorien sinnvoll ist, die Rel als speziellen (und etwas trivialen) Fall enthalten. Wenn wir nur in Rel arbeiten, macht es keinen Sinn, eine höhere, aber entartete Struktur einzuführen. Jetzt verstehe ich Ihre ursprüngliche Antwort.
Sonat
@ SonatSüer: Wenn Sie an Verallgemeinerungen interessiert sind, besteht die Standardmethode zum Verallgemeinern von Beziehungen zu anderen Kategorien als Set darin, sie als "gemeinsam monische Bereiche" zu behandeln. Möglicherweise erhalten Sie eine mit Vorbestellungen angereicherte Kategorie anstelle einer mit Posets angereicherten Kategorie, aber die Struktur mit zwei Kategorien ist immer noch dieselbe.
Uday Reddy
@ SonatSüer: Und wenn Sie wirklich an einer richtigen axiomatischen Theorie interessiert sind, die alles abdeckt, was wir wissen, kann ich Sie auf unser kürzlich veröffentlichtes Papier Logische Beziehungen und Parametrizität - Ein Reynolds-Programm verweisen .
Uday Reddy