In this paper our attention
centers on partial recursive retracing functions, especially countable ones (as definedbelow), and on their relationship with classes of number theoretic functions
constituting solution sets for ∏20 function predicates in the Kleene hierarchy.
Arithmetical function predicates which have singleton solution sets (i.e., so
called implicit arithmetical definitions) have received ample attention in the
recursion-theoretic literature. We shall be concerned with such predicates, at tke
levels ∏10 and ∏20; but we shall primarily be concerned with the wider classes of
∏10 and ∏20 predicates having countable solution sets. In §5, we show (by
obtaining examples which range over the whole of ℋ∩{D|D > 0′}, ℋ as
defined in §4) that a solution of a countable ∏10 predicate need not be
definable by means of a “strong” ∏20 predicate; in fact, we establish the
corresponding (slightly stronger) proposition for countable, finite-to-one,
general recursive retracing functions. The question whether all solutions of a
countable ∏20 predicate are ∏2n definable is left open but subjected to
conjecture.
