• Images
• Videos
• Documents
• Books
• Articles

Definitions

The objects of study in α {\displaystyle \alpha } recursion are subsets of α {\displaystyle \alpha } . These sets are said to have some properties:

• A set A ⊆ α {\displaystyle A\subseteq \alpha } is said to be α {\displaystyle \alpha } -recursively-enumerable if it is Σ 1 {\displaystyle \Sigma _{1}} definable over L α {\displaystyle L_{\alpha }} , possibly with parameters from L α {\displaystyle L_{\alpha }} in the definition.¹
• A is α {\displaystyle \alpha } -recursive if both A and α ∖ A {\displaystyle \alpha \setminus A} (its relative complement in α {\displaystyle \alpha } ) are α {\displaystyle \alpha } -recursively-enumerable. It's of note that α {\displaystyle \alpha } -recursive sets are members of L α + 1 {\displaystyle L_{\alpha +1}} by definition of L {\displaystyle L} .
• Members of L α {\displaystyle L_{\alpha }} are called α {\displaystyle \alpha } -finite and play a similar role to the finite numbers in classical recursion theory.
• Members of L α + 1 {\displaystyle L_{\alpha +1}} are called α {\displaystyle \alpha } -arithmetic. ²

There are also some similar definitions for functions mapping α {\displaystyle \alpha } to α {\displaystyle \alpha } :³

• A partial function from α {\displaystyle \alpha } to α {\displaystyle \alpha } is α {\displaystyle \alpha } -recursively-enumerable, or α {\displaystyle \alpha } -partial recursive,⁴ iff its graph is Σ 1 {\displaystyle \Sigma _{1}} -definable on ( L α , ∈ ) {\displaystyle (L_{\alpha },\in )} .
• A partial function from α {\displaystyle \alpha } to α {\displaystyle \alpha } is α {\displaystyle \alpha } -recursive iff its graph is Δ 1 {\displaystyle \Delta _{1}} -definable on ( L α , ∈ ) {\displaystyle (L_{\alpha },\in )} . Like in the case of classical recursion theory, any total α {\displaystyle \alpha } -recursively-enumerable function f : α → α {\displaystyle f:\alpha \rightarrow \alpha } is α {\displaystyle \alpha } -recursive.
• Additionally, a partial function from α {\displaystyle \alpha } to α {\displaystyle \alpha } is α {\displaystyle \alpha } -arithmetical iff there exists some n ∈ ω {\displaystyle n\in \omega } such that the function's graph is Σ n {\displaystyle \Sigma _{n}} -definable on ( L α , ∈ ) {\displaystyle (L_{\alpha },\in )} .

Additional connections between recursion theory and α recursion theory can be drawn, although explicit definitions may not have yet been written to formalize them:

• The functions Δ 0 {\displaystyle \Delta _{0}} -definable in ( L α , ∈ ) {\displaystyle (L_{\alpha },\in )} play a role similar to those of the primitive recursive functions.⁵

We say R is a reduction procedure if it is α {\displaystyle \alpha } recursively enumerable and every member of R is of the form ⟨ H , J , K ⟩ {\displaystyle \langle H,J,K\rangle } where H, J, K are all α-finite.

A is said to be α-recursive in B if there exist R 0 , R 1 {\displaystyle R_{0},R_{1}} reduction procedures such that:

K ⊆ A ↔ ∃ H : ∃ J : [ ⟨ H , J , K ⟩ ∈ R 0 ∧ H ⊆ B ∧ J ⊆ α / B ] , {\displaystyle K\subseteq A\leftrightarrow \exists H:\exists J:[\langle H,J,K\rangle \in R_{0}\wedge H\subseteq B\wedge J\subseteq \alpha /B],} K ⊆ α / A ↔ ∃ H : ∃ J : [ ⟨ H , J , K ⟩ ∈ R 1 ∧ H ⊆ B ∧ J ⊆ α / B ] . {\displaystyle K\subseteq \alpha /A\leftrightarrow \exists H:\exists J:[\langle H,J,K\rangle \in R_{1}\wedge H\subseteq B\wedge J\subseteq \alpha /B].}

If A is recursive in B this is written A ≤ α B {\displaystyle \scriptstyle A\leq _{\alpha }B} . By this definition A is recursive in ∅ {\displaystyle \scriptstyle \varnothing } (the empty set) if and only if A is recursive. However A being recursive in B is not equivalent to A being Σ 1 ( L α [ B ] ) {\displaystyle \Sigma _{1}(L_{\alpha }[B])} .

We say A is regular if ∀ β ∈ α : A ∩ β ∈ L α {\displaystyle \forall \beta \in \alpha :A\cap \beta \in L_{\alpha }} or in other words if every initial portion of A is α-finite.

Work in α recursion

Shore's splitting theorem: Let A be α {\displaystyle \alpha } recursively enumerable and regular. There exist α {\displaystyle \alpha } recursively enumerable B 0 , B 1 {\displaystyle B_{0},B_{1}} such that A = B 0 ∪ B 1 ∧ B 0 ∩ B 1 = ∅ ∧ A ≰ α B i ( i < 2 ) . {\displaystyle A=B_{0}\cup B_{1}\wedge B_{0}\cap B_{1}=\varnothing \wedge A\not \leq _{\alpha }B_{i}(i<2).}

Shore's density theorem: Let A, C be α-regular recursively enumerable sets such that A < α C {\displaystyle \scriptstyle A<_{\alpha }C} then there exists a regular α-recursively enumerable set B such that A < α B < α C {\displaystyle \scriptstyle A<_{\alpha }B<_{\alpha }C} .

Barwise has proved that the sets Σ 1 {\displaystyle \Sigma _{1}} -definable on L α + {\displaystyle L_{\alpha ^{+}}} are exactly the sets Π 1 1 {\displaystyle \Pi _{1}^{1}} -definable on L α {\displaystyle L_{\alpha }} , where α + {\displaystyle \alpha ^{+}} denotes the next admissible ordinal above α {\displaystyle \alpha } , and Σ {\displaystyle \Sigma } is from the Levy hierarchy.⁶

There is a generalization of limit computability to partial α → α {\displaystyle \alpha \to \alpha } functions.⁷

A computational interpretation of α {\displaystyle \alpha } -recursion exists, using " α {\displaystyle \alpha } -Turing machines" with a two-symbol tape of length α {\displaystyle \alpha } , that at limit computation steps take the limit inferior of cell contents, state, and head position. For admissible α {\displaystyle \alpha } , a set A ⊆ α {\displaystyle A\subseteq \alpha } is α {\displaystyle \alpha } -recursive iff it is computable by an α {\displaystyle \alpha } -Turing machine, and A {\displaystyle A} is α {\displaystyle \alpha } -recursively-enumerable iff A {\displaystyle A} is the range of a function computable by an α {\displaystyle \alpha } -Turing machine. ⁸

A problem in α-recursion theory which is open (as of 2019) is the embedding conjecture for admissible ordinals, which is whether for all admissible α {\displaystyle \alpha } , the automorphisms of the α {\displaystyle \alpha } -enumeration degrees embed into the automorphisms of the α {\displaystyle \alpha } -enumeration degrees.⁹

Relationship to analysis

Some results in α {\displaystyle \alpha } -recursion can be translated into similar results about second-order arithmetic. This is because of the relationship L {\displaystyle L} has with the ramified analytic hierarchy, an analog of L {\displaystyle L} for the language of second-order arithmetic, that consists of sets of integers.¹⁰

In fact, when dealing with first-order logic only, the correspondence can be close enough that for some results on L ω = HF {\displaystyle L_{\omega }={\textrm {HF}}} , the arithmetical and Levy hierarchies can become interchangeable. For example, a set of natural numbers is definable by a Σ 1 0 {\displaystyle \Sigma _{1}^{0}} formula iff it's Σ 1 {\displaystyle \Sigma _{1}} -definable on L ω {\displaystyle L_{\omega }} , where Σ 1 {\displaystyle \Sigma _{1}} is a level of the Levy hierarchy.¹¹ More generally, definability of a subset of ω over HF with a Σ n {\displaystyle \Sigma _{n}} formula coincides with its arithmetical definability using a Σ n 0 {\displaystyle \Sigma _{n}^{0}} formula.¹²

• Gerald Sacks, Higher recursion theory, Springer Verlag, 1990 https://projecteuclid.org/euclid.pl/1235422631
• Robert Soare, Recursively Enumerable Sets and Degrees, Springer Verlag, 1987 https://projecteuclid.org/euclid.bams/1183541465
• Keith J. Devlin, An introduction to the fine structure of the constructible hierarchy (p.38), North-Holland Publishing, 1974
• J. Barwise, Admissible Sets and Structures. 1975

Inline references

References

1. P. Koepke, B. Seyfferth, Ordinal machines and admissible recursion theory (preprint) (2009, p.315). Accessed October 12, 2021 https://www.math.uni-bonn.de/people/koepke/Preprints/Ordinal_machines_and_admissible_recursion_theory.pdf ↩

2. R. Gostanian, The Next Admissible Ordinal, Annals of Mathematical Logic 17 (1979). Accessed 1 January 2023. https://www.sciencedirect.com/science/article/pii/0003484379900251 ↩

3. Srebrny, Marian, Relatively constructible transitive models (1975, p.165). Accessed 21 October 2021. http://matwbn.icm.edu.pl/ksiazki/fm/fm96/fm96114.pdf ↩

4. W. Richter, P. Aczel, "Inductive Definitions and Reflecting Properties of Admissible Ordinals" (1974), p.30. Accessed 7 February 2023. https://www.duo.uio.no/bitstream/handle/10852/44063/1973-13.pdf ↩

5. Srebrny, Marian, Relatively constructible transitive models (1975, p.165). Accessed 21 October 2021. http://matwbn.icm.edu.pl/ksiazki/fm/fm96/fm96114.pdf ↩

6. T. Arai, Proof theory for theories of ordinals - I: recursively Mahlo ordinals (1998). p.2 https://www.sciencedirect.com/science/article/pii/S0168007203000204 ↩

7. S. G. Simpson, "Degree Theory on Admissible Ordinals", pp.170--171. Appearing in J. Fenstad, P. Hinman, Generalized Recursion Theory: Proceedings of the 1972 Oslo Symposium (1974), ISBN 0 7204 22760. ↩

8. P. Koepke, B. Seyfferth, "Ordinal machines and admissible recursion theory". Annals of Pure and Applied Logic vol. 160 (2009), pp.310--318. https://www.math.uni-bonn.de/people/koepke/Preprints/Ordinal_machines_and_admissible_recursion_theory.pdf ↩

9. D. Natingga, Embedding Theorem for the automorphism group of the α-enumeration degrees (p.155), PhD thesis, 2019. ↩

10. P. D. Welch, The Ramified Analytical Hierarchy using Extended Logics (2018, p.4). Accessed 8 August 2021. https://arxiv.org/pdf/1808.03814.pdf#page=4 ↩

11. G. E. Sacks, Higher Recursion Theory (p.152). "Perspectives in Logic", Association for Symbolic Logic. ↩

12. P. Odifreddi, Classical Recursion Theory (1989), theorem IV.3.22. ↩