Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
What does "Entscheidungsproblem has a negative answer" mean here? –  Raphael Feb 12 '12 at 9:43
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.