This article is cited in 31 papers

Complexity of Categorical Theories with Computable Models

S. S. Goncharov^a, B. Khoussainov<sup>b

a</sup> Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
^b University of Auckland

Abstract: M. Lerman and J. Scmerl specified some sufficient conditions for computable models of countably categorical arithmetical theories to exist. More precisely, it was shown that if $T$ is a countably categorical arithmetical theory, and the set of its sentences beginning with an existential quantifier and having at most $n+1$ alternations of quantifiers is $\Sigma_{n+1}^0$ for any $n$, then $T$ has a computable model. J. Night improved this result by allowing certain uniformity and omitting the requirement that $T$ is arithmetical. However, all of the known examples of theories of $\aleph_0$-categorical computable models had low level of algorithmic complexity, and whether there are theories that would satisfy the above conditions for sufficiently large $n$ was unknown. This paper will include such examples.

Keywords: computable model, countably categorical theory.

UDC: 510.53+510.67

Received: 08.09.2002
Revised: 16.09.2003

 English version: Algebra and Logic, 2004, 43:6, 365–373

Bibliographic databases:

• 
• 
•