Journal of Symbolic Logic 74 (3):1047-1060 (2009)

Valentina Harizanov
George Washington University
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
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 68,916
Through your library

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.
Effective Model Theory Vs. Recursive Model Theory.John Chisholm - 1990 - Journal of Symbolic Logic 55 (3):1168-1191.

View all 10 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Philosophy of Chemistry and Limits of Complexity.Hrvoj Vančik - 2003 - Foundations of Chemistry 5 (3):237-247.
The Intrinsic Difficulty of Recursive Functions.F. W. Kroon - 1996 - Studia Logica 56 (3):427 - 454.
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.


Added to PP index

Total views
54 ( #207,931 of 2,497,789 )

Recent downloads (6 months)
1 ( #428,370 of 2,497,789 )

How can I increase my downloads?


My notes