Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


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?

share|improve this question
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. –  Andres Caicedo Dec 19 '10 at 18:14
add comment

1 Answer

up vote 4 down vote accepted

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)$.

share|improve this answer
Thanks for the answer! Can you prove that the hierarchy does not collapse? –  nibbles Dec 19 '10 at 9:38
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.