4
$\begingroup$

I had asked and then deleted a few questions over the last few days. I've pinpointed my confusion to the following (mainly to the second set of questions in bold):

Assume we are working in a standard FOL.

Given a set of formula $\Gamma$ and a formula $\varphi$ we have:

  • '$\Gamma \models \varphi$' means:

$$ \forall \mathfrak A \bigl[ (\forall \psi\in\Gamma: \mathfrak A\models \psi) \;\to\; \mathfrak A\models\varphi \bigr ] $$

Where $\forall \mathfrak A$ ranges over structures defined in typical fashion.

  • When $\Gamma$ is empty, we write '$\models \varphi$' and may also say that $\varphi$ is valid.

  • '$\Gamma \vdash \varphi$' means there is a derivation of $\varphi$ from $\Gamma$, where a derivation is defined in typical fashion.

  • When $\Gamma$ is empty, we write '$\vdash \varphi$' to mean $\varphi$ is derivable (provable) from just axioms and inference rules of our system.


The soundness and completeness properties given below are properties of our standard first-order-logic (as opposed to properties of theories).

  • Soundess: $\Gamma$ $\vdash \varphi$ then $\Gamma \models \varphi$
  • Completeness: $\Gamma \models \varphi$ then $\Gamma \vdash \varphi$

The completeness theorem of FOL established the latter. Thus, we have: $\Gamma$ $\vdash \varphi$ $\iff$ $\Gamma \models \varphi$

Questions: What is strong completeness and what is weak completeness and how do they relate to the above definition of completeness? But moreso, what is the proof that the following are logically equivalent definitions of soundness and completeness:

  • Soundness: If $\Gamma$ has a model, then $\Gamma$ is consistent

  • Completeness: If $\Gamma$ is consistent, then $\Gamma$ has a model.


  • A theory (of standard FOL) is simply a set of formulas of our language (whether a theory is deductively closed or not depends on the definition given by the author)
  • A theory $\mathcal{T}$ is said to be consistent if there does not exist a formula $\varphi$ in $\mathcal{T}$ such that $\mathcal{T} \vdash \varphi$ and $\mathcal{T} \vdash \neg\varphi$
  • A theory $\mathcal{T}$ is said to be complete if for every formula $\varphi$ (in its vocabulary) either $\mathcal{T} \vdash \varphi$ or $\mathcal{T} \vdash \neg\varphi$

Questions: Are the following alternative definitions of a theory being consistent/complete logically equivalent to the ones given above (I think yes as it i think it would follow from the soundness and completeness of FOL)

  • A theory $\mathcal{T}$ is said to be consistent if there does not exist a formula $\varphi$ in $\mathcal{T}$ such that $\mathcal{T} \models \varphi$ and $\mathcal{T} \models \neg\varphi$
  • A theory $\mathcal{T}$ is said to be complete if for every formula $\varphi$ (in its vocabulary) either $\mathcal{T} \models \varphi$ or $\mathcal{T} \models\neg\varphi$
$\endgroup$
  • $\begingroup$ Edit: It seems like you were using $\phi$ (\phi) and $\Phi$ (\Phi) interchangeably, sometimes within the same sentence. I changed all instances to $\varphi$ (\varphi) for consistency (and because I think it looks nicer). $\endgroup$ – Alex Kruckman Apr 30 '17 at 18:17
  • $\begingroup$ Ok, thanks. Yeah, the consistency is better. $\endgroup$ – Parry Apr 30 '17 at 18:18
  • 2
    $\begingroup$ Strong and weak completeness are also discussed in my recent question here: math.stackexchange.com/questions/2257971/… $\endgroup$ – symplectomorphic Apr 30 '17 at 19:05
  • $\begingroup$ Whats FOL? Perhaps you should make ur question self contained, if even its by explaining what FOL stands for. $\endgroup$ – Charlie Parker Feb 19 '18 at 3:50
5
$\begingroup$

On strong/weak completeness: Let's say we have a logic, which comes with a syntax (defining what it means to be a sentence), a notion of semantic entailment $\models$ (from sets of sentences to sentences), and a notion of provability $\vdash$ (again, from sets of sentences to sentences).

Then we say $\vdash$ is weakly complete if, for every sentence $\varphi$, $$(\models \varphi)\text{ implies }(\vdash \varphi).$$ And we say $\vdash$ is strongly complete if, for every sentence $\varphi$ and every set of sentences $\Gamma$, $$(\Gamma\models \varphi)\text{ implies }(\Gamma \vdash \varphi).$$ Strong completeness is often just called completeness, as you did in your question. Now strong completeness obviously implies weak completeness, taking $\Gamma = \emptyset$. Conversely, if our logic satisfies the compactness theorem (as FOL does), then under a few basic assumptions on how $\vdash$ behaves, weak completeness also implies strong completeness. See this question and answer for details.

For the rest of the answer, I'll assume we're talking about the standard notions of $\models$ and $\vdash$ for FOL. But again, what I write below will apply to any abstract logic which satisfies some basic assumptions on how $\vdash$ and $\models$ behave.

On the alternative definitions of soundness and completeness:

Let's call your first definition of soundness S1 and your second definition S2.

S1$\implies$S2: Suppose $\Gamma$ has a model $M$. Then $\Gamma\not\models \bot$, since $M\not\models \bot$. So by S1, $\Gamma\not\vdash \bot$. That is, $\Gamma$ is consistent.

S2$\implies$S1: Suppose $\Gamma\vdash \varphi$. Then $\Gamma\cup \{\lnot\varphi\}$ is inconsistent, since it can prove $\varphi\land \lnot\varphi$. By S2, $\Gamma\cup \{\lnot\varphi\}$ has no models. So every model of $\Gamma$ satisfies $\varphi$, i.e. $\Gamma\models \varphi$.

Similarly, let's call your first definition of completeness C1 and your second definition C2.

C1$\implies$C2: We prove the contrapositive. If $\Gamma$ has no models, then vacuously $\Gamma\models \bot$, so by C1 $\Gamma\vdash \bot$. That is, $\Gamma$ is inconsistent.

C2$\implies$C1: Again, we prove the contrapositive. If $\Gamma\not\vdash \varphi$, $\Gamma\cup\{\lnot\varphi\}$ is consistent (here we use proof by contradiction in $\vdash$, i.e. if $\Gamma\cup \{\lnot \varphi\}\vdash \bot$, then $\Gamma\vdash \varphi$). By C2, $\Gamma \cup\{\lnot\varphi\}$ has a model $M$. So $\Gamma\not\models \varphi$, since $M\models \Gamma$ but $M\not\models \varphi$.

On completeness and consistency of a theory: Yes, the semantic ($\models$) and syntactic ($\vdash$) definitions of completeness and consistency of $\mathcal{T}$ are equivalent, thanks to the soundness and completeness of FOL, which says that $\models$ and $\vdash$ agree!

$\endgroup$
  • $\begingroup$ What a great answer. Thank you. $\endgroup$ – Parry Apr 30 '17 at 19:05

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.