Content deleted Content added
No edit summary |
|||
Line 26:
==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.<!--https://arxiv.org/pdf/1808.03814.pdf#page=4, "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-->
==References==
| |||