Элементарная вложимость относительно сводимости по Вайрауху
https://doi.org/10.26907/2949-3919.2024.4.4-23
Аннотация
Изучается сложность по Вайрауху для проблем нахождения элементарных вложений в контексте классической теории моделей. Доказано, что проблема нахождения элементарного вложения из простой модели M в произвольную модель N (элементарно эквивалентную M) является сильно эквивалентной по Вайрауху известной проблеме lim, которая находит предел последовательности в пространстве Бэра. Установлено, что проблема нахождения элементарного вложения из произвольной модели M в счетно-насыщенную модель N также сильно эквивалентна по Вайрауху проблеме lim.
Ключевые слова
При поддержке: Работа Н.А.Баженова и М.И.Марчук выполнена в рамках государственного задания ИМ СО РАН (проект № FWNF-2022-0011).
Об авторах
Н. А. Баженов
Институт математики им. С.Л.Соболева СО РАН
Россия
Россия
Николай Алексеевич Баженов
пр. Акад. Коптюга, д. 4, г. Новосибирск, 630090
М. И. Марчук
Институт математики им. С.Л.Соболева СО РАН
Россия
Россия
Маргарита Игоревна Марчук
пр. Акад. Коптюга, д. 4, г. Новосибирск, 630090
M. Фьори-Каронес
Институт математики им. С.Л.Соболева СО РАН
Россия
Россия
Марта Фьори-Каронес
пр. Акад. Коптюга, д. 4, г. Новосибирск, 630090
Список литературы
1. S.G.Simpson, Subsystems of second order arithmetic. Second edition. Cambridge Univ. Press, Cambridge, 2009. DOI: https://doi.org/10.1017/CBO9780511581007
2. D.R.Hirschfeldt, Slicing the truth: On the computable and reverse mathematics of combinatorial principles. World Scientific Publishing Co., Hackensack, NJ, 2015. DOI: https://doi.org/10.1142/9208
3. D.R.Hirschfeldt, R.A.Shore, T.A.Slaman, The atomic model theorem and type omitting, Trans. Amer. Math. Soc. 361 (11), 5805–5837 (2009). DOI: https://doi.org/10.1090/S0002-9947-09-04847-8
4. D.R.Belanger, Reverse mathematics of first-order theories with finitely many models, J. Symb. Log. 79 (3), 955–984 (2014). DOI: https://doi.org/10.1017/jsl.2014.32
5. D.R.Belanger, WKL<sub>0</sub> and induction principles in model theory, Ann. Pure Appl. Logic 166 (7–8), 767–799 (2015). DOI: https://doi.org/10.1016/j.apal.2015.04.001
6. P.Cholak, C.McCoy, Effective prime uniqueness, Proc. Amer. Math. Soc. 145 (12), 5363–5379 (2017). DOI: https://doi.org/10.1090/proc/13675
7. D.R.Hirschfeldt, K.Lange, R.A.Shore, Induction, bounding, weak combinatorial principles, and the homogeneous model theorem, Mem. Amer. Math. Soc. 249 (1187), 2017. DOI: https://doi.org/10.1090/memo/1187
8. K.Harris, The reverse mathematics of saturated models, preprint (2006).
9. V.Brattka, Weihrauch complexity and the Hagen school of computable analysis, arXiv:2203.06166 (2022). DOI: https://doi.org/10.48550/arXiv.2203.06166
10. V.Brattka, G.Gherardi, A.Pauly, Weihrauch complexity in computable analysis, in: Handbook of Computability and Complexity in Analysis, Springer, Cham, 367–417 (2021). DOI: https://doi.org/10.1007/978-3-030-59234-9_11
11. Г.Кейслер, Ч.Ч.Чэн, Теория моделей, Мир, М., 1977.
12. F.G.Dorais, D.D.Dzhafarov, J.L.Hirst, J.R.Mileti, P.Shafer, On uniform relationships between combinatorial problems, Trans. Amer. Math. Soc. 368 (2), 1321–1359 (2016). DOI: https://doi.org/10.1090/tran/6465
13. Н.А.Баженов, М.И.Марчук, Степени автоустойчивости относительно сильных конструктивизаций графов, Сиб. матем. журн. 59 (4), 719–735 (2018). DOI: https://doi.org/10.17377/smzh.2018.59.401
14. D.Marker, Model theory: An introduction, Springer, New York, 2002. DOI: https://doi.org/10.1007/b98860
15. W.Hodges, Model theory, Cambridge Univ. Press, Cambridge, 1993. DOI: https://doi.org/10.1017/CBO9780511551574
16. J.G.Rosenstein, Linear orderings, Academic Press, New York, 1982. URL: https://www.sciencedirect.com/bookseries/pure-and-applied-mathematics/vol/98
17. D.Cenzer, V.Harizanov, J.B.Remmel, Σ<sup>0</sup><sub>1</sub> and Π<sup>0</sup><sub>1</sub> equivalence structures, Ann. Pure Appl. Logic 162 (7), 490–503 (2011). DOI: https://doi.org/10.1016/j.apal.2011.01.002
Рецензия
Для цитирования:
Баженов Н.А., Марчук М.И., Фьори-Каронес M. Элементарная вложимость относительно сводимости по Вайрауху. Математика и теоретические компьютерные науки. 2024;2(4):4-23. https://doi.org/10.26907/2949-3919.2024.4.4-23
For citation:
Bazhenov N.A., Marchuk M.I., Fiori-Carones M. Elementary embeddability with respect to Weihrauch reducibility. Mathematics and Theoretical Computer Science. 2024;2(4):4-23. (In Russ.) https://doi.org/10.26907/2949-3919.2024.4.4-23
Просмотров:
68
Послать статью по эл. почте 