Alpha recursion theory: Difference between revisions

Revision as of 03:39, 16 October 2021

Revision as of 14:59, 21 October 2021

Line 1:

In [[recursion theory]], '''α recursion theory''' is a generalisation of [[recursion theory]] to subsets of [[admissible ordinal]]s <math>\alpha</math>. An admissible set is closed under <math>\Sigma_1(L_\alpha)</math> functions, where <math>L_\xi</math> denotes a rank of Godel's [[constructible hierarchy]]. <math>\alpha</math> is an admissible ordinal if <math>L_{\alpha}</math> is a model of [[Kripke–Platek set theory]]. In what follows <math>\alpha</math> is considered to be fixed.

The objects of study in <math>\alpha</math> recursion are subsets of <math>\alpha</math>. These sets are said to have some properties:
*A set <math>A\subseteq\alpha</math> is said to be <math>\alpha</math>-recursively-enumerable if it is <math> \Sigma_1</math> definable over <math>L_\alpha</math>.<ref>P. Koepke, B. Seyfferth, [https://www.math.uni-bonn.de/people/koepke/Preprints/Ordinal_machines_and_admissible_recursion_theory.pdf Ordinal machines and admissible recursion theory (preprint)] (2009, p.315). Accessed October 12, 2021</ref>
*A is '''<math>\alpha</math>-recursive''' if both A and <math>\alpha \setminus A</math> (its [[relative complement]] in <math>\alpha</math>) are <math>\alpha</math>-recursively-enumerable. It's of note that <math>\alpha</math>-recursive sets are members of <math>L_{\alpha+1}</math> by definition of <math>L</math>.

*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, [https://matwbn.icm.edu.pl/ksiazki/fm/fm96/fm96114.pdf Relatively constructible transitive models] (p.165). Accessed 21 October 2021.</ref>

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.

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.