Index set (computability)

Let \varphi_e be a computable enumeration of all partial computable functions, and W_{e} be a computable enumeration of all c.e. sets. Let \mathcal{A} be a class of partial computable functions. If A = \{x \,:\, \varphi_{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 \varphi_x \simeq \varphi_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 non-computable, aside from two trivial exceptions. This is stated in Rice's theorem: Let \mathcal{C} be a class of partial computable functions with its index set C. Then C is computable if and only if C is empty, or C is all of \mathbb{N}. Rice's theorem says "any nontrivial property of partial computable functions is undecidable". == 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 \Sigma_n set A is \Sigma_n-complete if, for every \Sigma_n set B, there is an m-reduction from B to A. \Pi_n-completeness is defined similarly. Here are some examples: • \mathrm{Emp} = \{ e \,:\, W_e = \varnothing \} is \Pi_1-complete. • \mathrm{Fin} = \{ e \,:\, W_e \text{ is finite} \} is \Sigma_2-complete. • \mathrm{Inf} = \{ e \,:\, W_e \text{ is infinite} \} is \Pi_2-complete. • \mathrm{Tot} = \{ e \,:\, \varphi_e \text{ is total} \} = \{ e : W_e = \mathbb{N} \} is \Pi_2-complete. • \mathrm{Con} = \{ e \,:\, \varphi_e \text{ is total and constant} \} is \Pi_2-complete. • \mathrm{Cof} = \{ e \,:\, W_e \text{ is cofinite} \} is \Sigma_3-complete. • \mathrm{Rec} = \{ e \,:\, W_e \text{ is computable} \} is \Sigma_3-complete. • \mathrm{Ext} = \{ e \,:\, \varphi_e \text{ is extendible to a total computable function} \} is \Sigma_3-complete. • \mathrm{Cpl} = \{ e \,:\, W_e \equiv_\mathrm{T} \mathrm{HP} \} is \Sigma_4-complete, where \mathrm{HP} is the halting problem. Empirically, if the "most obvious" definition of a set A is \Sigma_n [resp. \Pi_n], we can usually show that A is \Sigma_n-complete [resp. \Pi_n-complete]. ==Notes==