Arch. Math. Logic 45, 323–350 (2006) Digital Object Identifier (DOI): 10.1007/s00153-005-0317-8

Mathematical Logic

Armin Hemmerling

The Hausdorff-Ershov Hierarchy in Euclidean Spaces Received: 16 March 2004 / Revised version: 23 September 2004 Published online: 10 November 2005 – © Springer-Verlag 2005 Abstract. The topological arithmetical hierarchy is the effective version of the Borel hierarchy. Its class
ta2 is just large enough to include several types of pointsets in Euclidean spaces Rk which are fundamental in computable analysis. As a crossbreed of Hausdorff’s difference hierarchy in the Borel class
B2 and Ershov’s hierarchy in the class
02 of the arithmetical hierarchy, the Hausdorff-Ershov hierarchy introduced in this paper gives a powerful classification within
ta2 . This is based on suitable characterizations of the sets from
ta2 which are obtained in a close analogy to those of the
B2 sets as well as those of the
02 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.

1. Introduction Hierarchies play an important role in set theoretic topology and descriptive set theory as well as in recursion theory and computable analysis. The similarities between the Borel hierarchy of finite order (BH) over the Euclidean spaces Rk and the arithmetical hierarchy (AH) over the discrete universes Nk were paradigmatic for the development of a unified effective descriptive set theory by Moschovakis in [20]. The effective version of the Borel hierarchy, in the present paper denoted as topological arithmetical hierarchy (TAH), consists of classes of effectively characterized subsets in Rk . It is fundamental for computable analysis and several areas connected with it, even if the related interest is mainly directed to the lower levels of that hierarchy and if some different systems of denotations are still in use. For a rough impression, the reader is referred to [16, 28, 7]. In particular, many notions of computable analysis concerning pointsets form subclasses of
ta 2 in the TAH. This applies especially to the several notions of A. Hemmerling: Ernst-Moritz-Arndt–Universit¨at Greifswald, Institut f¨ur Mathematik und Informatik, Friedrich-Ludwig-Jahn–Str. 15a, 17487 Greifswald, Germany. e-mail: [email protected] Key words or phrases: 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 Mathematics Subject Classification (2000): 03D65, 03D55, 03E15, 03F60, 26E40, 68Q01

324

A. Hemmerling

decidability in Euclidean spaces, cf. [9]. Notice in this context that all partial real −→ R, which are computable from the approximate point of functions f : Rk
view that we take throughout this paper, are continuous on their domains. Thus, the characteristic functions of non-trivial sets cannot be computable, and the classical way of defining decidability of sets by the computability of the characteristic functions does not work. In fact, the problem of defining decidability for pointsets in Euclidean spaces, in a generally accepted way, has not yet been finally solved so far. This has explicitly been stressed by Penrose’s question in [22] whether the Mandelbrot set is decidable (or recursive) in some sense. So the class
ta 2 of the TAH is already large enough to include many classes of pointsets which are important in computable analysis and around. Hence it is highly desirable to have some substructure giving a finer classification for the members of that class, i.e., to establish a hierarchy of subclasses within
ta 2 . Like the TAH can be seen as a crossbreed of the BH with the AH, a hierarchy within
ta 2 can be established by using both principles of Hausdorff’s difference hierarchy within the Borel class
B 2 as well as techniques developed by Ershov and others in order to classify 0 the
2 sets of the AH. The resulting Hausdorff-Ershov hierarchy (HEH) seems indeed to provide a powerful tool in investigating and localizing several subclasses of
ta 2 . Surprisingly, it has not yet been considered so far over Euclidean spaces. Most of our techniques could also be applied to more general effective metric or topological spaces as specified, e.g., in [27, 8]. Nevertheless, throughout this paper we concentrate ourselves to the case of Euclidean spaces Rk with their natural topology. They are surely the most important universes from the viewpoint of computable analysis. With respect to some problems, the Cantor space {0, 1}ω and the Baire space Nω behave even easier than Euclidean spaces. An example of this kind is presented by the Wadge hierarchy, see [26, 28, 24]. It consists of classes of subsets, which are compared w.r.t. the reducibility by means of continuous functions. On the Cantor and the Baire space, the Wadge hierarchy is almost well-founded, cf. [24]. In contrast to this, reducibility by continuous functions yield a much more complicated structure if it is applied to subsets of Rk . This was discussed in [9] generalizing results from [12]. Even if the elements of the Cantor or the Baire space are sometimes simply denoted as “the real numbers”, there are considerable topological differences between the connected Euclidean spaces and the totally disconnected spaces of sequences w.r.t. the Baire metric. Many serious problems of computable analysis are just caused by these differences on the one hand and the wish or demand, on the other hand, to represent the real numbers by sequences of bits or other symbols, since only the latter ones can directly be processed by discrete devices like Turing machines. In [24], Selivanov considered effective Wadge hierarchies exhausting the related
02 classes of the Cantor and Baire space, respectively. Their definition is based on certain effective difference chains, and the proof of the exhaustion result applies techniques similar to those from [3, 2], which we adapted too, in order to obtain the main result in [10]. For an example of difference hierarchies in other types of spaces, the reader is referred to [25].

The Hausdorff-Ershov Hierarchy in Euclidean Spaces

325

The present paper establishes the HEH, shows the basic hierarchy properties and considers the notions of decidability introduced in [9] within the developed framework. The basic notions are taken over from [10], where also some fundamental relationships of computable analysis and recursion theory are reported. Section 2 summarizes characterizations of the
2 classes within the BH, the AH and the TAH. They were also discussed and proved in detail in [10], but are now put into a general unified framework. For example, the notion of α-resolvability is transferred from pointsets to discrete universes, whereas the α-openess of pointsets is an analogue of α-recursive enumerability connected with the Ershov hierarchy over the natural numbers. The related effective versions for pointsets are the toprecursive α-resolvability and the α-toprecursive exhaustibility (α-t.r.ex.), respectively. Section 3 deals with several tools from descriptive set theory, such as depth analysis, resolutions of sets and weak characteristic functions. Even if some of them are essentially known already from Hausdorff’s book [4], our presentation will contribute several new details, e.g., the existence of greedy resolutions and weak characteristic functions for resolvable pointsets. Section 4 reports both the Haus0 dorff hierarchy within
B 2 and Ershov’s hierarchy within
2 from a unified point of view which is then applied to establish and investigate the HEH. In particular, the hierarchy properties can simply be shown by effectivizing a related proof for the Hausdorff hierarchy, which employs suitably constructed pointsets defined by means of weak semi-characteristic functions. Finally, Section 5 applies the framework of HEH in order to characterize straightforward generalizations of notions of decidability for pointsets which were introduced in [9]. So this paper can be seen as a direct continuation of [10]. Meanwhile, as we can just say in writing the present paper’s final version, a third paper [11] on a closely related subject is available. It deals with hierarchies of classes of partial functions which are established analogously to the hierarchies of classes of pointsets in the present paper.

2. Resolutions and weak characteristic functions Throughout this paper, we will use the same basic notions and notations as they were introduced in [10], Section 2. For notations and fundamental facts on constructive ordinals, the reader is referred to Section 5 (page 515) in [10].  In the present section, two versions of characterizations of
2 sets, for  ∈ {B, ta, 0}, are reported. They are closely related to each other and form the basis  on which the hierarchies exhausting the classes
2 will be introduced and discussed later. For some further characterizations and details, the reader is again referred to [10]. Here we only remark that a limit characterization, as it is given by Shoenfield’s lemma for
02 , is analogously available both for the class
B 2 as well as for
ta in the TAH. Also, characterizations by difference chains of open, 2 t.r.ex. and r.e. sets, respectively, are possible. However, they yield only the initial segments corresponding to finite levels of the hierarchies based on resolutions or weak characteristic functions we now are going to deal with.

326

A. Hemmerling

For an arbitrary sequence of sets, S = (Sξ )ξ <α with an ordinal number α > 0, let RDC(S) denote the result of the related difference chain, i.e.,
 (Sξ \ Sξ +1 ) if α is even , RDC(S) = ξ <α , ξ is even   if α is odd and α = α + 1 . (S \ S ) ∪ S  ξ ξ +1 α ξ <α , ξ is even By Hausdorff [4, 5], cf. also [19, 14], a set A (in an arbitrary metric or topological space) is called resolvable iff there is a decreasing sequence of closed sets, F = (Fξ )ξ <α , Fη ⊇ Fξ for η ≤ ξ < α, such that RDC(F) = A. More precisely, we shall also say that A is α-resolvable in this case, and the sequence F is called a resolution (of length α) or an (α-) resolution of A. Let also the empty resolution ∅ = (Fξ )ξ <0 be allowed, where RDC(∅) = ∅. The prolongation of a resolution F by the emptyset Fα = ∅ yields the sequence F  = (Fξ )ξ <α+1 with RDC(F  ) = RDC(F) and ξ <α+1 Fξ = ∅ . On the other hand, all empty sets in resolutions are superfluous w.r.t. the result of the difference chain. Moreover, given a resolution F = (Fξ )ξ <α , one can inductively define a strictly increasing sequence of ordinals, (βξ )ξ <α  , with α  ≤ α such that F  = (Fβξ )ξ <α  is strictly decreasing, i.e., Fβξ ⊃ Fβη for ξ < η < α  , and RDC(F  ) = RDC(F). Thus, each resolvable set is representable by a strict resolution, i.e., by the difference chain of a strictly decreasing sequence of non-empty closed sets. One easily sees that for any strict α-resolution in a separable space like Rk , the length α must belong to the second number class CII . Remark. The notion of ω-resolvability introduced in [9] is more restrictive than that of α-resolvability defined above, for α = ω. More precisely, ω-resolvability of a set A in the sense of [9] means that both A and A are α-resolvable for α = ω in the above defined sense. This will turn out to be equivalent to the ω-clopeness of A in the sense defined below. The following basic result characterizing the
B 2 sets by means of resolvability is due to Hausdorff [4]. Proposition 1. A pointset belongs to
B 2 iff it is resolvable, i.e., iff it is α-resolvable for some ordinal α ∈ CII . For the practical use, it is often more convenient to work with weak semi-characteristic functions instead of resolutions. This notion is obtained by transferring an analogue introduced by Epstein-Haas-Kramer [2] in dealing with Ershov’s hierarchy. By a weak semi-characteristic function, briefly: WSF, (of length α ) of a set A ⊆ Rk , we understand a partial function g : Rk × CII
−→ {0, 1} such that: 1. the sets Gβ,b = {x : g(x, β) = b} are open for all ordinals β ( < α ) and b ∈ {0, 1}, and 2. for all x ∈ Rk it holds x ∈ A iff there is an ordinal β ( < α ) for which g(x, β) ↓ , and g(x, βx ) = 1 for βx = min{β : g(x, β) ↓ }. A set A ⊆ Rk is called α-open iff it has a WSF of length α.

The Hausdorff-Ershov Hierarchy in Euclidean Spaces

327

Obviously, ∅ is the only 0-open set, the 1-open sets are just the (topologically) open sets, whereas the class of 2-open sets includes already the closed pointsets. A WSF g of length α can always be thought to be restricted to ordinals β < α as the second arguments, i.e., g : Rk × α
−→ {0, 1}. Notice that for α > 1 a set has infinitely many WSFs of length α if it has such one at all, see also the end of Section 3. The following result shows the close relationships between α-openess and αresolvability. Lemma 1. For each ordinal α and any set A ⊆ Rk , we have: if α is even, then A is α-open iff it is α-resolvable; if α is odd, then A is α-open iff A is α-resolvable. To prove this, we first suppose that α is even. If g is a WSF of length α for a set A, then we put for each even ordinal β < α : Fβ = {x : g(x, ξ ) ↑ for all ξ < β, and g(x, β) = 1 or g(x, β) ↑ } , Fβ+1 = {x : x ∈ Fβ , g(x, β) ↑ , and g(x, β + 1) = 0 or g(x, β + 1) ↑ }. Then F = (Fξ )ξ <α is a decreasing sequence of closed sets, and A = RDC(F). Conversely, let A = RDC(F) for a decreasing α-sequence F = (Fξ )ξ <α of closed sets. Then we put for all even β < α:

0 if x ∈ Fβ , 1 if x ∈ Fβ+1 , g(x, β) and g(x, β + 1) ↑ if x ∈ Fβ , ↑ if x ∈ Fβ+1 . This yields a WSF g showing that A is α-open. Now let α be an odd ordinal, hence α = α  +1 for an even α  . If A is α-open and g a corresponding WSF, we put g  (x, β) g(x, β), for all β < α, and g  (x, α) = 0. For β ≤ α let g(x, β) 1 − g  (x, β). Then g is a WSF of length α + 1 for the complement A, and it holds g(x, α) = 1 for all x ∈ Rk . Now let the sequence F = (Fβ )β<α+1 be defined as above for the even length α + 1 instead of α and with g instead of g. Then we have Fα = Fα  +1 = {x : g(x, β  ) ↑ for all β  < α  , g(x, α  ) = 0 or g(x, α  ) ↑ , and g  (x, α  +1) = 1 or g  (x, α  +1) ↑ } = ∅. Thus, A is α-resolvable. If, conversely, A is α-resolvable, then it has an (α + 1)-resolution (Fξ )ξ <α+1 with Fα = ∅. Let the WSF g of A be defined as above, for the even ordinal α + 1 instead of α. Then g(x, α) = 1 for all x ∈ Rk . Thus, x ∈ A iff g(x, βx ) = 0 for βx = min{β ≤ α : g(x, β) ↓}, and we have βx < α for all x ∈ A. Hence the function h(x, ξ ) 1 − g(x, ξ ), ξ < α, is a WSF of length α for the set A.   By a weak characteristic function, briefly: WCF, (of length α ) of a set A ⊆ Rk , we mean a partial function g : Rk × CII
−→ {0, 1} such that: 1. the sets Gβ,b = {x : g(x, β) = b } are open for all ordinals β ( < α ) and b ∈ {0, 1}, 2. for all x ∈ Rk , there is an ordinal β ( < α ) with g(x, β) ↓ , and 3. χA (x) = g(x, βx ), where βx = min{β : g(x, β) ↓}. A pointset A is said to be α-clopen iff it has a WCF of length α.

328

A. Hemmerling

In contrast to α-openess, the notion of α-clopeness is closed under complement: if g is a WCF of A, then 1 − g(x, ξ ) defines a WCF of the complement A, of the same length as g. If A is α-open, then it is (α + 1)-clopen: one has only to extend a WSF g : Rk × α
−→ {0, 1} of A by g(x, α) = 0. In the next section, we shall see that a set A is α-clopen iff both A and its complement A are α-open or, equivalently by Lemma 1, iff both A and A are α-resolvable. Thus, α-openess can be considered as the notion of decidability related to the notion of (non-effective) semi-decidability given by the α-openess or by the α-resolvability. The notions of α-openess and α-clopeness are not customary in descriptive set theory. In this paper, they are introduced in order to keep a close analogy to the following concepts of α-r.e. and α-recursive set, which are well-known from recursion theoretic papers around Ershov’s hierarchy, cf. [2, 1]. For a discrete set M ⊆ Nk , by a WSF (of length α) of M, we mean a partial −→ {0, 1} such that for all x ∈ Nk : function g : Nk × CII
x ∈ M iff there is an ordinal β < α for which g(x, β) ↓ , and g(x, βx ) = 1 for βx = min{β : g(x, β) ↓ }. If, moreover, for all x ∈ Nk , there is an ordinal β < α such that g(x, β) ↓ , then we have always χM (x) = g(x, βx ) , and g is called a WCF (of length α) of the set M. For a constructive ordinal α and a corresponding (r.r.u.) naming system S, a set M ⊆ Nk is said to be α/S-r.e. iff there is an S-computable WSF g of length α, and M is called α/S-recursive iff there is such a WCF g of M. In both cases, the S-computability of the function g implies that the preimage sets Gβ,b = {x ∈ Nk : g(x, β) = b } are r.e., even uniformly for all β < α and b ∈ {0, 1}. More precisely, there is a partial recursive function ϕ : N × {0, 1}
−→ N such that Gβ,b = Wϕ(n,b) whenever νS (n) = β < α. If, for some constructive ordinal α, there is a naming system S witnessing that M is α/S-r.e. and α/S-recursive, respectively, we say that the set M is α-r.e. resp. α-recursive. Obviously, every α (/S)-r.e. set is (α + 1) (/S)-recursive if α + 1 ∈ ran(νS ). Moreover, one easily proves Lemma 2. A set M ⊆ Nk is α (/S)-recursive iff both M and Nk \ M are α (/S)-r.e. As an effective counterpart of α-resolvability, a set M ⊆ Nk is called recursively α/S-resolvable iff M = RDC(V), for an S-computable decreasing sequence of length α of co-r.e. sets, V = ( W f (β) )β<α with an S-computable function f : α −→ N. The proof of Lemma 1 can immediately be effectivized, and we have Lemma 3. For each r.r.u. system α/S and any set M ⊆ Nk it holds: if α is even, then M is α/S-r.e. iff it is recursively α/S-resolvable; if α is odd, then M is α/S-r.e. iff Nk \ M is recursively α/S-resolvable. Finally, we recall Ershov’s fundamental result from [3], see also [2].

The Hausdorff-Ershov Hierarchy in Euclidean Spaces

329

Proposition 2. A set M ⊆ Nk belongs to
02 iff there are a constructive ordinal α and a (r.r.u.) naming system S such that M is α/S-r.e. On the other hand, every member of
02 is already ω2 -recursive. After these preparations, the definitions of the related effective notions for pointsets are nearly straightforward. For a naming system α/S, a set A ⊆ Rk is called α/S-t.r.ex. (this means α/S-toprecursively exhaustible) iff it has an S-computable WSF of length α. Notice that an S-computation of a WSF g has to be performed by an OTM now. It follows that the preimages Gβ,b = {x ∈ Rk : g(x, β) = b } are uniformly t.r.ex., for all β < α and b ∈ {0, 1}. This means that there is a partial recursive function ϕ : N × {0, 1}
−→ N such that Gβ,b = Xϕ(n,b) whenever νS (n) = β. Indeed, given an OTM M performing the S-computation of g, the sets Gβ,b can effectively be exhausted by rational open balls, simply by feeding M with all finite initial parts w of Cauchy sequences σ and exhausting succes|w|−1 sively the union of all sets i=0 Ball2−i (qw(i) ), for which Mw (νS−1 (β)) = b. By Mw (n) = b, we mean that the machine halts with the output b and has put only oracle queries of form “m ?” for m < |w|, when it was fed with an (arbitrary) infinite prolongation σ of the finite string w. The following effective counterpart of α-resolvability is suggested: For a naming system α/S, a set A ⊆ Rk is called toprecursively α/S-resolvable iff A = RDC(Y) for a decreasing S-computable sequence Y of co-t.r.ex. sets, i.e., Y = ( Xf (β) )β<α , with an S-computable function f : α −→ N. By the straightforward effectivization of the proof of Lemma 1, we have Lemma 4. For each r.r.u. system α/S and any set A ⊆ Rk it holds: if α is even, then A is α/S-t.r.ex. iff it is toprecursively α/S-resolvable; if α is odd, then A is α/S-t.r.ex. iff A is toprecursively α/S-resolvable. Finally, a set A ⊆ Rk is said to be α/S-toprecursive iff it has an S-computable WCF of length α. Lemma 5. A pointset A is α/S-toprecursive iff both A and A are α/S-t.r.ex. The only-if-part is obvious. The proof of the if-part requires a some more effort. The crucial point consists in representing the points x ∈ Rk by special Cauchy sequences of k-tuples of dyadic rational numbers, instead of the representation by sequences from CFx according to our standard notations. More precisely, by D and Dn , we denote the sets of dyadic numbers  and of those of precision n, respectively. Thus, Dn = {z·2−n : z ∈ Z} and D = n∈N Dn . Let be fixed an injective standard numbering of the dyadic numbers, νD = (dn : n ∈ N), which is injectively transferred to higher dimensions by Cantors k-tuple function. So we have Dk = {dn : n ∈ N} and dn = dn if n = n . The points x ∈ Rk are represented by the sequences σ ∈ Nω for which dσ (n) ∈ Dnk and x ∈ cl (Ball2−n (dσ (n) )) for all n ∈ N. Let DCFx denote the set of all such sequences, where x ∈ Rk . This modified representation, called DCF-representation, is computationally equivalent to the standard one. Moreover, the sets DCFx are always compact w.r.t. the Baire metric in Nω . For these details, we again refer to [10]. To sketch the proof of the if-part of the lemma, let be given OTMs M0 and M1 computing functions g0 , g1 : Rk × α
−→ {0, 1} witnessing that pointsets A and

330

A. Hemmerling

A, respectively, are α/S-t.r.ex., however w.r.t. the DCF-representation. This means that the arguments x have to be given to the machines by oracle sequences from DCFx . To compute, also w.r.t. the DCF-representation, a function g showing that A is α/S-toprecursive, let an OTM M, on input n and oracle sequence σ ∈ DCFx , simulate both M0 and M1 for all initial words w, ordered by increasing lengths, of sequences from DCFx . Each of these simulations has to be performed only as long as the oracle queries refer to elements from w. The related outputs, if there are any, are denoted by Mw i (n), i ∈ {0, 1}. Let the process of simulations stop at the   moment when it is realized that Mσ0 (n) = 1 for all σ  ∈ DCFx or Mσ1 (n) = 1 for all σ  ∈ DCFx . Then M has to output g(x, νS (n)) = 0 and g(x, νS (n)) = 1, respectively. For βx = min{β : g0 (x, β) ↓ or g1 (x, β) ↓} and νS (n) = βx , this situation occurs at some time, and then g(x, βx ) = χA (x). Indeed, the compactness of DCFx w just ensures that there is a number l ∈ N such that Mw 0 (n) ↓ or M1 (n) ↓, each for all initial words w of length l from sequences of DCFx . For β < βx , Mσ (νS−1 (β)) remains undefined. For β > βx , the value of Mσ (νS−1 (β)) doesn’t matter, it may be undefined or belong to {0, 1}. Of course, it has to be and is indeed independent on the special sequence σ ∈ DCFx .   The DCF-representations play also a crucial role in the proof of the following basic result obtained in [10]. Proposition 3. A pointset A belongs to
ta 2 iff there are a constructive ordinal α and a (r.r.u.) naming system S such that A is α/S-r.e. 3. Depth analysis and greediness ∂ For a closed set F ⊆ Rk and an arbitrary subset A ⊆ F , let A|◦F , A|cl F and A|F denote the interior, closure and boundary, respectively, of A relatively to F , where the latter is considered as a complete subspace of Rk . Thus, we have A|◦F = {B ∩F : B ∩  k cl {C ∩ F : A ⊆ C ∩ F, C is closed in Rk } F ⊆ A, B is open in R } , A|F = ∂ ∂ cl cl and A|F = A|F ∩ (F \ A)|F . Notice that A|cl F and A|F are closed sets, both w.r.t. Rk as well as w.r.t. the subspace F . For any pointset A ⊆ Rk , we define the sets Aξ, ◦ , A ξ, ◦ and Aξ, ∂ for all ordinal numbers ξ by transfinite recursion: ◦

A0, ◦ = A ,

◦

A 0, ◦ = A ,

and A0, ∂ = A∂ .

If Aη, ◦ , A η, ◦ and Aη, ∂ have been defined for all η < ξ , then let  ξ UA = Aη, ∂ , η<ξ

Aξ, ◦

= (A ∩ UA )|◦ ξ ,

A ξ, ◦ =

ξ

UA

ξ (A ∩ UA )|◦ ξ U

,

A

ξ

Aξ, ∂ = (A ∩ UA )|∂ ξ . UA

The Hausdorff-Ershov Hierarchy in Euclidean Spaces

331

In fact, the initial step for  ξ = 0 is also included in the second part of the ∅ = Rk . definition, since usually UA0 = Our definition is closely related to Hausdorff’s [4] construction of the sequence of residua of the set A, which was also adapted by Hertling and Weihrauch [12, 13] in defining their levels of discontinuity. The construction is well-known in descriptive set theory, cf. [15]. There the emphasis is mainly put on the sequence of the ξ ξ universes UA . Notice that UA = Aξ −1, ∂ if ξ is a successor number. In [9], where the main interest is directed to decidability of the set A, the sequences of the relative interiors, Aξ, ◦ , A ξ, ◦ , play a crucial role. They are indeed the basis of the decision of A in successive stages: At a first stage, the decision can be done for points from A0, ◦ and A 0, ◦ (with the results yes and no, respectively), whereas the critical points of A0, ∂ , in which A0, ◦ and A 0, ◦ touch each other, remain unprocessed. At the second stage, answers can be given for the points from A1, ◦ and A 1, ◦ , and the points from A1, ∂ remain unprocessed. Generally, at stage 1 + ξ , from the points of ξ UA , answers are obtained for the elements of Aξ, ◦ and A ξ, ◦ , whereas the points of ξ, A ∂ are left to be processed at a later stage. Of course, to get a notion of effective decidability, certain requirements of computability have to be fulfilled in addition. For further details, we refer to Section 5 and to the literature. Remark. Since in [9] the emphasis was put on the finite stages of decision beginning with the first one, there we started the related recursive definition with ξ = 1. ◦ ◦ So we defined A1, ◦ = A , A 1, ◦ = A , and A1, ∂ = A∂ , and the finite indices there are shifted by 1 compared with the present definition above. The latter one, however, is caused by the aim to have all ordinal numbers as indices of decision stages. This corresponds better to the set-theoretic point of view and simplifies some formulations in the sequel. A corresponding remark applies to the definition of depths below in this paper, which also slightly modifies those from [9]. ξ

Since the universes UA form a decreasing sequence of closed subsets of Rk , η ξ there is a least ordinal number α ∈ CII such that UAα = UAα+1 . Then UA ⊃ UA , for ξ all η < ξ < α, and UAα = UA , for all ξ ≥ α. If moreover UAα = ∅, we have A=

 ξ <α

Aξ, ◦ =

 ξ <α

( ( Aξ, ◦ ∪ Aξ, ∂ ) \ Aξ, ∂ ) ,

hence A is α-resolvable. Then, by the if-part of Proposition 1, A ∈
B .  2 Conversely, from B = Aα, ∂ = UAα = UAα+1 = Rk \( ξ <α Aξ, ◦ ∪ ξ <α A ξ, ◦ ), for some A ∈
B 2 , it follows that B = ∅. This is proved by standard techniques of descriptive set theory, cf. [4, 15], we omit the details. In particular, the only-if-part of Proposition 1 is obtained in this way. So we also have α Lemma 6. A ∈
B 2 iff there is an α ∈ CII such that UA = ∅.

Now we are going to show how the sequences of the Aξ, ◦ , A ξ, ◦ and Aξ, ∂ can be used to obtain a special shortest resolution of a set A. To this purpose, we start with E0 = A0, ◦ ∪A0, ∂ and E1 = A 1, ◦ ∪A1, ∂ . More general, for any finite i < ω,

332

A. Hemmerling

if λ = 0 or λ is a limit number, let Eλ+2i = Aλ+2i, ◦ ∪ Aλ+2i, ∂ , Eλ+2i+1 = A λ+2i+1, ◦ ∪ Aλ+2i+1, ∂ . β

If UA = ∅ for some ordinal β ≥ 1, which is supposed to be even, w.l.o.g., then we have  ( Aξ, ◦ ∪ Aξ +1, ◦ ) A= ξ <β, ξ is even  = ( Eξ \ Eξ +1 ). ξ <β, ξ is even

Moreover, (Eξ )ξ <β is a decreasing sequence of closed sets. Thus, it determines a resolution of A. The sequence of Eξ is even strictly decreasing as long as the boundaries Aξ, ∂ decrease strictly. To be more precise, we first recall Lemma 9 from [9]: Lemma 7. If Aξ, ◦ = ∅ for some ordinal ξ , then A ξ +1, ◦ = Aξ +2, ◦ = ∅; if A ξ, ◦ = ∅, then Aξ +1, ◦ = A ξ +2, ◦ = ∅. From Eλ+2i = Eλ+2i+1 (for a limit number λ or λ = 0, and i < ω) it follows Aλ+2i, ◦ = Aλ+2i+1, ◦ = ∅, hence, by Lemma 7, ∅ = A λ+2i+1, ◦ = A λ+2i+2, ◦ , and this implies that Aλ+2i, ∂ = Aλ+2i+1, ∂ = Aλ+2i+η, ∂ for all ordinals η.Analogously, Eλ+2i+1 = Eλ+2i+2 implies Aλ+2i+1, ∂ = Aλ+2i+η, ∂ for all η ≥ 1. So Eξ = Eξ +1 yields Eξ = Eξ +η = Aξ +η, ∂ , for all ordinals ξ and η. For resolvable sets A, this ξ +η+1 implies Eξ +η = ∅, since Aξ +η, ∂ = UA . If εA = min{ξ : Eξ = Eξ +1 }, the sequence (Eξ )ξ ≤εA is strictly decreasing w.r.t. inclusion, and EεA = ∅. So we have shown the first part of the following proposition. The second one is an essential sharpening of Lemma 10 in [9]. Proposition 4. For any resolvable set A ⊆ Rk , by E A = ( Eξ )ξ <εA

with

εA = min{ξ : Eξ = Eξ +1 }

a strict resolution of A is defined. If (Fξ )ξ <α is an arbitrary resolution of A, then we have εA ≤ α and Eξ ⊆ Fξ for all ordinals ξ < α. To prove the second part, we first show Eξ ⊆ Fξ by transfinite induction. The trivial case that A = ∅ can be excluded. Since E0 = A0, ◦ ∪ A0, ∂ = cl(A) is the smallest closed set including A and A ⊆ F0 , we have E0 ⊆ F0 . From A0, ∂ ⊆ E0 ⊆ F0 , it follows A ∩ A0, ∂ ⊆ F1 . Since E1 = A 1, ◦ ∪ A1, ∂ is the smallest closed set including A ∩ A0, ∂ , it holds E1 ⊆ F1 . In particular, A0, ∂ ⊆ F0 and A1, ∂ ⊆ F1 .  ξ Now let ξ be an even ordinal and suppose that UA ⊆ η<ξ Fη . Since Eξ =

Aξ, ◦ ∪ Aξ, ∂ is the smallest closed set including A ∩ UA , it follows Eξ ⊆ Fξ and  ξ +1 UA = Aξ, ∂ ⊆ η<ξ +1 Fη = Fξ . Analogously, we obtain Eξ +1 ⊆ Fξ +1 and   ξ +2 UA = Aξ +1, ∂ ⊆ η<ξ +2 Fη = Fξ +1 . It also follows UAλ ⊆ η<λ Fη , for any limit number λ < α. ξ

The Hausdorff-Ershov Hierarchy in Euclidean Spaces

333

So we have shown that Eξ ⊆ Fξ for all ξ < α. Since any resolution (Fξ )ξ <α can be extended by Fα = ∅, it also follows that Eα = Eα+1 = ∅, hence εA ≤ α.   Notice that Eα = ∅ implies Aα, ∂ = UAα+1 = ∅. This shows again that for ξ resolvable sets A the sequence of universes UA becomes ultimately stationary at  some index α  , with UAα = ∅. By Proposition 4, E A is a shortest resolution of a set A and any Eξ is the smallest possible element at index ξ , in an arbitrary resolution of A. So we shall refer to E A as the greedy resolution of A in the sequel. The process of deriving the sequences of Aξ, ◦ , A ξ, ◦ and Aξ, ∂ up to reaching ξ UA = ∅ at the first time will be referred to as the depth analysis of a (resolvable) set A. This is motivated by the following definitions. For a resolvable set A ⊆ Rk , the depth of a point x ∈ Rk (or the local depth of A at point x) is defined as depthA (x) = ξ

iff

x ∈ Aξ, ◦ ∪ A ξ, ◦ .

By the (global) supremum depth of the set A, we understand the ordinal number sdepth(A) = sup {depthA (x) : x ∈ Rk } . Sometimes it is convenient to distinguish between the set and its complement: sdepth+ (A) = sup{depthA (x) : x ∈ A} and sdepth− (A) = sup{depthA (x) : x ∈ A}. Obviously, sdepth(A) = 0 iff A ∈ {∅, Rk }. For any non-trivial closed set A ∈ {∅, Rk }, we have sdepth+ (A) = 1, sdepth− (A) = 0. It always holds sdepth(A) = max(sdepth+ (A), sdepth− (A)) and sdepth− (A) = sdepth+ (A). By Lemma 7, sdepth(A) ≤ min(sdepth+ (A), sdepth− (A)) + 1. Another measure of global depth is given by the first ξ at which the universe ξ UA is empty: ξ

ξ

udepth(A) = min {ξ : UA = ∅ } and udepth+ (A) = min {ξ : UA ∩ A = ∅ }. Hence udepth+ (A) ≤ udepth(A) ≤ sdepth(A) + 1. If udepth(A) is a limit number, it coincides with sdepth(A). If udepth(A) = ξ + 1, then sdepth(A) = ξ . Thus, for limit numbers λ and resolvable sets A, we have sdepth(A) = λ iff udepth(A) ∈ {λ, λ + 1}. So the function udepth yields a finer classification of sets than the function sdepth does. In the following lemma, the depth functions are used to characterize the length εA of the greedy resolution E A . Lemma 8. Let A be an arbitrary resolvable pointset. If sdepth(A) is a limit number or equal to 0, then εA = udepth+ (A) . If sdepth(A) is a successor number, then
εA =

max(sdepth+ (A), sdepth− (A)) + 1 if sdepth+ (A) is even , min(sdepth+ (A), sdepth− (A)) + 1 if sdepth+ (A) is odd .

334

A. Hemmerling

Let λ be a limit number or λ = 0. For sdepth(A) = λ, we have sdepth+ (A) = sdepth− (A) = λ. If there is no point x ∈ A with depthA (x) = λ, then Eλ = ∅ and εA = λ = udepth+ (A). If there is an x ∈ A with depthA (x) = λ, then Eλ = ∅, but Eλ+1 = ∅, i.e., εA = λ + 1 = udepth+ (A). If sdepth+ (A) = λ + 2i ≥ sdepth− (A), then Aλ+2i, ◦ = ∅ and Aλ+2i, ∂ = ∅. Hence, by definition of the sets of the greedy resolution, Eλ+2i = ∅, Eλ+2i+1 = ∅, and εA = λ+2i+1.Analogously, from sdepth+ (A) = λ+2i and sdepth− (A) = λ+ 2i + 1, it follows A λ+2i+1, ◦ = ∅, Aλ+2i+1, ∂ = ∅, Eλ+2i+1 = ∅ and Eλ+2i+2 = ∅, hence εA = λ + 2i + 2. From sdepth+ (A) = λ + 2i + 1 and sdepth− (A) = λ + 2i + 2, we obtain Eλ+2i+2 = Aλ+2i+2, ◦ ∪ Aλ+2i+2, ∂ = ∅, Eλ+2i+1 ⊇ Aλ+2i+1, ∂ ⊇ A λ+2i+2, ◦ = ∅, hence εA = λ + 2i + 2. If sdepth+ (A) = λ + 2i + 1 = sdepth− (A), then Eλ+2i+2 = ∅ and Eλ+2i+1 = ∅, thus εA = λ + 2i + 2. Finally, for sdepth+ (A) = λ + 2i + 1 and sdepth− (A) = λ + 2i, it follows Eλ+2i = ∅ and Eλ+2i+1 = ∅, i.e.,   εA = λ + 2i + 1. Now we give some examples illustrating the notions introduced so far. They will be employed and considered still more detailed in the following sections. Examples. Firstly, for all ordinals ξ ∈ CII , ξ ≥ 1, sets Aξ ⊆ R are recursively defined such that  Aξ ⊆ ( 21 , 1); (∗) depthAξ (x) < ξ for all x ∈ Aξ , and depthAξ (1) = sdepth(Aξ )  = sdepth− (Aξ ) = ξ . Notice that (∗) implies sdepth+ (Aξ ) = ξ − 1 if ξ is a successor number. For a limit number λ, we obtain sdepth+ (Aλ ) = λ, even if there is no point of Aλ that takes the local depth λ. For ξ = Aξ ∪ {1} , A ξ ) = sdepth+ (A ξ ) = depthA (1) = ξ . we have sdepth(A ξ The construction will use the real shrink function gsh : R −→ R defined by x gsh (x) = 1+|x| . This is a monotonously increasing homeomorphism mapping the whole real line onto the open interval (−1, 1). It transforms rational open intervals into rational open intervals, in an easily computable way, i.e., there is a recursive total function ϕ satisfying gsh [balln ] = ballϕ(n) , for all n ∈ N. Moreover, for any set A ⊆ R and any ordinal η ≥ 1, (gsh [A])η, ◦ = gsh [Aη, ◦ ], (gsh [A])η, ◦ ⊇ gsh [Aη, ◦ ] and (gsh [A])η, ∂ ⊆ gsh [Aη, ∂ ] ∪ {−1, 1}. The numbers −1 and 1 can in fact be accumulation points of (gsh [A])η, ◦ . This happens if Aη, ◦ contains sequences which diverge to −∞ resp. ∞. That is just a crucial point in the construction below. Moreover, if A ⊆ [a, b] and B ⊆ [c, d], for disjoint closed intervals [a, b] and [c, d], then for any x ∈ R,

The Hausdorff-Ershov Hierarchy in Euclidean Spaces

335

  depthA (x) if x ∈ [a, b] , depthA∪B (x) = depthB (x) if x ∈ [c, d] ,  0 if x ∈  [a, b] ∪ [c, d] .  The corresponding result holds also for countable unions i∈N Ai of sets Ai included in mutually disjoint closed intervals of lengths > y, for some real y > 0. The latter condition ensures that there is no convergent sequence (xi )i∈N , xi ∈ Ai . For ξ = 1, let Aξ = ( 21 , 1 ) . Obviously, the requirement (∗) is fulfilled. Given a set Aξ satisfying (∗), let
 {i + x : x ∈ Aξ } if i is even , B= Bi , where Bi = ξ } if i is odd . i∈N+ {i + x : x ∈ A It follows depthB (x) < ξ for all x ∈ B \ N+ and depthB (x) = ξ for all x ∈ N\{0, 1}, where the even positive integers belong to B but the odd doesn’t. Since the set {gsh (n) : n ∈ N } has its only accumulation point at number 1 and gsh (min B) = gsh ( 23 ) = 35 > 21 , by the set Aξ +1 = gsh [B] the requirement (∗) for ξ + 1 instead of ξ is fulfilled. Given sets Aξ satisfying (∗), for all ξ < λ, where λ is a limit number, let (ξi )i∈N be a countable sequence of ordinals such that limi→∞ ξi = λ. Then the requirement (∗) for ξ = λ is satisfied by the set Aλ obtained by
 {i + x : x ∈ Aξi } if i is even , and Bi , where Bi = Bλ = ξi } if i is odd , i∈N+ {i + x : x ∈ A Aλ = gsh [Bλ ] . The set Bλ defined above satisfies sdepth(Bλ ) = λ, but depthBλ (x) < λ for all ξ } and Cξ = Aξ ∪ A . Then sdepth(Cξ ) = x ∈ R. Finally, let Aξ = {−x : x ∈ A ξ sdepth+ (Cξ ) = sdepth− (Cξ ) = ξ , and there are points x ∈ Cξ and y ∈ Cξ such that depthCξ (x) = depthCξ (y) = ξ . Applying the set operator of cylindrification already used in [9], one can obtain subsets of Rl+1 with analogous depth properties as the one-dimensional sets A.

l,k (A) = Rl × A for any A ⊆ Rk . Then for all ordinals ξ , More precisely, let G ξ, ◦

l,k (A)

l,k (A) ξ, ∂ =

l,k (A) ) ξ, ◦ = Rl × A ξ, ◦ , G we have G = Rl × Aξ, ◦ , ( G l l k ξ, ∂ R × A . Moreover, depthG

l,k (A) (y, x) = depthA (x), for all y ∈ R , x ∈ R , and

l,k (A)) = sdepth+ (A) and

l,k (A)) = sdepth(A), sdepth+ (G sdepth(G

sdepth− (Gl,k (A)) = sdepth− (A). Next we are going to study the relationships between the length of a shortest WSF or WCF of a resolvable set and its depth. Given a WSF g of a pointset A ⊆ Rk , the related (local) depth function is defined by depthg (x) min{β : g(x, β) ↓ }. We have A ⊆ dom(depthg ) = {x : there is an ordinal β with g(x, β) ↓ }. If g is a WCF of length α, then dom(depthg ) = Rk and depthg (x) < α for all points x.

336

A. Hemmerling

Lemma 9. For any WSF g of length α of a set A and each x ∈ dom(depthg ), we have depthA (x) ≤ depthg (x). Moreover, udepth+ (A) ≤ α. For the length α of a WCF of A, it always holds udepth(A) ≤ α. To prove this for non-trivial sets A ∈ {∅, Rk }, we show by induction on ξ that, for all x ∈ Rk , depthg (x) = ξ implies depthA (x) ≤ ξ . This is true for ξ = 0, since G0,b = {x : g(x, 0) = b} is open for b = 0, 1. Thus, G0,0 ⊆ A 0, ◦ and G0,1 ⊆ A0, ◦ . If the assertion holds true for some ordinal ξ , then it follows for ξ + 1. Indeed, assume that depthg (x) = ξ + 1 and depthA (x) = η > ξ + 1. Then there are sequences, (xn )n∈N and (yn )n∈N , both converging to x such that xn ∈ A, yn ∈ A and depthA (xn ), depthA (yn ) ≥ ξ + 1 for all n ∈ N. By the supposition of induction, depthg (xn ) ≥ ξ +1 and depthg (yn ) ≥ ξ +1 or undefined. On the other hand, since Gξ +1,b is open for b = χA (x), we have g(xn , ξ + 1) = g(yn , ξ + 1) = b for almost all indices n. This is a contradiction to xn ∈ A and yn ∈ A however. Quite similarly, for all limit numbers λ one shows that from the validity of the assertion for all ordinals ξ < λ it follows for ξ = λ, too. Finally, from depthg (x) < α for all x ∈ A, it follows udepth+ (A) ≤ α. We have even udepth(A) ≤ α if g is a WCF.   Now it is natural to call a WSF g of a set A greedy iff depthg (x) = depthA (x) whenever depthg (x) is defined. In particular, then depthg (x) = depthA (x) < udepth+ (A) for all x ∈ A. Thus, the length of a greedy WSF of A can always be restricted to udepth+ (A). A WCF g of a set A is greedy iff depthg (x) = depthA (x) for all x ∈ Rk . Then the length of g can be restricted to udepth(A). Proposition 5. Every resolvable pointset A has a greedy WSF (of length udepth+ (A)) and a greedy WCF (of length udepth(A)).   If A is resolvable, then A = ξ
The Hausdorff-Ershov Hierarchy in Euclidean Spaces

337

Aξ, ◦ and A ξ, ◦ are obviously obtained by  {x : g(x, ξ ) ↓} and Aξ, ◦ = {x : g(x, ξ ) = 1 } \ β<ξ  A ξ, ◦ = {x : g(x, ξ ) = 0 } \ {x : g(x, ξ ) ↓} . β<ξ

Whereas the greedy resolution of a resolvable set A is uniquely determined, there are continuum many different greedy WSFs if udepth(A) ≥ 2. Indeed, then we have A1, ◦ ∪ A 1, ◦ = ∅. W.l.o.g. we may assume that A1, ◦ = ∅, and Lemma 7 implies A 0, ◦ = ∅. Thus, there are a point x0 ∈ A 0, ◦ and a real number r0 > 0 such that cl(Ballr0 (x0 )) ⊆ A 0, ◦ . If g is a greedy WCF of A and 0 < r  < r0 , then the following function g  is a greedy WCF of A too:  g(x, ξ ) if ξ = 1 or x ∈ cl(Ballr0 (x0 ) ) ,    1 if ξ = 1 and x ∈ Ballr0 (x0 ) \ cl(Ballr  (x0 ) ) , g  (x, ξ ) 0 if ξ = 1 and x ∈ Ballr  (x0 ) ,    ↑ otherwise (ξ = 1 and x ∈ (Ballr0 (x0 ) )∂ ∪ (Ballr  (x0 ) )∂ ) . 4. The hierarchies 0 ta Hierarchies within
B 2 ,
2 and
2 , respectively, could be introduced on the basis of (the lengths of) resolutions of pointsets by (possibly effective) difference chains of closed, co-r.e. and co-t.r.ex. sets, respectively. A second way is offered by considering the lengths of (possibly computable) WSFs of pointsets. By Lemmas 1, 3 and 4, both these variants are closely connected. They differ only in interchanging the corresponding  classes with the  classes at the odd levels. In the present paper, we prefer the second way, in order to develop the notions in all the three hierarchies analogously to each other and to remain also in accordance with some common notations concerning Ershov’s hierarchy. For all α ∈ CII , let the related  class of the Hausdorff hierarchy (HH) be defined by

αH = {A : A ⊆ Rk for some k ∈ N+ , and A is α-open } . H H of the members of αH , and
H H α is the class of all complements α = α ∩  α .  H H Moreover, let <α = β<α β . For successor numbers α this class coincides H , for the more interesting case of limit numbers α, by the first part of with α−1  Lemma 11 below, it is equal to β<α H β.  By Proposition 1 and Lemma 1, we have α∈CII αH =
B 2 . The first level, for k H H H α = 0, is trivial: 0 = {∅}, 0 = {R : k ∈ N+ },
0 = ∅. 1H = 1B consists B of all open subsets of Euclidean spaces, H 1 = 1 is the class of the closed sets, 2 3 B H hence
H 1 =
1 = {∅, R, R , R , . . . }. 2 consists of all differences F0 \ F1 of H , for closed sets F0 and F1 , etc. Also, it is not hard to show that the members of m finite m ∈ N+ , are just the sets RDC(G), with decreasing sequences of length m of open sets, G = (G0 , G1 , . . . , Gm−1 ). By Proposition 4 and Lemma 1, for the lengths εA of the greedy resolutions E A , it follows immediately

338

A. Hemmerling

Lemma 10. For all A ⊆ Rk and even α ∈ CII , A ∈ αH iff εA ≤ α; for odd ordinals α, we have A ∈ αH iff εA ≤ α. So the levels of the HH are closely connected with the lengths of greedy resolutions which, by Lemma 8, are determined by the depths of the sets under consideration. These relationships can also be used to prove the basic hierarchy properties, by means of the examples from the preceding section. Lemma 11. For all α ∈ CII ,

αH H H H H H H ⊂ αH ∪ H
α ⊂ α ⊂
α+1 , α ⊆ α , and α ⊆ α ; H α H ⊂
H for all limit numbers λ ∈ C . and <λ II λ

The validity of the not necessarily strict inclusions is easily seen. We have noticed the related facts already in Section 2 when we previously have discussed the notions of α-openess and α-clopeness. Next we show that αH and H α are incomparable w.r.t. inclusion. For a limit number α = λ, consider the set Aλ ⊆ R from the examples of Section 3. By Property (∗), sdepth(Aλ ) = λ, depthAλ (x) < λ for all x ∈ Aλ , but depthAλ (1) = λ. So, udepth+ (Aλ ) = λ and udepth+ (Aλ ) = λ + 1. Lemma 8 implies that εAλ = λ H H and εAλ = λ + 1, hence Aλ ∈ λH \ H λ and Aλ ∈ λ \ λ . For successor numbers α with α = α  + 1, consider Aα ⊆ R with the property (∗). We have sdepth+ (Aα ) = sdepth− (Aα ) = α  and sdepth− (Aα ) = sdepth+ (Aα ) = α. Thus, by Lemma 8, if α  is even, then εAα = α + 1 and εAα = α; if α is odd, then εAα = α and εAα = α + 1. In both cases, by Lemma 10, we have again Aα ∈ αH \ H α and H H A α ∈ α \  α . To complete the proof of the first statement of Lemma 11, the strict inclusion H H H α ∪ α ⊂
α+1 remains to show. Consider Cα from the examples. By Lemma H H 8, we have εCα = εCα = α + 1, hence Cα ∈
H α+1 \ (α ∪ α ). To prove the H H   second assertion, we remark that Bλ ∈
λ \ <λ for all limits λ. By means of the set operator of cylindrification described in the examples, one also obtains higher dimensional sets witnessing the strictness of the inclusions and the incomparabilities in Lemma 11. E and For constructive ordinals α and r.r.u. naming systems α/S, the classes α/S αE of the Ershov hierarchy, EH, are defined by E = {M : M ⊆ Nk for some k ∈ Nk , and M is α(/S)-r.e. }. α(/S) E E Let E α(/S) consist of the complements of α(/S)-r.e. sets,
α(/S) = α(/S) ∩

E α(/S) contains just the α(/S)-recursive sets. In particular for limit numbers λ, let  E E . <λ(/S) = β<λ β(/S) Remember that for finite ordinals m ∈ N+ all r.r.u. naming systems are recurE =  E . This class consists just of the RDC(W) for sively isomorphic, hence m/S m

The Hausdorff-Ershov Hierarchy in Euclidean Spaces

339

arbitrary decreasing sequences of length m of r.e. sets, W = (Wi0 , Wi1 , . . . , Wim−1 ). 0 So 1E = 10 is the class of all r.e. sets, E 1 = 1 that of the co-r.e. sets, and 0
E 1 =
1 is the class of the recursive sets. The classes at level 0 of the EH are as trivial as those of the HH.  By Proposition 2, we have {αE : α is a constructive ordinal } = ωE2 =
02 . So the notation-independent hierarchy collapses already at level ω2 . W.r.t. any fixed system α/S, however, the related Ershov classes form a strict hierarchy. This can be shown by standard techniques which yield m-complete sets in each of these classes. We only formulate the results precisely, for proofs the reader is referred to [3, 2], and partially to [21]. Lemma 12. For all constructive ordinals α and r.r.u. systems (α + 1)/S,

E  α/S E ∪ E ⊂
E
E ⊂ α/S α/S ⊂ α/S (α+1)/S , E α/S E ⊆ E , E ⊆  E ; α/S α/S α/S α/S E moreover, <λ/S ⊂
E λ/S for all limit numbers λ ≤ α and r.r.u. systems λ/S. On

the other hand,
02 =
E . ω2 Now we are going to deal with the main subject of this paper, the HausdorffHE HE Ershov hierarchy, HEH, classifying the members of
ta 2 . Its classes α/S and α , for constructive ordinals α (and r.r.u. naming systems S), are defined by HE = {A : A ⊆ Rk for some k ∈ N , and A is α(/S)-t.r.ex. }. α(/S) + HE HE HE α(/S) is the class of all complements of α(/S)-t.r.ex. sets,
α(/S) = α(/S) ∩

HE α(/S) is the class of α(/S)-toprecursive sets, and, in particular for limit numbers  HE HE . λ, let <λ(/S) = β<λ β(/S) It holds 1HE = 1ta and HE = ta 1 1 . Obviously, α-t.r.ex. sets are α-open, toprecursively α-resolvable sets are α-resolvable and α-toprecursive sets are αclopen. Thus, the classes of the HEH are subclasses of those of the HH, and due to their cardinalities, they are proper subclasses. Lemma 13. For any constructive ordinal α > 0, αHE ⊂ αH , HE ⊂ H α α, HE H
α ⊂
α . Like for the TAH and the AH, cf. Lemma 1 in [10], between the HEH and the EH are close relationships too: Proposition 6. For all r.r.u. systems α/S, α > 0, we have HE ) =  E , dis(HE ) = E and dis(
HE ) =
E , dis(α/S α/S α/S α/S α/S α/S

the latter only if α = 1. Moreover, E ⊆  HE E HE E HE α/S (1+α)/S , α/S ⊆ (1+α)/S and
α/S ⊆
(1+α)/S .

340

A. Hemmerling

HE , then its discrete part, dis(A) = A ∩ Nk , belongs to  E . Indeed, If A ∈ α/S α/S an OTM witnessing that A is α/S-t.r.ex. yields immediately an ordinary Turing machine computing a function g showing that dis(A) is α/S-r.e. (Even the indices of t.r.ex. sets can effectively be transformed into Post indices of their discrete parts, i.e., there is a total recursive function ψd : N −→ N such that dis(Xnk ) = Wψk d (n) HE ) ⊆  E . Since dis(A) = Nk \ dis(A), it also for all n ∈ N.) So we have dis(α/S α/S E HE E follows that dis(HE α/S ) ⊆ α/S and dis(
α/S ) ⊆
α/S . E , then the pointset A = Conversely, for M ⊆ Nk , if M ∈ α/S M



{Ball 1 (x) : 2

HE and it holds dis(A ) = M. Thus,  E ⊆ dis( HE ). x ∈ M} belongs to α/S M α/S α/S k E , then A k HE and A k HE . It If M ∈ E , i.e., N \ M ∈  ∈  ∈  α/S α/S α/S α/S N \M N \M E ⊆ dis(HE ). Notice, follows that M = dis( ANk \M ) ∈ dis(HE ). Thus,  α/S α/S α/S however, that it does not yet follow that
E ⊆ dis(
HE ). In particular,
E is the α/S

α/S

1

2 class of all recursive sets, whereas dis(
HE 1 ) = {∅, N, N , . . . }. HE E For α ≥ 2,
E α/S ⊆ dis(
α/S ) can be shown as follows. Let M ∈
α/S , i.e., k M is α/S-recursive via a function g : N × α
−→ {0, 1}. We have to describe a function g  : Rk × α
−→ {0, 1} witnessing the α/S-toprecursivity of a set A  such that M = dis(A ). Let g  (y, 0) = 0 for y from Rk \Nk , excepted all closed balls cl(Ball2−m (x)) for x ∈ Nk , for which the computation of g(x, 0) terminates after just m steps. Moreover, let for all these x, g  (y, 0) = g(x, 0), for all y ∈ Ball2−m (x). Thus, g  (y, 0) is defined on Rk excepted the points x, for which g(x, 0) ↑, and the surfaces of balls around the points points x, for which g(x, 0) ↓, each with a distance from x corresponding to the number of steps of the computation of g(x, 0). Quite similarly, let g  (y, 1) = 0 for y from Rk \ Nk , excepted all closed balls cl(Ball2−m (x)) for x ∈ Nk , for which the computation of g(x, 1) terminates after just m steps, where m = m if the computation of g(x, 0) does not halt after just m steps, and m = m + 1 otherwise. Thus, for all y ∈ Rk \ Nk at least one of the values g  (y, 0) or g  (y, 1) is defined. Moreover, let g  (y, 1) = g(x, 1) for all y ∈ Ball2−m (x) if the computation of g(x, 1) after just m steps terminates. For β ≥ 2, we put g  (y, β) g(x, β) for all y ∈ Ball 1 (x), x ∈ Nk . 2 The sets Gβ,b = {y : g  (y, β) = b} are open, and there is an OTM that S-computes the function g  . Moreover, there is a set A ⊆ Rk such that g  witnesses the α/S-toprecursivity of A . Finally, we have M = dis(A ), since g  (x, β) g(x, β) for all x ∈ Nk and β < α. So we have seen that, excepted
HE 1 , the discrete parts of the classes of the HEH are just the related Ershov classes. E and g : Nk × α
Finally, let M ∈ α/S −→ {0, 1} be a corresponding funck k  tion. Put g (y, 0) = 0 for all y ∈ R \ N , g  (y, 1 + β) g(x, β) for all β < ω and y ∈ Ball 1 (x), and g  (y, β) g(x, β) for all β ∈ α \ ω and y ∈ Ball 1 (x), 2

2

HE E ⊆  HE x ∈ Nk . So we see that M ∈ (1+α)/S , i.e., α/S (1+α)/S . The inclusions HE E HE E α/S ⊆ (1+α)/S and
α/S ⊆
(1+α)/S follow analogously.

 

The Hausdorff-Ershov Hierarchy in Euclidean Spaces

341

We remark that Proposition 6 in connection with Lemma 12 shows that even closed sets, i.e., members of H 1 , might be lifted to an arbitrary high class in the notation-dependent HEH. The first statement of the proposition also means that, for any pointset A ⊆ Rk , the level of its discrete part within the EH gives a lower bound E HE . implies that A ∈ <α(/S) of the level of A within the HEH, e.g., dis(A) ∈ <α(/S) Moreover, by Proposition 6, the strict inclusions between the classes of the EH can be transferred to the HEH. So we obtain Corollary 2. For all constructive ordinals α and r.r.u. systems (α + 1)/S,

HE  α/S HE ∪ HE ⊂
HE
HE ⊂ α/S α/S ⊂ α/S (α+1)/S , HE α/S HE ⊆ HE , HE ⊆  HE , α/S α/S α/S α/S HE ⊂
HE for all limit numbers λ ≤ α . and <λ/S λ/S

The following main result of the present paper shows that, in contrast to the EH, within the HEH we have also strict inclusions between the notation-independent classes. Thus, even the notation-independent HEH does not collapse at any level. , is mainly a feature In other words, the collapsing property of the EH,
02 =
E ω2 of discreteness, not of effectivity. Theorem 1. For each constructive ordinal α > 0,
HE  α HE ⊂ αHE ∪ HE ⊂
HE α α ⊂
α+1 , HE α HE ⊆  HE , αHE ⊆ HE α , α α HE ⊂
HE for all limit numbers λ ≤ α . In particular, there is no construcand <λ λ HE tive ordinal α such that
ta 2 ⊆
α .

The not necessarily strict inclusions follow easily, like those in Lemma 11. To prove the strictness of the inclusions and the incomparabilities stated in the theorem, we return once more to the examples from the end of Section 3. They are now reviewed, in order to specify computable WSFs. The proof will also confirm again Corollary 2. Examples reviewed. Let S be a r.r.u. naming system such that α ∈ ran(νS ). We shall define a partial function g : R × (α + 1) × (α + 1)
−→ {0, 1} satisfying the following conditions: 1. whenever 1 ≤ ξ ≤ α, the related section of g, i.e., the function gξ : R × ξ
−→ {0, 1} defined by gξ (x, β) g(x, β, ξ ) for β < ξ , is a WSF (of length ξ ) of a set Aξ ⊆ R such that   Aξ ⊆ ( 21 , 1 ) and β<ξ {x : gξ (x, β) ↓ } = ( 21 , 1) ; depthAξ (x) < ξ if x ∈ Aξ , and (∗)  depthAξ (1) = sdepth(Aξ ) = sdepth− (Aξ ) = ξ ;

342

A. Hemmerling

2. g is S-computable w.r.t. the second and third argument, i.e., there is an OTM M such that Mσ (n, m) g(x, η, ξ ) if x ∈ R, σ ∈ CFx , νS (n) = η and νS (m) = ξ ; in particular, the sections gξ , for ξ ≤ α, are S-computable. The sets Aξ will be defined like in the examples from Section 3. Also, let ξ = Aξ ∪ {1}. A First we give a definition of function g which is recursive on the third argument w.r.t. the naming system S. More precisely, we define the functions gξ : R × ξ
−→ {0, 1} by means of suitable gη , where 1 ≤ η < ξ and all the employed ordinals η can effectively be obtained from ξ w.r.t. νS , i.e., by means of the functions pS and qS of the naming system S according to the definition of constructive ordinals, cf. page 515 in [10]. For ξ = 1, let Aξ = ( 21 , 1 ). Then A1 is 1/S-t.r.ex. via the S-computable function
1 if β = 0 and x ∈ ( 21 , 1 ) , g1 (x, β) ↑ otherwise . So Conditions 1 and 2 are fulfilled for ξ = 1. For a successor number ξ = η + 1 ≤ α, η ≥ 1, the predecessor η can be computed from ξ w.r.t. νS by the function pS . Let Aη be the η/S-open set determined by the WSF gη such that (∗) from Condition 1 holds. We shall define a function gξ , by means of gη and the shrink function gsh , in such a way that it becomes a WSF of the set Aξ = gsh [B] , where B =

 i∈N+


Bi with Bi =

{i + x : x ∈ Aη } if i is even , η } if i is odd . {i + x : x ∈ A

To specify gξ as a WSF of length ξ for this set Aξ , we put   −1  0 if β = 0 and gsh (x) ∈ i∈N+ ( i , i + 21 ) ,      −1 −1  h(gsh (x), β) if β < η and gsh (x) ∈ i∈N+ ( i + 21 , i + 1 ) ,      −1 (x) ∈ i∈N+ ( i + 41 , i + 43 ) 0 if β = η and gsh gξ (x, β)   ∪ i∈N+ (2i − 41 , 2i + 41 ) ,      −1  1 if β = η and gsh (x) ∈ i∈N+ ( 2i + 43 , 2i + 45 ) ,     ↑ otherwise , where h(i + y, β) gη (y, β) if y ∈ ( 21 , 1 ) and i ∈ N+ .  Notice that gsh (1) = 21 < 35 = gsh ( 23 ). Moreover, we have i∈N+ ( i , i +  1 1 i∈N+ ( i , i + 2 ) ∪ B ∪ (N \ {0, 1}) = ( 1 , ∞ ). So the first line 2 ) ∩ B = ∅ and on the right-hand side of the definition of gξ (x, β) is consistent with the definition of the set B. It just enables us to define the required values of gξ (x, β) at the points x ∈ {gsh (i) : i ∈ N \ {0, 1} } ∪ {gsh (i + 21 ) : i ∈ N+ }. This is done by the third and forth line in the definition, for β = η, and this is in fact the first ordinal β for

The Hausdorff-Ershov Hierarchy in Euclidean Spaces

343

which gξ (x, β) is defined for those points x. So, gξ is indeed a WSF for the set Aξ and Condition 1 is fulfilled. For a limit number λ ≤ α, the recursive function qS yields an increasing sequence of ordinals, (ηi )i∈N , with limi→∞ ηi = λ. More precisely, ηi = νS (φn (i)) for n = qS (νS−1 (λ)). Then a strictly increasing sequence of ordinals, (ηi )i∈N , where limi→∞ ηi = λ and ηi ≥ 1, is effectively obtained too. Now the function gλ is defined by means of the sections gηi such that for the sets Aηi , which are determined via the WSFs gηi ,

where Bλ =



i∈N+

Aλ = gsh [B] ,
{i + x : x ∈ Aηi } if i is even , Bi with Bi = ηi } if iis odd . {i + x : x ∈ A

Now a WSF gλ of length λ for Aλ can be defined by  0     −1    h(gsh (x), β)   0 gλ (x, β)       1    ↑

 −1 (x) ∈ i∈N+ ( i , i + 21 ), if β = 0 and gsh −1 if β < ηi and gsh (x) ∈ (i + 21 , i + 1), for some i ∈ N+ ,

−1 (x) ∈ (i + 41 , i + 43 ), for i ∈ N+ , if β = ηi+1 and gsh −1 or gsh (x) ∈ (i + 43 , i + 45 ), for an odd i ∈ N+ , −1 (x) ∈ (i + 43 , i + 45 ), for an even i ∈ N+ , if β = ηi+1 and gsh otherwise ,

where h(i + y, β) gηi (y, β) if y ∈ ( 21 , 1 ) and i ∈ N+ .  Again, Condition 1 is fulfilled by Aλ , for ξ = λ. In particular, β<λ {x : 1 gλ (x, β) ↓ } = ( 2 , 1 ) . So we have recursively defined a function g : R×(α + 1)×(α + 1)
−→ {0, 1} satisfying Condition 1. Its S-computability according to Condition 2 follows from the uniform effectivity of the steps of definition and since the ordinals are naturally well-ordered. Moreover, the approximate computability of the inverse of the shrink −1 function, gsh , has to be used. Indeed, to compute g(x, β, ξ ) for arguments given by an oracle sequence σ ∈ CFx and an input n, m with νS (n) = β, νS (m) = ξ , an OTM M first tries to realize that x ∈ ( 21 , 1 ) and β < ξ . If this doesn’t hold, then g(x, β, ξ ) =↑. If yes, then M either realizes that g(x, β, ξ ) ∈ {0, 1} according to the first or third or forth lines in the definitions of gξ (x, β) and gλ (x, β), respectively, or it computes an x1 ∈ ( 21 , 1), x = gsh (i + x1 ) for some i ∈ N+ , and ordinals β1 and ξ1 < ξ such that g(x, β, ξ ) g(x1 , β1 , ξ1 ). More precisely, M can only compute a sufficiently long initial part of a sequence σ1 ∈ CF(x1 ) and numbers n1 , m1 with νS (n1 ) = β1 , νS (m1 ) = ξ1 . Now the process is iterated. This yields a strictly decreasing sequence of ordinals ξ > ξ1 > · · · , together with corresponding reals xi and ordinals βi , which terminates ultimately at values from which g(x, β, ξ ) is obtained, or it occurs g(x, β, ξ ) =↑ by a non-terminating computation at some step. Hence Condition 2 has been confirmed too. In particular, the set Aα is α/S-t.r.ex. Thus, Aα ∈ αHE . On the other hand, H Aα ∈ HE α , since Aα ∈ α by Lemma 10. For limits λ ≤ α, the sets Bλ are

344

A. Hemmerling

α } are λ/S-toprecursive. Finally, the sets Cα = Aα ∪ Aα , with Aα = {−x : x ∈ A (α + 1)/S-t.r.ex. as their complements too. On the basis of these ingredients, the proof of Theorem 1 now proceeds quite similar to that of Lemma 11. So we can omit the further details.   Like for Lemma 11, by means of the operator of cylindrification, with respect to which the property of being α/S-t.r.ex. is hereditary, one obtains multi-dimensional sets witnessing the strictness of inclusions and incomparabilities of the classes in Theorem 1. 5. Generalized concepts of decidability Now we are going to deal with straightforward generalizations of the notions of effective decidability, introduced and discussed in [9] for ω-clopen subsets of Euclidean spaces, to arbitrary resolvable sets. It will turn out that they have natural characterizations within the framework developed so far. A resolvable set A ⊆ Rk is called weakly decidable (w.r.t. some r.r.u. naming system S for which udepth(A) ⊆ ran(νS ) ) iff there are recursive functions ϕ0 , ϕ1 : N × N
−→ N such that, for all m ∈ N with νS (m) < udepth(A),  ν (m) ν (m), ◦ i. A S = ( n∈N ballϕ0 (m,n) ) ∩ UAS and  νS (m) ν (m), ◦ S = ( n∈N ballϕ1 (m,n) ) ∩ UA . ii. A This means that the components Aξ, ◦ and A ξ, ◦ are t.r.ex. relatively to the ξ universes UA , uniformly for all ordinals ξ < udepth(A) and w.r.t. the numbering νS . Here we have used a formulation which is close to the original one from [9]. By means of the standard numbering (Xnk : n ∈ N) of the k-dimensional t.r.ex. sets, equivalently to i. and ii. one could require that A νS (m), ◦ = ν (m) ν (m) and AνS (m), ◦ = Xϕk  (m) ∩ UAS , with recursive functions Xϕk  (m) ∩ UAS 0

1

−→ N and for νS (m) < udepth(A). In other words: there are S-comϕ0 , ϕ1 : N
putable functions f0 : udepth− (A) −→ N and f1 : udepth+ (A) −→ N such that ξ ξ A ξ, ◦ = Xfk0 (ξ ) ∩ UA and Aξ, ◦ = Xfk1 (ξ ) ∩ UA for all ordinals ξ < udepth− (A) and ξ < udepth− (A), respectively. The set A is called (approximately) decidable (w.r.t. the naming system S) iff, ξ in addition to i. and ii., the universes UA are uniformly r.e. closed w.r.t. S. In other words, there is a third recursive function ϕ2 : N × N
−→ N satisfying, for all m ∈ N with νS (m) < udepth(A), ν (m)

= cl{xn : n ∈ N} , where xn = liml→∞ qϕ2 (m,n,l) and qϕ2 (m,n,l) − xn  < 2−l for all n, l ∈ N . For udepth(A) ≤ ω, one can suppose that always νS (m) = m. Moreover, UAm = Am−1, ∂ , and this yields just the notions of weak and approximate decidability introduced in [9]. The underlying idea of weak decidability is that the related sets A can effectively be decided in stages corresponding to the ordinals from 0 up to (exclusively) udepth(A), cf. Section 3. In the case of approximate decidability, this decision procedure can be performed with an additional confidence of correctness. For further details, the reader is referred to [9].

iii.

UAS

The Hausdorff-Ershov Hierarchy in Euclidean Spaces

345

First we are going to show that the weak decidability of a pointset can be characterized by means of the computability of the greedy resolutions, both of the set and of its complement. Proposition 7. A set A ⊆ Rk is weakly decidable w.r.t. a r.r.u. naming system S iff the greedy resolutions both of A and of A are S-computable, i.e., there are S-computable functions f1 : εA
−→ N and f0 : εA
−→ N such that E A = ( Xfk1 (ξ ) )ξ <εA and E A = ( Xfk0 (ξ ) )ξ <εA . To prove this, suppose that A is weakly decidable w.r.t. S, i.e., A νS (m), ◦ = ν (m) ν (m) ∩ UAS and AνS (m), ◦ = Xϕk  (m) ∩ UAS , for recursive functions

Xϕk  (m) 0 ϕ0 , ϕ1 :

1

N
−→ N . For the elements of the greedy resolution E A = (Eξ )ξ <εA and for λ = 0 or limits λ and i < ω, we have (now omitting the upper indices k)  Eλ+2i = (Aλ+2i, ◦ ∪ Aλ+2i, ∂ ) = (A ξ, ◦ ∪ Aξ, ◦ ) ∪ A λ+2i, ◦ ξ <λ+2i  (Xϕ  (ν −1 (ξ )) ∪ Xϕ  (ν −1 (ξ )) ) ∪ Xϕ  (ν −1 (λ+2i)) , = ξ <λ+2i

0

1

S

S



0

S

Eλ+2i+1 = ( A λ+2i+1, ◦ ∪ Aλ+2i+1, ∂ ) = (A ξ, ◦ ∪ Aξ, ◦ ) ∪ Aλ+2i+1, ◦ ξ ≤λ+2i  = (Xϕ  (ν −1 (ξ )) ∪ Xϕ  (ν −1 (ξ )) ) ∪ Xϕ  (ν −1 (λ+2i+1)) . ξ ≤λ+2i

0

1

S

S

1

S

From this, by standard techniques of recursion theory, a function f1 as specified in the proposition is obtained. The elements of the greedy resolution E A of the complement of A can analogously be represented by an S-computable function f0 . Conversely, if Eξ = Xf1 (ξ ) , by means of the above representations, we have Xf1 (λ+2i) ∩ UAλ+2i = Eλ+2i ∩ UAλ+2i = A λ+2i, ◦ , Xf1 (λ+2i+1) ∩ UAλ+2i+1 = Eλ+2i+1 ∩ UAλ+2i+1 = Aλ+2i+1, ◦ . From E A = ( Xf0 (ξ ) )ξ <εA , one gets analogous representations of the components Aλ+2i, ◦ and A λ+2i+1, ◦ . Thus, A is weakly decidable.   If A ξ, ◦ = Xf0 (ξ ) ∩ UA and Aξ, ◦ = Xf1 (ξ ) ∩ UA with S-computable functions f0 , f1 , then we get an S-computable greedy WCF of the set A by putting   0 if ξ < udepth− (A) and x ∈ Xf0 (ξ ) , g(x, ξ ) 1 if ξ < udepth+ (A) and x ∈ Xf1 (ξ ) ,  ↑ otherwise . ξ

ξ

Conversely, let be given an S-computable greedy WCF g of length α, for a set A. Then the sets Gξ,b = {x : g(x, ξ ) = b} are uniformly t.r.ex., w.r.t. νS . Thus, there are S-computable functions f0 , f1 such that Gξ,b = Xfb (ξ ) for all ξ < α and b ∈ {0, 1}. On the other hand, since g is greedy, A ξ, ◦ = Gξ,0 ∩ UA and Aξ, ◦ = Gξ,1 ∩ UA . ξ

ξ

Thus, the weak decidability of A has been shown, and we have

346

A. Hemmerling

Proposition 8. A pointset A is weakly decidable w.r.t. a r.r.u. naming system S iff A has an S-computable greedy WCF (of length udepth(A) ). So the weakly decidable pointsets A are just those ones which are decidable, in a generalized sense, by computable greedy WCFs g. Here greediness means that for each point x ∈ Rk the effective decision is done at the first level which is topologically possible. From each of the Propositions 7 and 8, it follows that the weakly decidable sets belong always to the same levels of
classes both within the HEH and in the HH. More precisely, let the
-levels be defined by 

-lev(A) = min{ξ : A ∈
ξ } , for  ∈ {H, HE} and A ⊆ Rk . Corollary 3. For all weakly decidable sets A, we have HE-lev(A) = H-lev(A) = udepth(A). By Lemma 13 and Proposition 5, we have HE-lev(A) ≥ H-lev(A) = udepth(A). On the other hand, the length of a greedy WCF of A can always be restricted to udepth(A). By Proposition 8, if A is weakly decidable, then it belongs to
HE udep(A) . It follows HE-lev(A) ≤ udepth(A), hence HE-lev(A) = udepth(A).   We remark that the conversion of Corollary 3 does not hold: Let M ⊆ Nk be  r.e., but non-recursive, and put AM = {Ball 1 (x) : x ∈ M}. AM 0, ◦ includes 2

the set Nk \ M, hence it cannot be t.r.ex., and AM is not weakly decidable. On the other hand, H-lev(AM ) = HE-lev(AM ) = udepth(AM ) = 2. For example, let g(x, 0) = 1 for all x ∈ AM , g(x, 1) = 0 for all x ∈ Rk and g(x, ξ ) ↑ otherwise. Then g is a computable WCF of length 2 for the set AM . Of course, it is not greedy. Finally, we are going to characterize the approximately decidable pointsets by means of a suitable modification of the notion of WCF. Here we are even able to compute a greedy WCF with arbitrarily small distance errors. Under an approximate characteristic function, briefly: ACF, (of length α) for a set A ⊆ Rk , we understand a partial function g : Rk × CII × N
−→ {0, 1} such that: 1. the sets Gβ,b,n = {x : g(x, β, n) = b } are open for all β (< α), b ∈ {0, 1} and n ∈ N, 2. for all x ∈ Rk and n ∈ N, there is an ordinal β (< α) with g(x, β, n) ↓ , 3. χA (x) = g(x, βx,n , n), where βx,n = min{β : g(x, β, n) ↓}, and 4. if g(x, β, n) ↓ for some β < α and n ∈ N, then there is a point y ∈ Ball2−n (x) such that χA (y) = g(x, β, n) and depthA (y) = β. It follows that for any fixed third component n ∈ N the related section gn , defined by gn (x, β) g(x, β, n) , is a WCF. So depthgn (x) is defined and Lemma 9 applies. We say that g is S-computable, w.r.t. some r.r.u. naming system S with α ∈ ran(νS ), iff there is an OTM

The Hausdorff-Ershov Hierarchy in Euclidean Spaces

347

M such that for all x ∈ Rk , σ ∈ CFx , m, n ∈ N: Mσ (m, n) g(x, νS (m), n). Then, for any total recursive function ϕ : N −→ N, one even obtains an OTM M satisfying M σ (m, n) g(x, νS (m), ϕ(n)). This means that within a distance < 2−ϕ(n) from x there is a point y for which the decision made for x by g is correct, both w.r.t. χA and w.r.t. depthA . An ACF g of a set A is called greedy iff each gn is a greedy WCF, i.e., depthgn (x) = depthA (x). Proposition 9. A pointset A ⊆ Rk is approximately decidable w.r.t. a naming system S iff it has an S-computable greedy ACF. To sketch the proof, we refer to that of Proposition 8. If the set A is even approxξ imately decidable w.r.t. S, the uniform r.e. closedness of the universes UA can be used to obtain an S-computation of the greedy ACF g defined by  0 if ξ < udepth− (A), x ∈ Xf0 (ξ ) and    ξ   Ball2−n (x) ∩ Xf0 (ξ ) ∩ UA = v∅, g(x, ξ, n) 1 if ξ < udepth+ (A), x ∈ Xf1 (ξ ) and    Ball2−n (x) ∩ Xf1 (ξ ) ∩ UAξ = ∅ ,   ↑ otherwise . Conversely, Property 4 of a computable greedy ACF, in particular the requireξ ment that β = depthA (y), implies that the universes UA are uniformly r.e. closed. We close this paper by discussing once more the sets Aξ from the examples of Sections 3 and 4. Now their approximate decidability can be shown by specifying computable greedy ACFs. Examples reviewed once more. Suppose again a r.r.u. naming system S with α ∈ ran(νS ). Let the pointsets Aξ be defined as in Section 4. The WSFs gξ defined there are not greedy if ξ > 2. For example, if ξ = η +1, then depthAξ (gsh ( 23 )) = 1, but depthgξ (gsh ( 23 )) = η > 1. To show that each Aξ has an S-computable greedy ACF, we need some more details on the structure of these sets. Put yξ = inf(Aξ ) and zξ = inf{x : x ≥ yξ and x ∈ Aξ }. By induction on ξ , one easily proves that for all ξ ≥ 2: yξ ∈ Aξ , zξ ∈ Aξ and Aξ = ( yξ , zξ ]∪Bξ , with a non-empty set Bξ ⊆ ( zξ , 1 ). Moreover, yξ and zξ are S-computable rational numbers. This means that there are recursive functions ϕy , ϕz : N
−→ N satisfying yξ = qϕy (ν −1 (ξ )) and zξ = qϕz (ν −1 (ξ )) if 1 ≤ ξ ≤ α, where Q = {qn : n ∈ N} S S according to our basic notations. Indeed, we have y1 =

, z1 = 1 , y2 = gsh ( 23 ) = 35 , z2 = gsh (2) = 23 ; yξ +1 = gsh (1 + yξ ) and zξ +1 = gsh (1 + zξ ) if 1 ≤ ξ ≤ α ; and yλ = gsh (1 + yη1 ) and zξ +1 = gsh (1 + zη1 ) for limit numbers λ , 1 2

where the sequence (ηi )i∈N is obtained as in Section 4. Thus, using the functions pS and qS of the naming system S, the S-computability of the sequences (yξ )1≤ξ ≤α and (zξ )1≤ξ ≤α follows. Applying the same technique as we have used in Section 4, we now define recur−→ {0, 1} such that for each (ξ, n), 2 ≤ ξ ≤ α, sively functions gξ : R × ξ × N


348

A. Hemmerling

 , defined by g  (x, β) g  (x, β, n) , is a greedy WSF of n ∈ N, the section gξ,n ξ,n ξ   (x, β) ↓} = ( 0 , 1 ), and if g  (x, β) ↓, then length ξ of Aξ with β<ξ {x : gξ,n ξ,n  (x, β) and depth (y) = β. there is a point y ∈ Ball2−n (x) satisfying χAξ (y) = gξ,n Aξ Then, putting   g (x, β, n) if x ∈ (0, 1) ,    ξ 0 if β = 0 and x ∈ (−∞, yξ ) ∪ (1, ∞) , gξ (x, β, n) 0 if β = ξ and x ∈ (1 − 2−n , 1 + 2−n ) ,    ↑ otherwise ,

we have a consistent definition of a greedy ACF of the set Aξ . Moreover, the Scomputability of gξ follows like in Section 4. Let  ∈ ( 0 , 23 ) ,   0 if β = 0 and x −1    0 if β = 0 and gsh (x) ∈ i∈N+ ( i + 1 , i + 23 ) ,     1 if β = 0 and g −1 (x) ∈  1  i∈N+ ( i + 2 , i + 1 ) , sh  g2,n (x, β) −1  0 if β = 1 and gsh (x) ∈ i∈N+ ( 2i − 2−n , 2i + 2−n ) ,     −1  1 if β = 1 and gsh (x) ∈ i∈N+ ( 2i + 1 − 2−n , 2i + 1 + 2−n ),    ↑ otherwise . For ξ = η + 1 ≥ 3, we put  0 if β = 0 and x ∈ ( 0 , 35 ) ,     −1 −1   h(gsh (x), β) if β < η and gsh (x) ∈ i∈N+ ( i , i + 1 ) ,     0 if β = η and   −1  gξ,n (x, β) gsh (x) ∈ i∈N+ ( 2i − 2−n , 2i + 2−n ) ,    1 if β = η and     −1  g (x) ∈ i∈N+ ( 2i + 1 − 2−n , 2i + 1 + 2−n ) ,  sh   ↑ otherwise ,  (y, β) if y ∈ ( 0 , 1 ), i ∈ N . where h(i + y, β) gη,n + For limit numbers λ and strictly increasing sequences (ηi )i∈N , limi→∞ ηi = λ, obtained by means of qS from νS−1 (λ) as in Section 4, put   0 if β = 0 and x ∈ ( 0 , 35 ) ,    −1 −1  h(gsh (x), β) if β < ηi and gsh (x) ∈ (i, i +1) for some i ∈ N+ ,     0 if β = η and  i   −1  gsh (x) ∈ ( i − 2−n , i + min(2−n , yηi+1 ) )   gλ,n (x, β) for an odd i ∈ N+ ,    and 1 if β = η i    −1  g (x) ∈ ( i − 2−n , i + min(2−n , yηi+1 ) )  sh    for an even i ∈ N+ ,    ↑ otherwise ,

where h(i + y, β) gη i ,n (y, β) if y ∈ ( 0 , 1 ) and i ∈ N+ .

The Hausdorff-Ershov Hierarchy in Euclidean Spaces

349

So it is ensured that the different lines in the definitions are consistent, even if the related conditions don’t always exclude each other. Moreover, the distance errors are less than 2−n as required. In fact they are even bounded by considerably smaller positive reals obtained by applying the shrink function gsh to error intervals ( i − 2−n , i + 2−n ) or ( i − 2−n , i + min(2−n , yηi+1 )), possibly repeatedly. References 1. Ash, C.J., Knight, J.F.: Recursive structures and Ershov’s hierarchy. Mathematical Logic Quarterly 42, 461–468 (1996) 2. Epstein, R.L., Haas, R., Kramer, R.L.: Hierarchies of sets and degrees below 0 . In: LogicYear 1979/80, Univ. of Connecticut. M. Lerman, J.H. Schmerl, R.I. Soare, (eds.), LN in Math 859, Springer Verlag, pp. 32–48 3. Ershov, Yu.L.: A hierarchy of sets. I; II; III. Algebra i Logica, v. 7 (1968), no.1, 47-74; no.4, 15-47; v. 9 (1970), no.1, 34–51 (English translation by Plenum P.C.) 4. Hausdorff, F.: Grundz¨uge der Mengenlehre. W. de Gruyter & Co., Berlin and Leipzig 1914; Reprint: Chelsea P.C., New York 1949 5. Hausdorff, F.: Mengenlehre. W. de Gruyter & Co., Berlin and Leipzig, 1927 6. Hausdorff, F.: Gesammelte Werke, Band II: “Grundz¨uge der Mengenlehre”. E. Brieskorn, S.D. Chatterji, M. Epple, U. Felgner, H. Herrlich, M. Huˇsek,V. Kanovej, P. Koepke, G. Preuß, W. Purkert und E. Scholz, (eds.), Springer Verlag, Berlin, Heidelberg, New York, 2002 7. Hemmerling, A.: On approximate and algebraic computability over the real numbers. Theoretical Computer Science 219, 185–223 (1999) 8. Hemmerling, A.: Effective metric spaces and representations of the reals. Theoretical Computer Science 284, 347–372 (2002) 9. Hemmerling, A.: Approximate decidability in Euclidean spaces. Mathematical Logic Quarterly 49, 34–56 (2003) 10. Hemmerling, A.: Characterizations of the class
2ta over Euclidean spaces. Mathematical Logic Quarterly 50, 507–519 (2004) 11. Hemmerling, A.: Hierarchies of function classes defined by the first-value operator. E.-M.-Arndt-Universit¨at Greifswald, Preprint-Reihe Mathematik, Nr. 12/2004. (PS file available from: http://www.math-inf.uni-greifswald.de/preprints/titel04); Extended abstract in: Proc. of CCA’2004. Electronic Notes in Theoretical Computer Science 120, 59–72 (2005) 12. Hertling, P.: Unstetigkeitsgrade von Funktionen in der effektiven Analysis. Dissertation. Informatik Berichte 208-11/1996, Fern-Uni Hagen, 1996 13. Hertling, P., Weihrauch, K.: Levels of degeneracy and exact lower complexity bounds for geometric algorithms. Proc. of the 6th Canadian Conf. on Computational Geometry, Saskatoon, 1994. pp. 237–242 14. Kanovej, V., Koepke, P.: Deskriptive Mengenlehre in Hausdorffs Grundz¨ugen der Mengenlehre. In: [6], pp. 773–787 15. Kechris, A.S.: Classical descriptive set theory. Springer Verlag, New York, 1995 16. Ko, K.-I.: Complexity theory of real functions. Birkh¨auser, Boston et al., 1991 17. Ko, K.-I., Friedman, H.: Computational complexity of real functions. Theoretical Computer Science 20, 323–352 (1982) 18. Kreitz, C., Weihrauch, K.: Complexity theory on real numbers and functions. LN in Computer Science 145, 165–174 (1982) 19. Kuratowski, K.: Topology I. Academic Press, New York and London; PWN Warszawa, 1966

350

A. Hemmerling

20. Moschovakis, Y.N.: Descriptive set theory. North-Holland P. C., Amsterdam et al., 1980 21. Odifreddi, P.: Classical recursion theory. North–Holland P.C., Amsterdam et al., 1989 22. Penrose, R.: The emperor’s new mind. Oxford University Press, New York, 1989 23. Rogers, H. Jr.: Theory of recursive functions and effective computability. McGrawHill, New York, 1967 24. Selivanov, V.L.: Wadge degrees of ω-languages of deterministic Turing machines. Theoretical Informatics and Applications 37, 67–83 (2003) 25. Selivanov, V.L.: Difference hierarchy in ϕ-spaces. Preprint 2003, to appear in: Algebra and Logic 26. Wadge, W.W.: Reducibility and determinateness in the Baire space. Ph.D. Thesis. Univ. of California, Berkeley 1984 27. Weihrauch, K.: Computability on computable metric spaces. Theoretical Computer Science 113, 191–210 (1993) 28. Weihrauch, K.: Computable analysis. Springer–Verlag, Berlin et al., 2000