2
$\begingroup$

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!

1 Answers 1

1

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$.