# HYP-Quantification and the Spector-Gandy Theorem

The (coded) *graph* of a function *a* : N ^ N is the set

and we often write “a e HYP” when we really mean “Graph(a) e HYP”, i.e., that *a* is hyperarithmetical. We collect here some interesting, easy (now) facts about the quantifier (3a e HYP) and we also formulate the basic *Spector-Gandy Theorem *about it—which has never been easy.

It is natural to code the HYP-functions using a subset of the coding of HYP-sets as effectively Borel in (5.25):

The key (easy) facts about this coding is that *B ^{1} is П* by Lemma 5.3.4 and Theorem 5.3.3, and that

*for each i e B*

^{1}, the relation

is *A* uniformly, by Theorem 5.3.3 again.

Theorem 5.3.10 *(1)* HYP*-Quantification Theorem, Kleene ([21 ], [22]). If*

*and Q(x, a) is П, then P(x) is also П.*

- (2) HYP
*is not a basis for*П^{0},*Kleene [21 ]. There is a non-empty,*П^{0}*set A c*N*which has no*HYP*members.* - (3)
*Upper classification of*HYP.*As a subset of N,*HYP*is П.* - (4)
*Lower classification of*HYP.*As a subset of N,*HYP*is not*?}.

*Proof* (1) Compute:

(2) Towards a contradiction, assume that every non-empty, П^{0} set A c N has a HYP member and let *P* c N be an arbitrary set. By the Normal Form for П Theorem 5.3.2 (applied to -*P*),

with a recursive *R.* Since every *A _{x}* is П0, our assumption implies that

which by (1) means that every subset of N is *П,* which it is not.

- (3) a e HYP (3i)[i e
*B*^{1}& a = ft]. - (4) The relation
*P*(*i, a) i e B*^{1}&*a = в*is П^{1}, so by the Kreisel Uni- formization Theorem 5.3.9, there is a П relation*P* (i, a)*such that

Let *D(i)* (3a e HYP)*P*(i, a).* This is П by (1), but if HYP is ?j, then it

is also ?}, since

It follows that the function

is ^1 and has no code in *B*^{1}, which is absurd. ?

Kleene [23] proved Part (1) of this theorem with a П0 relation *Q(x,a)* and asked whether this version of (5.46) gives a normal form for *П.* Spector [49] proved that it does, and gandy [10] gave an independent proof of this basic fact after hearing of Spector’s result.

Theorem 5.3.11 (Spector [49], Gandy [10]) *Every П relation P on* N *satisfies an equivalence*

*P(x)* (3a e HYP)(Vt)*R(x,a(t*)) (5.47)

*with a recursive R(x, u). In fact, R(x, u) can be chosen so that*

*P(x)* (3a e HYP)(Vt)*R(x,a(t*)) (3!a e HYP)(Vt)*R(x,a(t)).*

Spector’s proof is difficult, as is Gandy’s, both of them depending on a detailed, combinatorial analysis of *П* definitions and properties of the constructive ordinals coded by *O*. Easier proofs and generalizations of the first claim (without the uniqueness) were found later, cf. Moschovakis [33-35].

Taken together, Kleene’s HYP-Quantification and the Spector-Gandy Theorem have important foundational import, perhaps best expressed by the following

Corollary 5.3.1 (Kleene, Spector) A *relation P (x) on* N *satisfies *
*with an arithmetical Q* i(x*, a ) if and only if it satisfies *
*with an arithmetical Q _{2}(x, a).*

Moreover, the equivalence holds *uniformly,* i.e., Q_{2} can be constructed from *Q _{1 }*and vice versa.

The Corollary reduces *one* quantification over the continuum N on arithmetical relations to one quantification (of the opposite kind) over the countable set HYP C N whose members are constructed by regimented iteration of quantification over N.