Quasi-simple relations in copies of a given recursive structure
type: Item
instance of: scholarly article
title: Quasi-simple relations in copies of a given recursive structure
zbMATH Open document ID: 0883.03030
DOI: 10.1016/S0168-0072(97)00010-9
author: C. J. Ash
author: J. F. Knight
author: Jeffrey Remmel
published in: Annals of Pure and Applied Logic
publication date: 1997-10-14T00:00:00Z
review text: Let \(\mathcal A\) be a recursive structure for a language \(L\) and \(R\) be a relation on \(\mathcal A\). The authors continue the study of the problem of which algorithmic properties can images of \(R\) in isomorphic recursive copies of \(\mathcal A\) have (see the brief survey on this problem in the present paper). They define the notion of quasi-simplicity for a relation and give a sufficient condition for \(R\) to have a quasi-simple isomorphic copy in a recursive copy of \(\mathcal A\). It is interesting that they prove, among other corollaries, Dekker's result on the existence of a simple set in any nonzero r.e. degree.
Mathematics Subject Classification ID: 03D45
Mathematics Subject Classification ID: 03C57
zbMATH DE Number: 1054201
zbMATH Keywords: quasi-simple relations
zbMATH Keywords: recursive structure
zbMATH Keywords: simple set
reviewed by: Andrei S. Morozov
MaRDI profile type: Publication
cites work: Ramified systems
cites work: Q3919698
cites work: A Theorem on Hypersimple Sets
cites work: Automorphisms of supermaximal subspaces
cites work: Automorphisms of substructure lattices in recursive algebra
cites work: Some effects of Ash-Nerode and other decidability conditions on degree spectra
cites work: Recursive properties of relations on models
cites work: Recursive isomorphism types of recursive Boolean algebras
full work available at URL: s0168-0072(97)00010-9
OpenAlex ID: W2091435900
description: scientific article; zbMATH DE number 1054201