12.  The Arithmetical Hierarchy

Kevin T. Kelly
Department of Philosophy
Carnegie Mellon University

We may think of ØK as posing the problem of induction for computational devices, for it is impossible to tell for sure whether a given computation will never halt.  Thus, K is effectively refutable and ØK is effectively verifiable.  We know from the philosophy of science that universal hypotheses are refutable and existential hypotheses are verifiable.  This correspondence also holds, if we think of the expressions of the sets in Kleene normal form.  Kleene normal form prenex normal form with U as the only predicate.  Thus, we have

Thus, we may think of K(x) as an "existential hypothesis" and of ØK(x) as a "universal hypothesis" given that instances of U are "observable" (e.g., the "scientist" is treating program x as a black box and watching what it does in various numbers of steps of computation on input x.

It is also notorious in the philosophy of science that most hypotheses are neither verifiable nor refutable.  Thus, Kant's antinomies of pure reason include such statements as that space is infinite, matter is infinitely divisible, and the series of efficient causes is infinite.  These hypotheses all have the form

"x$y F(x, y).
But computers have their own "antinomies of pure reason", for example:
Tot(x) Û f[x] is total Û "w$zU(x, d(z, 1), d(z, 2), <w>).
Inf(x)  Û W[x] is infinite Û "w$z$y>w. U(x, d(z, 1), d(z, 2), <y>).
In both cases, things get worse as the quanatifier structure of the hypothesis becomes more complex, where complexity is measured as number of  blocks of quantifiers:  i.e.,$"""$$ counts as three blocks.  Also, verification and refutation depend on whether the block is $ or " and in general we will want to keep track of the leading quantifier.  We can count quantifier alternations as follows.

The Arithmetical Hierarchy

S[A]0(P) Û P is recursive in A.
S[A]n + 1(P) Û $R. S[A]n(R) Ù "x, P(x) Û $y. ØR(x, y).

P[A]0(P) Û P is recursive in A.
P[A]n + 1(P) Û $P. P[A]n(R) Ù "x, P(x) Û "y. ØR(x, y).

D[A]n(P) Û S[A]n(P) Ù P[A]n(P).

Arith =ÈnS[A]n.

N.b. you can define the whole thing as a hierarchy of sets rather than relations by treating relations as sets of coded n-tuples.

Proposition 1 (basic structure and closure laws):

  1. D[A]n = recursive in A; S[A]n = r.e. in A; P[A]n = co-r.e. in A;
  2. P[A]n(R) Û S[A]n(ØR);
  3. D[A]n Í S[A]n, P[A]n Í Dn + 1;
  4. D[A]n, S[A]n, P[A]n are closed downward under £m.
  5. D[A]n is closed under Ù, Ú, Ø;
  6. S[A]n is closed under Ù, Ú, $;
  7. P[A]n is closed under Ù, Ú, ".
Exercise 1.  Prove it.   Hint:  use logical rules and some induciton on n.  These are all very easy so don't work too hard!
-|

The Arithmetical Hierarchy Theorem

We don't know yet whether the whole hierarchy collapses into some finite level.  The simplest way to do it is to index the levels in the hierarchy the way we did for the r.e. sets and then diagonlize all the levels at once.

R is universal for G Û G(R) Ù "P, G(P) Þ ($n"xP(x) Û R(n, <x>)).

Define

W1[x](<y>) Û W[x](<y>).
Wn + 1[x](y) Û $z ØWn[x](<y, z>).


Proposition 2 (universal indexing theorem):  "n > 0, R(x, y) Û Wn[x](<y>) is universal for Sn.

Proof:  By induction.  The base case is immediate by the fundamental theorem for r.e. sets.
Inductively, suppose that Wn[x](<y>) is universal for Sn.
Now suppose Sn + 1(R).
So $P. Sn(P) Ù "x, P(x) Û $y. ØP(x, y).
By the induction hypothesis there exists k such that
"x, P(x) Û $z. ØWn[k](<x, z>)
Û Wn + 1[k](x).
-|

We can now form the usual Cantorian table for the Sn sets just as we did for the r.e. sets before:

Tn[x, y] = Wn [x](y).
Counterdiagonalizing, we obtain a non Sn  set as follows
ØKn(x) Û ØTn[x, x] Û ØW[n, x](x).
Proposition 3 (arithmetical hierarchy theorem):
  1. Sn(Kn) Ù ØP[A]n(Kn).
  2. ØSn(ØKn) Ù P[A]n(ØKn).
Proof:  (1) the counter-diagonal set ØKn differs from each set  Wn [x].
By the universal indexing theorem, ØKn therefore differs from each Sn set.
On the other hand, the definitional form of ØKn witnesses its membership in Pn.

(2) follows by duality.
-|

Jumps and the Hierarchy

We can also use the jumps to hold the hierarchy apart.  An advantage of this approach is that it yields a constructive perspective on the D classes.

Proposition 4 (Post's theorem):

  1. S[A]n + 1(R) Û $P. P[A]n(P) Ù R is r.e. in P.
  2. S[A]n + 1(R) Û $P. S[A]n(P) Ù R is r.e. in P.
  3. S[A]n + 1(R) Û R is r.e. in A(n).
  4. D[A]n + 1(R) Û R is recursive in A(n).
  5. n > 0 Þ A(n) is S[A]n-m-complete.
Corollary:
  1. Sn + 1(P) Û R is r.e. in 0(n).
  2. Dn + 1(R) Û R is recursive in 0(n).
  3. n > 0 Þ0(n) is Sn-m-complete.
Proof following Soare p. 64:
1.  Suppose S[A]n + 1(R).
So
$P. S[A]n(P) Ù "x, P(x) Û $y. P(x, y).
By the P-relativized projection theorem, R is r.e. in P.

Conversely, suppose $P. P[A]n(P) Ù R is r.e. in P.
Then by the relativized fundamental theorem of r.e. sets:

R(x) ÛW[P, y](x)
Û $wU[P](y, d(w, 0), d(w, 1), <x>)
Û $wU[P|w](y, d(w, 0), d(w, 1), <x>)
Û $w$ finite S. S = P|w Ù U[S](y, d(w, 0), d(w, 1), <x>)
Û $w$k. lh(k) = w Ù"v £w,  (P(v) Û $u £w d(k, w) = y) Ù U[k](y, d(w, 0), d(w, 1), <x>).
where we define U[k](y, a, b, <x>) just like the Kleene predicate except that when lh(y) = 6, we have
U[k](y, a, b, <x>) = 1 if $u £w d(k, w) = y and
U[k](y, a, b, <x>) = 0 otherwise.
This is clearly recursive in all arguments including k.
Also, (P(v) Û $u £w d(k, w) = y)) is S[A]n + 1 since P[A]n(P).
Hence, R(x) is S[A]n+ 1.

2. The preceding construction could have been done just as well with ØP.

5. By in induction:  A' is S[A]1-complete (proposition 11.4.4).
Suppose that A(n) is S[A]n-complete.
Hence ØA(n) is S[A]n-complete.
Let S[A]n + 1(B).
So $P. S[A]n(P) Ù B is r.e. in P (by part 2).
So B is r.e. in A(n) , since P £mA(n), (by induction hypothesis).
So B £mA(n + 1) (proposition 11.4.4).

3. By parts 1 and 5.

4. D[A]n + 1(R) Û S[A]n + 1(R) Ù S[A]n + 1(ØR)
Û R, ØR are r.e. in A(n) (by part 3).
R £ A(n) (bythe relativized proof that recursive sets are  r.e. and co-r.e.).
-|

Exercise 2:  How many D[A]n  degrees are there?

Proposition 5 (arithmetical hierarchy theorem again):

  1. S[A]n(A(n)) Ù ØP[A]n(A(n)).
  2. ØS[A]n(ØA(n)) Ù P[A]n(ØA(n)).
Proof: A(n + 1) is S[A]n-m-complete (by proposition 2.4).
A(n) is D[A]n complete (by proposition 2.5).
Suppose P[A]n + 1(A(n + 1)).
Then D[A]n + 1(A(n + 1)).
Then A(n + 1) £ A(n), contradicting proposition 11.4.2.
-|