Alpha recursion theory: Difference between revisions

Revision as of 14:24, 18 November 2022

Revision as of 03:33, 8 December 2022

Line 37:

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 some results on <math>L_\omega=\textrm{HF}</math>, the arithmetical and Levy hierarchies can become interchangeable. For example, a set of natural numbers is definable by a <math>\Sigma_1^0</math> formula iff it's <math>\Sigma_1</math>-definable on <math>L_\omega</math>, where <math>\Sigma_1</math> is a level of the Levy hierarchy.<ref>G>. E. Sacks, ''Higher Recursion Theory'' (p.152). "Perspectives in Logic", Association for Symbolic Logic.</ref>

==References==