Enderton (in A Mathematical Introduction to Logic) gives the following theorems:
Theorem $17$F : A set of expressions is decidable iff both it and its complement (relative to the set of all expressions) are effectively enumerable.
Theorem $17$G : If $\Sigma$ is a decidable set of wffs, then the set of tautological consequences of $\Sigma$ is effectively enumerable.
Are those two theorems enough to prove the following claim?
Claim: Every complete axiomatizable theory is decidable.
My attempt : let $T$ be an axiomatizable theory, such that there is a decidable set $\Sigma$ of sentences such that $\mathsf{Cn}(\Sigma)=T$ (where $\mathsf{Cn}(\Sigma)$ is the deductive closure of $\Sigma$). Since $\Sigma$ is decidable, then by Theorem $17$G, the set of its tautological consequences is effectively enumerable. But this set is precisely $\mathsf{Cn}(\Sigma)$, therefore $\mathsf{Cn}(\Sigma)$ is effectively enumerable. Thus, by Theorem $17$F, $\mathsf{Cn}(\Sigma)$ is decidable. Finally, since $\mathsf{Cn}(\Sigma)=T$, $T$ is decidable.
I think my application of Theorem $17$F is not correct, since I haven't shown that the complement of $\mathsf{Cn}(\Sigma)$ is also effectively enumerable. How can I do that? I guess I have to use the fact that $T$ is a complete theory, but I'm not sure how.
Best Answer
Hint: since the theory is complete, for any sentence $\sigma$, $\sigma \not \in Cn(\Sigma) \iff \neg \sigma \in Cn(\Sigma)$.