On orders of translations and enumerations
John Helm, Albert R. Meyer, Paul Young · Pacific Journal of Mathematics · 1973
A basic result of intuitive recursion theory is that a set (of natural numbers) is decidable (recursive) iff it can be effectively enumerated in its natural order (of increasing magnitude).The chief theorems of this paper give simple, but very basic facts relating to enumerations in natural order of magnitude and the extent to which translations must preserve the orders of the sets being enumerated.Under very general conditions for what constitutes a programming system for enumerating the recursively enumerable (r.e.) sets, we prove in Theorem 1 that not every recursive set is " best" enumerated in its natural order, and we later show that under these same general conditions, in every programming system, every recursive set is enumerable in its natural order.We accomplish the latter result by extending Rogers' Isomorphism Theorem to a result which asserts that under these same general conditions, every programming system can be effectively translated into any other in a manner which preserves the order of the sets being enumerated (Theorems 4 and 5).In fact, we show that for every translator, t, there is an order preserving pretranslator, p, such that t is orderpreserving modulo p; i.e., t © p is an order preserving translator.In addition, the restriction of the original programming system to the recursive set {range p] is a standard programming system on which t is order-preserving.Along the way we establish the existence of sets best enumerated in their natural order and, for every r.e.set, the existence of bad orders for enumerating the set.All proofs are fairly straightforward.Notation and basic definitions* We let XxD x denote a canonical enumeration of all finite sets (of natural numbers).Given x, we can effectively list D z and know when the listing is completed.Except for [the indexings XxW x of the r.e.sets which we are about to describe and the notation Wΐ described later, our notation generally follows [7].(x, y) is (an encoding of) the ordered pair of integers x and y.DEFINITION, ([8]).An [enumeration technique is a total recursive function E(x, y) such that for every (r.e.) set W there exists an e such that W = \J n D E (e,n)-We call e an index of W and denote U^ Djsie.n) by W e E , the superscript E being suppressed whenever there is no danger of ambiguity.D Έ , ie , n) = U**» A? An enumeration technique is called standard if the Sί-theorem is 185