Index set (recursion theory)

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

Let A be a class of partial recursive functions. If A = { x : ϕ x ∈ A } then A is the index set of A . In general A is an index set if for every x , y ∈ N with ϕ x ≃ ϕ y (i.e. they index the same function), we have x ∈ A ↔ y ∈ 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 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 ω .

where ω is the set of natural numbers, including zero.

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