Bar recursion and products of selection functions

Journal of Symbolic Logic 80 (1):1-28 (2015)
  Copy   BIBTEX

Abstract

We show how two iterated products of selection functions can both be used in conjunction with systemTto interpret, via the dialectica interpretation and modified realizability, full classical analysis. We also show that one iterated product is equivalent over systemTto Spector’s bar recursion, whereas the other isT-equivalent to modified bar recursion. Modified bar recursion itself is shown to arise directly from the iteration of a different binary product of ‘skewed’ selection functions. Iterations of the dependent binary products are also considered but in all cases are shown to beT-equivalent to the iteration of the simple products.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

On Spector's bar recursion.Paulo Oliva & Thomas Powell - 2012 - Mathematical Logic Quarterly 58 (4-5):356-265.
The equivalence of bar recursion and open recursion.Thomas Powell - 2014 - Annals of Pure and Applied Logic 165 (11):1727-1754.
Term rewriting theory for the primitive recursive functions.E. A. Cichon & Andreas Weiermann - 1997 - Annals of Pure and Applied Logic 83 (3):199-223.
Unary primitive recursive functions.Daniel E. Severin - 2008 - Journal of Symbolic Logic 73 (4):1122-1138.
Learning and selection.Justine Kingsbury - 2008 - Biology and Philosophy 23 (4):493-507.
On nested simple recursion.Ján Komara - 2011 - Archive for Mathematical Logic 50 (5-6):617-624.
Tailoring recursion for complexity.Erich Grädel & Yuri Gurevich - 1995 - Journal of Symbolic Logic 60 (3):952-969.
Recursion on the countable functionals.Dag Normann - 1980 - New York: Springer Verlag.
Subrecursion: functions and hierarchies.H. E. Rose - 1984 - New York: Oxford University Press.
Characterizing PSPACE with pointers.Isabel Oitavem - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
Warrant, Functions, History.Peter J. Graham - 2014 - In Abrol Fairweather & Owen Flanagan (eds.), Naturalizing Epistemic Virtue. New York: Cambridge University Press. pp. 15-35.
More existence theorems for recursion categories.Florian Lengyel - 2004 - Annals of Pure and Applied Logic 125 (1-3):1-41.
Revisiting recent etiological theories of functions.Daniel M. Kraemer - 2014 - Biology and Philosophy 29 (5):747-759.
There is no safe pairing function over an arbitrary structure.Olga Xirotiri - 2006 - Mathematical Logic Quarterly 52 (4):362-366.

Analytics

Added to PP
2016-06-30

Downloads
24 (#639,942)

6 months
6 (#504,917)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Bar recursion over finite partial functions.Paulo Oliva & Thomas Powell - 2017 - Annals of Pure and Applied Logic 168 (5):887-921.

Add more citations

References found in this work

On Spector's bar recursion.Paulo Oliva & Thomas Powell - 2012 - Mathematical Logic Quarterly 58 (4-5):356-265.
The equivalence of bar recursion and open recursion.Thomas Powell - 2014 - Annals of Pure and Applied Logic 165 (11):1727-1754.

Add more references