# Index set (recursion theory)

In the field of recursion theory, index sets describe classes of partial recursive functions, specifically they give all indices of functions in that class according to a fixed enumeration of partial recursive functions (a Gödel numbering).

## Definition

Fix an enumeration of all partial recursive functions, or equivalently of recursively enumerable sets whereby the eth such set is ${\displaystyle W_{e}}$  and the eth such function (whose domain is ${\displaystyle W_{e}}$ ) is ${\displaystyle \phi _{e}}$ .

Let ${\displaystyle {\mathcal {A}}}$  be a class of partial recursive functions. If ${\displaystyle A=\{x:\phi _{x}\in {\mathcal {A}}\}}$  then ${\displaystyle A}$  is the index set of ${\displaystyle {\mathcal {A}}}$ . In general ${\displaystyle A}$  is an index set if for every ${\displaystyle x,y\in \mathbb {N} }$  with ${\displaystyle \phi _{x}\simeq \phi _{y}}$  (i.e. they index the same function), we have ${\displaystyle x\in A\leftrightarrow y\in A}$ . Intuitively, these are the sets of natural numbers that we describe only with reference to the functions they index.

## Index sets and Rice's theorem

Most index sets are incomputable (non-recursive) aside from two trivial exceptions. This is stated in Rice's theorem:

Let ${\displaystyle {\mathcal {C}}}$  be a class of partial recursive functions with index set ${\displaystyle C}$ . Then ${\displaystyle C}$  is recursive if and only if ${\displaystyle C}$  is empty, or ${\displaystyle C}$  is all of ${\displaystyle \omega }$ .

where ${\displaystyle \omega }$  is the set of natural numbers, including zero.

Rice's theorem says "any nontrivial property of partial recursive functions is undecidable"[1]

## Notes

1. ^ Odifreddi, P. G. Classical Recursion Theory, Volume 1.; page 151

## References

• Odifreddi, P. G. (1992). Classical Recursion Theory, Volume 1. Elsevier. p. 668. ISBN 0-444-89483-7.
• Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT Press. p. 482. ISBN 0-262-68052-1.