Hybrid realizability for intuitionistic and classical choice

Valentin Blot

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

In intuitionistic realizability like Kleene's or Kreisel's, the axiom of choice is trivially realized. It is even provable in Martin-Löf's intuitionistic type theory. In classical logic, however, even the weaker axiom of countable choice proves the existence of non-computable functions. This logical strength comes at the price of a complicated computational interpretation which involves strong recursion schemes like bar recursion. We take the best from both worlds and define a realizability model for arithmetic and the axiom of choice which encompasses both intuitionistic and classical reasoning. In this model two versions of the axiom of choice can co-exist in a single proof: intuitionistic choice and classical countable choice. We interpret intuitionistic choice efficiently, however its premise cannot come from classical reasoning. Conversely, our version of classical choice is valid in full classical logic, but it is restricted to the countable case and its realizer involves bar recursion. Having both versions allows us to obtain efficient extracted programs while keeping the provability strength of classical logic.

Original languageEnglish
Title of host publicationLICS '16, Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science
Place of PublicationNew York, U. S. A.
PublisherIEEE
Pages575-584
Number of pages10
ISBN (Print)9781450343916
DOIs
Publication statusPublished - 5 Jul 2016
Event31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016 - New York, USA United States
Duration: 5 Jul 20168 Jul 2016

Conference

Conference31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016
CountryUSA United States
CityNew York
Period5/07/168/07/16

Fingerprint Dive into the research topics of 'Hybrid realizability for intuitionistic and classical choice'. Together they form a unique fingerprint.

Cite this