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
Additional Information
- Denis R. Hirschfeldt
- Affiliation: Department of Mathematics, University of Chicago, 5734 S. University Avenue, Chicago, Illinois 60637
- MR Author ID: 667877
- Email: drh@math.uchicago.edu
- Ken Kramer
- Affiliation: Department of Mathematics, Queens College – C.U.N.Y., 65-30 Kissena Boulevard, Flushing, New York 11367 — and — Ph.D. Program in Mathematics, C.U.N.Y. Graduate Center, 365 Fifth Avenue, New York, New York 10016
- MR Author ID: 194747
- Email: kkramer@qc.cuny.edu
- Russell Miller
- Affiliation: Department of Mathematics, Queens College – C.U.N.Y., 65-30 Kissena Boulevard, Flushing, New York 11367 — and — Ph.D. Programs in Mathematics and Computer Science, C.U.N.Y. Graduate Center, 365 Fifth Avenue, New York, New York 10016
- MR Author ID: 679194
- Email: Russell.Miller@qc.cuny.edu
- Alexandra Shlapentokh
- Affiliation: Department of Mathematics, East Carolina University, Greenville, North Carolina 27858
- MR Author ID: 288363
- ORCID: 0000-0003-1990-909X
- Email: shlapentokha@ecu.edu
- Received by editor(s): November 3, 2011
- Received by editor(s) in revised form: January 29, 2013
- Published electronically: October 20, 2014
- Additional Notes: The first author was partially supported by Grants # DMS–0801033 and DMS–1101458 from the National Science Foundation
The second author was partially supported by Grant # DMS–0739346 from the National Science Foundation and by Grant #44-459 from the PSC-CUNY Research Award Program
The third author was partially supported by Grant # DMS–1001306 from the National Science Foundation, by Grant # 13397 from the Templeton Foundation, by the Centre de Recerca Matemática, and by several grants from The City University of New York PSC-CUNY Research Award Program
The fourth author was partially supported by Grants # DMS–0650927 and DMS–1161456 from the National Science Foundation, by Grant # 13419 from the Templeton Foundation, and by an ECU Faculty Senate Summer 2011 Grant - © Copyright 2014 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 367 (2015), 3981-4017
- MSC (2010): Primary 03D45; Secondary 03C57, 12L99
- DOI: https://doi.org/10.1090/S0002-9947-2014-06094-7
- MathSciNet review: 3324917