index set

In computability theory, a set $A\subseteq \omega$ is called an index set if for all $x,y$,

$$x\in A,{\phi }_x={\phi }_y⟹y\in A.$$

${\phi }_x$ stands for the partial function with Gödel number (or index) $x$.

Thus, if $A$ is an index set and ${\phi }_x={\phi }_y$, then either $x,y\in A$ or $x,y\notin A$. Intuitively, if $A$ contains the Gödel index $x$ of a partial function $\phi$, then $A$ contains all indices for the partial function. (Recall that there are ${\mathrm{\aleph }}_0$ Gödel numbers for each partial function.)

It is instructive to compare the notion of an index set in computability theory with that of an indexing set.

Title	index set
Canonical name	IndexSet
Date of creation	2013-03-22 18:09:48
Last modified on	2013-03-22 18:09:48
Owner	yesitis (13730)
Last modified by	yesitis (13730)
Numerical id	5
Author	yesitis (13730)
Entry type	Definition
Classification	msc 03D25