This article is cited in 5 papers

Research papers

Index sets of prime model

E. N. Pavlovskii

Novosibirsk State University, Mechanics and Mathematics Department

Abstract: We prove that for every nontrivial language $\sigma$, the index set of the class of $d$-decidable prime computable models of $\sigma$ is $\Sigma_3^{0,d}\setminus\Sigma_3^{0,d}$-complete and that the index set of all prime computable models of $\sigma$ is $\Pi_{\omega+2}^0$-complete.

Keywords: prime model, computable model, index sets, model-theoretic constructions, hyperarithmetic hierarchy.

UDC: 517.1, 519.5

MSC: 03C50, 03C52, 03C57, 03D35

Received February 14, 2008, published May 5, 2008

Bibliographic databases:

•