Computable categoricity for algebraic fields with splitting algorithms
HTML articles powered by AMS MathViewer
- by Russell Miller and Alexandra Shlapentokh PDF
- Trans. Amer. Math. Soc. 367 (2015), 3955-3980 Request permission
Abstract:
A computably presented algebraic field $F$ has a splitting algorithm if it is decidable which polynomials in $F[X]$ are irreducible there. We prove that such a field is computably categorical iff it is decidable which pairs of elements of $F$ belong to the same orbit under automorphisms. We also show that this criterion is equivalent to the relative computable categoricity of $F$.References
- 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
- J. Chisholm, On intrinsically $1$-computable trees, unpublished manuscript.
- J. P. Cleave, Some properties of recursively inseparable sets, Z. Math. Logik Grundlagen Math. 16 (1970), 187–200. MR 269499, DOI 10.1002/malq.19700160208
- 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
- Ekaterina B. Fokina, Iskander Kalimullin, and Russell Miller, Degrees of categoricity of computable structures, Arch. Math. Logic 49 (2010), no. 1, 51–67. MR 2592045, DOI 10.1007/s00153-009-0160-4
- Michael D. Fried and Moshe Jarden, Field arithmetic, 2nd ed., Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol. 11, Springer-Verlag, Berlin, 2005. MR 2102046
- 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
- Klaus Ambos-Spies, Benedikt Löwe, and Wolfgang Merkle (eds.), Mathematical theory and computational practice, Lecture Notes in Computer Science, vol. 5635, Springer, Berlin, 2009. MR 2742547, DOI 10.1007/978-3-642-03073-4
- 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. Gončarov and V. D. Dzgoev, Autostability of models, Algebra i Logika 19 (1980), no. 1, 45–58, 132 (Russian). MR 604657
- D.R. Hirschfeldt, K. Kramer, R. G. Miller, and A. Shlapentokh, Categoricity properties for computable algebraic fields, in this issue.
- Carl G. Jockusch Jr. and Robert I. Soare, $\Pi ^{0}_{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33–56. MR 316227, DOI 10.1090/S0002-9947-1972-0316227-0
- 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
- L. Kronecker, Grundzüge einer arithmetischen Theorie der algebraischen Größen, Crelle Jour. Math. 92 (1882), 1–122.
- 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
- 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, $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/$\tilde {~}$rmiller/research.html.
- 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
- 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
- Dana Scott, Algebras of sets binumerable in complete extensions of arithmetic, Proc. Sympos. Pure Math., Vol. V, American Mathematical Society, Providence, R.I., 1962, pp. 117–121. MR 0141595
- S. Simpson, Degrees of unsolvability: a survey of results, in Handbook of Mathematical Logic, ed. J. Barwise (Amsterdam: North-Holland, 1977), 631–652.
- 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
Additional Information
- 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 Grant # DMS–1001306 from the National Science Foundation, by Grant # 13397 from the Templeton Foundation, by the Centre de Recerca Matemática and the European Science Foundation, and by several grants from The City University of New York PSC-CUNY Research Award Program
The second 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), 3955-3980
- MSC (2010): Primary 03D45; Secondary 03C57, 12E05, 12L99
- DOI: https://doi.org/10.1090/S0002-9947-2014-06093-5
- MathSciNet review: 3324916