The Tarski–Lindenbaum algebra of the class of prime models with infinite algorithmic dimensions having omega-stable theories

M. G. Peretyat'kin

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 277-292

Résumé

We study the class of all prime strongly constructivizable models of infinite algorithmic dimensions having $\omega$-stable theories in a fixed finite rich signature. It is proved that the Tarski-Lindenbaum algebra of this class considered together with a Gödel numbering of the sentences is a Boolean $\Sigma^1_1$-algebra whose computable ultrafilters form a dense subset in the set of all ultrafilters; moreover, this algebra is universal with respect to the class of Boolean $\Sigma^1_1$-algebras. This gives a characterization to the Tarski–Lindenbaum algebra of the class of all prime strongly constructivizable models of infinite algorithmic dimensions having $\omega$-stable theories.

Détail

Keywords: Tarski–Lindenbaum algebra, strongly constructive model, computable isomorphism, semantic class of models, $\omega$-stable theory, prime model.

Bibliographie

[1] S.S. Goncharov, Yu.L. Ershov, Constructive models, Siberian School of Algebra Logic, Consultants Bureau, New York, 2000 | MR | Zbl

[2] S.S. Goncharov, A.T. Nurtazin, “Constructive models of complete decidable theories”, Algebra Logic, 12:2 (1973), 67–77 | DOI | MR | Zbl

[3] W. Hanf, D. Myers, “Boolean sentence algebras: Isomorphism constructions”, J. Symb. Log., 48:2 (1983), 329–338 | DOI | MR | Zbl

[4] V.S. Harizanov, “Pure computable model theory”, Handbook of recursive mathematics, v. 1, Recursive model theory, eds. Ershov, Yu.L. et al., Elsevier, Amsterdam, 1998, 3–114 | MR | Zbl

[5] L. Harrington, “Recursively presented prime models”, J. Symb. Log., 39:2 (1974), 305–309 | DOI | MR | Zbl

[6] W. Hodges, A shorter model theory, Cambridge University Press, Cambridge, 1997 | MR | Zbl

[7] S. Lempp, M.G. Peretyat'kin, R. Solomon, “The Lindenbaum algebra of the theory of the class of all finite models”, J. Math. Log., 2:2 (2002), 145–225 | DOI | MR | Zbl

[8] A.T. Nurtazin, “Strong and weak constructivizations and computable families”, Algebra Logic, 13:3 (1974), 177–184 | DOI | MR | Zbl

[9] M.G. Peretyat'kin, Finitely axiomatizable theories, Consultants Bureau, New York, 1997 | MR | Zbl

[10] M.G. Peretyat'kin, “Finitely axiomatizable theories and Lindenbaum algebras of semantic classes”, Computability theory and its applications. Current trends and open problems, Proceedings of a 1999 AMS-IMS-SIAM joint summer research conference (Boulder, CO, USA, June 13-17, 1999), Contemp. Math., 257, eds. Cholak, Peter A. et al., 2000, 221–239 | DOI | MR | Zbl

[11] M.G. Peretyat'kin, “On the Tarski-Lindenbaum algebra of the class of all strongly constructivizable prime models”, How the world computes, CiE2012, Proceedings of the Turing Centenary Conference, Lecture Notes in Computer Science, 7318, eds. Cooper, S. Barry et al., Springer, Berlin, 2012, 589–598 | DOI | MR | Zbl

[12] M.G. Peretyat'kin, “The Tarski-Lindenbaum algebra of the class of all strongly constructivizable countable saturated models”, The nature of computation. Logic, algorithms, applications, Proceedings CiE 2013, Lecture Notes in Computer Science, 7921, eds. Bonizzoni, Paola et al., Springer, Berlin, 2013, 342–352 | DOI | MR | Zbl

[13] M.G. Peretyat'kin, “The Tarski-Lindenbaum algebra of the class of all prime strongly constructivizable models of algorithmic dimension one”, Sib. Èlektron. Mat. Izv., 17 (2020), 913–922 | DOI | MR | Zbl

[14] H.J. Rogers, Theory of recursive functions and effective computability, McGraw-Hill Publishing Company, New York, 1967 | MR | Zbl

[15] R. Sikorski, Boolean algebras, 3rd edition, Springer-Verlag, New York, 1969 | MR

[16] R.L. Vaught, “Denumerable models of complete theories”, Infinitistic methods, Proc. Symp. Foundations Math. (Warsaw, 1959), Pergamon Press, 1961, 303–321 | MR | Zbl