2
$\begingroup$

Let $K$ be the set of all total recursive functions of non-negative integers having only non-negative integers as values. Let $L$ be any well-ordered subset of $K$ in which the ordering $<$ is defined as follows. If $f(n),g(n)$ are elements of $L$, then $f(n)< g(n)$ just in case there exists a non-negative integer $h$ such that $f(n)$ is less than $g(n)$ whenever n is greater than $h$. Suppose that $L$ contains a maximum element. Is the ordinal number of the well-ordered set $L$ always a constructive ordinal number (in the sense of Church and Kleene)? Can arbitrarily large constructive ordinal numbers be represented in this way?

$\endgroup$
2
  • $\begingroup$ I seem to have lost most of my question $\endgroup$ Mar 1, 2015 at 19:56
  • $\begingroup$ Please disregard this last comment $\endgroup$ Mar 1, 2015 at 20:01

1 Answer 1

5
$\begingroup$

The answer to the first question is No and the second question Yes, because in fact every countable (successor) ordinal arises that way. (The successor part is only because you insisted that $L$ has a maximal element; otherwise we could say that every countable ordinal arises this way.)

The reason is that $K$ contains a countable dense linear order, and every countable linear order, including every countable well-order, can therefore be found as a suborder.

In particular, we can find $L$ having order type larger than $\omega^{CK}_1$ this way.

$\endgroup$
1
  • $\begingroup$ I was trying to work out whether any useful notation systems for a segment of the countable ordinal numbers could be developed, using recursive functions-or even just primitive recursive functions-as the notations. When you pointed out the existence of subsets of K which are densely ordered by "<", I saw what was wrong with this idea and why Hardy (who, I believe, first investigated the ordering "<") never went very far with it. $\endgroup$ Mar 3, 2015 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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