On autostability of almost prime models relative to strong constructivizations. (English. Russian original) Zbl 1219.03038

Goncharov, S. S.

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.

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

Keywords:

computable model; constructive model; strongly constructive model; autostability; prime model; almost prime model; Ehrenfeucht theory; decidable theory; decidable model