Recursive Structures and Ershov's Hierarchy

&
Mathematical Logic Quarterly 42 (1):461-468 (1996)
  Copy   BIBTEX

Abstract

Ash and Nerode [2] gave natural definability conditions under which a relation is intrinsically r. e. Here we generalize this to arbitrary levels in Ershov's hierarchy of Δmath image sets, giving conditions under which a relation is intrinsically α-r. e

Categories

Keywords

Reprint years

DOI

10.1002/malq.19960420138

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,891

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

Some effects of Ash–Nerode and other decidability conditions on degree spectra.Valentina S. Harizanov - 1991 - Annals of Pure and Applied Logic 55 (1):51-65.
The discrete parts of approximately decidable sets in Euclidean spaces.Armin Hemmerling - 2003 - Mathematical Logic Quarterly 49 (4):428.
The Hausdorff-Ershov Hierarchy in Euclidean Spaces.Armin Hemmerling - 2006 - Archive for Mathematical Logic 45 (3):323-350.
A Completeness Theorem for Certain Classes of Recursive Infinitary Formulas.Christopher J. Ash & Julia F. Knight - 1994 - Mathematical Logic Quarterly 40 (2):173-181.
Characterizations of the class ~2^t^a over Euclidean spaces.Armin Hemmerling - 2004 - Mathematical Logic Quarterly 50 (4):507.
Inseparability in recursive copies.Kevin J. Davey - 1994 - Annals of Pure and Applied Logic 68 (1):1-52.
Characterizations of the class Δ ta 2 over Euclidean spaces.Armin Hemmerling - 2004 - Mathematical Logic Quarterly 50 (4-5):507-519.
Index sets in Ershov's hierarchy.Jacques Grassin - 1974 - Journal of Symbolic Logic 39 (1):97-104.
Possible degrees in recursive copies II.C. J. Ash & J. F. Knight - 1997 - Annals of Pure and Applied Logic 87 (2):151-165.
On Genericity and Ershov's Hierarchy.Amy Gale & Rod Downey - 2001 - Mathematical Logic Quarterly 47 (2):161-182.

Analytics

Added to PP
2013-12-01

Downloads
26 (#598,207)

6 months
9 (#437,668)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Turing degrees of certain isomorphic images of computable relations.Valentina S. Harizanov - 1998 - Annals of Pure and Applied Logic 93 (1-3):103-113.
Characterizations of the class Δ ta 2 over Euclidean spaces.Armin Hemmerling - 2004 - Mathematical Logic Quarterly 50 (4-5):507-519.
The Hausdorff-Ershov Hierarchy in Euclidean Spaces.Armin Hemmerling - 2006 - Archive for Mathematical Logic 45 (3):323-350.

View all 6 citations / Add more citations

References found in this work

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.

Add more references