Vol. 41, No. 2, 1972

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 329: 1  2
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Online Archive
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
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