most recent 30 from http://mathoverflow.net 2013-05-18T20:22:56Z http://mathoverflow.net/feeds/question/109550 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109550/a-question-about-recursively-enumerable-sets-of-rational-numbers Garabed Gulbenkian 2012-10-13T18:23:47Z 2012-10-13T19:23:05Z

<p>Let (Q*,&lt;) denote the ordered set in which the elements of Q* are just the positive rational numbers less than 1 and "&lt;" 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,&lt;) is ordinally similar to S. Consequently there exist many sets N* of positive integers which have the property that (f(N*),&lt;) 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*),&lt;) 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*),&lt;) is well-ordered appears to be as computationally unsolvable as the the general halting problem for Turing machines-if not more so.</p>

http://mathoverflow.net/questions/109550/a-question-about-recursively-enumerable-sets-of-rational-numbers/109555#109555 Linda Brown Westrick 2012-10-13T19:23:05Z 2012-10-13T19:23:05Z

<p>The ordering (f(N*),&lt;) 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.</p>