A simple set which is not effectively simple

and let We be the range of fe. Then Wo, W1, W2, is the Kleene enumeration of the recursively enumerable sets. Post [51 calls a recursively enumerable set simple if its complement is infinite but does not contain any infinite, recursively enumerable set. Raymond Smullyan calls a recursively enumerable set W effectively simple if its complement is infinite, and if there is a partial recursive function f such that for each e, if We is contained in the complement of W, then f(e) is defined and is greater than the cardinality of We.2 Clearly, an effectively simple set is simple. The simple set S constructed by Post in [51 is effectively simple. This latter is no accident. In fact it is not unreasonable to claim that any direct attack on the problem of constructing a simple set must result in an effectively simple set. Our purpose here is to obtain a simple set which is not effectively simple. We will make strong use of the recursion theorem of Kleene [2]; however, we will use it in the informal manner of Myhill [4]. Our notation is that of [2 1. We introduce a recursive function E: