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.
