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.


The ordering (f(N*),<) that you describe is a recursive ordering, so if it is well-founded, it has the order type of a recursive ordinal. It is known (see e.g. Higher Recursion Theory by Sacks) that the recursive ordinals coincide with the constructive ordinals. Therefore, the order type is constructive.

  • 2
    $\begingroup$ 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$). $\endgroup$ – Andreas Blass Oct 14 '12 at 0:04
  • $\begingroup$ Many thanks for settling this question for me so clearly and completely. $\endgroup$ – Garabed Gulbenkian Oct 14 '12 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.