Alpha recursion theory: Difference between revisions

Revision as of 22:15, 25 October 2021

Revision as of 02:56, 3 November 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 name="relconstr">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>.