Computable categoricity and the Ershov hierarchy

, &
Annals of Pure and Applied Logic 156 (1):86-95 (2008)
  Copy   BIBTEX

Abstract

In this paper, the notions of Fα-categorical and Gα-categorical structures are introduced by choosing the isomorphism such that the function itself or its graph sits on the α-th level of the Ershov hierarchy, respectively. Separations obtained by natural graphs which are the disjoint unions of countably many finite graphs. Furthermore, for size-bounded graphs, an easy criterion is given to say when it is computable-categorical and when it is only G2-categorical; in the latter case it is not Fα-categorical for any recursive ordinal α

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2008.06.010

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,349

External links

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

Through your library

My notes

Similar books and articles

Equivalence structures and isomorphisms in the difference hierarchy.Douglas Cenzer, Geoffrey LaForte & Jeffrey Remmel - 2009 - Journal of Symbolic Logic 74 (2):535-556.
Rogers semilattices of families of two embedded sets in the Ershov hierarchy.Serikzhan A. Badaev, Mustafa Manat & Andrea Sorbi - 2012 - Mathematical Logic Quarterly 58 (4-5):366-376.
The Hausdorff-Ershov Hierarchy in Euclidean Spaces.Armin Hemmerling - 2006 - Archive for Mathematical Logic 45 (3):323-350.
Degrees of Categoricity and the Hyperarithmetic Hierarchy.Barbara F. Csima, Johanna N. Y. Franklin & Richard A. Shore - 2013 - Notre Dame Journal of Formal Logic 54 (2):215-231.
Degrees of categoricity of computable structures.Ekaterina B. Fokina, Iskander Kalimullin & Russell Miller - 2010 - Archive for Mathematical Logic 49 (1):51-67.
Characterizations of the class ~2^t^a over Euclidean spaces.Armin Hemmerling - 2004 - Mathematical Logic Quarterly 50 (4):507.
The discrete parts of approximately decidable sets in Euclidean spaces.Armin Hemmerling - 2003 - Mathematical Logic Quarterly 49 (4):428.
Recursive Structures and Ershov's Hierarchy.Christopher J. Ash & Julia F. Knight - 1996 - Mathematical Logic Quarterly 42 (1):461-468.
On Genericity and Ershov's Hierarchy.Amy Gale & Rod Downey - 2001 - Mathematical Logic Quarterly 47 (2):161-182.
On Σ₁-Structural Differences among Finite Levels of the Ershov Hierarchy.Yue Yang & Liang Yu - 2006 - Journal of Symbolic Logic 71 (4):1223 - 1236.
On the complexity of categoricity in computable structures.Walker M. White - 2003 - Mathematical Logic Quarterly 49 (6):603.
Effective algebraicity.Rebecca M. Steiner - 2013 - Archive for Mathematical Logic 52 (1-2):91-112.
Monotonically Computable Real Numbers.Robert Rettinger, Xizhong Zheng, Romain Gengler & Burchard von Braunmühl - 2002 - Mathematical Logic Quarterly 48 (3):459-479.

Analytics

Added to PP
2013-12-26

Downloads
23 (#664,515)

6 months
8 (#342,364)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Σ 1 0 and Π 1 0 equivalence structures.Douglas Cenzer, Valentina Harizanov & Jeffrey B. Remmel - 2011 - Annals of Pure and Applied Logic 162 (7):490-503.

Add more citations

References found in this work

Limiting recursion.E. Mark Gold - 1965 - Journal of Symbolic Logic 30 (1):28-48.
Δ20-categoricity in Boolean algebras and linear orderings.Charles F. D. McCoy - 2003 - Annals of Pure and Applied Logic 119 (1-3):85-120.
< i> Δ_< sub> 2< sup> 0-categoricity in Boolean algebras and linear orderings.Charles F. D. McCoy - 2003 - Annals of Pure and Applied Logic 119 (1-3):85-120.
A proof of Beigel's cardinality conjecture.Martin Kummer - 1992 - Journal of Symbolic Logic 57 (2):677-681.

Add more references