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.

I am trying to show the following equivalence: a (consistent) first-order theory $T$ is essentially undecidable if and only if every complete extension of $T$ is undecidable. By "$T$ is essentially undecidable" I mean that any consistent extension of $T$ is undecidable. So clearly the forward direction is obvious.

So far, my idea for the reverse direction is to suppose, towards contradiction, that there exists a consistent extension $S$ of $T$ such that the theory generated by $S$, denoted $Th_S$, is decidable. I now want to prove that for any decidable theory there exists a decidable complete extension, but I do not know how to construct such a complete extension.

Any advice would be much appreciated! Thanks!

share|improve this question
    
Why the low accept rate? –  Brett Frankel Apr 18 '12 at 2:41
add comment

1 Answer

up vote 1 down vote accepted

Never mind, I figured it out. I just forgot that complete r.e. theories are decidable.

What one needs to do is to suppose that $S$ is so that $Th_S$ is decidable. Then one can build up recursively a complete extension $S^*$ of $Th_S$.

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.