index set

In computability theory, a set Aω is called an index setMathworldPlanetmathPlanetmath if for all x,y,


φx stands for the partial functionMathworldPlanetmath with Gödel number (or index) x.

Thus, if A is an index set and φx=φy, then either x,yA or x,yA. Intuitively, if A contains the Gödel index x of a partial function φ, then A contains all indices for the partial function. (Recall that there are 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