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.

  • $\begingroup$ See Coroll 26I, page 157. $\endgroup$ – Mauro ALLEGRANZA May 13 '15 at 10:05
  • $\begingroup$ @MauroALLEGRANZA Well, yes, but that brings me back to Coroll 25F and Coroll 25G of the enumerability theorem (page 142), which is (more or less) equivalent to theorem 17G. That seems a bit circular to me. Can we show the claim in question using only the two theorems stated in the question? $\endgroup$ – Demosthene May 13 '15 at 10:16
  • 1
    $\begingroup$ Exactly : Coroll 25G : "for any sentence $\sigma$ either $\Gamma \vDash \sigma$ or $\Gamma \vDash \lnot \sigma$. Then the set of sentences implied by $\Gamma$ is decidable." But this (see page 156) is guaranteed by the fact that $\mathsf{Cn}(\Gamma)=T$ is complete. $\endgroup$ – Mauro ALLEGRANZA May 13 '15 at 10:22
  • $\begingroup$ @MauroALLEGRANZA That makes perfect sense, thank you :) I just realised that my lecturer used a different definition of $\mathsf{Cn}$ than Enderton, hence my confusion. $\endgroup$ – Demosthene May 13 '15 at 10:24
  • $\begingroup$ I see ... :) From you previous post, I deduce that $\mathsf{Cn}(\Sigma) = \{ \phi \mid \Sigma \vdash \phi \}$. But, for prop logic as well as f-o logic, by completeness this is equivalent to : $\mathsf{Cn}(\Sigma) = \{ \phi \mid \Sigma \vDash \phi \}$. $\endgroup$ – Mauro ALLEGRANZA May 13 '15 at 10:27

Hint: since the theory is complete, for any sentence $\sigma$, $\sigma \not \in Cn(\Sigma) \iff \neg \sigma \in Cn(\Sigma)$.

  • 1
    $\begingroup$ Ohhh, right. I think I got a bit confused because my lecturer uses the syntactic definition of $\mathsf{Cn}$ whereas Enderton uses the semantic one. Thanks! $\endgroup$ – Demosthene May 13 '15 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.