It is apparent to me what the difference between syntactic consistency and semantic consistency is.

A theory $T$ is syntactically consistent if there exists no formula $\phi$ in the language such that both $\phi$ and $\neg \phi$ are provable.

A theory $T$ is semantically consistent if it has a model. If $T$ has a model, there exists an interpretation where all formulas of $T$ are true.

However, I do not understand the difference between syntactic completeness and semantic completeness. My understanding of the two properties is:

A theory $T$ is syntactically complete if for every formula $\phi$ in the language of the theory, either $\phi$ or $\neg \phi$ is provable.

A theory $T$ is semantically complete if, in every interpretation, every true formula $\phi$ is provable.

I do not understand how syntactic completeness can be false while semantic completeness can be true at the same time. I understand that this is true (it's true in any first order theory that is subject to Gödel's incompleteness theorem), I just do not see how they are not always true at the same time.

  • $\begingroup$ You need to add a few more definitions before this can be properly addressed: What is an interpretation? What is a true formula? What does it mean to prove a formula in an interpretation? $\endgroup$ Jul 10 '17 at 1:38
  • $\begingroup$ @user462082 Can you tell me which textbooks you are reading? Where these definitions from? I'm also a learner. Thanks. :) $\endgroup$
    – Eric
    Jul 11 '17 at 16:32

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.

  • 2
    $\begingroup$ Just so that I am 100% clear, when you say "Take $T$ to be predicate logic with equality" you mean that T is every syntactically correct formula in predicate logic, as opposed to T being some specific theory with only specific axioms and theorems, like ZFC or PA? So Gödel's completeness theorem basically says that every tautology in predicate logic is provable, given a specific proof system? I think my initial confusing was between a logical system (predicate calculus) and a logical theory (something like ZFC). $\endgroup$
    – user462082
    Jul 12 '17 at 1:20
  • $\begingroup$ The completeness theorem says that any consistent theory has a model. $\endgroup$
    – Rob Arthan
    Jul 12 '17 at 2:41
  • $\begingroup$ To expand on my rather terse comment: if a sentence $\phi$ is not provable from $T$, then $T \cup \{\lnot\phi\}$ is consistent and so by completeness has a model (in which $\phi$ is not true). On your second point, it may help to think of predicate calculus as a logical theory in which the intended universe of discourse has no properties other than the ones required by pure logic. $\endgroup$
    – Rob Arthan
    Jul 13 '17 at 22:27
  • $\begingroup$ This is a naïve question... but, if $\phi$ is true in every model of T and thus semantically complete and provable, how can it be that the same $\phi$ or its negation are not provable? $\endgroup$
    – Lugh
    Aug 24 '17 at 17:53
  • 2
    $\begingroup$ @RobArthan Do you mean "$\forall x(x\cdot x=x)$" instead of "$\forall x\cdot x=x$"? The statement "$\forall x(x=x)$" - which is what the expression you've written looks like right now - is definitely true in every structure (at least, assuming the usual semantics for first-order logic in which the empty "structure" is not permitted). $\endgroup$ Nov 9 '18 at 2:17

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.

  • 2
    $\begingroup$ A variation is an empty proof system, in which you cannot deduce anything. $\endgroup$ Jul 9 '17 at 1:27
  • 2
    $\begingroup$ @MarianoSuárez-Álvarez Yeah, I thought of using that, but it's not as much fun as Hokus Ponens! :) $\endgroup$
    – Bram28
    Jul 9 '17 at 1:28
  • 3
    $\begingroup$ Your hokus ponens doesn't answer the question. The OP wants a system with a $\phi$ such that neither $\phi$ nor $\lnot\phi$ is provable, but such that every formula that is true in all models is provable. $\endgroup$
    – Rob Arthan
    Jul 9 '17 at 23:16

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.