Alpha recursion theory: Difference between revisions

Revision as of 20:13, 22 October 2021

Revision as of 01:42, 23 October 2021

Line 6:

*Members of <math>L_\alpha</math> are called '''<math>\alpha</math>-finite''' and play a similar role to the finite numbers in classical recursion theory.

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

*A function mapping <math>\alpha</math> to <math>\alpha</math> is '''<math>\alpha</math>-recursively-enumerable''' iff its graph is <math>\Sigma_1</math>-definable in <math>(L_\alpha,\in)</math>.

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

*Additionally, a function mapping <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 in <math>(L_\alpha,\in)</math>.

We say R is a reduction procedure if it is <math>\alpha</math> recursively enumerable and every member of R is of the form <math> \langle H,J,K \rangle </math> where ''H'', ''J'', ''K'' are all α-finite.