index set (original) (raw)

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

Thus, if A is an index set and φx=φy, then either x,y∈A or x,y∉A. 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.