# A question about recursively enumerable sets of rational numbers

Let (Q*,<) denote the ordered set in which the elements of Q* are just the positive rational numbers less than 1 and "<" is the ordering relation of the ordered field (of all rational numbers) Q. Let f be a fixed effective enumeration (without repetitions) of Q*-many examples of which are well known. It is also well known that if S is any denumerable ordered set, there exist many subsets X of Q* such that (X,<) is ordinally similar to S. Consequently there exist many sets N* of positive integers which have the property that (f(N*),<) is ordinally similar to S. I am interested in the case where S is well-ordered. MY question is this. If N* is any recursively enumerable set of positive integers such that (f(N*),<) is well-ordered, is its ordinal number always constructive (in the sense of Church and Kleene)? Or if larger non-constuctive ordinal numbers are attainable by means of this procedure, how large can they get? Various theorems about recursive ordinal numbers make it seem likely that one would not be able to reach beyond these numbers in this way. But one aspect of the situation renders it difficult to work out a straightforward solution to this problem. If one thinks of recursively enumerable sets such as N* as being generated by Turing machines, the problem of determining whether the resulting ordered set (f(N*),<) is well-ordered appears to be as computationally unsolvable as the the general halting problem for Turing machines-if not more so.

• You've completely answered the question, but it might be useful to add that considerably more is true. The hyperarithmetical ordinals also coincide with the constructive ordinals. Thus, the order-type of $f(N^*)$ will be constructive whenever it is well-ordered and $N^*$ is hyperarithmetic (or even lightface $\Sigma^1_1$). – Andreas Blass Oct 14 '12 at 0:04