Alpha recursion theory: Difference between revisions

Revision as of 09:00, 10 August 2023

Revision as of 02:46, 23 December 2023

Line 8:

There are also some similar definitions for functions mapping <math>\alpha</math> to <math>\alpha</math>:<ref name="relconstr">Srebrny, Marian, [http://matwbn.icm.edu.pl/ksiazki/fm/fm96/fm96114.pdf Relatively constructible transitive models] (1975, p.165). Accessed 21 October 2021.</ref>

*A partial function mappingfrom <math>\alpha</math> to <math>\alpha</math> is '''<math>\alpha</math>-recursively-enumerable''', or '''<math>\alpha</math>-partial recursive''',<ref>W. Richter, P. Aczel, "[https://www.duo.uio.no/bitstream/handle/10852/44063/1973-13.pdf Inductive Definitions and Reflecting Properties of Admissible Ordinals]" (1974), p.30. Accessed 7 February 2023.</ref> iff its graph is <math>\Sigma_1</math>-definable on <math>(L_\alpha,\in)</math>. Like in the case of classical recursion theory, any <math>\alpha</math>-partial recursive total function from <math>\alpha</math> to <math>\alpha</math> is <math>\alpha</math>-recursive.

*A partial function mappingfrom <math>\alpha</math> to <math>\alpha</math> is '''<math>\alpha</math>-recursive''' iff its graph is <math>\Delta_1</math>-definable on <math>(L_\alpha,\in)</math>.

*Additionally, a partial function mappingfrom <math>\alpha</math> to <math>\alpha</math> is '''<math>\alpha</math>-arithmetical''' iff there exists some <math>n\in\omega</math> such that the function's graph is <math>\Sigma_n</math>-definable on <math>(L_\alpha,\in)</math>.

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