Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
What does "Entscheidungsproblem has a negative answer" mean here? – Raphael Feb 12 '12 at 9:43
up vote 8 down vote accepted

From wikipedia

The Entscheidungsproblem has often been identified in particular with the decision problem for first-order logic (that is, the problem of algorithmically determining whether a first-order statement is universally valid).

The set of universally valid first-order statements is known to be r.e. and not recursive. If it was co-r.e. (by which I mean its complement is r.e.), then it would be recursive. (A set that is both r.e. and co-r.e. is recursive). Hence it is not co-r.e.

share|cite|improve this answer

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.

share|cite|improve this answer

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.