The Analytical Hierarchy; HYP c A|

Useful and natural as the characterization HYP = B may be, it does not provide explicit definitions for the hyperarithmetical sets and relations. These require quantification over sets of natural numbers or, equivalently, the Baire space N = Nn.

A relation P (x, в) with arguments in N and (possibly) N is analytical if it is first-order definable in the two-sorted structure of analysis

where ap (a, t) = a(t) is the application operation. Kleene [19] classifies the arithmetical and analytical relations with arguments in N and N in hierarchies which look so much like the arithmetical hierarchy over N that we pictured them together in Fig. 5.1. We are mostly interested here in the “first level” of the analytical hierarchy, thepointclasses1& П, ?}, A, but it is almost as easy to define them all. Briefly, and using the notions and notation in the Appendix:

(1) P (x, в) with x = (x1,...,xn) e Nn and в = (в1,---, Pm) e Nm is ?0 if it is the domain of convergence of a recursive partial function,

P is П0 if it is the negation of a ?0 relation; P is ?0+1 if [1]

and k = ?° П П0.

These are the arithmetical relations with arguments in N and N, those which can be defined in N2 without using quantification over N.

(2) P (x, в) is П if

with arithmetical Q(x, в, a); it is П0 if it is the negation of a ?0 relation; and it is ?0+1 if

and A = ?0 П П0.

The analytical pointclasses П0, ?0, A0 have all the closure properties of their analogs П0, ?0,Ak in the arithmetical hierarchy over N, and they are also closed under number quantification of both kinds and under substitution of total recursive functions into N or N, App 8. In addition, П0 is closed under Va and ?0 is closed under 3a. These closure properties are very easy to prove, but not without consequence[2]:

Lemma 5.3.4 The codeset B of B = HYP defined in (5.25) is П0.

Proof By its definition, B is the least fixed point Ф of the monotone operator Ф : P (N) ^ P (N) defined by

so that by (5.59),

If we code each set A by the k-set Za = {x : a(x) = k} of some a e N and set then Ф(х, a) is arithmetical (just replace u e A by a(u) = k in (5.33)); and so that B is П0. ?

This is a very general method of proof: it can be used to show that if Ф is monotone on P(N) and the relation Ф(х, a) associated with Ф by (5.34) is П1, then Ф is П1 and, of course, it can be generalized in many ways.

Much of the theory of П1 depends on the following refinement of its definition (5.32):

Theorem 5.3.2 (Normal Form for П1) Every П relation P (x, в) satisfies an equivalence

where R(x, в, u) is recursive and monotone upward on its last (sequence code) argument, i.e.,

It is easy to prove, using the closure properties of П1, the somewhat unusual “dual” of the Axiom of Choice, that for every relation R(t, s),

and the Normal Form Theorem for recursive partial functions, App 5. By App 5 again, it implies the analog of (2) in Lemma 5.1.1:

Lemma 5.3.5 (N-Parametrization for П1) For all n, m > 0, there is a П relation such that for every П1 relation P (x, в),

moreover, there are recursive injections Sln : N1+l ^ N such that for all tuples y = y1,..., yl e N,

When (5.37) holds, we call e a n1-code of P(x, в) and a Encode of its negation -P(x, в); and if e is a n1-code and m a Ej-code of P(x, в), then (e, m) is a A1-code of it.

To see how the Parametrization Property is used, suppose R(x, t) is a П relation on N (for simplicity) with code e and

Let Q(m, x) (3t)G(m, x, t) (with the appropriate superscripts) and let s be a

n11-code of Q; then

so 5} (s, e) is a code of P(x). The upshot is that П is uniformly closed under 3s, and by similar, trivial computations, П}, ?j and are uniformly closed under all (reasonable) operations under which they are closed, including those listed above. This implies that the collection of A 1 subsets of N is an effective о -algebra on N, which with Lemma 5.3.3 then yields

Theorem 5.3.3 (Kleene [ 1 9]) HYP c A} , uniformly. In detail, there are relations H?(i, x) and Hn(i, x) in ? } and П}} respectively, such that

Davis [4] and Mostowski [39] had already shown that every HYP-relation is analytical, but Kleene’s result is a considerable improvement and begs for the converse.

  • [1] A pointclass in this paper is any collection Г of relations P (x, a) with arguments in N and N.It is an awkward term but useful, and is has been well established since the 70s for collections ofrelations in various spaces typically specified by the context.
  • [2] They also suffice to prove that the notation system Sj is П}, cf. Lemma 1 in the proof of Theorem9.2 in Moschovakis [37].
< Prev   CONTENTS   Source   Next >