Journal of Symbolic Logic 83 (1):103-116 (2018)

Abstract
A Turing degreedis the degree of categoricity of a computable structure${\cal S}$ifdis the least degree capable of computing isomorphisms among arbitrary computable copies of${\cal S}$. A degreedis the strong degree of categoricity of${\cal S}$ifdis the degree of categoricity of${\cal S}$, and there are computable copies${\cal A}$and${\cal B}$of${\cal S}$such that every isomorphism from${\cal A}$onto${\cal B}$computesd. In this paper, we build a c.e. degreedand a computable rigid structure${\cal M}$such thatdis the degree of categoricity of${\cal M}$, butdis not the strong degree of categoricity of${\cal M}$. This solves the open problem of Fokina, Kalimullin, and Miller [13].For a computable structure${\cal S}$, we introduce the notion of the spectral dimension of${\cal S}$, which gives a quantitative characteristic of the degree of categoricity of${\cal S}$. We prove that for a nonzero natural numberN, there is a computable rigid structure${\cal M}$such that$0\prime$is the degree of categoricity of${\cal M}$, and the spectral dimension of${\cal M}$is equal toN.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1017/jsl.2017.70
Options
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: 62,268
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Categoricity Spectra for Rigid Structures.Ekaterina Fokina, Andrey Frolov & Iskander Kalimullin - 2016 - Notre Dame Journal of Formal Logic 57 (1):45-57.
Stability of Recursive Structures in Arithmetical Degrees.C. J. Ash - 1986 - Annals of Pure and Applied Logic 32:113-135.

View all 6 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Categoricity Spectra for Rigid Structures.Ekaterina Fokina, Andrey Frolov & Iskander Kalimullin - 2016 - Notre Dame Journal of Formal Logic 57 (1):45-57.
Degrees That Are Not Degrees of Categoricity.Bernard Anderson & Barbara Csima - 2016 - Notre Dame Journal of Formal Logic 57 (3):389-398.
Categoricity Spectra for Polymodal Algebras.Nikolay Bazhenov - 2016 - Studia Logica 104 (6):1083-1097.
Categoricity and Mathematical Knowledge.Fernando Ferreira - 2017 - Revista Portuguesa de Filosofia 73 (3-4):1423-1436.
On Downey's Conjecture.Marat M. Arslanov, Iskander Sh Kalimullin & Steffen Lempp - 2010 - Journal of Symbolic Logic 75 (2):401-441.
On an Application of Categoricity.Alexander Paseau - 2005 - Proceedings of the Aristotelian Society 105 (3):411–415.
Categoricity in Hyperarithmetical Degrees.C. J. Ash - 1987 - Annals of Pure and Applied Logic 34 (1):1-14.

Analytics

Added to PP index
2018-05-03

Total views
18 ( #584,017 of 2,444,966 )

Recent downloads (6 months)
2 ( #311,040 of 2,444,966 )

How can I increase my downloads?

Downloads

My notes