Categoricity properties for computable algebraic fields

Hirschfeldt, Denis; Kramer, Ken; Miller, Russell; Shlapentokh, Alexandra

doi:10.1090/S0002-9947-2014-06094-7

Categoricity properties for computable algebraic fields
HTML articles powered by AMS MathViewer

by Denis R. Hirschfeldt, Ken Kramer, Russell Miller and Alexandra Shlapentokh PDF

Trans. Amer. Math. Soc. 367 (2015), 3981-4017 Request permission

Abstract:

We examine categoricity issues for computable algebraic fields. We give a structural criterion for relative computable categoricity of these fields, and use it to construct a field that is computably categorical, but not relatively computably categorical. Finally, we show that computable categoricity for this class of fields is $\Pi ^0_4$-complete.

References

C. J. Ash and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy (Amsterdam: Elsevier, 2000).
Chris Ash, Julia Knight, Mark Manasse, and Theodore Slaman, Generic copies of countable structures, Ann. Pure Appl. Logic 42 (1989), no. 3, 195–205. MR 998606, DOI 10.1016/0168-0072(89)90015-8
V. Kalvert, V. S. Kharizanova, D. F. Naĭt, and S. Miller, Index sets of computable models, Algebra Logika 45 (2006), no. 5, 538–574, 631–632 (Russian, with Russian summary); English transl., Algebra Logic 45 (2006), no. 5, 306–325. MR 2307694, DOI 10.1007/s10469-006-0029-0
J. Chisholm, On intrinsically $1$-computable trees, unpublished manuscript.
R. Douni, D. Khirshvel′d, and B. Khusainov, Uniformity in the theory of computable structures, Algebra Logika 42 (2003), no. 5, 566–593, 637 (Russian, with Russian summary); English transl., Algebra Logic 42 (2003), no. 5, 318–332. MR 2025716, DOI 10.1023/A:1025971406116
Ju. L. Eršov, Theorie der Numerierungen. III, Z. Math. Logik Grundlagen Math. 23 (1977), no. 4, 289–371. MR 439603, DOI 10.1002/malq.19770231902
Yu. L. Ershov and S. S. Goncharov, Constructive fields, Section 2.5 in Constructive Models (New York: Kluwer Academic/Plenum Press, 2000).
Michael D. Fried and Moshe Jarden, Field arithmetic, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 11, Springer-Verlag, Berlin, 1986. MR 868860, DOI 10.1007/978-3-662-07216-5
A. Fröhlich and J. C. Shepherdson, Effective procedures in field theory, Philos. Trans. Roy. Soc. London Ser. A 248 (1956), 407–432. MR 74349, DOI 10.1098/rsta.1956.0003
S. S. Gončarov, Selfstability, and computable families of constructivizations, Algebra i Logika 14 (1975), no. 6, 647–680, 727 (Russian). MR 0437335
S. S. Goncharov; Nonequivalent constructivizations, Proc. Math. Inst. Sib. Branch Acad. Sci. (Novosibirsk: Nauka, 1982).
S. S. Goncharov, Autostable models and algorithmic dimensions, Handbook of recursive mathematics, Vol. 1, Stud. Logic Found. Math., vol. 138, North-Holland, Amsterdam, 1998, pp. 261–287. MR 1673641, DOI 10.1016/S0049-237X(98)80007-4
S. S. Gončarov and V. D. Dzgoev, Autostability of models, Algebra i Logika 19 (1980), no. 1, 45–58, 132 (Russian). MR 604657
Sergey S. Goncharov, Steffen Lempp, and Reed Solomon, The computable dimension of ordered abelian groups, Adv. Math. 175 (2003), no. 1, 102–143. MR 1970243, DOI 10.1016/S0001-8708(02)00042-7
Valentina S. Harizanov, Pure computable model theory, Handbook of recursive mathematics, Vol. 1, Stud. Logic Found. Math., vol. 138, North-Holland, Amsterdam, 1998, pp. 3–114. MR 1673621, DOI 10.1016/S0049-237X(98)80002-5
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
Nathan Jacobson, Basic algebra. I, 2nd ed., W. H. Freeman and Company, New York, 1985. MR 780184
Bakhadyr Khoussainov and Richard A. Shore, Computable isomorphisms, degree spectra of relations, and Scott families, Ann. Pure Appl. Logic 93 (1998), no. 1-3, 153–193. Computability theory. MR 1635605, DOI 10.1016/S0168-0072(97)00059-6
N. T. Kogabaev, O. V. Kudinov, and R. Miller, The computable dimension of $I$-trees of infinite height, Algebra Logika 43 (2004), no. 6, 702–729, 759 (Russian, with Russian summary); English transl., Algebra Logic 43 (2004), no. 6, 393–407. MR 2135388, DOI 10.1023/B:ALLO.0000048828.44523.94
O. V. Kudinov, An autostable $1$-decidable model without a computable Scott family of $\exists$-formulas, Algebra i Logika 35 (1996), no. 4, 458–467, 498 (Russian, with Russian summary); English transl., Algebra and Logic 35 (1996), no. 4, 255–260. MR 1444430, DOI 10.1007/BF02367027
Serge Lang, Algebra, 3rd ed., Graduate Texts in Mathematics, vol. 211, Springer-Verlag, New York, 2002. MR 1878556, DOI 10.1007/978-1-4613-0041-0
Serge Lang, Algebraic number theory, 2nd ed., Graduate Texts in Mathematics, vol. 110, Springer-Verlag, New York, 1994. MR 1282723, DOI 10.1007/978-1-4612-0853-2
Steffen Lempp, Charles McCoy, Russell Miller, and Reed Solomon, Computable categoricity of trees of finite height, J. Symbolic Logic 70 (2005), no. 1, 151–215. MR 2119128, DOI 10.2178/jsl/1107298515
G. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1979), no. 3, 289–320. MR 556895, DOI 10.1016/0003-4843(79)90011-1
Russell Miller, The computable dimension of trees of infinite height, J. Symbolic Logic 70 (2005), no. 1, 111–141. MR 2119126, DOI 10.2178/jsl/1107298513
Russell Miller, Computable fields and Galois theory, Notices Amer. Math. Soc. 55 (2008), no. 7, 798–807. MR 2436510
Russell Miller, Is it harder to factor a polynomial or to find a root?, Trans. Amer. Math. Soc. 362 (2010), no. 10, 5261–5281. MR 2657679, DOI 10.1090/S0002-9947-2010-04918-9
Russell Miller, $d$-computable categoricity for algebraic fields, J. Symbolic Logic 74 (2009), no. 4, 1325–1351. MR 2583823, DOI 10.2178/jsl/1254748694
Russell Miller, Computability and differential fields: a tutorial, to appear in Differential Algebra and Related Topics: Proceedings of the Second International Workshop, eds. L. Guo & W. Sit (World Scientific, 2014), ISBN 978-981-283-371-6. Also available at qcpages.qc.cuny.edu/~rmiller/research.html.
R. Miller, J. Park, B. Poonen, H. Schoutens, and A. Shlapentokh, A computable functor from graphs to fields, in preparation.
Russell Miller and Hans Schoutens, Computably categorical fields via Fermat’s last theorem, Computability 2 (2013), no. 1, 51–65. MR 3123253, DOI 10.3233/com-13017
Russell Miller and Alexandra Shlapentokh, Computable categoricity for algebraic fields with splitting algorithms, in this issue
Michael O. Rabin, Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc. 95 (1960), 341–360. MR 113807, DOI 10.1090/S0002-9947-1960-0113807-4
J. B. Remmel, Recursively categorical linear orderings, Proc. Amer. Math. Soc. 83 (1981), no. 2, 387–391. MR 624937, DOI 10.1090/S0002-9939-1981-0624937-1
J. B. Remmel, Recursive isomorphism types of recursive Boolean algebras, J. Symbolic Logic 46 (1981), no. 3, 572–594. MR 627907, DOI 10.2307/2273757
Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
V. Stoltenberg-Hansen and J. V. Tucker, Computable rings and fields, Handbook of computability theory, Stud. Logic Found. Math., vol. 140, North-Holland, Amsterdam, 1999, pp. 363–447. MR 1720739, DOI 10.1016/S0049-237X(99)80028-7
B. L. van der Waerden, Algebra. Vol. I, Springer-Verlag, New York, 1991. Based in part on lectures by E. Artin and E. Noether; Translated from the seventh German edition by Fred Blum and John R. Schulenberger. MR 1080172, DOI 10.1007/978-1-4612-4420-2
Yu. G. Ventsov, The effective choice problem for relations and reducibilities in classes of constructive and positive models, Algebra i Logika 31 (1992), no. 2, 101–118, 220 (Russian, with Russian summary); English transl., Algebra and Logic 31 (1992), no. 2, 63–73 (1993). MR 1289026, DOI 10.1007/BF02259845
Walker M. White, On the complexity of categoricity in computable structures, MLQ Math. Log. Q. 49 (2003), no. 6, 603–614. MR 2013721, DOI 10.1002/malq.200310066