4
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ 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. $\endgroup$
    – Andrés E. Caicedo
    Commented Dec 19, 2010 at 18:14
  • $\begingroup$ "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." This is not true, as this is a question about a particular proof that nibbles wrote, which is presumably wrong as it contradicts the well-known theorem that the Kleene hierarchy does NOT collapse, and would NOT be given. To make matters worse, you are not giving an actual reference, but only an entire long complex text. That is no answer!! $\endgroup$
    – Charlie V
    Commented Apr 16, 2018 at 13:18
  • $\begingroup$ If you know it's in there you must have seen it before so you can say where. It is not math or logic to simply give a book title. $\endgroup$
    – Charlie V
    Commented Apr 16, 2018 at 13:18
  • 5
    $\begingroup$ @CharlieV Notice that Andrés posted his reply as a comment, not as an answer. He also intended to be helpful, by mentioning a text that he considered relevant. Besides, this thread is over 7 years old, and the OP presumably had matters resolved to his/her satisfaction long ago. Taking all of this into account, it seems to me you're overreacting here. $\endgroup$
    – Todd Trimble
    Commented Apr 16, 2018 at 14:10
  • 1
    $\begingroup$ @CharlieV Although, as you said, Andrés's comment isn't an answer, no one has claimed that it is. Also, to amplify what Todd said, the fact that an answer was accepted by the OP would indicate that the matter has been satisfactorily resolved (apparently about an hour and a half after the question was asked). $\endgroup$
    – Andreas Blass
    Commented Apr 16, 2018 at 18:45

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the answer! Can you prove that the hierarchy does not collapse? $\endgroup$
    – nibbles
    Commented Dec 19, 2010 at 9:38
  • 5
    $\begingroup$ The undecidability of the halting problem separates $\Sigma^0_1$ from $\Delta^0_1$. The proof of that fact relatives to any $n>1$. $\endgroup$
    – Ed Dean
    Commented Dec 19, 2010 at 10:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .