index set (computability)

Let $\backslash varphi\_e$ be a computable enumeration of all partial computable functions, and $W\_\{e\}$ be a computable enumeration of all c.e. sets.

Let $\backslash mathcal\{A\}$ be a class of partial computable functions. If $A\; =\; \backslash \{x\; \backslash ,:\backslash ,\; \backslash varphi\_\{x\}\; \backslash in\; \backslash mathcal\{A\}\; \backslash \}$ then $A$ is the index set of $\backslash mathcal\{A\}$. In general $A$ is an index set if for every $x,y\; \backslash in\; \backslash mathbb\{N\}$ with $\backslash varphi\_x\; \backslash simeq\; \backslash varphi\_y$ (i.e. they index the same function), we have $x\; \backslash in\; A\; \backslash leftrightarrow\; y\; \backslash in\; A$. Intuitively, these are the sets of natural numbers that we describe only with reference to the functions they index.

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

Let $\backslash 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 $\backslash mathbb\{N\}$.

Rice's theorem says "any nontrivial property of partial computable functions is undecidable".{{cite book | title=Classical Recursion Theory, Volume 1| author=Odifreddi, P. G. }}; page 151

Index sets provide many examples of sets which are complete at some level of the arithmetical hierarchy. Here, we say a $\backslash Sigma\_n$ set $A$ is $\backslash Sigma\_n$-complete if, for every $\backslash Sigma\_n$ set $B$, there is an m-reduction from $B$ to $A$. $\backslash Pi\_n$-completeness is defined similarly. Here are some examples:{{Citation|last=Soare|first=Robert I.|title=Turing Reducibility|date=2016|url=http://dx.doi.org/10.1007/978-3-642-31933-4_3|work=Turing Computability|series=Theory and Applications of Computability |pages=51–78|place=Berlin, Heidelberg|publisher=Springer Berlin Heidelberg|doi=10.1007/978-3-642-31933-4_3 |isbn=978-3-642-31932-7|access-date=2021-04-21|url-access=subscription}}

• $\backslash mathrm\{Emp\}\; =\; \backslash \{\; e\; \backslash ,:\backslash ,\; W\_e\; =\; \backslash varnothing\; \backslash \}$ is $\backslash Pi\_1$-complete.
• $\backslash mathrm\{Fin\}\; =\; \backslash \{\; e\; \backslash ,:\backslash ,\; W\_e\; \backslash text\{\; is\; finite\}\; \backslash \}$ is $\backslash Sigma\_2$-complete.
• $\backslash mathrm\{Inf\}\; =\; \backslash \{\; e\; \backslash ,:\backslash ,\; W\_e\; \backslash text\{\; is\; infinite\}\; \backslash \}$ is $\backslash Pi\_2$-complete.
• $\backslash mathrm\{Tot\}\; =\; \backslash \{\; e\; \backslash ,:\backslash ,\; \backslash varphi\_e\; \backslash text\{\; is\; total\}\; \backslash \}\; =\; \backslash \{\; e\; :\; W\_e\; =\; \backslash mathbb\{N\}\; \backslash \}$ is $\backslash Pi\_2$-complete.
• $\backslash mathrm\{Con\}\; =\; \backslash \{\; e\; \backslash ,:\backslash ,\; \backslash varphi\_e\; \backslash text\{\; is\; total\; and\; constant\}\; \backslash \}$ is $\backslash Pi\_2$-complete.
• $\backslash mathrm\{Cof\}\; =\; \backslash \{\; e\; \backslash ,:\backslash ,\; W\_e\; \backslash text\{\; is\; cofinite\}\; \backslash \}$ is $\backslash Sigma\_3$-complete.
• $\backslash mathrm\{Rec\}\; =\; \backslash \{\; e\; \backslash ,:\backslash ,\; W\_e\; \backslash text\{\; is\; computable\}\; \backslash \}$ is $\backslash Sigma\_3$-complete.
• $\backslash mathrm\{Ext\}\; =\; \backslash \{\; e\; \backslash ,:\backslash ,\; \backslash varphi\_e\; \backslash text\{\; is\; extendible\; to\; a\; total\; computable\; function\}\; \backslash \}$ is $\backslash Sigma\_3$-complete.
• $\backslash mathrm\{Cpl\}\; =\; \backslash \{\; e\; \backslash ,:\backslash ,\; W\_e\; \backslash equiv\_\backslash mathrm\{T\}\; \backslash mathrm\{HP\}\; \backslash \}$ is $\backslash Sigma\_4$-complete, where $\backslash mathrm\{HP\}$ is the halting problem.

Empirically, if the "most obvious" definition of a set $A$ is $\backslash Sigma\_n$ [resp. $\backslash Pi\_n$], we can usually show that $A$ is $\backslash Sigma\_n$-complete [resp. $\backslash Pi\_n$-complete].

{{reflist}}

• {{cite book | title=Classical Recursion Theory, Volume 1| author=Odifreddi, P. G. | publisher=Elsevier| year=1992 | isbn=0-444-89483-7 | pages=668 }}
• {{ cite book | title=Theory of Recursive Functions and Effective Computability | author=Rogers Jr., Hartley | publisher=MIT Press|isbn=0-262-68052-1 | pages=482 | year=1987}}

Category:Computability theory