# Why does the Kleene Hierarchy not collapse?

Hello,

Consider some logical statement (I am talking about natural numbers all the way). P(x, y, z) is a computable statement:

For all x: There exists an y: For all z: P(x,y,z) is true.

I suppose this would have a Kleene level of 3.

Now, you could not consider all x, y and z, but only the values from zero to below a+q, a+v and a+w:

For all x < a + q: There exists an y < a + v: For all z < a + w: P(x, y, z) is true.

Clearly, you could program a Turing machine to check whether this is true.

Now: Is the statement "No matter how big you make a, you can always find (q, v, w) (natural numbers) were said Turing machine will output 'True'" equivalent to the first statement?

Consider it were. Because you can construct functions that map one integer to n integers, you could represent the tuple (q, v, w) as one natural number (call it p), and the Turing machine calculates the (q, v, w) out of this natural number (we call this Turing TM_P). Then you could rephrase the question:

For all a: There exists a p: TM_P(a, p) will output true.

Now, that would clearly imply a collapse of the Arithmetical hierarchy, as you only need some number of levels to make statements about Turing machines (I don't know the details here) and then two additional levels to make the "For all a, there exists a p" claim.

Where does this reasoning fail? And does it fail, after all? If no: What did I do wrong that I did not read about it?

-
A reference for this is Rogers "Theory of Recursive functions and effective computability" or a similar introductory text, where these questions are treated in detail. – Andrés Caicedo Dec 19 '10 at 18:14

You're right that the statement $\varphi(a,q,v,w)$ defined by $\forall x<a+q \,\, \exists y<a+v \,\, \forall z<a+w [P(x,y,z)]$ can be checked by a Turing machine. If I read you correctly, you're wondering whether (1) $\forall x \exists y \forall z P(x,y,z)$ is generally equivalent to (2) $\forall a \exists q,v,w \varphi(a,q,v,w)$, because an affirmative answer would conflict with the fact that the Kleene hierarchy doesn't collapse.
Happily, (1) and (2) aren't generally equivalent. Let $P(x,y,z)$ be the statement $x+z<y$ for instance. Then (2) is true: for any $a$, set $q=w=0$ and $v=a+1$, and the $y<a+v=2a+1$ that you need can always be witnessed by $2a$. But (1) is certainly false for this $P(x,y,z)$.
The undecidability of the halting problem separates $\Sigma^0_1$ from $\Delta^0_1$. The proof of that fact relatives to any $n>1$. – Ed Dean Dec 19 '10 at 10:07