In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals
α
. An admissible ordinal is closed under
Σ
1
(
L
α
)
functions. Admissible ordinals are models of Kripke–Platek set theory. In what follows
α
is considered to be fixed.
The objects of study in
α
recursion are subsets of
α
. A is said to be
α
recursively enumerable if it is
Σ
1
definable over
L
α
. A is recursive if both A and
α
/
A
(its complement in
α
) are
α
recursively enumerable.
Members of
L
α
are called
α
finite and play a similar role to the finite numbers in classical recursion theory.
We say R is a reduction procedure if it is
α
recursively enumerable and every member of R is of the form
⟨
H
,
J
,
K
⟩
where H, J, K are all α-finite.
A is said to be α-recursive in B if there exist
R
0
,
R
1
reduction procedures such that:
K
⊆
A
↔
∃
H
:
∃
J
:
[
⟨
H
,
J
,
K
⟩
∈
R
0
∧
H
⊆
B
∧
J
⊆
α
/
B
]
,
K
⊆
α
/
A
↔
∃
H
:
∃
J
:
[
⟨
H
,
J
,
K
⟩
∈
R
1
∧
H
⊆
B
∧
J
⊆
α
/
B
]
.
If A is recursive in B this is written
A
≤
α
B
. By this definition A is recursive in
∅
(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
]
)
.
We say A is regular if
∀
β
∈
α
:
A
∩
β
∈
L
α
or in other words if every initial portion of A is α-finite.
Shore's splitting theorem: Let A be
α
recursively enumerable and regular. There exist
α
recursively enumerable
B
0
,
B
1
such that
A
=
B
0
∪
B
1
∧
B
0
∩
B
1
=
∅
∧
A
≰
α
B
i
(
i
<
2
)
.
Shore's density theorem: Let A, C be α-regular recursively enumerable sets such that
A
<
α
C
then there exists a regular α-recursively enumerable set B such that
A
<
α
B
<
α
C
.
