Vol. 41, No. 2, 1972

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 311: 1
Vol. 310: 1  2
Vol. 309: 1  2
Vol. 308: 1  2
Vol. 307: 1  2
Vol. 306: 1  2
Vol. 305: 1  2
Vol. 304: 1  2
Online Archive
The Journal
Editorial Board
Submission Guidelines
Submission Form
Policies for Authors
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author Index
To Appear
Other MSP Journals
Supersimple sets and the problem of extending a retracing function

Thomas Graham McLaughlin

Vol. 41 (1972), No. 2, 485–494

An infinite set A of natural numbers is called regressive if there is a (non-repeating) sequential ordering a0,aI, of A and a partial recursive function f such that A domain (f), f(a0) = a0, and (n)[f(an+1) = an]; in case a0,a1, is the natural ordering of A by increasing size of elements, A is called retraceable and f is said to retrace A. It sometimes happens that a retraceable set does not admit an everywhere-defined retracing function, or that it does not admit a finite-to-one retracing function. Question: does there exist an infinite set A of natural numbers such that A is retraced both by a total recursive function and by a finite-to-one partial recursive function, but not by a function which is both total recursive and finite-toone? Via some theorems relating to D. A. Martin’s motions of supersimple and superimmune sets of natural numbers, a strongly affirmative result is obtained.

Mathematical Subject Classification
Primary: 02F25
Received: 30 November 1970
Revised: 1 September 1971
Published: 1 May 1972
Thomas Graham McLaughlin