Recursive linear orders with recursive successivities
type: Item
instance of: scholarly article
title: Recursive linear orders with recursive successivities
zbMATH Open document ID: 0572.03025
DOI: 10.1016/0168-0072(84)90028-9
author: Michael Moses
published in: Annals of Pure and Applied Logic
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D45
Mathematics Subject Classification ID: 03C57
Mathematics Subject Classification ID: 03C65
zbMATH DE Number: 3912366
zbMATH Keywords: intrinsically recursively enumerable
zbMATH Keywords: recursive relation
zbMATH Keywords: recursive linear ordering
zbMATH Keywords: order type
reviewed by: Peter Clote
MaRDI profile type: Publication
full work available at URL: 0168-0072(84)90028-9
OpenAlex ID: W1992932719
cites work: Q3919698
cites work: Autostability of models
cites work: Some properties of the constructivization of Boolean algebras
cites work: Autostability of models and Abelian groups
cites work: Q3952086
cites work: Effective content of field theory
cites work: Recursive Boolean algebras with recursive atoms
cites work: Recursively Categorical Linear Orderings
cites work: Q3949039
description: scientific article; zbMATH DE number 3912366