Computable categoricity of trees of finite height

Journal of Symbolic Logic 70 (1):151-215 (2005)
  Copy   BIBTEX

Abstract

We characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a Σ03-condition. We show that all trees which are not computably categorical have computable dimension ω. Finally, we prove that for every n≥ 1 in ω, there exists a computable tree of finite height which is δ0n+1-categorical but not δ0n-categorical

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 103,401

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The computable dimension of trees of infinite height.Russell Miller - 2005 - Journal of Symbolic Logic 70 (1):111-141.
Computable dimension for ordered fields.Oscar Levin - 2016 - Archive for Mathematical Logic 55 (3-4):519-534.
d-computable Categoricity for Algebraic Fields.Russell Miller - 2009 - Journal of Symbolic Logic 74 (4):1325 - 1351.
The isomorphism problem for ω-automatic trees.Dietrich Kuske, Jiamou Liu & Markus Lohrey - 2013 - Annals of Pure and Applied Logic 164 (1):30-48.

Analytics

Added to PP
2010-08-24

Downloads
72 (#302,539)

6 months
11 (#246,005)

Historical graph of downloads
How can I increase my downloads?