HYP as Effective Borel

An effective о-algebra on N is any collection X c P (N) of sets of natural numbers which admits a coding (C, n) in N so that the following hold:

(1) Every singleton [1] belongs to X uniformly, i.e., for some total, recursive u1(t) and every t, u1(t) is a code of [1] in X. 17

(2) X is uniformly closed under complements, i.e., there is a recursive partial function u2(c) such that

(3) X is uniformly closed under recursive unions, i.e., for some recursive partial function u3(e),

As in the definition of (51, | |), let b : N ^ P(N) be the least partial function on N to P (N), such that

  • (1) b«1, t)) = [3],
  • (2) b((2, y)) = N b(y), and
  • (3) if ye is total and for every i, b(^e(i)) l, then b((3, e)) = U; b(P(i)) and set


the collection of effective Borel subsets of N.

Lemma 5.3.3 B is the least effective a-algebra on N, uniformly.

Proof The coding (B, i ^ Bi) witnesses that B is an effective a -algebra on N. To see that it is uniformly the least one, suppose (C, n) is a coding witnessing that some X is an effective a -algebra on N and define by a natural effective grounded recursion a recursive partial function u such that

Theorem 5.3.1 HYP = B uniformly, i.e., (C, n) in (5.24) and (B, i ^ B;) in (5.25) are equivalent codings of HYP.

Proof HYP is an effective a-algebra on N by Lemmas 5.3.1 and 5.3.2 and a simple construction which puts into it every singleton, uniformly. By Lemma 5.3.3 then, B c HYP, uniformly. To prove HYP c B, we need to verify that every effective a - algebra on N is uniformly closed under the jump operation, relative recursion and diagonalization, which is not difficult as these operations can be effectively reduced to complementation and the taking of recursive unions; we then use effective grounded recursion to define a uniform embedding of HYP into B. ?

Remark 5.3.1 The theorem gives us a different view of hyperarithmetical sets and a simpler way to prove important properties of them which do not explicitly refer to the Ha-sets, and these include most of the important properties of HYP. I am not certain who should be credited for it: it was “in the air” in the mid-sixties and I think that it was probably first formulated by Shoenfield, but I cannot find now a specific citation. In any case, it was certainly not known in the 50s, and our use of it here is the most substantial anachronism in this exposition of what was proved then.

< Prev   CONTENTS   Source   Next >