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*if

_{f(e)}*W*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!

_{e}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*. As I said, it seems like cheating, but it isn’t!

_{g(e)}