×

zbMATH — the first resource for mathematics

Computable categoricity of trees of finite height. (English) Zbl 1104.03026
The main result of this paper is a characterization of computably categorical trees of finite height. It is also proven that for such trees the computable categoricity is equivalent to the relative computable categoricity. It follows that if such a tree is not computably categorical then it has \(\omega\) computably non-isomorphic isomorphic computable presentations. It is also proven that, for each natural number \(n\geq 1\), there exists a computable tree which is \(\Delta_{n+1}^0\)-categorical but not \(\Delta_n^0\)-categorical.

MSC:
03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
03C35 Categoricity and completeness of theories
PDF BibTeX Cite
Full Text: DOI
References:
[1] Notices of the American Mathematical Society 24 pp A– (1977)
[2] DOI: 10.1016/0003-4843(79)90011-1 · Zbl 0469.03028
[3] DOI: 10.1007/BF01669323 · Zbl 0476.03046
[4] Algebra and Logic 14 pp 647– (1975)
[5] DOI: 10.1090/S0002-9939-1994-1203984-4
[6] Complexity, logic, and recursion theory pp 157– (1997)
[7] DOI: 10.1016/0168-0072(86)90070-9 · Zbl 0605.03023
[8] DOI: 10.1002/malq.200310066 · Zbl 1035.03017
[9] DOI: 10.1090/S0002-9939-98-04314-7 · Zbl 0906.03044
[10] DOI: 10.1016/0168-0072(89)90015-8 · Zbl 0678.03012
[11] Recursively enumerable sets and degrees (1987)
[12] Computable structures and the hyperarithmetic hierarchy (2000)
[13] DOI: 10.1090/S0002-9939-98-04307-X · Zbl 0894.03017
[14] DOI: 10.1016/0168-0072(87)90038-8 · Zbl 0617.03016
[15] Harvey Friedman’s research on the foundations of mathematics pp 87– (1985)
[16] DOI: 10.1090/S0002-9939-1981-0624937-1
[17] Transactions of the American Mathematical Society 95 pp 210– (1960)
[18] Models and computability: Invited papers from Logic Colloquium ’97 259 pp 193– (1999)
[19] DOI: 10.1016/S0168-0072(97)00059-6 · Zbl 0927.03072
[20] DOI: 10.1016/S0168-0072(01)00087-2 · Zbl 1016.03034
[21] DOI: 10.1007/BF01054216 · Zbl 0684.20025
[22] DOI: 10.1016/S0001-8708(02)00042-7 · Zbl 1031.03058
[23] Algebra and Logic 19 pp 45– (1980)
[24] Autostable models and algorithmic dimensions 1 (1998) · Zbl 0958.03030
[25] Nonequivalent constructivizations (1982)
[26] Soviet Mathematics Doklady 19 pp 58– (1981)
[27] Recursive isomorphism types of recursive Boolean algebras 46 pp 572– (1981)
[28] DOI: 10.1007/BF01463352 · Zbl 0305.02061
[29] DOI: 10.1017/S0305004100003844
[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] DOI: 10.1007/BF02367027
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.