Computable categoricity of trees of finite height
Lempp, Steffen ; McCoy, Charles ; Miller, Russell ; Solomon, Reed
J. Symbolic Logic, Tome 70 (2005) no. 1, p. 151-215 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
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.
Publié le : 2005-03-14
Classification:  
@article{1107298515,
     author = {Lempp, Steffen and McCoy, Charles and Miller, Russell and Solomon, Reed},
     title = {Computable categoricity of trees of finite height},
     journal = {J. Symbolic Logic},
     volume = {70},
     number = {1},
     year = {2005},
     pages = { 151-215},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1107298515}
}

Lempp, Steffen; McCoy, Charles; Miller, Russell; Solomon, Reed. Computable categoricity of trees of finite height. J. Symbolic Logic, Tome 70 (2005) no. 1, pp.  151-215. http://gdmltest.u-ga.fr/item/1107298515/