MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer
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
Many thanks for settling this question for me so clearly and completely. – Garabed Gulbenkian Oct 14 '12 at 19:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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