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.