Archive for Mathematical Logic 41 (4):309-320 (2002)
| Abstract |
In many classes of structures, each computable structure has computable dimension 1 or $\omega$. Nevertheless, Goncharov showed that for each $n < \omega$, there exists a computable structure with computable dimension $n$. In this paper we show that, under one natural definition of relativized computable dimension, no computable structure has finite relativized computable dimension greater than 1
|
| Keywords | Legacy |
| Categories | (categorize this paper) |
| DOI | 10.1007/s001530100113 |
| Options |
Mark as duplicate
Export citation
Request removal from index
|
Download options
References found in this work BETA
Generic Copies of Countable Structures.Chris Ash, Julia Knight, Mark Manasse & Theodore Slaman - 1989 - Annals of Pure and Applied Logic 42 (3):195-205.
Computably Categorical Structures and Expansions by Constants.Peter Cholak, Sergey Goncharov, Bakhadyr Khoussainov & Richard A. Shore - 1999 - Journal of Symbolic Logic 64 (1):13-37.
Citations of this work BETA
Enumerations in Computable Structure Theory.Sergey Goncharov, Valentina Harizanov, Julia Knight, Charles McCoy, Russell Miller & Reed Solomon - 2005 - Annals of Pure and Applied Logic 136 (3):219-246.
Degrees of Categoricity on a Cone Via Η-Systems.Barbara F. Csima & Matthew Harrison-Trainor - 2017 - Journal of Symbolic Logic 82 (1):325-346.
Non-Density in Punctual Computability.Noam Greenberg, Matthew Harrison-Trainor, Alexander Melnikov & Dan Turetsky - 2021 - Annals of Pure and Applied Logic 172 (9):102985.
Similar books and articles
Prime Models of Finite Computable Dimension.Pavel Semukhin - 2009 - Journal of Symbolic Logic 74 (1):336-348.
The Computable Dimension of Trees of Infinite Height.Russell Miller - 2005 - Journal of Symbolic Logic 70 (1):111-141.
Computable Categoricity of Trees of Finite Height.Steffen Lempp, Charles McCoy, Russell Miller & Reed Solomon - 2005 - Journal of Symbolic Logic 70 (1):151-215.
Categoricity of Computable Infinitary Theories.W. Calvert, S. S. Goncharov, J. F. Knight & Jessica Millar - 2009 - Archive for Mathematical Logic 48 (1):25-38.
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.
Computable Metrization.Tanja Grubba, Matthias Schröder & Klaus Weihrauch - 2007 - Mathematical Logic Quarterly 53 (4‐5):381-395.
On Computable Self-Embeddings of Computable Linear Orderings.Rodney G. Downey, Bart Kastermans & Steffen Lempp - 2009 - Journal of Symbolic Logic 74 (4):1352 - 1366.
On Computability Theoretic Properties of Structures and Their Cartesian Products.Bakhadyr Khoussainov - 2000 - Mathematical Logic Quarterly 46 (4):467-476.
When Series of Computable Functions with Varying Domains Are Computable.Iraj Kalantari & Larry Welch - 2013 - Mathematical Logic Quarterly 59 (6):471-493.
Recursive Approximability of Real Numbers.Xizhong Zheng - 2002 - Mathematical Logic Quarterly 48 (S1):131-156.
Effectively Closed Sets and Enumerations.Paul Brodhead & Douglas Cenzer - 2008 - Archive for Mathematical Logic 46 (7-8):565-582.
Intrinsic Bounds on Complexity and Definability at Limit Levels.John Chisholm, Ekaterina B. Fokina, Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Sara Quinn - 2009 - Journal of Symbolic Logic 74 (3):1047-1060.
The Block Relation in Computable Linear Orders.Michael Moses - 2011 - Notre Dame Journal of Formal Logic 52 (3):289-305.
Realizing Levels of the Hyperarithmetic Hierarchy as Degree Spectra of Relations on Computable Structures.Walker M. White & Denis R. Hirschfeldt - 2002 - Notre Dame Journal of Formal Logic 43 (1):51-64.
Analytics
Added to PP index
2013-11-23
Total views
6 ( #1,133,780 of 2,507,707 )
Recent downloads (6 months)
1 ( #416,820 of 2,507,707 )
2013-11-23
Total views
6 ( #1,133,780 of 2,507,707 )
Recent downloads (6 months)
1 ( #416,820 of 2,507,707 )
How can I increase my downloads?
Downloads
