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?



Why does the Kleene Hierarchy not collapse?
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)$.


