# Is Entscheidungsproblem in Co-RE? And Proof if it is.

As I study through, I learned that Entscheidungsproblem has a negative answer. Then I came to wonder whether the problem is in Co-RE. If it is, can anyone show me the proof?

Thanks.

• What does "Entscheidungsproblem has a negative answer" mean here? – Raphael Feb 12 '12 at 9:43

Suppose $X$ is the set of all first-order statements true in $\mathbb{N}$. You already know that $X$ is uncomputable. Now suppose that $X$ was r.e. or co-r.e., and consider $\{\lnot \varphi : \varphi \in X \}$. What can you deduce?
Edit: It seems that the correct interpretation of "universally valid" implies that we can use Gödel's completeness theorem to recursively enumerate all universally true statements by going through all valid proofs. The incompleteness theorem shows that for some theories there will be statements $\varphi$ such that neither $\varphi$ nor $\lnot \varphi$ show up in this enumeration.