Return to Answer

You have made an error. One cannot prove that a set is computably enumerable by reducing the halting problem to it. That would be like trying to show that someone is short by proving that they are at least as tall as a particular short person. After all, even very tall people are at least as tall as your given short person. Similarly, we cannot deduce that a set is simply by reducing a set to it, since even very complicated sets will have that feature. The halting problem reduces to sets of arbitrarily high complexity, since $0'\leq_T 0'\oplus A$ for any set $A$, but this doesn't mean that those sets are simple.

So that was the error in your proof. But meanwhile, let me help to analyze the complexity of your set by finding the exact complexity. I claim that your set $L$ is $\Pi^0_2$ complete, and therefore it is exactly equivalent to the double jump $0''$, which is the halting problem relativized to an oracle for the usual halting problem. Specifically, it is easy to see that $L$ has complexity $\forall\exists$, since $M$ is in $L$ just in case every even number input leads to an accepting computation, which is a $\forall\exists$ statement. Convesely, consider any $\forall\exists$ statement $\forall n\exists m\,\varphi(n,m)$, where $\varphi$ has only bounded quantifiers. We can create a machine $M$ that on input $2n$ searches for an $m$ for which $\varphi(n,m)$, accepting $2n$ when such an $m$ is found. Thus, the statement is true if and only if $M\in L$. So we have reduced $\Pi^0_2$ truth to $L$, and so it is $\Pi^0_2$-complete.

You have made an error. One cannot prove that a set is computably enumerable by reducing the halting problem to it. That would be like trying to show that someone is short by proving that they are at least as tall as a particular short person. After all, even very tall people are at least as tall as your given short person. Similarly, we cannot deduce that a set is simple by reducing a simple set to it, since even very complicated sets will have that feature. The halting problem reduces to sets of arbitrarily high complexity, since $0'\leq_T 0'\oplus A$ for any set $A$, but this doesn't mean that those sets are simple.

So that was the error in your proof. But meanwhile, let me help to analyze the complexity of your set by finding the exact complexity. I claim that your set $L$ is $\Pi^0_2$ complete, and therefore it is exactly equivalent to the double jump $0''$, which is the halting problem relativized to an oracle for the usual halting problem. Specifically, it is easy to see that $L$ has complexity $\forall\exists$, since $M$ is in $L$ just in case every even number input leads to an accepting computation, which is a $\forall\exists$ statement. Convesely, consider any $\forall\exists$ statement $\forall n\exists m\,\varphi(n,m)$, where $\varphi$ has only bounded quantifiers. We can create a machine $M$ that on input $2n$ searches for an $m$ for which $\varphi(n,m)$, accepting $2n$ when such an $m$ is found. Thus, the statement is true if and only if $M\in L$. So we have reduced $\Pi^0_2$ truth to $L$, and so it is $\Pi^0_2$-complete.

You have made an error. One cannot prove that a set is computably enumerable by reducing the halting problem to it. That would be like trying to show that someone is short by proving that they are at least as tall as a particular short person. After all, even very tall people are at least as tall as your given short person. Similarly, the halting problem reduces to sets of arbitrarily high complexity, since $0'\leq_T 0'\oplus A$ for any set $A$.

So that was the error in your proof. But meanwhile, let me help to analyze the complexity of your set by finding the exact complexity. I claim that your set $L$ is $\Pi^0_2$ complete, and therefore it is exactly equivalent to the double jump $0''$, which is the halting problem relativized to an oracle for the usual halting problem. Specifically, it is easy to see that $L$ has complexity $\forall\exists$, since $M$ is in $L$ just in case every even number input leads to an accepting computation, which is a $\forall\exists$ statement. Convesely, consider any $\forall\exists$ statement $\forall n\exists m\,\varphi(n,m)$, where $\varphi$ has only bounded quantifiers. We can create a machine $M$ that on input $2n$ searches for an $m$ for which $\varphi(n,m)$, accepting $2n$ when such an $m$ is found. Thus, the statement is true if and only if $M\in L$. So we have reduced $\Pi^0_2$ truth to $L$, and so it is $\Pi^0_2$-complete.

You have made an error. One cannot prove that a set is computably enumerable by reducing the halting problem to it. That would be like trying to show that someone is short by proving that they are at least as tall as a particular short person. After all, even very tall people are at least as tall as your given short person. Similarly, we cannot deduce that a set is simply by reducing a set to it, since even very complicated sets will have that feature. The halting problem reduces to sets of arbitrarily high complexity, since $0'\leq_T 0'\oplus A$ for any set $A$, but this doesn't mean that those sets are simple.

So that was the error in your proof. But meanwhile, let me help to analyze the complexity of your set by finding the exact complexity. I claim that your set $L$ is $\Pi^0_2$ complete, and therefore it is exactly equivalent to the double jump $0''$, which is the halting problem relativized to an oracle for the usual halting problem. Specifically, it is easy to see that $L$ has complexity $\forall\exists$, since $M$ is in $L$ just in case every even number input leads to an accepting computation, which is a $\forall\exists$ statement. Convesely, consider any $\forall\exists$ statement $\forall n\exists m\,\varphi(n,m)$, where $\varphi$ has only bounded quantifiers. We can create a machine $M$ that on input $2n$ searches for an $m$ for which $\varphi(n,m)$, accepting $2n$ when such an $m$ is found. Thus, the statement is true if and only if $M\in L$. So we have reduced $\Pi^0_2$ truth to $L$, and so it is $\Pi^0_2$-complete.

You have made an error. One cannot prove that a set is computably enumerable by reducing the halting problem to it. After all, the halting problem reduces to sets of arbitrarily high complexity, since $0'\leq_T 0'\oplus A$ for any set $A$.

Meanwhile, to give an exact answer for the complexity of your set, let me prove that your set $L$ is $\Pi^0_2$ complete, and therefore exactly equivalent to the double jump $0''$, which is the halting problem relativized to an oracle for the usual halting problem. Specifically, it is easy to see that $L$ has complexity $\forall\exists$, since $M$ is in $L$ just in case every even number input leads to an accepting computation, which is a $\forall\exists$ statement. Convesely, consider any $\forall\exists$ statement $\forall n\exists m\,\varphi(n,m)$, where $\varphi$ has only bounded quantifiers. We can create a machine $M$ that on input $2n$ searches for an $m$ for which $\varphi(n,m)$, accepting $2n$ when such an $m$ is found. Thus, the statement is true if and only if $M\in L$. So we have reduced $\Pi^0_2$ truth to $L$, and so it is $\Pi^0_2$-complete.

You have made an error. One cannot prove that a set is computably enumerable by reducing the halting problem to it. That would be like trying to show that someone is short by proving that they are at least as tall as a particular short person. After all, even very tall people are at least as tall as your given short person. Similarly, the halting problem reduces to sets of arbitrarily high complexity, since $0'\leq_T 0'\oplus A$ for any set $A$.

So that was the error in your proof. But meanwhile, let me help to analyze the complexity of your set by finding the exact complexity. I claim that your set $L$ is $\Pi^0_2$ complete, and therefore it is exactly equivalent to the double jump $0''$, which is the halting problem relativized to an oracle for the usual halting problem. Specifically, it is easy to see that $L$ has complexity $\forall\exists$, since $M$ is in $L$ just in case every even number input leads to an accepting computation, which is a $\forall\exists$ statement. Convesely, consider any $\forall\exists$ statement $\forall n\exists m\,\varphi(n,m)$, where $\varphi$ has only bounded quantifiers. We can create a machine $M$ that on input $2n$ searches for an $m$ for which $\varphi(n,m)$, accepting $2n$ when such an $m$ is found. Thus, the statement is true if and only if $M\in L$. So we have reduced $\Pi^0_2$ truth to $L$, and so it is $\Pi^0_2$-complete.