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

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 α
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2008.06.010
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: 71,316
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

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

Citations of this work BETA

Σ 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

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 index

Total views
14 ( #735,166 of 2,519,509 )

Recent downloads (6 months)
1 ( #407,153 of 2,519,509 )

How can I increase my downloads?


My notes