# 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 $W_{e}$  and the eth such function (whose domain is $W_{e}$ ) is $\phi _{e}$ .

Let ${\mathcal {A}}$  be a class of partial recursive functions. If $A=\{x:\phi _{x}\in {\mathcal {A}}\}$  then $A$  is the index set of ${\mathcal {A}}$ . In general $A$  is an index set if for every $x,y\in \mathbb {N}$  with $\phi _{x}\simeq \phi _{y}$  (i.e. they index the same function), we have $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 ${\mathcal {C}}$  be a class of partial recursive functions with index set $C$ . Then $C$  is recursive if and only if $C$  is empty, or $C$  is all of $\omega$ .

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

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