Bar recursion over finite partial functions

DOI10.1016/J.APAL.2016.11.003MaRDI QIDQ515562zbMATH OpenOpenAlexFDO

Authors Yong-Cai Geng, Sumit K. Garg

Publication date 16 March 2017

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.6361

zbMATH Keywords

countable choiceprogram extractionbar recursiondialectica interpretation

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Higher-type and set recursion theory (03D65) Relative consistency and interpretations (03F25) Functionals in proof theory (03F10)

Abstract: We introduce a new, demand-driven variant of Spector's bar recursion in the spirit of the Berardi-Bezem-Coquand functional. The recursion takes place over finite partial functions $u$, where the control parameter $varphi$, used in Spector's bar recursion to terminate the computation at sequences $s$ satisfying $varphi(hats)<|s|$, now acts as a guide for deciding exactly where to make bar recursive updates, terminating the computation whenever $varphi(hatu)inmboxdom(u)$. We begin by exploring theoretical aspects of this new form of recursion, then in the main part of the paper we show that demand-driven bar recursion can be directly used to give an alternative functional interpretation of classical countable choice. We provide a short case study as an illustration, in which we extract a new bar recursive program from the proof that there is no injection from $mathbbNomathbbN$ to $mathbbN$, and compare this to the program that would be obtained using Spector's original variant. We conclude by formally establishing that our new bar recursor is primitive recursively equivalent to the original Spector bar recursion, and thus defines the same class of functionals when added to G"odel's system $sfT$.

Recommendations

• On Spector's bar recursion
• On the computational content of the axiom of choice
• Logical Approaches to Computational Barriers
• Bar recursion is not computable via iteration
• The equivalence of bar recursion and open recursion

Cites work

• scientific article; zbMATH DE number 3163761 (Why is no real title available?)
• scientific article; zbMATH DE number 1215497 (Why is no real title available?)
• scientific article; zbMATH DE number 3216998 (Why is no real title available?)
• scientific article; zbMATH DE number 3231083 (Why is no real title available?)
• scientific article; zbMATH DE number 3259893 (Why is no real title available?)
• scientific article; zbMATH DE number 3335898 (Why is no real title available?)
• scientific article; zbMATH DE number 2222013 (Why is no real title available?)
• Applied Proof Theory: Proof Interpretations and Their Use in Mathematics
• Bar recursion and products of selection functions
• Exhaustible sets in higher-type computation
• Interactive learning-based realizability for Heyting arithmetic with \(\mathrm{EM}_1\)
• Logical Approaches to Computational Barriers
• Metamathematical investigation of intuitionistic arithmetic and analysis. With contributions by C. A. Smorynski, J. I. Zucker and W. A. Howard
• Modified bar recursion
• On Spector's bar recursion
• On the computational content of the axiom of choice
• Strongly majorizable functionals of finite type: A model for barrecursion containing discontinuous functionals
• The equivalence of bar recursion and open recursion
• Update procedures and the 1-consistency of arithmetic
• ÜBER EINE BISHER NOCH NICHT BENÜTZTE ERWEITERUNG DES FINITEN STANDPUNKTES

Cited in

(14)

• On the uncountability of \(\mathbb{R}\)
• Diller-Nahm bar recursion
• Strongly majorizable functionals of finite type: A model for barrecursion containing discontinuous functionals
• scientific article; zbMATH DE number 7297814 (Why is no real title available?)
• Bar recursion is not computable via iteration
• A universal algorithm for Krull's theorem
• Selection functions, bar recursion and backward induction
• Logical Approaches to Computational Barriers
• The equivalence of bar recursion and open recursion
• scientific article; zbMATH DE number 7692241 (Why is no real title available?)
• Bar recursion and products of selection functions
• Computational interpretations of classical reasoning: from the epsilon calculus to stateful programs
• Equivalence of bar induction and bar recursion for continuous functions with continuous moduli
• On Spector's bar recursion

This page was built for publication: Bar recursion over finite partial functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q515562)