RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2008 Volume 49, Number 3, Pages 635–649 (Mi smj1867)

This article is cited in 12 papers

Estimation of the algorithmic complexity of classes of computable models

E. N. Pavlovskii

Novosibirsk State University, Mechanics and Mathematics Department

Abstract: We estimate the algorithmic complexity of the index set of some natural classes of computable models: finite computable models ($\Sigma_2^0$-complete), computable models with $\omega$-categorical theories ($\Delta_\omega^0$-complex $\Pi_{\omega+2}^0$-set), prime models ($\Delta_\omega^0$-complex $\Pi_{\omega+2}^0$-set), models with $\omega_1$-categorical theories ($\Delta_\omega^0$-complex $\Sigma_{\omega+1}^0$-set). We obtain a universal lower bound for the model-theoretic properties preserved by Marker's extensions ($\Delta_\omega^0$).

Keywords: computable model, index set.

UDC: 510.67+510.5+510.635

Received: 14.06.2007
Revised: 04.04.2008


 English version:
Siberian Mathematical Journal, 2008, 49:3, 512–523

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024