Recursive linear orders with recursive successivities (Q1062051): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q455764 |
||
Property / reviewed by | |||
Property / reviewed by: Peter Clote / rank | |||
Revision as of 02:33, 15 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Recursive linear orders with recursive successivities |
scientific article |
Statements
Recursive linear orders with recursive successivities (English)
0 references
1984
0 references
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.
0 references
intrinsically recursively enumerable
0 references
recursive relation
0 references
recursive linear ordering
0 references
order type
0 references