COUNTABLE RETRACING FUNCTIONS AND PI0/2 PREDICATES

In this paper our attention centers on partial recursive retracing functions, especially countable ones (as defined below), and on their relationship with classes of number theoretic functions constituting solution sets for Π20 function predicates in the Kleene hierarchy. Arithmetical function predicates whichhave 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 the 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 meansof 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 Π20 definable is left open but supjected to conjecture. © 1969 by Pacific Journal of Mathematics.