Computable Categoricity of Trees of Finite Height
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 $\Sigma _{3}^{0}$ -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 $\Delta _{n+1}^{0}$ -categorical but not $\Delta _{n}^{0}$ -categorical | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,664 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesRussell Miller (2005). The Computable Dimension of Trees of Infinite Height. Journal of Symbolic Logic 70 (1):111 - 141.
Wesley Calvert, Julia F. Knight & Jessica Millar (2006). Computable Trees of Scott Rank $\Omega _{1}^{\Mathit{CK}}$ , and Computable Approximation. Journal of Symbolic Logic 71 (1):283 - 298.
Barbara F. Csima, Johanna N. Y. Franklin & Richard A. Shore (2013). Degrees of Categoricity and the Hyperarithmetic Hierarchy. Notre Dame Journal of Formal Logic 54 (2):215-231.
Fabio Bellissima & Saverio Cittadini (1999). Finite Trees in Tense Logic. Studia Logica 62 (2):121-140.
Rolf Backofen, James Rogers & K. Vijay-Shanker (1995). A First-Order Axiomatization of the Theory of Finite Trees. Journal of Logic, Language and Information 4 (1):5-39.
Denis R. Hirschfeldt, Bakhadyr Khoussainov & Richard A. Shore (2003). A Computably Categorical Structure Whose Expansion by a Constant has Infinite Computable Dimension. Journal of Symbolic Logic 68 (4):1199-1241.
Denis R. Hirschfeldt (2002). Degree Spectra of Relations on Computable Structures in the Presence of Δ02 Isomorphisms. Journal of Symbolic Logic 67 (2):697 - 720.
Denis R. Hirschfeldt (2002). Degree Spectra of Relations on Computable Structures in the Presence of Δ02 Isomorphisms. Journal of Symbolic Logic 67 (2):697 - 720.
Dmitrij Skvortsov (2004). On Intermediate Predicate Logics of Some Finite Kripke Frames, I. Levelwise Uniform Trees. Studia Logica 77 (3):295 - 323.
Wesley Calvert, Julia F. Knight & Jessica Millar (2006). Computable Trees of Scott Rank Ω 1 CK , and Computable Approximation. Journal of Symbolic Logic 71 (1):283-298.
Michael Moses (2010). The Block Relation in Computable Linear Orders. Notre Dame Journal of Formal Logic 52 (3):289-305.
James H. Schmerl (1980). Decidability and ℵ0-Categoricity of Theories of Partially Ordered Sets. Journal of Symbolic Logic 45 (3):585 - 611.
Alex M. McAllister (1998). Completions of PA: Models and Enumerations of Representable Sets. Journal of Symbolic Logic 63 (3):1063-1082.
D. Skvortsov (1995). On the Predicate Logics of Finite Kripke Frames. Studia Logica 54 (1):79 - 88.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2010-08-24Total downloads1 ( #274,602 of 549,010 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
