What is the difference between syntactic and semantic completeness?

The key is that syntactical consistency and completeness are defined relative to a proof system. That is, the notions of syntactical consistency and completeness refer to provability, and provability is always relative to a proof system.

Now, if you have a sound and complete proof system, then $T$ is syntactically complete if and only if $T$ is semantically complete, and the same goes for syntactic consistency vs semantic consistency.

However, if your proof system is unsound, or incomplete, then the two will diverge. Consider, for example, if your proof system contains the following inference rule:

$$\frac{}{\therefore P}\qquad \text{(Hokus Ponens)}$$

Well, such a proof system can of course prove everything, and any theory $T$ will be syntactically complete and syntactically inconsistent relative to this proof system, even as $T$ could well be semantically incomplete and semantically consistent.


Take $T$ to be predicate logic with equality. Any sentence that is true in every model of $T$ is provable (by Gödel's completeness theorem), so $T$ is semantically complete. Now take $\phi$ to be $\forall x\cdot \forall y\cdot x = y$. Neither $\phi$ nor $\lnot\phi$ can be provable, because $\phi$ is true in some models but not in others. So $T$ is not syntactically complete.

Tags:

Logic