John Chisholm, Ekaterina B. Fokina, Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Sara Quinn
Journal of Symbolic Logic 74 (3):1047-1060 (2009)
Authors |
|
Abstract |
We show that for every computable limit ordinal α, there is a computable structure A that is $\Delta _\alpha ^0 $ categorical, but not relatively $\Delta _\alpha ^0 $ categorical (equivalently. it does not have a formally $\Sigma _\alpha ^0 $ Scott family). We also show that for every computable limit ordinal a, there is a computable structure A with an additional relation R that is intrinsically $\Sigma _\alpha ^0 $ on A. but not relatively intrinsically $\Sigma _\alpha ^0 $ on A (equivalently, it is not definable by a computable $\Sigma _\alpha $ formula with finitely many parameters). Earlier results in [7], [10], and [8] establish the same facts for computable successor ordinals α
|
Keywords | No keywords specified (fix it) |
Categories | (categorize this paper) |
DOI | 10.2178/jsl/1245158098 |
Options |
![]() ![]() ![]() ![]() |
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.
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.
Effective Model Theory Vs. Recursive Model Theory.John Chisholm - 1990 - Journal of Symbolic Logic 55 (3):1168-1191.
Π 1 1 Relations and Paths Through.Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Richard A. Shore - 2004 - Journal of Symbolic Logic 69 (2):585-611.
View all 10 references / Add more references
Citations of this work BETA
Computability-Theoretic Categoricity and Scott Families.Ekaterina Fokina, Valentina Harizanov & Daniel Turetsky - 2019 - Annals of Pure and Applied Logic 170 (6):699-717.
Similar books and articles
Philosophy of Chemistry and Limits of Complexity.Hrvoj Vančik - 2003 - Foundations of Chemistry 5 (3):237-247.
Complexity of Interpolation and Related Problems in Positive Calculi.Larisa Maksimova - 2002 - Journal of Symbolic Logic 67 (1):397-408.
Π 1 1 Relations and Paths Through.Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Richard A. Shore - 2004 - Journal of Symbolic Logic 69 (2):585-611.
Π₁¹ Relations and Paths Through ᵊ.Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Richard A. Shore - 2004 - Journal of Symbolic Logic 69 (2):585 - 611.
Isomorphism Relations on Computable Structures.Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles Mccoy & Antonio Montalbán - 2012 - Journal of Symbolic Logic 77 (1):122-132.
The Intrinsic Difficulty of Recursive Functions.F. W. Kroon - 1996 - Studia Logica 56 (3):427 - 454.
Characterizing Definability of Second-Order Generalized Quantifiers.Juha Kontinen & Jakub Szymanik - 2011 - In L. Beklemishev & R. de Queiroz (eds.), Proceedings of the 18th Workshop on Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence 6642. Springer.
Self-Representation: Searching for a Neural Signature of Self-Consciousness.Albert Newen & Kai Vogeley - 2003 - Consciousness and Cognition 12 (4):529-543.
The Structure of Intrinsic Complexity of Learning.Sanjay Jain & Arun Sharma - 1997 - Journal of Symbolic Logic 62 (4):1187-1201.
More About Uniform Upper Bounds on Ideals of Turing Degrees.Harold T. Hodes - 1983 - Journal of Symbolic Logic 48 (2):441-457.
The Fine Structure of Real Mice.Daniel W. Cunningham - 1998 - Journal of Symbolic Logic 63 (3):937-994.
Asymptotic Conditional Probabilities: The Non-Unary Case.Adam J. Grove, Joseph Y. Halpern & Daphne Koller - 1996 - Journal of Symbolic Logic 61 (1):250-276.
Analytics
Added to PP index
2010-09-12
Total views
54 ( #184,886 of 2,411,486 )
Recent downloads (6 months)
2 ( #346,414 of 2,411,486 )
2010-09-12
Total views
54 ( #184,886 of 2,411,486 )
Recent downloads (6 months)
2 ( #346,414 of 2,411,486 )
How can I increase my downloads?
Downloads