matatecsМатематика и теоретические компьютерные наукиMathematics and Theoretical Computer Science2949-3919Казанский (Приволжский) федеральный университет10.26907/2949-3919.2024.4.4-23matatecs-60Research ArticleСТАТЬИЭлементарная вложимость относительно сводимости по ВайраухуElementary embeddability with respect to Weihrauch reducibilityБаженовН. А.BazhenovN. A.

Николай Алексеевич Баженов

пр. Акад. Коптюга, д. 4, г. Новосибирск, 630090

Nikolay Alekseyevich Bazhenov

4 Acad. Koptyug Ave., Novosibirsk 630090

bazhenov@math.nsc.ruМарчукМ. И.MarchukM. I.

Маргарита Игоревна Марчук

пр. Акад. Коптюга, д. 4, г. Новосибирск, 630090

Margarita Igorevna Marchuk

4 Acad. Koptyug Ave., Novosibirsk 630090

margaretmarchuk@gmail.comФьори-КаронесM.Fiori-CaronesM.

Марта Фьори-Каронес

пр. Акад. Коптюга, д. 4, г. Новосибирск, 630090

Marta Fiori-Carones

4 Acad. Koptyug Ave., Novosibirsk 630090

marta.fioricarones@outlook.itИнститут математики им. С.Л.Соболева СО РАНРоссияSobolev Institute of MathematicsRussian Federation20242401202524423Copyright © Баженов Н.А., Марчук М.И., Фьори-Каронес M., 20252025Баженов Н.А., Марчук М.И., Фьори-Каронес M.Bazhenov N.A., Marchuk M.I., Fiori-Carones M.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://matatecs.elpub.ru/jour/article/view/60

Изучается сложность по Вайрауху для проблем нахождения элементарных вложений в контексте классической теории моделей. Доказано, что проблема нахождения элементарного вложения из простой модели M в произвольную модель N (элементарно эквивалентную M) является сильно эквивалентной по Вайрауху известной проблеме lim, которая находит предел последовательности в пространстве Бэра. Установлено, что проблема нахождения элементарного вложения из произвольной модели M в счетно-насыщенную модель N также сильно эквивалентна по Вайрауху проблеме lim.

We study the Weihrauch complexity for problems of finding an elementary embedding (within the framework of the classical model theory). We prove that the problem of finding an elementary embedding from a prime model M into an arbitrary model N (which is elementarily equivalent to M) is strongly Weihrauch equivalent to the familiar problem lim (i.e., the problem of finding the limit of a sequence in Baire space). We show that the problem of finding an elementary embedding from an arbitrary model M into a countable saturated model N is also strongly Weihrauch equivalent to lim.

сводимость по Вайраухуэлементарное вложениепростая модельсчетно-насыщенная модельWeihrauch reducibilityelementary embeddingprime modelcountable saturated modelРабота Н.А.Баженова и М.И.Марчук выполнена в рамках государственного задания ИМ СО РАН (проект № FWNF-2022-0011).The work of N.A.Bazhenov and M.I.Marchuk was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project no. FWNF-2022-0011).ReferencesS.G.Simpson, Subsystems of second order arithmetic. Second edition. Cambridge Univ. Press, Cambridge, 2009. DOI: https://doi.org/10.1017/CBO9780511581007S.G.Simpson, Subsystems of second order arithmetic. Second edition. Cambridge Univ. Press, Cambridge, 2009. DOI: https://doi.org/10.1017/CBO9780511581007D.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/9208D.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/9208D.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-8D.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-8D.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.32D.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.32D.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.001D.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.001P.Cholak, C.McCoy, Effective prime uniqueness, Proc. Amer. Math. Soc. 145 (12), 5363–5379 (2017). DOI: https://doi.org/10.1090/proc/13675P.Cholak, C.McCoy, Effective prime uniqueness, Proc. Amer. Math. Soc. 145 (12), 5363– 5379 (2017). DOI: https://doi.org/10.1090/proc/13675D.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/1187D.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/1187K.Harris, The reverse mathematics of saturated models, preprint (2006).K.Harris, The reverse mathematics of saturated models, preprint (2006).V.Brattka, Weihrauch complexity and the Hagen school of computable analysis, arXiv:2203.06166 (2022). DOI: https://doi.org/10.48550/arXiv.2203.06166V.Brattka, Weihrauch complexity and the Hagen school of computable analysis, arXiv:2203.06166 (2022). DOI: https://doi.org/10.48550/arXiv.2203.06166V.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_11V.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Г.Кейслер, Ч.Ч.Чэн, Теория моделей, Мир, М., 1977.C.C.Chang, H.J.Keisler, Model theory, North-Holland, Amsterdam, 1973. URL: https://www.sciencedirect.com/bookseries/studies-in-logic-and-the-foundations-of-mathematics/vol/73/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/6465F.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Н.А.Баженов, М.И.Марчук, Степени автоустойчивости относительно сильных конструктивизаций графов, Сиб. матем. журн. 59 (4), 719–735 (2018). DOI: https://doi.org/10.17377/smzh.2018.59.401N.A.Bazhenov, M.I.Marchuk, Degrees of autostability relative to strong constructivi- zations of graphs, Siberian Math. J. 59 (4), 565–577 (2018). DOI: https://doi.org/10.1134/S0037446618040018D.Marker, Model theory: An introduction, Springer, New York, 2002. DOI: https://doi.org/10.1007/b98860D.Marker, Model theory: An introduction, Springer, New York, 2002. DOI: https://doi.org/10.1007/b98860W.Hodges, Model theory, Cambridge Univ. Press, Cambridge, 1993. DOI: https://doi.org/10.1017/CBO9780511551574W.Hodges, Model theory, Cambridge Univ. Press, Cambridge, 1993. DOI: https://doi.org/10.1017/CBO9780511551574J.G.Rosenstein, Linear orderings, Academic Press, New York, 1982. URL: https://www.sciencedirect.com/bookseries/pure-and-applied-mathematics/vol/98J.G.Rosenstein, Linear orderings, Academic Press, New York, 1982. URL: https://www.sciencedirect.com/bookseries/pure-and-applied-mathematics/vol/98D.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.002D.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

The authors declare that there are no conflicts of interest present.