×

A note on decidable categoricity and index sets. (English) Zbl 1443.03020

Summary: A structure \(S\) is decidably categorical if \(S\) has a decidable copy, and for any decidable copies \(A\) and \(B\) of \(S\), there is a computable isomorphism from \(A\) onto \(B\). S. S. Goncharov and M. I. Marchuk [Algebra Logic 54, No. 2, 108–126 (2015; Zbl 1347.03069); translation from Algebra Logika 54, No. 2, 163–192 (2015)] proved that the index set of decidably categorical graphs is \(\sum^0_{\omega +2}\) complete. In this paper, we isolate two familiar classes of structures \(K\) such that the index set for decidably categorical members of \(K\) has a relatively low complexity in the arithmetical hierarchy. We prove that the index set of decidably categorical real closed fields is \(\sum^0_3\) complete. We obtain a complete characterization of decidably categorical equivalence structures. We prove that decidably presentable equivalence structures have a \(\sum^0_4\) complete index set. A similar result is obtained for decidably categorical equivalence structures.

MSC:

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures

Citations:

Zbl 1347.03069
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Yu. L. Ershov,Constructive models, In: Yu. L. Ershov, M. I. Kargapolov, Yu. I. Merzlyakov, D. M. Smirnov, A. I. Shirshov, editors,Selected Questions of Algebra and Logic, pp. 111-130. Nauka, Novosibirsk, 1973. In Russian. MR0351803 · Zbl 0271.00005
[2] M. Morley,Decidable models, Isr. J. Math.,25:3-4 (1976), 233-240. MR0457190 · Zbl 0361.02067
[3] S. S. Goncharo, A. T. Nurtazin,Constructive models of complete solvable theories, Algebra Logic,12:2 (1973), 67-77. MR0398816
[4] L. Harrington,Recursively presentable prime models, J. Symb. Log.,39:2 (1974), 305-309. MR0351804 · Zbl 0332.02055
[5] S. S. Goncharov,Strong constructivizability of homogeneous models, Algebra Logic,17:4 (1978), 247-263. MR0538302 · Zbl 0441.03015
[6] M. G. Peretyat’kin,Criterion for strong constructivizability of a homogeneous model, Algebra Logic,17:4 (1978), 290-301. MR0538306
[7] V. S. Harizanov,Pure computable model theory, In: Yu. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, editors,Handbook of Recursive Mathematics. Volume 1, vol. 138 of Stud. Logic Found. Math., pp. 3-114. Elsevier Science B.V., Amsterdam, 1998. MR1673621 · Zbl 0952.03037
[8] P. Cholak, C. McCoy,Effective prime uniqueness, Proc. Am. Math. Soc.,145:12 (2017), 5363-5379. MR3717963 · Zbl 1377.03033
[9] S. S. Goncharov,On autostability of almost prime models relative to strong constructivizations, Russ. Math. Surv.,65:5 (2010), 901-935. MR2767909 · Zbl 1219.03038
[10] D. R. Hirschfeldt, K. Lange, R. A. Shore,Induction, bounding, weak combinatorial principles, and the homogeneous model theorem, Mem. Am. Math. Soc.,249(2017), iii+101 pp. MR3709722 · Zbl 1406.03039
[11] A. T. Nurtazin,Strong and weak constructivization and computable families, Algebra Logic, 13:3 (1974), 177-184. MR0381962 · Zbl 0305.02061
[12] S. S. Goncharov, M. I. Marchuk,Index sets of constructive models of bounded signature that are autostable relative to strong constructivizations, Algebra Logic,54:2 (2015), 108-126. MR3467209 · Zbl 1347.03069
[13] R. G. Downey, A. M. Kach, S. Lempp, A. Lewis-Pye, A. Montalb´an, D. Turetsky,The complexity of computable categoricity, Adv. Math.,268(2015), 423-466. MR3276601 · Zbl 1345.03063
[14] S. S. Goncharov, V. D. Dzgoev,Autostability of models, Algebra Logic,19:1 (1980), 28-37. MR0604657 · Zbl 0468.03023
[15] S. S. Goncharov, N. A. Bazhenov, M.I. Marchuk,Index set of linear orderings that are autostable relative to strong constructivizations, J. Math. Sci., New York,221:6 (2017), 840-848. MR3608977 · Zbl 1349.03036
[16] D. Cenzer, V. Harizanov, J. B. Remmel, Σ01andΠ01equivalence structures, Ann. Pure Appl. Logic,162:7 (2011), 490-503. MR2781091 · Zbl 1239.03023
[17] C. J. Ash, J. F. Knight,Computable Structures and the Hyperarithmetical Hierarchy, vol. 144 of Stud. Logic Found. Math. Elsevier Science B.V., Amsterdam, 2000. MR1767842 · Zbl 0960.03001
[18] Yu. L. Ershov, S. S. Goncharov,Constructive models, Consultants Bureau, New York, 2000. MR1749622 · Zbl 0954.03036
[19] C. C. Chang, H. J. Keisler,Model theory, North-Holland, Amsterdam, 1973. MR0409165 · Zbl 0276.02032
[20] S. S. Goncharov, M. I. Marchuk,Index sets of constructive models of finite and graph signatures that are autostable relative to strong constructivizations, Algebra Logic,54:6 (2016), 428-439. MR3497815 · Zbl 1375.03037
[21] S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk,The index set of Boolean algebras autostable relative to strong constructivizations, Siberian Math. J.,56:3 (2015), 393-404. MR3442797 · Zbl 1328.03036
[22] S. S. Goncharov, N. A. Bazhenov, and M. I. Marchuk,The index set of the groups autostable relative to strong constructivizations, Siberian Math. J.,58:1 (2017), 72-77. MR3686943 · Zbl 1420.03071
[23] M. I. Marchuk,Index set of structures with two equivalence relations that are autostable relative to strong constructivizations, Algebra Logic,55:4 (2016), 306-314. MR3711124 · Zbl 1402.03050
[24] S. Lang,Algebra, Revised third edition, vol. 211 of Graduate Texts in Mathematics, SpringerVerlag, New York, 2002. MR1878556
[25] N. Jacobson,Lectures in abstract algebra. Vol. III: Theory of fields and Galois theory, D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto, Ont.-London-New York, 1964. MR0172871 · Zbl 0124.27002
[26] R. Miller, V. Ocasio Gonz´alez,Degree spectra of real closed fields, Arch. Math. Logic,58:3-4 (2019), 387-411. MR3928390
[27] W. Calvert, V. S. Harizanov, J. F. Knight, S. Miller,Index sets of computable structures, Algebra Logic,45:5 (2006), 306-325. MR2307694 · Zbl 1164.03325
[28] V. A. Ocasio,Computability in the class of real closed fields, Ph.D. Thesis, University of Notre Dame, 2014. MR3251193
[29] W. Calvert,The isomorphism problem for classes of computable fields, Arch. Math. Logic, 43:3 (2004), 327-336. MR2052886 · Zbl 1059.03039
[30] W. Calvert, D. Cenzer, V. Harizanov, A. Morozov,Effective categoricity of equivalence structures, Ann. Pure Appl. Logic,141:1-2 (2006), 61-78. MR2229930 · Zbl 1103.03037
[31] S. S. Goncharov,Degrees of autostability relative to strong constructivizations, Proc. Steklov Inst. Math.,274:1 (2011), 105-115. MR2962937 · Zbl 1294.03025
[32] N. Bazhenov,Autostability spectra for decidable structures, Math. Struct. Comput. Sci.,28:3 (2018), 392-411. MR3778208
[33] N. Bazhenov, M. Harrison-Trainor, I. Kalimullin, A. Melnikov, K. M. Ng,Automatic and polynomial-time algebraic structures, J. Symb. Log.,84:4 (2019), 1630-1669. MR4045992 · Zbl 1454.03042
[34] S. S. Goncharov, R. Miller, V. Harizanov,Turing degrees of complete formulas of almost prime models, Algebra Logic,58:3 (2019), 282-287. Zbl 07175626 · Zbl 1485.03112
[35] N. A. Bazhenov, M. Harrison-Trainor,Constructing decidable graphs from decidable structures, Algebra Logic,58:5 (2019), 369-382. Zbl 07175775 · Zbl 1480.03022
[36] N. Bazhenov, S. Goncharov, A. Melnikov,Decompositions of decidable abelian groups, Int. J. Algebra Comput.,30:1 (2020), 49-90. MR4062374 · Zbl 1516.03012
[37] S. S. Goncharov, J. F. Knight,Computable structure and non-structure theorems, Algebra Logic,41:6 (2002), 351-373. MR1967769 · Zbl 1034.03044
[38] E. B. Fokina,Index sets of decidable models, Siberian Math. J.,48:5 (2007), 939-948. MR2364636 · Zbl 1164.03326
[39] Yu. L. Ershov,Decidability problems and constructive models, Nauka, Moscow, 1980. In Russian. MR598465
[40] A. G. Melnikov,Computable abelian groups, Bull. Symb. Log.,20:3 (2014), 315-356. MR3271281 · Zbl 1345.03065
[41] W.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.