# 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}\u27f9y\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 |