Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-24T02:25:18.300Z Has data issue: false hasContentIssue false
  • English
  • Français

d-computable categoricity for algebraic fields

Published online by Cambridge University Press:  12 March 2014

Russell Miller
Russell Miller*
Affiliation:
Department of Mathematics, Queens College – C.U.N.Y., 65-30 Kissena Blvd., Flushing, New York 11367, USA Ph.D. Programs in Computer Science & Mathematics, The Graduate Center of C.U.N.Y., 365 Fifth Avenue, New York, New York 10016, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We use the Low Basis Theorem of Jockusch and Soare to show that all computable algebraic fields are d-computably categorical for a particular Turing degree d with d′ = 0″, but that not all such fields are 0′-computably categorical. We also prove related results about algebraic fields with splitting algorithms, and fields of finite transcendence degree over ℚ.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 74 , Issue 4 , December 2009 , pp. 1325 - 1351
Copyright
Copyright © Association for Symbolic Logic 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Ash, C.J., Knight, J.F., Manasse, M.S., and Slaman, T.A., Generic copies of countable structures, Annals of Pure and Applied Logic, vol. 42 (1989), pp. 195–205.CrossRefGoogle Scholar
[2]Calvert, W., Harizanov, V., and Shlapentokh, A., Turing degrees of the isomorphism types of algebraic objects, Journal of London Mathematical Society, vol. 73 (2007), pp. 273–286.CrossRefGoogle Scholar
[3]Cenzer, D., Π10-classes in recursion theory, Handbook of computability theory (Griffor, E.R., editor). Elsevier, Amsterdam, 1999, pp. 37–85.CrossRefGoogle Scholar
[4]Downey, R.G. and Jockusch, C.G. Jr., Every low Boolean algebra is isomorphic to a recursive one. Proceedings of the American Mathematical Society, vol. 122, 1994, pp. 871–880.CrossRefGoogle Scholar
[5]Downey, R.G., Hirschfeldt, D.R., and Khoussainov, B., Uniformity in computable structure theory, Algebra and Logic, vol. 42 (2003), pp. 318–332.CrossRefGoogle Scholar
[6]Edwards, H.M., Galois theory, Springer-Verlag, New York, 1984.Google Scholar
[7]Ershov, Y.L. and Goncharov, S.S., Constructive fields, Constructive models, Kluwer Academic/Plenum Press, New York, 2000, Section 2.5.CrossRefGoogle Scholar
[8]Ershov, Yu.L., Theorie der Numerierungen, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 23 (1977), pp. 289–371.Google Scholar
[9]Fokina, E., Kalimullin, I., and Miller, R.G., Degrees of categoricity of computable structures, to appear.Google Scholar
[10]Fried, M.D. and Jarden, M., Field arithmetic, Springer-Verlag, Berlin, 1986.CrossRefGoogle Scholar
[11]Frohlich, A. and Shepherdson, J.C., Effective procedures in field theory. The Philosophical Transactions of the Royal Society, Series A, vol. 248 (1956), no. 950, pp. 407–432.Google Scholar
[12]Goncharov, S.S., Autostability and computable families of constructivizations, Algebra and Logic, vol. 14 (1975), pp. 647–680, (Russian), 392–409 (English translation).CrossRefGoogle Scholar
[13]Goncharov, S.S., Nonequivalent constructivizations, Proc. Math. Inst. Sib. Branch Acad. Sci., Nauka, Novosibirsk, 1982.Google Scholar
[14]Goncharov, S.S., Autostable models and algorithmic dimensions, Handbook of recursive mathematics, vol. 1, Elsevier, Amsterdam, 1998, pp. 261–287.Google Scholar
[15]Goncharov, S.S. and Dzgoev, V.D., Autostability of models, Algebra and Logic, vol. 19 (1980), pp. 45–58, (Russian), 28–37 (English translation).Google Scholar
[16]Goncharov, S.S., Lempp, S., and Solomon, R.. The computable dimension of ordered abelian groups, Advances in Mathematics, vol. 175 (2003), no. 1, pp. 102–143.CrossRefGoogle Scholar
[17]Hirschfeldt, D.R., Khoussainov, B., Shore, R.A., and Slinko, A.M., Degree spectra and computable dimensions in algebraic structures, Annals of Pure and Applied Logic, vol. 115 (2002), pp. 71–113.CrossRefGoogle Scholar
[18]Jacobson, N., Basic algebra I, W.H. Freeman & Co., New York, 1985.Google Scholar
[19]Jockusch, C.G. and Soare, R.I., Π10-classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 33–56.Google Scholar
[20]Jockusch, C.G., Degrees of orderings not isomorphic to recursive linear orderings, Annals of Pure and Applied Logic, vol. 52 (1991), pp. 39–64.CrossRefGoogle Scholar
[21]Khoussainov, B. and Shore, R.A., Effective model theory: The number of models and their complexity, Models and computability: Invited papers from Logic Colloquium '97 (Cooper, S.B. and Truss, J.K., editors), LMSLNS, vol. 259, Cambridge University Press, Cambridge, 1999, pp. 193–240.CrossRefGoogle Scholar
[22]Kogabaev, N., Kudinov, O., and Miller, R.G., The computable dimension of I-trees of infinite height, Algebra and Logic, vol. 43 (2004), no. 6, pp. 393–407.CrossRefGoogle Scholar
[23]Kronecker, L., Grundzüge einer arithmetischen Theorie der algebraischen Größen, Journal für die reine undangewandte Mathematik, vol. 92 (1882), pp. 1–122.Google Scholar
[24]Lempp, S., Mccoy, C., Miller, R.G., and Solomon, R., Computable categoricity of trees of finite height, this Journal, vol. 70 (2005), pp. 151–215.Google Scholar
[25]Miller, R.G., The δ20-spectrum of a linear order, this Journal, vol. 66 (2001), pp. 470–486.Google Scholar
[26]Miller, R.G., The computable dimension of trees of infinite height, this Journal, vol. 70 (2005), pp. 111–141.Google Scholar
[27]Miller, R.G. and Schoutens, H., Computably categorical fields via Fermat's Last Theorem, to appear.Google Scholar
[28]Metakides, G.Nerode, A., Effective content of field theory, Annals of Mathematical Logic, vol. 17 (1979), pp. 289–320.CrossRefGoogle Scholar
[29]Rabin, M., Computable algebra, general theory, and theory of computable fields, Transactions of the American Mathematical Society, vol. 95 (1960), pp. 341–360.Google Scholar
[30]Remmel, J.B., Recursive isomorphism types of recursive Boolean algebras, this Journal, vol. 46 (1981), pp. 572–594.Google Scholar
[31]Remmel, J.B., Recursively categorical linear orderings, Proceedings of the American Mathematical Society, vol. 83 (1981), pp. 387–391.CrossRefGoogle Scholar
[32]Richter, L.J., Degrees of structures, this Journal, vol. 46 (1981), pp. 723–731.Google Scholar
[33]Soare, R.I., Recursively enumerable sets and degrees, Springer-Verlag, New York, 1987.CrossRefGoogle Scholar
[34]Stoltenberg-Hansen, V. and Tucker, J.V., Computable rings and fields, Handbook of computability theory (Griffor, E.R., editor), Elsevier, Amsterdam, 1999, pp. 363–447.CrossRefGoogle Scholar
[35]Ventsov, Y.G., Effective choice for relations and reducibilities in classes of constructive and positive models, Algebra and Logic, vol. 31 (1992), pp. 63–73.CrossRefGoogle Scholar
[36]van der Waerden, B.L., Algebra, vol. I, Springer-Verlag, New York, 1970, trans. Blum, F. and Schulenberger, J.R..Google Scholar