Computable categoricity for algebraic fields with splitting algorithms

Miller, Russell; Shlapentokh, Alexandra

doi:10.1090/S0002-9947-2014-06093-5

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