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 wellordered. MY question is this. If N* is any recursively enumerable set of positive integers such that (f(N*),<) is wellordered, is its ordinal number always constructive (in the sense of Church and Kleene)? Or if larger nonconstuctive 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 wellordered appears to be as computationally unsolvable as the the general halting problem for Turing machinesif not more so.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
The ordering (f(N*),<) that you describe is a recursive ordering, so if it is wellfounded, 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. 

