Recursive linear orders with recursive successivities (Q1062051): Difference between revisions

A successivity in a linear ordering \(<_ R\) is an ordered pair (x,y) of integers such that \(x<_ Ry\) and for which there is no intermediate integer z satisfying \(x<_ Rz<_ Ry\). A recursive linear ordering \(<_ R\) is recursively categorical if any isomorphic recursive linear ordering \(<_ S\) is recursively isomorphic with \(<_ R\). The author characterizes recursively categorical recursive linear orderings having recursive successivities as exactly those which can be decomposed into finitely many intervals, each of which has either finite order type or order type among \(\{\omega,\omega^*,\omega +\omega^*\}\cup \{k\cdot \eta:\) \(1\leq k<\omega \}\). Here, \(k\cdot \eta\) is the order type of the set obtained by replacing each point of the rationals by a block of k elements. This work generalizes a result of \textit{J. B. Remmel} [Proc. Am. Math. Soc. 83, 387-391 (1981; Zbl 0493.03022)] which characterizes recursively categorical linear orderings as exactly those which can be decomposed into finitely many intervals, each of which has finite order type or order type of the rationals. The main technical tool used in the paper under review is a theorem proved by a priority argument which gives a sufficient condition for a relation R recursive on a recursive structure M (the universe of M can be taken to be \({\mathbb{N}})\) for a finite relational language to be not intrinsically r.e. on M: If there exists a recursive function \(f:{\mathbb{N}}^ 2\to {\mathbb{N}}\) such that for every integer m there exists a tuple \(\vec a\) in R for which there exist infinitely many integers s with embeddings \(\Phi\) :M\(| \{0,...,s\}\to M| \{0,...,f(m,s)\}\) which are the identity on \(M| \{0,...,m\}\) but for which \(\Phi\) (\(\vec a)\) does not belong to R, then R is not intrinsically r.e.