Bar recursion over finite partial functions

DOI10.1016/J.APAL.2016.11.003zbMATH Open1422.03091arXiv1410.6361OpenAlexW2290067105MaRDI QIDQ515562FDOQ515562

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)

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$.

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

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

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)

Cites Work

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

Cited In (14)

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

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)