×

zbMATH — the first resource for mathematics

The computable dimension of trees of infinite height. (English) Zbl 1098.03049
The author proves that every computable tree of infinite height has \(\omega\) pairwisely non-computably isomorphic computable presentations. Moreover, given any computable enumeration of its computable presentations, one can effectively construct a computably isomorphic copy of this tree so that it will be not computably isomorphic to all presentations listed in this enumeration, i.e., the class of all computable presentations of such trees is effectively infinite.

MSC:
03D45 Theory of numerations, effectively presented structures
03C57 Computable structure theory, computable model theory
PDF BibTeX Cite
Full Text: DOI
References:
[1] Handbook of recursive mathematics 1 pp 261– (1998)
[2] Algebra and Logic 19 pp 45– (1980)
[3] Algebra i Logika 19 (1980)
[4] Algebra and Logic 14 pp 647– (1975)
[5] DOI: 10.1016/0168-0072(91)90022-E · Zbl 0758.03025
[6] Constructive models (2000)
[7] Complexity, logic, and recursion theory pp 157– (1997)
[8] DOI: 10.1016/0168-0072(86)90070-9 · Zbl 0605.03023
[9] DOI: 10.1016/0168-0072(87)90038-8 · Zbl 0617.03016
[10] Recursively enumerable sets and degrees (1987)
[11] Harvey Friedman’s research on the foundations of mathematics pp 87– (1985)
[12] DOI: 10.1090/S0002-9939-1981-0624937-1
[13] Recursive isomorphism types of recursive Boolean algebras 46 pp 572– (1981)
[14] DOI: 10.1017/S0305004100003844
[15] Computable categoricity of trees offinite height 70 pp 151– (2005)
[16] Transactions of the American Mathematical Society 95 pp 210– (1960)
[17] Models and computability: Invited papers from Logic Colloquium ’97 259 pp 193– (1999)
[18] DOI: 10.1016/S0168-0072(97)00059-6 · Zbl 0927.03072
[19] Nonequivalent constructivizations (1982)
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.