n-Recursive Linear Orders without (n+1)-Recursive Copies
Michael F. Moses · Birkhäuser Boston eBooks · 1993
An algebraic structure, with universe ω, is said to be recursive if, and only if, the quantifier-free formulae in its language uniformly denote recursive relations in the structure. This concept generalizes to that of an n -recursive structure, in which the Σ n formulae uniformly denote recursive relations. I present a sequence of simply defined relations in the language of linear order and show that a recursive linear order of type ω k (with k < ω) is n -recursive if, and only if, it has the first n relations in the sequence recursive. I can then show that, for each k , and each n ≤ (2 k − 2), ω k has an n -recursive copy that is not ( n +1)-recursive. This means that, for each n , there is an n -recursive but not ( n +1)-recursive linear order (of some type ω k ). I show, in fact, that there is, for each n, a linear order (of some type ω k · τ) that is n -recursive but has no ( n +1)- recursive copy .