# 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
##### Keywords:
simplicity; computable structure; effectiveness; computable copy
Full Text: