A structure of punctual dimension two

Melnikov, Alexander; Ng, Keng Meng

doi:10.1090/proc/15020

A structure of punctual dimension two
HTML articles powered by AMS MathViewer

by Alexander Melnikov and Keng Meng Ng

Proc. Amer. Math. Soc. 148 (2020), 3113-3128

DOI: https://doi.org/10.1090/proc/15020

Published electronically: April 14, 2020

PDF | Request permission

Abstract:

This paper contributes to the general program which aims to eliminate an unbounded search from proofs and procedures in computable structure theory. A countable structure in a finite language is punctual if its domain is $\omega$ and its operations and relations are primitive recursive. A function $f$ is punctual if both $f$ and $f^{-1}$ are primitive recursive. We prove that there exists a countable rigid algebraic structure which has exactly two punctual presentations, up to punctual isomorphism.

References

C. J. 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. MR 1767842
P. E. Alaev, Structures computable in polynomial time. I, Algebra Logika 55 (2016), no. 6, 647–669 (Russian); English transl., Algebra Logic 55 (2016), no. 6, 421–435. MR 3722412, DOI 10.1007/s10469-017-9416-y
P. E. Alaev, Structures computable in polynomial time. II, Algebra Logika 56 (2017), no. 6, 651–670 (Russian); English transl., Algebra Logic 56 (2017), no. 6, 429–442. MR 3786915, DOI 10.1007/s10469-018-9465-x
Pavel Alaev and Victor Selivanov, Polynomial-time presentations of algebraic number fields, Sailing routes in the world of computation, Lecture Notes in Comput. Sci., vol. 10936, Springer, Cham, 2018, pp. 20–29. MR 3840148, DOI 10.1007/978-3-319-94418-0_{2}
Nikolay Bazhenov, Rod Downey, Iskander Kalimullin, and Alexander Melnikov, Foundations of online structure theory, Bull. Symb. Log. 25 (2019), no. 2, 141–181. MR 3984971, DOI 10.1017/bsl.2019.20
Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel, and Zia Uddin, Space complexity of abelian groups, Arch. Math. Logic 48 (2009), no. 1, 115–140. MR 2480938, DOI 10.1007/s00153-008-0113-3
Douglas Cenzer and Jeffrey B. Remmel, Polynomial-time versus computable Boolean algebras, Recursion theory and complexity (Kazan, 1997) De Gruyter Ser. Log. Appl., vol. 2, de Gruyter, Berlin, 1999, pp. 15–53. MR 1724930
Douglas Cenzer and Jeffrey Remmel, Polynomial-time versus recursive models, Ann. Pure Appl. Logic 54 (1991), no. 1, 17–58. MR 1130218, DOI 10.1016/0168-0072(91)90008-A
Douglas Cenzer and Jeffrey Remmel, Polynomial-time abelian groups, Ann. Pure Appl. Logic 56 (1992), no. 1-3, 313–363. MR 1167697, DOI 10.1016/0168-0072(92)90076-C
D. Cenzer and J. B. Remmel, Complexity-theoretic model theory and algebra, Handbook of recursive mathematics, Vol. 1, Stud. Logic Found. Math., vol. 138, North-Holland, Amsterdam, 1998, pp. 381–513. MR 1673574, DOI 10.1016/S0049-237X(98)80011-6
Barbara F. Csima and Jonathan Stephenson, Finite computable dimension and degrees of categoricity, Ann. Pure Appl. Logic 170 (2019), no. 1, 58–94. MR 3870041, DOI 10.1016/j.apal.2018.08.012
Rod Downey, Matthew Harrison-Trainor, Iskander Kalimullin, Alexander Melnikov, and Daniel Turetsy, Graphs are not universal for online computability, Preprint, 2018.
David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson, and William P. Thurston, Word processing in groups, Jones and Bartlett Publishers, Boston, MA, 1992. MR 1161694, DOI 10.1201/9781439865699
Yuri L. Ershov and Sergei S. Goncharov, Constructive models, Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000. MR 1749622, DOI 10.1007/978-1-4615-4305-3
Ekaterina B. Fokina, Valentina Harizanov, and Alexander Melnikov, Computable model theory, Turing’s legacy: developments from Turing’s ideas in logic, Lect. Notes Log., vol. 42, Assoc. Symbol. Logic, La Jolla, CA, 2014, pp. 124–194. MR 3497661
S. S. Gončarov, The problem of the number of nonautoequivalent constructivizations, Algebra i Logika 19 (1980), no. 6, 621–639, 745 (Russian). MR 622606
S. S. Gončarov, Groups with a finite number of constructivizations, Dokl. Akad. Nauk SSSR 256 (1981), no. 2, 269–272 (Russian). MR 600943
Serge Grigorieff, Every recursive linear ordering has a copy in $\textrm {DTIME}$-$\textrm {SPACE}(n,\log (n))$, J. Symbolic Logic 55 (1990), no. 1, 260–276. MR 1043556, DOI 10.2307/2274966
Denis Roman Hirschfeldt, Degree spectra of relations on computable structures, ProQuest LLC, Ann Arbor, MI, 1999. Thesis (Ph.D.)–Cornell University. MR 2699435
Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore, and Arkadii M. Slinko, Degree spectra and computable dimensions in algebraic structures, Ann. Pure Appl. Logic 115 (2002), no. 1-3, 71–113. MR 1897023, DOI 10.1016/S0168-0072(01)00087-2
Matthew Harrison-Trainor, Alexander Melnikov, Russell Miller, and Antonio Montalbán, Computable functors and effective interpretability, J. Symb. Log. 82 (2017), no. 1, 77–97. MR 3625736, DOI 10.1017/jsl.2016.12
Henry A. Kierstead, An effective version of Dilworth’s theorem, Trans. Amer. Math. Soc. 268 (1981), no. 1, 63–77. MR 628446, DOI 10.1090/S0002-9947-1981-0628446-X
H. A. Kierstead, On-line coloring $k$-colorable graphs, Israel J. Math. 105 (1998), 93–104. MR 1639735, DOI 10.1007/BF02780324
I. Sh. Kalimullin, A. G. Mel′nikov, and K. M. Ng, Different versions of categoricity without delays, Algebra Logika 56 (2017), no. 2, 256–266 (Russian); English transl., Algebra Logic 56 (2017), no. 2, 171–177. MR 3744783, DOI 10.1007/s10469-017-9437-6
Iskander Kalimullin, Alexander Melnikov, and Keng Meng Ng, Algebraic structures computable without delay, Theoret. Comput. Sci. 674 (2017), 73–98. MR 3634709, DOI 10.1016/j.tcs.2017.01.029
Bakhadyr Khoussainov and Anil Nerode, Automatic presentations of structures, Logic and computational complexity (Indianapolis, IN, 1994) Lecture Notes in Comput. Sci., vol. 960, Springer, Berlin, 1995, pp. 367–392. MR 1449670, DOI 10.1007/3-540-60178-3_{9}3
H. A. Kierstead, S. G. Penrice, and W. T. Trotter, On-line coloring and recursive graph theory, SIAM J. Discrete Math. 7 (1994), no. 1, 72–89. MR 1259011, DOI 10.1137/S0895480192224737
Bakhadyr Khoussainov and Richard A. Shore, Effective model theory: the number of models and their complexity, Models and computability (Leeds, 1997) London Math. Soc. Lecture Note Ser., vol. 259, Cambridge Univ. Press, Cambridge, 1999, pp. 193–239. MR 1721168, DOI 10.1017/CBO9780511565670.009
László Lovász, Michael Saks, and W. T. Trotter, An on-line graph coloring algorithm with sublinear performance ratio, Discrete Math. 75 (1989), no. 1-3, 319–325. Graph theory and combinatorics (Cambridge, 1988). MR 1001404, DOI 10.1016/0012-365X(89)90096-4
A. I. Mal′cev, Constructive algebras. I, Uspehi Mat. Nauk 16 (1961), no. 3 (99), 3–60 (Russian). MR 0151377
Alexander G. Melnikov, Eliminating unbounded search in computable algebra, Unveiling dynamics and complexity, Lecture Notes in Comput. Sci., vol. 10307, Springer, Cham, 2017, pp. 77–87. MR 3678739, DOI 10.1007/978-3-319-58741-7
Russell Miller, An introduction to computable model theory on groups and fields, Groups Complex. Cryptol. 3 (2011), no. 1, 25–45. MR 2806080, DOI 10.1515/GCC.2011.002
Alexander G. Melnikov and Keng Meng Ng, The back-and-forth method and computability without delay, Israel J. Math. 234 (2019), no. 2, 959–1000. MR 4040850, DOI 10.1007/s11856-019-1948-5
Russell Miller, Bjorn Poonen, Hans Schoutens, and Alexandra Shlapentokh, A computable functor from graphs to fields, J. Symb. Log. 83 (2018), no. 1, 326–348. MR 3796287, DOI 10.1017/jsl.2017.50
J. B. Remmel, Graph colorings and recursively bounded $\Pi ^0_1$-classes, Ann. Pure Appl. Logic 32 (1986), no. 2, 185–194. MR 863333, DOI 10.1016/0168-0072(86)90051-5
Todor Tsankov, The additive group of the rationals does not have an automatic presentation, J. Symbolic Logic 76 (2011), no. 4, 1341–1351. MR 2895399, DOI 10.2178/jsl/1318338853