Quasi-simple relations in copies of a given recursive structure
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.
scientific article; zbMATH DE number 1054201