On autostability of almost prime models relative to strong constructivizations.

*(English. Russian original)*Zbl 1219.03038
Russ. Math. Surv. 65, No. 5, 901-935 (2010); translation from Usp. Mat. Nauk 65, No. 5, 107-142 (2010).

A model \(M\) together with a numbering \(\nu:\omega\to\omega\) (i.e., a pair \(\langle M,\nu\rangle\)) is called a constructive (strongly constructive) model if the set \(\{\varphi(\nu\bar m) \mid \varphi\) is a quantifier-free formula and \(M\models\varphi(\nu\bar m)\}\) (\(\{\varphi(\nu\bar m) \mid \varphi\) is any formula and \(M\models\varphi(\nu\bar m)\}\)) is computable. Here \(\nu\) is called a (strong) constructivization of \(M\). If a model possesses a (strong) constructivization then it is called (strongly) constructivizable. Two computable models \(\langle M_0,\nu_0\rangle\) and \(\langle M_1,\nu_1\rangle\) are called computably isomorphic if there exists an isomorphism \(\theta:M_0\to M_1\) from \(M_0\) onto \(M_1\) such that, for some computable function \(f\), \(\nu_1f=\theta\nu_0\) holds. A model \(M\) is called autostable (autostable relative to strong constructivizations) if it has at least one (strong) constructivization and, for any of its (strong) constructivizations \(\nu_0\) and \(\nu_1\), \(\langle M,\nu_0\rangle\) and \(\langle M,\nu_1\rangle\) are computably isomorphic.

The author gives a survey of the results on autostability relative to strong constructivizations and proves a series of new results. The basic results of this paper are the following: 1. There exists a countably categorical theory with quantifier elimination having a countable model that is not autostable and is not autostable relative to strong constructivizations. Moreover, its class of constructivizations up to recursive isomorphism is not computable. 2. There exists a decidable Ehrenfeucht theory whose prime model is autostable and is autostable relative to strong constructivizations having a strongly constructivizable model which is prime in some finite enrichment by constants but is not autostable. 3. If a theory \(T\) has a strong constructivizable prime model which is not autostable relative to strong constructivizations and, in addition, has a model which is autostable relative to strong constructivizations, then \(T\) is not \(\omega\)-stable. It follows that a) there is no uncountably categorical decidable theory whose prime model is not autostable relative to strong constructivizations having another model autostable relative to strong constructivizations, and b) if some model of an uncountably categorical theory is autostable relative to strong constructivizations, then its prime model is autostable relative to strong constructivizations. 4. There exists a complete decidable theory with countably many countable models whose prime model is strongly constructivizable but is not autostable relative to strong constructivizations having a strongly constructivizable model which is prime in a finite enrichment by constants and is autostable relative to strong constructivizations. 5. There exists a decidable uncountably categorical theory all of whose countable models are strongly constructivizable and are not autostable relative to strong constructivizations. 6. There exists an uncountably categorical theory whose prime model is autostable relative to strong constructivizations and all other models fail to have this property.

The author gives a survey of the results on autostability relative to strong constructivizations and proves a series of new results. The basic results of this paper are the following: 1. There exists a countably categorical theory with quantifier elimination having a countable model that is not autostable and is not autostable relative to strong constructivizations. Moreover, its class of constructivizations up to recursive isomorphism is not computable. 2. There exists a decidable Ehrenfeucht theory whose prime model is autostable and is autostable relative to strong constructivizations having a strongly constructivizable model which is prime in some finite enrichment by constants but is not autostable. 3. If a theory \(T\) has a strong constructivizable prime model which is not autostable relative to strong constructivizations and, in addition, has a model which is autostable relative to strong constructivizations, then \(T\) is not \(\omega\)-stable. It follows that a) there is no uncountably categorical decidable theory whose prime model is not autostable relative to strong constructivizations having another model autostable relative to strong constructivizations, and b) if some model of an uncountably categorical theory is autostable relative to strong constructivizations, then its prime model is autostable relative to strong constructivizations. 4. There exists a complete decidable theory with countably many countable models whose prime model is strongly constructivizable but is not autostable relative to strong constructivizations having a strongly constructivizable model which is prime in a finite enrichment by constants and is autostable relative to strong constructivizations. 5. There exists a decidable uncountably categorical theory all of whose countable models are strongly constructivizable and are not autostable relative to strong constructivizations. 6. There exists an uncountably categorical theory whose prime model is autostable relative to strong constructivizations and all other models fail to have this property.

Reviewer: Andrei S. Morozov (Novosibirsk)

##### MSC:

03C57 | Computable structure theory, computable model theory |

03C35 | Categoricity and completeness of theories |

03D45 | Theory of numerations, effectively presented structures |