Journal Title

The Journal of Symbolic Logic

Publication Date

3-2005

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.

Subjects

Computable functions

Publication Information

Copyright 2005 Association for Symbolic Logic

Peer-Reviewed

Yes

Document Type

Journal Article

Included in

Mathematics Commons

Share

COinS