In a dependent type theory satisfying the propositions as types correspondence together with the proofs-as-programs paradigm, the validity of the unique choice rule or even more of the choice rule says that the extraction of a computable witness from an existential statement under hypothesis can be performed within the same theory. Here we show that the unique choice rule, and hence the choice rule, are not valid both in Coquand’s Calculus of Constructions with indexed sum types, list types and binary disjoint sums and in its predicative version implemented in the intensional level of the Minimalist Founda- tion. This means that in these theories the extraction of computational witnesses from existential statements must be performed in a more ex- pressive proofs-as-programs theory.

On choice rules in dependent type theory

MAIETTI, MARIA EMILIA
2017

Abstract

In a dependent type theory satisfying the propositions as types correspondence together with the proofs-as-programs paradigm, the validity of the unique choice rule or even more of the choice rule says that the extraction of a computable witness from an existential statement under hypothesis can be performed within the same theory. Here we show that the unique choice rule, and hence the choice rule, are not valid both in Coquand’s Calculus of Constructions with indexed sum types, list types and binary disjoint sums and in its predicative version implemented in the intensional level of the Minimalist Founda- tion. This means that in these theories the extraction of computational witnesses from existential statements must be performed in a more ex- pressive proofs-as-programs theory.
2017
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
9783319559100
File in questo prodotto:
File Dimensione Formato  
ch.pdf

accesso aperto

Descrizione: .pdf
Tipologia: Postprint (accepted version)
Licenza: Accesso gratuito
Dimensione 235.44 kB
Formato Adobe PDF
235.44 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/3234330
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
  • OpenAlex ND
social impact