Kleene’s Arithmetical Hierarchy

Kleene [15] focusses on the arithmetical sets, those which are first-order definable in the standard model of arithmetic

and measures the complexity of a set by its simplest definition in N. His crucial contribution is the choice of a useful measure of complexity of first-order definitions in N: a relation P c Nn is ?0 (or in ?0) if it satisfies an equivalence of the form

where R(x, t) is recursive and Qk is 3 or V accordingly as k is odd or even. A relation P (x) is in П0 = —?0 if its negation is in ?0, so that

with a recursive R(x, t), and A(0 = ?0 П Пk. The relations which belong to one of these classes are exactly the arithmetical ones, and that was well known after Kleene [13]. The novelty here is that by allowing a recursive matrix in (5.3) and (5.4) rather than, say, a quantifier free one, Kleene can prove robust closure properties and to construct N-parametrizations for these classes of relations:

Lemma 5.1.1 (1) Closure properties: ?0 and П0 are closed under recursive substitutions, &, v and bounded number quantification of both kinds; ?0 is also closed under number quantification 3s; П0 is closed under Vs; and A°k is closed under negation.

(2) The N-Parametrization Property: there are relations Gn C N1+n in ?0 and recursive injections Sln : N1+l ^ N such that for every n-ary P (x) in ?0,

and for all y = (y1t..., yl)

These facts are very easy by induction, starting with k = 1 where they are immediate by the Normal Form and Enumeration Theorem for recursive partial functions

The arithmetical (i = 0) and analytical (i = 1) hierarchies

Fig. 5.1 The arithmetical (i = 0) and analytical (i = 1) hierarchies

App5. Theyimply the Hierarchy Theorem for the arithmetical sets pictured in Fig. 5.1 (with i = 0), and they can be used very effectively to measure the complexity of a set by placing it in the arithmetical hierarchy, sometimes exactly. Such were, in fact, their first applications.[1] Its main significance, however, was that it set the stage for its non-trivial extensions into the analytical hierarchy, also pictured in Fig. 5.1 with i = 1, as well as the hyperarithmetical hierarchy which lies between them and is our main concern.

The closure of the arithmetical classes under recursive substitutions imply that for every n-ary relation P(*),

i.e., these classes are determined by the sets in them; so we will sometimes abuse notation and use ^0 to denote the class of ^0 sets—and similarly for Пk, A°k.

  • [1] For example, Davis [4] proves that the set {e : (Vx )[{e}(x) ф]| of codes of total recursive functionsis in П0 E^. The Hierarchy Theorem also yields a trivial proof of Tarski’s Theorem for N, thatarithmetical truth is not arithmetical.
< Prev   CONTENTS   Source   Next >