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

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|cite|improve this question
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|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.