Two notes on recursive functions and regressive isols
Joseph Barback · Transactions of the American Mathematical Society · 1969
Introduction.The theory of regressive isols was introduced by J. C. E. Dekker in [7].The results that we wish to present in this paper belong to this theory and is a continuation of some of our studies in [1], [3] and [4].We will assume that the reader is familiar with the terminology and some of the main results of the papers listed as references.We let E denote the collection of all nonnegative integers (numbers), A the collection of all isols, A* the collection of all isolic integers, and AB the collection of all regressive isols.If/is a function from a subset of E into E then 8/ will denote its domain and pf its range.Let un and vn be two one-to-one functions from E into E. Then un ^ * vn, if there is a partial recursive function / such that (1) pu S 8/ and (In addition, un and vn are said to be recursively equivalent (denoted Hn~i>n), if there is a one-to-one partial recursive function/such that (1) holds.It is easy to see that "n -1>» => PUn -PVn-Also, it can be shown [8], that (2) wn ~ vn o (un £*vn and vn g * un).Let a and ß be two infinite subsets of E. Then a ^ *ß, if there is a partial recursive function / such that a^8ff(a)=ß and/is one-to-one on a.If a and ß are each isolated sets then the following is true [8, Proposition P9.(b)], (3) (a ^ * ß and ß ^ * a) o a ~ ß.Let a and ß be infinite and isolated regressive sets, and let an and bn be any regressive functions that range over a and ß respectively.Then (4) a<,*ßoanu*bn,