We study the primitive recursive content of various closure results in algebra and model theory, including the algebraic, the real, and the differential closure theorems. In the case of ordered fields and their real closures, our result settles a question recently raised by Selivanova and Selivanov.
P.E.Alaev, Existence and uniqueness of structures computable in polynomial time, Algebra and Logic55(1) (2016), 72–76. doi:10.1007/s10469-016-9377-6.
2.
P.E.Alaev, Categoricity for primitively recursive and polynomial Boolean algebras, Algebra Logika57(4) (2018), 389–426. doi:10.1007/s10469-018-9498-1.
3.
P.E.Alaev, Finitely generated structures computable in polynomial time, Sib. Math. J.63(5) (2022), 801–818. doi:10.1134/S0037446622050019.
4.
P.E.Alaev and V.L.Selivanov, Fields of algebraic numbers computable in polynomial time. II, Algebra Logic60(6) (2021), 349–359. doi:10.1007/s10469-022-09661-3.
5.
P.E.Alaev and V.L.Selivanov, Searching for applicable versions of computable structures, in: Connecting with Computability, Lecture Notes in Comput. Sci., Vol. 12813, Springer, Cham, 2021, pp. 1–11.
6.
C.Ash and J.Knight, Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, Vol. 144, North-Holland Publishing Co., Amsterdam, 2000.
7.
N.Bazhenov, R.Downey, I.Kalimullin and A.Melnikov, Foundations of online structure theory, Bull. Symb. Log.25(2) (2019), 141–181. doi:10.1017/bsl.2019.20.
8.
N.Bazhenov, M.Fiori-Carones, L.Liu and A.Melnikov, Primitive recursive reverse mathematics, Preprint.
9.
N.Bazhenov, M.Harrison-Trainor, I.Kalimullin, A.Melnikov and K.Meng Ng, Automatic and polynomial-time algebraic structures, J. Symb. Log.84(4) (2019), 1630–1669. doi:10.1017/jsl.2019.26.
10.
N.Bazhenov, I.Kalimullin, A.Melnikov and K.Meng Ng, Online presentations of finitely generated structures, Theoret. Comput. Sci.844 (2020), 195–216. doi:10.1016/j.tcs.2020.08.021.
L.Blum, Generalized algebraic structures: A model theoretic approach, PhD thesis, Massachussetts Institute of Technology, Cambridge, MA, 1968.
13.
D.A.Cenzer and J.B.Remmel, Polynomial-time versus recursive models, Ann. Pure Appl. Logic54(1) (1991), 17–58. doi:10.1016/0168-0072(91)90008-A.
14.
D.A.Cenzer and J.B.Remmel, Polynomial-time Abelian groups, Ann. Pure Appl. Logic56(1–3) (1992), 313–363. doi:10.1016/0168-0072(92)90076-C.
15.
A.L.Chistov and D.Y.Grigor’ev, Complexity of quantifier elimination in the theory of algebraically closed fields, in: Mathematical Foundations of Computer Science, 1984, Prague, 1984, Lecture Notes in Comput. Sci., Vol. 176, Springer, Berlin, 1984, pp. 17–31. doi:10.1007/BFb0030287.
16.
J.H.Davenport and J.Heintz, Real quantifier elimination is doubly exponential, J. Symbolic Comput.5(1–2) (1988), 29–35. doi:10.1016/S0747-7171(88)80004-X.
M.V.Dorzhieva, A.A.Issakhov, B.S.Kalmurzayev, R.A.Kornev and M.V.Kotov, Punctual dimension of algebraic structures in certain classes, Lobachevskii J. Math.42(4) (2021), 716–725. doi:10.1134/S1995080221040089.
19.
R.Downey, N.Greenberg, A.Melnikov, K.Meng Ng and D.Turetsky, Punctual categoricity and universality, J. Symb. Log.85(4) (2020), 1427–1466. doi:10.1017/jsl.2020.51.
20.
R.Downey, M.Harrison-Trainor, I.Kalimullin, A.Melnikov and D.Turetsky, Graphs are not universal for online computability, J. Comput. System Sci.112 (2020), 1–12. doi:10.1016/j.jcss.2020.02.004.
21.
R.Downey, A.Melnikov and K.Meng Ng, Foundations of online structure theory II: The operator approach, Log. Methods Comput. Sci.17(3) (2021), 6.
22.
Y.Ershov and S.Goncharov, Constructive Models. Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000.
23.
Y.L.Ershov, Numbered fields, in: Methodology and Philosophy of Science III, B.Van Rootselaar and J.F.Staal, eds, Studies in Logic and the Foundations of Mathematics, Vol. 52, North-Holland Publishing Co., Amsterdam, 1968, pp. 31–34.
24.
J.Fels Ritt, Differential Algebra, American Mathematical Society Colloquium Publications, Vol. XXXIII, American Mathematical Society, New York, NY, 1950.
25.
S.Goncharov, Countable Boolean Algebras and Decidability. Siberian School of Algebra and Logic, Consultants Bureau, New York, 1997.
26.
S.S.Goncharov and A.T.Nurtazin, Constructive models of complete decidable theories, Algebra i Logika12(125–142) (1973), 243.
27.
N.Greenberg, M.Harrison-Trainor, A.Melnikov and D.Turetsky, Non-density in punctual computability, Ann. Pure Appl. Logic172(9) (2021), 102985. doi:10.1016/j.apal.2021.102985.
28.
D.Y.Grigor’ev, Complexity of quantifier elimination in the theory of ordinary differential equations, in: EUROCAL ’87, Leipzig, 1987, Lecture Notes in Comput. Sci., Vol. 378, Springer, Berlin, 1989, pp. 11–25. doi:10.1007/3-540-51517-8_81.
29.
V.S.Harizanov, Pure computable model theory, in: Handbook of Recursive Mathematics, Stud. Logic Found. Math., Vol. 1, North-Holland, Amsterdam, 1998, pp. 3–114.
30.
L.Harrington, Recursively presentable prime models, J. Symbolic Logic39 (1974), 305–309. doi:10.2307/2272643.
31.
M.Harrison-Trainor, A.Melnikov and A.Montalbán, Independence in computable algebra, J. Algebra443 (2015), 441–468. doi:10.1016/j.jalgebra.2015.06.004.
32.
M.Harrison-Trainor, A.G.Melnikov and R.Miller, On computable field embeddings and difference closed fields, Canadian Journal of Mathematics69(6) (2017), 1338–1363. doi:10.4153/CJM-2016-044-7.
33.
I.Kalimullin, A.Melnikov and K.Meng Ng, Algebraic structures computable without delay, Theoret. Comput. Sci.674 (2017), 73–98. doi:10.1016/j.tcs.2017.01.029.
34.
I.Kalimullin, A.Melnikov and A.Montalban, Punctual definability on structures, Ann. Pure Appl. Logic172(8) (2021), 102987. doi:10.1016/j.apal.2021.102987.
35.
I.S.Kalimullin and R.Miller, Primitive recursive fields and categoricity, Algebra and Logic58(1) (2019), 95–99. doi:10.1007/s10469-019-09527-1.
36.
I.Kaplansky, An Introduction to Differential Algebra, Publ. Inst. Math. Univ. Nancago, Vol. 5, Hermann, Paris, 1957.
37.
E.W.Madison, A note on computable real fields, The Journal of Symbolic Logic35(2) (1970), 239–241. doi:10.2307/2270515.
38.
A.Mal’cev, Constructive algebras. I, Uspehi Mat. Nauk16(3) (1961), 3–60.
39.
D.Marker, Model theory of differential fields, in: Model Theory, Algebra, and Geometry, Math. Sci. Res. Inst. Publ., Vol. 39, Cambridge Univ. Press, Cambridge, 2000, pp. 53–63.
40.
D.Marker, Model Theory: An Introduction, Graduate Texts in Mathematics, Springer, 2002.
41.
D.Marker and R.Miller, Turing degree spectra of differentially closed fields, J. Symb. Log.82(1) (2017), 1–25. doi:10.1017/jsl.2016.73.
42.
A.Melnikov and K.Meng Ng, A structure of punctual dimension two, Proc. Amer. Math. Soc.148(7) (2020), 3113–3128. doi:10.1090/proc/15020.
43.
A.Montalbán, Computable Structure Theory – Within the Arithmetic. Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Ithaca, NY, 2021.
44.
M.O.Rabin, Computable algebra, general theory and theory of computable fields, Transactions of the American Mathematical Society95(2) (1960), 341–360. doi:10.1090/S0002-9947-1960-0113807-4.
45.
A.Robinson, On the concept of a differentially closed field, Bull. Res. Council Israel Sect. F8F (1959), 113–128.
46.
G.E.Sacks, Saturated Model Theory, 2nd edn, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2010.
47.
V.L.Selivanov and S.Selivanova, Primitive recursive ordered fields and some applications, in: Computer Algebra in Scientific Computing, CASC 2021, F.Boulier, M.England, T.M.Sadykov and E.V.Vorozhtsov, eds, Lecture Notes in Computer Science, Vol. 12865, Springer, Cham, 2021, pp. 353–369. doi:10.1007/978-3-030-85165-1_20.
48.
S.Simpson, Subsystems of Second Order Arithmetic. Perspectives in Logic, 2nd edn, Cambridge University Press, Cambridge, 2009.
49.
R.Smith, Two theorems on autostability in p-groups, in: Logic Year 1979–80 (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80), Lecture Notes in Math., Vol. 859, Springer, Berlin, 1981, pp. 302–311. doi:10.1007/BFb0090954.
50.
M.V.Zubkov, I.S.Kalimullin, A.G.Mel’nikov and A.N.Frolov, Punctual copies of algebraic structures, Sibirsk. Mat. Zh.60(6) (2019), 1271–1285. doi:10.33048/smzh.2019.60.607.
