Degrees of categoricity and treeable degrees

Journal of Mathematical Logic (forthcoming)
  Copy   BIBTEX

Abstract

In this paper, we give a characterization of the strong degrees of categoricity of computable structures greater or equal to [Formula: see text]. They are precisely the treeable degrees — the least degrees of paths through computable trees — that compute [Formula: see text]. As a corollary, we obtain several new examples of degrees of categoricity. Among them we show that every degree [Formula: see text] with [Formula: see text] for [Formula: see text] a computable ordinal greater than [Formula: see text] is the strong degree of categoricity of a rigid structure. Using quite different techniques we show that every degree [Formula: see text] with [Formula: see text] is the strong degree of categoricity of a structure. Together with the above example this answers a question of Csima and Ng. To complete the picture we show that there is a degree [Formula: see text] with [Formula: see text] that is not the degree of categoricity of a rigid structure.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,873

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

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 Rigid Structures.Ekaterina Fokina, Andrey Frolov & Iskander Kalimullin - 2016 - Notre Dame Journal of Formal Logic 57 (1):45-57.
Infima of d.r.e. degrees.Jiang Liu, Shenling Wang & Guohua Wu - 2010 - Archive for Mathematical Logic 49 (1):35-49.
Bi-Isolation in the D.C.E. Degrees.Guohua Wu - 2004 - Journal of Symbolic Logic 69 (2):409 - 420.
Bi-isolation in the d.c.e. degrees.Guohua Wu - 2004 - Journal of Symbolic Logic 69 (2):409-420.

Analytics

Added to PP
2023-07-12

Downloads
6 (#1,479,724)

6 months
3 (#1,036,110)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references