Die Referenz für die Tatsache, dass (0 = 1) falsch impliziert, erfordert ein Universum in MLTT

10

Es ist eine ziemlich bekannte Tatsache, dass das Ableiten eines Widerspruchs aus einer Ungleichheit (zum Beispiel ) in der Martin-Loef-Typentheorie ein Universum erfordert.(0=1)→⊥

Der Beweis ist auch ziemlich einfach - in Abwesenheit von Universen können wir die Abhängigkeiten von jedem abhängigen Typ löschen, um einen einfachen Typ als seine Form zu erhalten, und so beweisen, dass impliziert, dass wir p → ⊥ beweisen können für ein beliebiges Atom p , was natürlich nicht möglich ist.(0=1)→⊥p→⊥p

Ich kann jedoch nicht finden, wer dies zuerst bewiesen hat! Hat jemand eine Referenz?

reference-request lo.logic pl.programming-languages type-theory dependent-type Neel Krishnaswami
quelle
Coquands "Ein neues Paradoxon in der Typentheorie" (94) beschreibt die wahrheitsbewertete Semantik minimaler Logik höherer Ordnung und scheint darauf hinzudeuten, dass diese Interpretation zuvor bekannt war. Ich scheine mich an eine Erwähnung eines solchen Modells zu erinnern, selbst für Russells Typentheorie, aber ich kann es nicht finden ...
Cody
Dieser Martin Hoffman-Text bestätigt die Jan Smith-Referenz in der Antwort und enthält eine angemessene Darstellung dieses Beweises mit kategorialer Semantik in den Übungen ioc.ee/~james/ITT9200/SyntaxAndSemanticsof%20DependentTypes.pdf
user833970

Antworten:

10

Ich weiß von:

Jan M. Smith, Die Unabhängigkeit von Peanos viertem Axiom von Martin-Löfs Typentheorie ohne Universen, The Journal of Symbolic Logic 53 (3), p. 840-845, 1988.

Ulrik Buchholtz
quelle