×

zbMATH — the first resource for mathematics

Simple and immune relations on countable structures. (English) Zbl 1024.03034
Summary: Let \(\mathcal A\) be a computable structure and let \(R\) be a new relation on its domain. We establish a necessary and sufficient condition for the existence of a copy \(\mathcal B\) of \(\mathcal A\) in which the image of \(R\) (\(\neg R\), resp.) is simple (immune, resp.) relative to \(\mathcal B\). We also establish, under certain effectiveness conditions on \(\mathcal A\) and \(R\), a necessary and sufficient condition for the existence of a computable copy \(\mathcal B\) of \(\mathcal A\) in which the image of \(R\) (\(\neg R\), resp.) is simple (immune, resp.).

MSC:
03C57 Computable structure theory, computable model theory
PDF BibTeX XML Cite
Full Text: DOI