Elementary embeddability with respect to Weihrauch reducibility
https://doi.org/10.26907/2949-3919.2024.4.4-23
Abstract
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.
Supporting agencies: 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).
About the Authors
N. A. Bazhenov
Sobolev Institute of Mathematics
Russian Federation
Russian Federation
Nikolay Alekseyevich Bazhenov
4 Acad. Koptyug Ave., Novosibirsk 630090
M. I. Marchuk
Sobolev Institute of Mathematics
Russian Federation
Russian Federation
Margarita Igorevna Marchuk
4 Acad. Koptyug Ave., Novosibirsk 630090
M. Fiori-Carones
Sobolev Institute of Mathematics
Russian Federation
Russian Federation
Marta Fiori-Carones
4 Acad. Koptyug Ave., Novosibirsk 630090
References
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. 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/
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. N.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/S0037446618040018
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
Review
For citations:
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
Views:
71
Email this article 