In computability theory, **index sets** describe classes of computable functions; specifically, they give all indices of functions in a certain class, according to a fixed Gödel numbering of partial computable functions.

## Definition

Let be a computable enumeration of all partial computable functions, and be a computable enumeration of all c.e. sets.

Let be a class of partial computable 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 theorem

Most index sets are non-computable, aside from two trivial exceptions. This is stated in Rice's theorem:

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

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

## Completeness in the arithmetical hierarchy

Index sets provide many examples of sets which are complete at some level of the arithmetical hierarchy. Here, we say a set is *-complete* if, for every set , there is an m-reduction from to . -completeness is defined similarly. Here are some examples:^{[2]}

- is -complete.
- is -complete.
- is -complete.
- is -complete.
- is -complete.
- is -complete.
- is -complete.
- is -complete.
- is -complete, where is the halting problem.

Empirically, if the "most obvious" definition of a set is [resp. ], we can usually show that is -complete [resp. -complete].

## Notes

**^**Odifreddi, P. G.*Classical Recursion Theory, Volume 1*.; page 151**^**Soare, Robert I. (2016), "Turing Reducibility",*Turing Computability*, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 51–78, ISBN 978-3-642-31932-7, retrieved 2021-04-21

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