As I understand, there exists the least ordinal $\alpha$ such that there is no well-ordering of $\mathbb{N}$ which is both order isomorphic to $\alpha$ and is an arithmetical set. Is there a conventional name for that ordinal? Is every ordinal above $\alpha$ non-arithmetical as well?
Least non-arithmetical ordinal
-
0I think nikov may be thinking of the relation itself being a non-arithmetical set (i.e., a non-arithmetical subset of $\mathbb{N}^2$). I am not an expert on this, but I would suspect that the ordinal $\varepsilon_0$ is strongly related to this concept. Otherwise, I am unaware of any notation/nomenclature for this ordinal. – 2011-11-25
2 Answers
As Joel David Hamkins pointed out to me in another question on MO, the set of arithmetical ordinals is exactly the set of recursive ordinals $\omega^{\mathrm{CK}}_1$. See https://mathoverflow.net/questions/82136/ordinals-and-complexity-classes/82144#82144.
As I said in the comment, you are probably looking for the least ordinal such there is no well-ordering of a subset of $\mathbb N$ that is both order isomorphic to $\alpha$ and arithmetical. Otherwise $0$ would the least such ordinal. So in the following I'll assume the modified definition.
I haven't heard of such ordinals before, but given the obvious similarities with recursive ordinals, I think that the term arithmetical ordinals would be appropriate.
As to your second question, assume $\alpha$ is an arithmetical ordinal. Let $\beta < \alpha$ (i.e. $\beta \in \alpha$). Let $R(x,y)$ be an arithmetical relation that well-orders $N \subseteq \mathbb N$ with the order type $\alpha$. Let $f : \alpha \to N$ define the isomorphism of $\langle \alpha, \in \rangle$ and $\langle N, R \rangle$. Denote $n_\beta = f(\beta)$. Then the relation defined by R'(x, y) = R(x, y) \land R(y, n_\beta) is an arithmetical well-ordering of a subset of $\mathbb N$ with the order type $\beta$. Hence $\beta$ is arithmetic too. Thus all ordinals above a non-arithmetical one are non-arithmetical themselves.