Alpha recursion theory: Difference between revisions

Revision as of 06:17, 5 December 2021

Revision as of 05:53, 7 January 2022

Line 35:

==Relation to analysis==

Some results in <math>\alpha</math>-recursion can be translated into similar results about [[second-order arithmetic]]. This is because of the relationship <math>L</math> has with the ramified analytic hierarchy, an analog of <math>L</math> for the language of second-order arithmetic, that consists of sets of integers.<!--ref>P. D. Welch, [https://arxiv.org/pdf/1808.03814.pdf#page=4 The Ramified Analytical Hierarchy using Extended Logics] (2018, p.4). Accessed 8 August 2021.</ref><!--"P_α = P(N) ∩ L_α"-->

In fact, when dealing with first-order logic only, the correspondence can be close enough that for results on <math>L_\omega=\textrm{HF}</math>, the arithmetic and Levy hierarchies can become interchangeable. For example, a set is recursive iff it's <math>\Sigma_1</math>-definable on <math>L_\omega</math>, where <math>\Sigma</math> is part of the Levy hierarchy.<!--Barwise, "Part C: α-Recursion", p.152-->