Complexity estimates for theories of some classes of prime models

Mikhail Peretyat'kin

doi:10.70474/wy2xaj39

Авторлар

Михаил Георгиевич Перетятькин Математика және математикалық модельдеу институты Author https://orcid.org/0000-0001-7067-3014

DOI:

https://doi.org/10.70474/wy2xaj39

Кілт сөздер:

Aлгоритмдік күрделілікті бағалау, модельдердің семантикалық класы, жай модель, алгебралық элементтері бар модель, бірінші ретті анықталатын элементтері бар модель, ақырлы модель

Аңдатпа

Ақырғы бай таңбаның жай модельдер класының ішкі сыныптарында алгоритмдік сипаттау мәселелері зерттеледі. Алгебралық элементтері бар модельдер және бірінші ретті анықталатын элементтері бар модельдер қарастырылады. Осы кластардағы әртүрлі өлшемді модельдердің күшті конструктивтілігінің болуының шарттары тұжырымдалған. Күшті конструктивті модельдер класының кейбір ішкі сыныптарының элементар теорияларының алгоритмдік күрделілігінің бағалары келтірілген.

##plugins.themes.default.displayStats.downloads##

##plugins.themes.default.displayStats.noStats##

Әдебиеттер тізімі

Ehrenfeucht A. An application of games to the completeness problem for formalized theories. Fund. Math. 49:2 (1961), 129–141. DOI: https://doi.org/10.2307/2271711 DOI: https://doi.org/10.4064/fm-49-2-129-141

Goncharov S.S., Ershov Yu.L. Constructive models. New York: Consultants Bureau, XII, 2000.

Goncharov S.S., Nurtazin A.T. Constructive models of complete decidable theories. Algebra and Logika. 12:2 (1973), 67–77. DOI: https://doi.org/10.1007/BF02219289

Harizanov V.S. Pure computable model theory. In: Handbook of Recursive Mathematics, ed. Yu.L. Ershov et al., North-Holland, 1998, Chapter 1, pp. 1–114.

Harrington L. Recursively presented prime models. J. Symbolic Logic. 39:2 (1974), 305–309. DOI: https://doi.org/10.2307/2272643 DOI: https://doi.org/10.2307/2272643

Hodges W. A shorter model theory. Cambridge Univ. Press, Cambridge, 1997.

Janiczak A. A remark concerning decidability of complete theories. J. Symbolic Logic. 15:4 (1950), 277–279. DOI: https://doi.org/10.2307/2268339

Peretyat'kin M.G. Turing Machine computations in finitely axiomatizable theories. Algebra and Logika. 21:4 (1982), 272–295. DOI: https://doi.org/10.1007/BF01980636

Peretyat'kin M.G. Finitely axiomatizable totally transcendental theories. Trudy Inst. Math. SB RAS. 2 (1982), 88–135.

Peretyat'kin M.G. Expressive power of finitely axiomatizable theories. Sib. Adv. Math. 3:2 (1993), 153–197; 3:3 (1993), 123–145; 3:4 (1993), 131–201.

Peretyat'kin M.G. Finitely axiomatizable theories. Plenum, New York, 1997.

Peretyat'kin M.G. On the Tarski-Lindenbaum algebra of the class of all strongly constructivizable prime models. In: Proc. Turing Centenary Conf. CiE 2012, LNCS 7318, Springer, 2012, 589–598. DOI: https://doi.org/10.1007/978-3-642-30870-3_59

Peretyat'kin M.G. The Tarski-Lindenbaum algebra of the class of all strongly constructivizable countable saturated models. In: CiE 2013, LNCS 7921, Springer, 2013, 342–352. DOI: https://doi.org/10.1007/978-3-642-39053-1_41

Peretyat'kin M.G. The Tarski-Lindenbaum algebra of the class of all strongly constructivizable prime models of algorithmic dimension one. Sib. Electron. Math. Rep. 17 (2020), 913–922. DOI: https://doi.org/10.33048/semi.2020.17.067

Peretyat'kin M.G. The Tarski-Lindenbaum algebra of the class of prime models with infinite algorithmic dimensions having ω-stable theories. Sib. Electron. Math. Rep. 21:1 (2024), 277–292.

Peretyat'kin M.G. The Tarski-Lindenbaum algebra of the class of strongly constructivizable models with ω-stable theories. Arch. Math. Logic. 64:1 (2025), 67–78. DOI: https://doi.org/10.1007/s00153-024-00927-4

Peretyat'kin M.G., Selivanov V.L. Universal Boolean algebras with applications to semantic classes of models. In: Computability in Europe, Springer Nature, Switzerland, 2024, 205–217. DOI: https://doi.org/10.1007/978-3-031-64309-5_17

Robinson A. Introduction to model theory and to the metamathematics of algebra. North-Holland, Amsterdam, 1963.

Rogers H.J. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.

Sikorski R. Boolean algebras. 3rd ed. Springer‑Verlag, Berlin‑Heidelberg‑New York, 1969.

Vaught R.L. Denumerable models of complete theories. In: Infinitistic methods, Proc. Symp. on Found. of Math., Warsaw, 2–9 Sept. 1959, Pergamon Press, 1961, 303–321.