On the Computational Content of the Axiom of Choice
Berardi, Stefano ; Bezem, Marc ; Coquand, Thierry
J. Symbolic Logic, Tome 63 (1998) no. 1, p. 600-622 / Harvested from Project Euclid
We present a possible computational content of the negative translation of classical analysis with the Axiom of (countable) Choice. Interestingly, this interpretation uses a refinement of the realizability semantics of the absurdity proposition, which is not interpreted as the empty type here. We also show how to compute witnesses from proofs in classical analysis of $\exists$-statements and how to extract algorithms from proofs of $\forall\exists$-statements. Our interpretation seems computationally more direct than the one based on Godel's Dialectica interpretation.
Publié le : 1998-06-14
Classification: 
@article{1183745524,
     author = {Berardi, Stefano and Bezem, Marc and Coquand, Thierry},
     title = {On the Computational Content of the Axiom of Choice},
     journal = {J. Symbolic Logic},
     volume = {63},
     number = {1},
     year = {1998},
     pages = { 600-622},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183745524}
}
Berardi, Stefano; Bezem, Marc; Coquand, Thierry. On the Computational Content of the Axiom of Choice. J. Symbolic Logic, Tome 63 (1998) no. 1, pp.  600-622. http://gdmltest.u-ga.fr/item/1183745524/