User:IssaRice/Computability and logic/K is recursively enumerable
Finding a partial recursive function that enumerates K
This proof is from Enderton.
Proof. Let be a standard enumeration of the partial recursive functions.
We can define the diagonal partial function . This is a partial recursive function because both and are, and we can obtain via substitution. Thus, for some . (Actually, is it really so simple to show is partial recursive? We're not just using a fixed , but rather we are allowing the partial function index to move around. To be more rigorous, I think we need to say that , where is the two-place universal function. Since the universal function is partial recursive, we can be sure that we can use the expression "" and move the index around. Even more formally, we can say .)
But now . Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that is recursively enumerable.
Discussion. The definition of doesn't seem to be important. Actually, I think we can just take . But it seems Enderton did the plus one to make a further point (namely, that it looks like we might be diagonalizing out of this class of functions, but luckily we're not, thanks to our objects only being partial functions).
Peter Smith. An Introduction to Gödel's Theorems. p. 24.
- Herbert Enderton. Computability Theory. p. 80