On into the Transfinite!

For any A c N, let[1]

It follows that for every B,

so that in particular A <T A!, and we can get a sequence of sets of increasing Turing complexity by setting recursively

Now Ki is (recursively isomorphic with) Post’s complete r.e. set K and for every k > 1, easily, Kk is ?0-complete, i.e., a set is ?0 exactly when it is i-i reducible to Kk. It is also easy to check that the diagonal set

is recursively isomorphic with the truth set for arithmetic

where гвn is the Godel number of the sentence в in the language of arithmetic, relative to some standard coding. This is not arithmetical; and then one can continue and define ever more complex non-arithmetical sets,

indexed by the ordinals f < ш[2] [3]. The sequence {K% : f < ш[4] [5] [6]} was defined by Davis

[4] who also showed that

These facts are all fairly simple to verify today. They were not so easy6 before 1955, when the theory of relative recursion had not been worked out in detail: Kleene [15, 18, 19], Davis [4, 5] and Mostowski [38, 39] all prove various versions of them, not always the cleanest or strongest, sometimes awkwardly and (in the case of Davis and Mostowski) mostly without knowing all of each other’s or Kleene’s work. Nevertheless, the later papers Davis [4], Mostowski [39] and Kleene [19] all take the crucial step of defining natural extensions of the arithmetical hierarchy beyond its first ш classes ?0, ??,..., “on into the transfinite” in Davis’ exhortation with which we headed this section.

The definitions (5.11)—(5.13) of [Kf : f < ш2} depend on choosing for each limit ordinal f = ш ? s < ш2 sequence n ^ ш ? (s - 1) + n converging to f. This is natural enough, but not the only choice, and it is not obvious how to make a “natural” or “best” choice[7] for ordinals above ш2. This leads us to the next, crucial bit:

  • [1] For completeness, we will repeat in this section some parts of §7—§9 of Moschovakis [37], whichgoes over some of the same ground in more detail and includes several proofs.
  • [2] 6For example, to prove that Kk is ?0-complete, you need the first of the following strengtheningsof (5.10): there are recursive injections u(e, t), v(e) such that for all A, B and ah e, t, Proof: For (1), choose m so that for any A, {m}A (e, t, y) = {e}A(t) and set u(e, t) = Sj2 (m, e, t). For
  • [3] you start with a recursive V1 (e) such that A f B ==$? {e}A (t) = {v1 (e)}B (t) and do a similar
  • [4] construction. That u(e, t) and v(e) are (absolutely) recursive injections—which has applications—
  • [5] depends on the fact that the functions S„ in App 5 are independent of any function parameters
  • [6] and injective, which I cannot find in any of the early texts (including Kleene [17]) even for m = 0.
  • [7] Spector [48] eliminates dramatically the most obvious approach at limit ordinals: No increasingsequence do < d1 < ??? of Turing degrees has a least upper bound. Of course, this was not knownto Davis, Kleene and Mostowski when they wrote these early papers.
 
Source
< Prev   CONTENTS   Source   Next >