The Hausdorff-Ershov Hierarchy in Euclidean Spaces

Archive for Mathematical Logic 45 (3):323-350 (2005)

Abstract
The topological arithmetical hierarchy is the effective version of the Borel hierarchy. Its class Δta 2 is just large enough to include several types of pointsets in Euclidean spaces ℝ k which are fundamental in computable analysis. As a crossbreed of Hausdorff's difference hierarchy in the Borel class ΔB 2 and Ershov's hierarchy in the class Δ0 2 of the arithmetical hierarchy, the Hausdorff-Ershov hierarchy introduced in this paper gives a powerful classification within Δta 2. This is based on suitable characterizations of the sets from Δta 2 which are obtained in a close analogy to those of the ΔB 2 sets as well as those of the Δ0 2 sets. A helpful tool in dealing with resolvable sets is contributed by the technique of depth analysis. On this basis, the hierarchy properties, in particular the strict inclusions between classes of different levels, can be shown by direct constructions of witness sets. The Hausdorff-Ershov hierarchy runs properly over all constructive ordinals, in contrast to Ershov's hierarchy whose denotation-independent version collapses at level ω 2. Also, some new characterizations of concepts of decidability for pointsets in Euclidean spaces are presented
Keywords Computable analysis  Effective descriptive set theory  Hausdorff's difference hierarchy  Ershov's hierarchy  Topological arithmetical hierarchy  Resolvable sets  Global and local depth of sets  Recursivity in analysis  Approximate decidability
Categories (categorize this paper)
Reprint years 2006
DOI 10.1007/s00153-005-0317-8
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 47,395
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

Recursive Structures and Ershov's Hierarchy.Christopher J. Ash & Julia F. Knight - 1996 - Mathematical Logic Quarterly 42 (1):461-468.
Characterizations of the classΔta2 Over Euclidean Spaces.Armin Hemmerling - 2004 - Mathematical Logic Quarterly 50 (45):507-519.
Approximate Decidability in Euclidean Spaces.Armin Hemmerling - 2003 - Mathematical Logic Quarterly 49 (1):34-56.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Approximate Decidability in Euclidean Spaces.Armin Hemmerling - 2003 - Mathematical Logic Quarterly 49 (1):34-56.
On Genericity and Ershov's Hierarchy.Amy Gale & Rod Downey - 2001 - Mathematical Logic Quarterly 47 (2):161-182.
Recursive Structures and Ershov's Hierarchy.Christopher J. Ash & Julia F. Knight - 1996 - Mathematical Logic Quarterly 42 (1):461-468.
A Hierarchy of Hereditarily Finite Sets.Laurence Kirby - 2008 - Archive for Mathematical Logic 47 (2):143-157.
An Analysis of the W -Hierarchy.Yijia Chen, Jörg Flum & Martin Grohe - 2007 - Journal of Symbolic Logic 72 (2):513 - 534.
Index Sets in Ershov's Hierarchy.Jacques Grassin - 1974 - Journal of Symbolic Logic 39 (1):97-104.

Analytics

Added to PP index
2013-11-23

Total views
31 ( #301,978 of 2,291,776 )

Recent downloads (6 months)
1 ( #825,549 of 2,291,776 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature