the hyperarithmetical vs. lightface Borel hierarchies

[David Madore]

Hi.

I'm very confused as to the relation between the [Kleene]
hyperarithmetical hierarchy and [Addison] lightface Borel (aka,
effective Borel) hierarchy.

(Very briefly, a subset S of the integers--or perhaps even of the
Baire space--is said to be Sigma_alpha in the hyperarithmetical
hierarchy, where alpha is some recursive ordinal, when S is
recursively enumerable in the alpha'th Turing jump of 0. The
lightface Borel hierarchy, on the other hand, is defined by
inductively giving a meaning to "recursive Borel codes", where each
recursive Borel code specifies the operations of taking a basic open
set, or of complementing another Borel, or of taking a countable union
of other Borel sets whose codes are produced by some recursive
function specified by the code; then a set is said to be Sigma_alpha
when it has a Borel code which describes it as a countable union of
sets which are Sigma_beta for beta<alpha.)

Do these notions coincide for sets of integers (I can more easily
imagine that they don't for subsets of the Baire space)? In either
case we get the hyperarithmetical=Delta^1_1 sets of integers when
taking the limit over all recursive ordinals; but my question is
whether each rank Sigma_alpha coincides in the two hierarchies, at
least if we're careful enough as to what happens at limit ordinals
(which may not be right in the previous paragraph).

Hinman's book (*Recursion-Theoretic Hierarchies*, Perspectives in
Mathematical Logic 9 (1978), Springer, ISBN 3-540-07904-1, <URL:
http://projecteuclid.org/euclid.pl/1235415519 >) defines both
hierarchies (chapter IV, section 4, p. 163-179), giving them a
different notation, and states that the first omega ranks coincide:
this seems to imply that they don't after that (and exercise 4.32 asks
the question, which makes it even less likely that they do), but I'm
confused. Does the difference arise from a subtelty in Hinman's
definition (like using many-to-one reducibility instead of Turing
reducibility when definining the hyperarithmetical hierarchy), or is
there something a bit deeper?

--
David A. Madore
( http://www.madore.org/~david/ )

[Robert E. Beaudoin]

You are misstating the known theorems slightly, which may be making
things more opaque to you: for finite n a set is (lightface)
\Sigma^0_{n+1} (not n) in the parameter x if and only if it is
recursively enumerable in the n-th jump of the Turing degree of x, which
is in turn equivalent to being many-one reducible to (a canonical set
in) the (n+1)-th jump of the degree of x. (E.g. the r.e. sets are the
\Sigma^0_1 sets, not the \Sigma^0_0 sets.) It follows that a set is
\Delta^0_{n+1} in x if and only if it is Turing reducible to the n-th
jump of the degree of x, and that the (n+1)-th jump of the degree of x
contains a (many-one) complete set among the \Sigma^0_{n+1}[x] sets of
integers.

At stage \omega the picture is (necessarily) a bit different, as \omega
has no predecessor. Different authors might possibly define the limit
levels of the effective Borel hierarchy slightly differently, but I
believe (actual recursion theorists please correct any errors you
detect) using the definition in Hinman's book that one can obtain the
result that a set is \Sigma^0_\omega in x if and only if it is r.e. in
the \omega-th iterated Turing jump of the degree of x, and so if and
only if it is many-one reducible to the (canonical element of the)
(\omega+1)-th jump. I.e. one begins to see the hyperarithmetical
hierarchy refine the effective Borel hierarchy. In any event I'd say
the divergence of the two hierarchies is a little deeper than a mere
quirk of the manner of their definitions.

Hope that helps.

Robert E. Beaudoin