Simple Sets and the Recursion Theorem

These notes on Simple Sets are a grabbag about the simple sets of recursion theory. If you don’t know what those are, you probably are not interested, but the Wikipedia article is nice and short and gives the basics.

The last result uses the “shiny black box” (see below), which seems like cheating, but isn’t!

I wrote up the notes sometime in the 1980s based on two papers, and on a lecture by Michael Stob at MIT (reporting on joint work with Maas and Shore). They discuss effectively simple sets and promptly simple sets.

The topics are unified by a common technique: Kleene’s recursion theorem. This says that if φ_e is a (computable) enumeration of the partial recursive functions, and if f is a (total) recursive function, then φ_e=φ_f(e) for some index e. (The theorem has the usual complement of variations, e.g., W_e=W_f(e) if W_e is an enumeration of the r.e. sets.) Kleene’s recursion theorem traces its ancestry back to Cantor’s diagonal argument, by way of Gödel’s incompleteness theorem and Turing’s Halting problem, so it very much belongs on this blog!

I always had a special affinity for uses of the theorem. The lecture by Stob gave a magical application, which Stob called the “shiny black box” method. (He attributed the term to someone else, I forget who. Maybe Harvey Friedman?) It combined the recursion theorem with Friedberg’s priority method. Truthfully, I found the method more interesting than the result. But maybe that’s just me.

As Stob put it, you give a construction to generate a series of r.e. sets, say V_e. While doing the construction, you assume you have a recursive function g giving you the indices of the sets: V_e=W_g(e). As I said, it seems like cheating, but it isn’t!