Vol. 30, No. 1, 1969

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 294: 1
Vol. 293: 1  2
Vol. 292: 1  2
Vol. 291: 1  2
Vol. 290: 1  2
Vol. 289: 1  2
Vol. 288: 1  2
Vol. 287: 1  2
Online Archive
The Journal
Editorial Board
Special Issues
Submission Guidelines
Submission Form
Author Index
To Appear
ISSN: 0030-8730
Countable retracing functions and Π20 predicates

Carl Groos Jockusch, Jr. and Thomas Graham McLaughlin

Vol. 30 (1969), No. 1, 67–93

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 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.

Mathematical Subject Classification
Primary: 02.77
Received: 27 November 1967
Revised: 14 October 1968
Published: 1 July 1969
Carl Groos Jockusch, Jr.
Thomas Graham McLaughlin