Armin Hemmerling
Preprint series:
Preprintreihe Mathematik 2003, 25
MSC 2000
- 03D65 Higher-type and set recursion theory
-
03D80 Applications of computability and recursion theory
-
03D55 Hierarchies
-
03E15 Descriptive set theory
-
03F60 Constructive and recursive analysis
-
26E40 Constructive real analysis
-
68Q01 General
Abstract
The topological arithmetical
hierarchy is an effective version of the Borel hierarchy. Its
class $\Delta^{\mbox{ta}}_2$ is just large enough to include several types
of
sets of points in Euclidean spaces $\R^k$ which are fundamental in
computable analysis. As a crossbreed of Hausdorff's difference
hierarchy in the Borel class $\Delta^{\mbox{B}}_2$ with
Ershov's hierarchy within $\Delta^0_2$, the Hausdorff-Ershov hierarchy
introduced in this paper gives a useful substructure within
$\Delta^{\mbox{ta}}_2$. This is based on suitable characterizations of the
sets
from $\Delta^{\mbox{ta}}_2$ which are developed in a close analogy to those
of
the $\Delta^{\mbox{B}}_2$ sets as well as those of the $\Delta^0_2$ sets.
So the paper also reviews some classical results
of descriptive set theory and recursion theory
from a unifying point of
view. A helpful tool is contributed by the technique of depth
analysis. The Hausdorff-Ershov hierarchy turns out to be even less
complicated, in a sense, than Ershov's hierarchy. It also allows
new characterizations of concepts of decidability for sets of
points in Euclidean spaces.
This document is well-formed XML.
