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
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
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
Abstract

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
Milestones
Received: 27 November 1967
Revised: 14 October 1968
Published: 1 July 1969
Authors
Carl Groos Jockusch, Jr.
Thomas Graham McLaughlin