License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2012.335
URN: urn:nbn:de:0030-drops-36828
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3682/
Go to the corresponding LIPIcs Volume Portal

Hida, Takanori

A Computational Interpretation of the Axiom of Determinacy in Arithmetic

pdf-format:
28.pdf (0.5 MB)

Abstract

We investigate the computational content of the axiom of determinacy (AD) in the setting of classical arithmetic in all finite types with the principle of dependent choices (DC). By employing the notion of realizability interpretation for arithmetic given by Berardi, Bezem and Coquand (1998), we interpret the negative translation of AD. Consequently, the combination of the negative translation with this realizability semantics can be seen as a model of DC, AD and the negation of the axiom of choice at higher types. In order to understand the computational content of AD, we explain, employing Coquand's game theoretical semantics, how our realizer behaves.

BibTeX - Entry

@InProceedings{hida:LIPIcs:2012:3682,
  author =	{Takanori Hida},
  title =	{{A Computational Interpretation of the Axiom of Determinacy in Arithmetic}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{335--349},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{Patrick C{\'e}gielski and Arnaud Durand},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3682},
  URN =		{urn:nbn:de:0030-drops-36828},
  doi =		{10.4230/LIPIcs.CSL.2012.335},
  annote =	{Keywords: The axiom of determinacy, Gale-Stewart’s theorem, Syntactic continuity, Realizability interpretation, Coquand’s game semantics}
}

Keywords: The axiom of determinacy, Gale-Stewart’s theorem, Syntactic continuity, Realizability interpretation, Coquand’s game semantics
Collection: Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL
Issue Date: 2012
Date of publication: 03.09.2012

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