On the computational content of the axiom of choice

被引:61
作者
Berardi, S
Bezem, M
Coquand, T
机构
[1] Univ Turin, Dipartimento Informat, I-10149 Turin, Italy
[2] Univ Utrecht, Dept Philosophy, NL-3508 TC Utrecht, Netherlands
[3] Chalmers Univ Technol, Dept Comp Sci, S-41296 Gothenburg, Sweden
关键词
D O I
10.2307/2586854
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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 nor interpreted as the empty type here. We also show how to compute witnesses from proofs in classical analysis of There Exists-statements and how to extract algorithms from proofs of For All There Exists-statements. Our interpretation seems computationally more direct than the one based on Godel's Dialectica interpretation.
引用
收藏
页码:600 / 622
页数:23
相关论文
共 28 条
[1]  
ACKERMANN W, 1924, MATH ANN, V93, P1
[2]  
[Anonymous], J SYMBOLIC LOGIC
[3]  
Bishop E., 1967, Foundations of constructive analysis
[4]  
Constable Robert L., 1991, LOGICAL FRAMEWORKS, P341
[5]   A SEMANTICS OF EVIDENCE FOR CLASSICAL ARITHMETIC [J].
COQUAND, T .
JOURNAL OF SYMBOLIC LOGIC, 1995, 60 (01) :325-337
[6]  
GODEL K, 1986, COLLECTED WORK, V1
[7]  
GODEL K, 1986, COLLECTED WORK, V2
[8]  
GOODMAN N, 1968, THESIS STANFORD U
[9]  
Hilbert D, 1923, MATH ANN, V88, P151
[10]  
HILBERT D, 1971, FDN MATH FREGE GODEL, P465