License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TYPES.2016.4
URN: urn:nbn:de:0030-drops-98590
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9859/
Go to the corresponding LIPIcs Volume Portal

Aschieri, Federico ; Manighetti, Matteo

On Natural Deduction for Herbrand Constructive Logics II: Curry-Howard Correspondence for Markov's Principle in First-Order Logic and Arithmetic

pdf-format:
LIPIcs-TYPES-2016-4.pdf (0.6 MB)

Abstract

Intuitionistic first-order logic extended with a restricted form of Markov's principle is constructive and admits a Curry-Howard correspondence, as shown by Herbelin. We provide a simpler proof of that result and then we study intuitionistic first-order logic extended with unrestricted Markov's principle. Starting from classical natural deduction, we restrict the excluded middle and we obtain a natural deduction system and a parallel Curry-Howard isomorphism for the logic. We show that proof terms for existentially quantified formulas reduce to a list of individual terms representing all possible witnesses. As corollary, we derive that the logic is Herbrand constructive: whenever it proves any existential formula, it proves also an Herbrand disjunction for the formula. Finally, using the techniques just introduced, we also provide a new computational interpretation of Arithmetic with Markov's principle.

BibTeX - Entry

@InProceedings{aschieri_et_al:LIPIcs:2018:9859,
  author =	{Federico Aschieri and Matteo Manighetti},
  title =	{{On Natural Deduction for Herbrand Constructive Logics II: Curry-Howard Correspondence for Markov's Principle in First-Order Logic and Arithmetic}},
  booktitle =	{22nd International Conference on Types for Proofs and  Programs (TYPES 2016)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-065-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{97},
  editor =	{Silvia Ghilezan and Herman Geuvers and Jelena Ivetić},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9859},
  URN =		{urn:nbn:de:0030-drops-98590},
  doi =		{10.4230/LIPIcs.TYPES.2016.4},
  annote =	{Keywords: Markov's Principle, first-order logic, natural deduction, Curry-Howard}
}

Keywords: Markov's Principle, first-order logic, natural deduction, Curry-Howard
Collection: 22nd International Conference on Types for Proofs and Programs (TYPES 2016)
Issue Date: 2018
Date of publication: 05.11.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI