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.

< Prev   CONTENTS   Source   Next >