Automatic models of first order theories

作者：Semukhin Pavel^*; Stephan Frank

来源：Annals of Pure and Applied Logic, 2013, 164(9): 837-854.

DOI：10.1016/j.apal.2013.03.001

• Automatic structures
• Model theory

Khoussainov and Nerode (2008) [14] posed various open questions on model-theoretic properties of automatic structures. In this work we answer some of these questions by showing the following results: (1) There is an uncountably categorical but not countably categorical theory for which only the prime model is automatic; (2) There are complete theories with exactly 3, 4, 5, . . . countable models, respectively, and every countable model is automatic; (3) There is a complete theory for which exactly 2 models have an automatic presentation; (4) If LOGSPACE = P then there is an uncountably categorical but not countably categorical theory for which the prime model does not have an automatic presentation but all the other countable models are automatic: (5) There is a complete theory with countably many countable models for which the saturated model has an automatic presentation but the prime model does not have one.

• 出版日期2013-9