Complexity estimates for theories of some classes of prime models

Mikhail Peretyat'kin

doi:10.70474/wy2xaj39

Авторы

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

DOI:

https://doi.org/10.70474/wy2xaj39

Ключевые слова:

Оценки алгоритмической сложности, семантический класс моделей, простая модель, модель с алгебраическими элементами, модель с формульно определимыми элементами

Аннотация

Исследуются вопросы алгоритмической характеризации в подклассах класса простых моделей конечной богатой сигнатуры. Рассматриваются модели с алгебраическими элементами и модели с формульно определимыми элементами. Формулируются условия существования сильных конструктивизаций моделей разных алгоритмических размерностей в этих классах. Приводятся оценки алгоритмической сложности элементарных теорий некоторых подклассов класса простых сильно конструктивизируемых моделей.

Скачивания

Данные по скачиваниям пока не доступны.

Библиографические ссылки

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.