Degrees of categoricity and spectral dimension

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

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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,466

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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
2018-05-03

Downloads
23 (#495,968)

6 months
4 (#171,914)

Historical graph of downloads
How can I increase my downloads?