# 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).

## DefinitionEdit

Fix an enumeration of all partial recursive functions, or equivalently of recursively enumerable sets whereby the *e*th such set is and the *e*th such function (whose domain is ) is .

Let be a class of partial recursive functions. If then is the **index set** of . In general is an index set if for every with (i.e. they index the same function), we have . Intuitively, these are the sets of natural numbers that we describe only with reference to the functions they index.

## Index sets and Rice's theoremEdit

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

Let be a class of partial recursive functions with index set . Then is recursive if and only if is empty, or is all of .

where is the set of natural numbers, including zero.

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

## NotesEdit

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

## ReferencesEdit

- 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.