Computable categoricity and the Ershov hierarchy

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


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 α



    Upload a copy of this work     Papers currently archived: 89,718

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

The Hausdorff-Ershov Hierarchy in Euclidean Spaces.Armin Hemmerling - 2006 - Archive for Mathematical Logic 45 (3):323-350.
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 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.


Added to PP

16 (#766,637)

6 months
1 (#1,018,209)

Historical graph of downloads
How can I increase my downloads?

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.
A proof of Beigel's cardinality conjecture.Martin Kummer - 1992 - Journal of Symbolic Logic 57 (2):677-681.

Add more references