13

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.

Community
  • 1
user462082
  • 155
  • 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? – Andrés E. Caicedo Jul 10 '17 at 01:38
  • @user462082 Can you tell me which textbooks you are reading? Where these definitions from? I'm also a learner. Thanks. :) – Eric Jul 11 '17 at 16:32

2 Answers2

7

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.

Rob Arthan
  • 48,577
  • 2
    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). – user462082 Jul 12 '17 at 01:20
  • The completeness theorem says that any consistent theory has a model. – Rob Arthan Jul 12 '17 at 02:41
  • 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. – Rob Arthan Jul 13 '17 at 22:27
  • 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? – Lugh Aug 24 '17 at 17:53
  • @Lugh: Semantic completeness is a property of $T$ not $\phi $. You can have a $\phi $ that is true in some models of $T $ but not others without violating semantic completeness: see the answer for an example. – Rob Arthan Aug 24 '17 at 19:00
  • Would the recent downvoter care to comment on his or her inexplicable action? – Rob Arthan Aug 26 '17 at 21:06
  • 2
    @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). – Noah Schweber Nov 09 '18 at 02:17
  • (Ignore my parenthetical - I somehow mixed up "$\forall x(x=x)$ is true" and "$\forall x(x\not=x)$ is false." Derp. My main point stands, though.) – Noah Schweber Nov 09 '18 at 03:21
  • @NoahSchweber: thanks for your comment, which has only just come to my attention. I've corrected the answer to say what I meant to say. – Rob Arthan Oct 01 '19 at 19:07
  • On reflection I think this answer is incorrect. I've never seen "semantically complete" used to mean "every sentence true in every model of the theory is provable from the theory" - completeness trivializes this. The definition of semantic completeness I've seen is "every sentence is either true in all models of $T$ or false in all models of $T$," which - like consistency - completeness implies is equivalent to its syntactic analogue. (cont'd) – Noah Schweber Oct 02 '19 at 02:48
  • This matches the OP's definition: "if, in every interpretation, every true formula $\varphi$ is provable" as opposed to "if every formula true in every interpretation is provable." In the absence of a source using the term in that way, I think what happened is that the OP misunderstood what's going on in incompleteness (the theory is both syntactically and semantically incomplete, but the logic itself is complete). – Noah Schweber Oct 02 '19 at 02:50
  • The OP's definition of "semantically complete" is a little unclear. I am taking it as meaning that every true formula is provable, where "true" means valid in every model, in some understood class of models. I think with that reading my answer is now OK. If you looked at the theory in the language with just equality generated by a proper subset of the usual axioms, you would get a theory that is not semantically complete in this sense. – Rob Arthan Oct 16 '19 at 14:37
5

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.

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • 2
    A variation is an empty proof system, in which you cannot deduce anything. – Mariano Suárez-Álvarez Jul 09 '17 at 01:27
  • 2
    @MarianoSuárez-Álvarez Yeah, I thought of using that, but it's not as much fun as Hokus Ponens! :) – Bram28 Jul 09 '17 at 01:28
  • 3
    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. – Rob Arthan Jul 09 '17 at 23:16