×

\(d\)-computable categoricity for algebraic fields. (English) Zbl 1202.03044

Let \(\mathbf d\) be a Turing degree. A computable structure \(A\) is called \(\mathbf d\)-computably categorical if for every computable structure \(B\) classically isomorphic to it there is a \(\mathbf d\)-computable isomorphism from \(A\) onto \(B\). A field is called algebraic if each of its elements is algebraic over its prime subfield.
The main subject of the paper is the study of relative computable categoricity for algebraic fields. In particular, the author proves that there exists an algebraic field that is not computably categorical but has a computable set of reducible polynomials; there exists a computable algebraic field that is not \(\mathbf 0'\)-categorical; there exists a degree \(\mathbf d\) with \({\mathbf d'}\leq_T {\mathbf 0''}\) such that every computable algebraic field is \(\mathbf d\)-computably categorical; there is no least degree \(\mathbf d\) such that every algebraic field is \(\mathbf d\)-computably categorical.
Similar problems are also studied for fields of finite transcendence degree over the field of rational numbers.

MSC:

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] DOI: 10.1023/B:ALLO.0000048828.44523.94 · Zbl 1096.03051
[2] DOI: 10.1023/A:1025971406116
[3] DOI: 10.1016/0168-0072(91)90038-N · Zbl 0734.03026
[4] DOI: 10.1002/malq.19770231902 · Zbl 0374.02028
[5] Constructive models (2000)
[6] Galois theory (1984)
[7] Algebra I (1970)
[8] DOI: 10.1007/BF02259845
[9] DOI: 10.1090/S0002-9939-1994-1203984-4
[10] Handbook of computability theory pp 363– (1999)
[11] Handbook of computability theory pp 37– (1999)
[12] Recursively enumerable sets and degrees (1987)
[13] Journal of London Mathematical Society 73 pp 273– (2007)
[14] Degrees of structures 46 pp 723– (1981)
[15] DOI: 10.1016/0168-0072(89)90015-8 · Zbl 0678.03012
[16] DOI: 10.1090/S0002-9939-1981-0624937-1
[17] Recursive isomorphism types of recursive Boolean algebras 46 pp 572– (1981)
[18] Transactions of the American Mathematical Society 173 pp 33– (1972) · Zbl 0247.00014
[19] Basic algebra I (1985)
[20] DOI: 10.1016/S0168-0072(01)00087-2 · Zbl 1016.03034
[21] DOI: 10.1016/S0001-8708(02)00042-7 · Zbl 1031.03058
[22] Algebra and Logic 19 pp 45– (1980)
[23] Handbook of recursive mathematics 1 pp 261– (1998)
[24] Nonequivalent constructivizations (1982)
[25] Algebra and Logic 14 pp 647– (1975)
[26] DOI: 10.1098/rsta.1956.0003 · Zbl 0070.03502
[27] Field arithmetic (1986)
[28] Transactions of the American Mathematical Society 95 pp 341– (1960)
[29] DOI: 10.1016/0003-4843(79)90011-1 · Zbl 0469.03028
[30] The computable dimension of trees of infinite height 70 pp 111– (2005) · Zbl 1098.03049
[31] The {\(\delta\)}2 0-spectrum of a linear order 66 pp 470– (2001)
[32] Computable categoricity of trees of finite height 70 pp 151– (2005) · Zbl 1104.03026
[33] Journal für die reine undangewandte Mathematik 92 pp 1– (1882)
[34] Models and computability: Invited papers from Logic Colloquium ’97 259 pp 193– (1999)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.