Undecidability of Equality in the Free Locally Cartesian Closed Category (Extended Version) - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Logical Methods in Computer Science Année : 2017

Undecidability of Equality in the Free Locally Cartesian Closed Category (Extended Version)

Résumé

We show that a version of Martin-Löf type theory with an extensional identity type former I, a unit type N1, Σ-types, Π-types, and a base type is a free category with families (supporting these type formers) both in a 1-and a 2-categorical sense. It follows that the underlying category of contexts is a free locally cartesian closed category in a 2-categorical sense because of a previously proved biequivalence. We show that equality in this category is undecidable by reducing it to the undecidability of convertibility in combinatory logic. Essentially the same construction also shows a slightly strengthened form of the result that equality in extensional Martin-Löf type theory with one universe is undecidable.
Fichier principal
Vignette du fichier
lmcs-2017.pdf (467.13 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01579415 , version 1 (31-08-2017)

Identifiants

Citer

Simon Castellan, Pierre Clairambault, Peter Dybjer. Undecidability of Equality in the Free Locally Cartesian Closed Category (Extended Version). Logical Methods in Computer Science, 2017, ⟨10.23638/LMCS-13(4:22)2017⟩. ⟨hal-01579415⟩

Relations

141 Consultations
53 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More