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 B1 is П by Lemma 5.3.4 and Theorem 5.3.3, and that for each i e B1, 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 Ax 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 B1 & a = ft].
- (4) The relation P(i, a) i e B1 & 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 B1, 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 Q2(x, a).
Moreover, the equivalence holds uniformly, i.e., Q2 can be constructed from Q1 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.