# index set

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

 $x\in A,\varphi_{x}=\varphi_{y}\Longrightarrow y\in A.$

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

Thus, if $A$ is an index set and $\varphi_{x}=\varphi_{y}$, then either $x,y\in A$ or $x,y\not\in A$. Intuitively, if $A$ contains the Gödel index $x$ of a partial function $\varphi$, then $A$ contains all indices for the partial function. (Recall that there are $\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 IndexSet 2013-03-22 18:09:48 2013-03-22 18:09:48 yesitis (13730) yesitis (13730) 5 yesitis (13730) Definition msc 03D25