Journal of Symbolic Logic 70 (1):151-215 (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
|
Keywords | No keywords specified (fix it) |
Categories | (categorize this paper) |
DOI | 10.2178/jsl/1107298515 |
Options |
![]() ![]() ![]() ![]() |
Download options
References found in this work BETA
Degree Spectra and Computable Dimensions in Algebraic Structures.Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore & Arkadii M. Slinko - 2002 - Annals of Pure and Applied Logic 115 (1-3):71-113.
Generic Copies of Countable Structures.Chris Ash, Julia Knight, Mark Manasse & Theodore Slaman - 1989 - Annals of Pure and Applied Logic 42 (3):195-205.
Computable Isomorphisms, Degree Spectra of Relations, and Scott Families.Bakhadyr Khoussainov & Richard A. Shore - 1998 - Annals of Pure and Applied Logic 93 (1-3):153-193.
Categoricity in Hyperarithmetical Degrees.C. J. Ash - 1987 - Annals of Pure and Applied Logic 34 (1):1-14.
On the Complexity of Categoricity in Computable Structures.Walker M. White - 2003 - Mathematical Logic Quarterly 49 (6):603.
View all 8 references / Add more references
Citations of this work BETA
Effective Categoricity of Equivalence Structures.Wesley Calvert, Douglas Cenzer, Valentina Harizanov & Andrei Morozov - 2006 - Annals of Pure and Applied Logic 141 (1):61-78.
D-Computable Categoricity for Algebraic Fields.Russell Miller - 2009 - Journal of Symbolic Logic 74 (4):1325 - 1351.
Effective Categoricity of Abelian P -Groups.Wesley Calvert, Douglas Cenzer, Valentina S. Harizanov & Andrei Morozov - 2009 - Annals of Pure and Applied Logic 159 (1-2):187-197.
Self-Embeddings of Computable Trees.Stephen Binns, Bjørn Kjos-Hanssen, Manuel Lerman, James H. Schmerl & Reed Solomon - 2008 - Notre Dame Journal of Formal Logic 49 (1):1-37.
Computability-Theoretic Categoricity and Scott Families.Ekaterina Fokina, Valentina Harizanov & Daniel Turetsky - 2019 - Annals of Pure and Applied Logic 170 (6):699-717.
View all 7 citations / Add more citations
Similar books and articles
The Computable Dimension of Trees of Infinite Height.Russell Miller - 2005 - Journal of Symbolic Logic 70 (1):111-141.
Computable Trees of Scott Rank $\omega _{1}^{\mathit{CK}}$ , and Computable Approximation.Wesley Calvert, Julia F. Knight & Jessica Millar - 2006 - Journal of Symbolic Logic 71 (1):283 - 298.
A First-Order Axiomatization of the Theory of Finite Trees.Rolf Backofen, James Rogers & K. Vijay-Shanker - 1995 - Journal of Logic, Language and Information 4 (1):5-39.
A Computably Categorical Structure Whose Expansion by a Constant has Infinite Computable Dimension.Denis R. Hirschfeldt, Bakhadyr Khoussainov & Richard A. Shore - 2003 - Journal of Symbolic Logic 68 (4):1199-1241.
On Intermediate Predicate Logics of Some Finite Kripke Frames, I. Levelwise Uniform Trees.Dmitrij Skvortsov - 2004 - Studia Logica 77 (3):295 - 323.
Computable Trees of Scott Rank [Image] , and Computable Approximation.Wesley Calvert, Julia F. Knight & Jessica Millar - 2006 - Journal of Symbolic Logic 71 (1):283 - 298.
The Block Relation in Computable Linear Orders.Michael Moses - 2011 - Notre Dame Journal of Formal Logic 52 (3):289-305.
Decidability and ℵ0-Categoricity of Theories of Partially Ordered Sets.James H. Schmerl - 1980 - Journal of Symbolic Logic 45 (3):585 - 611.
Analytics
Added to PP index
2010-08-24
Total views
27 ( #423,061 of 2,506,137 )
Recent downloads (6 months)
1 ( #416,984 of 2,506,137 )
2010-08-24
Total views
27 ( #423,061 of 2,506,137 )
Recent downloads (6 months)
1 ( #416,984 of 2,506,137 )
How can I increase my downloads?
Downloads