×

Decidable expansions of structures. (Russian) Zbl 0665.03004

Let \(M=(A,S)\) be a countable first-order structure, and \(M_ V\) denote the expansion of M by adding a new relation V. A condition on M is given such that under this condition there exists a relation V such that V is not definable in M and the theory of \(M_ V\) is reducible to the theory of M. This result implies that for decidable weak monadic theories there exist no maximal structures, i.e. for any structure M with decidable weak monadic theory there exists a proper expansion of M with decidable weak monadic theory. Investigation of existence of maximal structues was begun in the sixties by C. C. Elgot and M. O. Rabin.
Reviewer: M.K.Valiev

MSC:

03B25 Decidability of theories and sets of sentences
03C07 Basic properties of first-order languages and structures
PDF BibTeX XML Cite