Complexity estimates for theories of some classes of prime models
DOI:
https://doi.org/10.70474/wy2xaj39Keywords:
Algorithmic complexity estimates, semantic class of models, prime model, model with algebraic elements, model with first-order definable elementsAbstract
The problems of algorithmic characterization in subclasses of the class of prime models of a finite rich signature are studied. Models with algebraic elements and models with first-order definable elements are considered. Conditions for the existence of strong constructivizations of models of different dimensions in these classes are formulated. Estimates of the algorithmic complexity of elementary theories of some subclasses of the class of prime strongly constructivizable models are given.
Downloads
References
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.
Additional Files
Published
Issue
Section
License
Copyright (c) 2025 Kazakh Mathematical Journal
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
One can find the license terms "CC Attribution-NonCommercial-NoDerivatives 4.0" here.
