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

Abstract : 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.
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01579415
Contributeur : Pierre Clairambault <>
Soumis le : jeudi 31 août 2017 - 10:23:48
Dernière modification le : jeudi 4 octobre 2018 - 01:15:41

Fichiers

lmcs-2017.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01579415, version 1

Relations

Citation

Simon Castellan, Pierre Clairambault, Peter Dybjer. Undecidability of Equality in the Free Locally Cartesian Closed Category (Extended Version). 2017. 〈hal-01579415〉

Partager

Métriques

Consultations de la notice

101

Téléchargements de fichiers

29