Vol. 41, No. 2, 1972

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 305: 1
Vol. 304: 1  2
Vol. 303: 1  2
Vol. 302: 1  2
Vol. 301: 1  2
Vol. 300: 1  2
Vol. 299: 1  2
Vol. 298: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Editorial Board
Subscriptions
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
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
Abstract

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
Milestones
Received: 30 November 1970
Revised: 1 September 1971
Published: 1 May 1972
Authors
Thomas Graham McLaughlin