Keine naiven Mengenmodelle der polymorphen Lambda-Rechnung?

In Philip Wadlers Aufsatz über Theorems for Free stellt er in Abschnitt 2 über Parametrizität fest, dass

Es gibt keine naiven satztheoretischen Modelle der polymorphen Lambda-Rechnung

In der naiven Mengenlehre sind Modelltypen Mengen und Funktionen Mengenlehrefunktionen, was vernünftig erscheint. Warum sagt er also, dass es keine naiven satztheoretischen Modelle der polymorphen Lambda-Rechnung gibt?

functional-programming MK
quelle

OK, ich bin gerade auf dieses Papier gestoßen : hal.inria.fr/inria-00076261/document . Ich muss es durchpflügen.

Dieser Artikel von Reynolds ist in der Tat der richtige zum Lesen! Wenn Sie viele Details weglassen , fasst das zusammen: Überlegen Sie data T = K ((T -> Bool) -> Bool). Dann sind Tund ((T->Bool)->Bool)isomorph. Wenn sie ein Mengenmodell haben, bei dem ->der Funktionsraum (als Menge) bezeichnet wird, hat letzterer eine höhere Kardinalität, sodass er nicht isomorph sein kann T. In einem Modell müssen wir also ->anders interpretieren - z. B. als Raum kontinuierlicher Funktionen.

Chi

Ich habe zu schnell geantwortet und die falsche Frage beantwortet. Das tut mir leid. Der Grund dafür, dass der polymorphe Lambda-Kalkül kein Modell in der Theorie der naiven Mengen hat, ist offensichtlich ein anderer als der für den untypisierten Lambda-Kalkül.

Antworten:

$\Pi_{S\in\mathrm{Set}}S$ $\times$ $\rightarrow$

$\bf 2$ $T=\Pi_X(X\rightarrow {\bf 2})\rightarrow{\bf 2}$ $(T\rightarrow {\bf 2})\rightarrow {\bf 2}$ $\rightarrow$

Beachten Sie, dass eine weitere Veröffentlichung von Andrew Pitts, Polymorphism is Set Theoretic, Constructively , diese Schlussfolgerung etwas umdreht, indem gezeigt wird, dass der obige Widerspruch nur in der klassischen Mengen-Theorie konstruiert werden kann und dass es mehrere konstruktive Mengen-Theorien gibt, in denen Polymorphismus möglich ist mit den üblichen Interpretationen von Funktionsräumen und Produkten interpretiert werden. Am bemerkenswertesten sind diese "großen Produkte" in den Effective Topos, wobei die umfassendste Einführung von Phoa gegeben wird .

Cody
quelle