0
$\begingroup$

I have trouble understanding the explanation provided in my notes which goes as follows:

A set $\Sigma$ of L-formulas being inconsistent means $\Sigma\vdash\bot$.

Sound means $\Gamma\vdash\phi$ implies $\Gamma\models\phi$. It follows from soundness that inconsistent formulas do not have models. Strongly complete means $\Gamma\models\phi$ implies $\Gamma\vdash\phi$. It follows from strong completeness that all consistent sets of sentences have models.

For context, $\vdash$ is defined as a proof system for first order logic that is sound and complete for first order validities and $\Gamma$ is defined as a set of first order sentences.

I understand $\Sigma\vdash\bot$ to mean to be able to prove something false. However, all along, I read elsewhere and thought inconsistency means given a formula $\mathit{P}$, $\Sigma\vdash\mathit{P}\vee\neg\mathit{P}$. Is that any different to $\Sigma\vdash\bot$?

Also, more importantly, how are soundness, consistency and strong completeness related? In other words, I would appreciate an explanation on how the inconsistent formulas not having models follows from soundness and how all consistent sets of sentences having models follows from strong completeness.

Thank you in advance to anyone for any help!

$\endgroup$
  • $\begingroup$ It should be that $\Sigma\vdash\bot$ means $\Sigma\vdash\mathit{P}\wedge\neg\mathit{P}$. These are equivalent because the conjunction is a contradiction. $\endgroup$ – Ross Millikan Apr 16 at 1:19
1
$\begingroup$

Consistency can be defined in either semantic or syntactic terms.

From a syntactical point of view, considering a proof system and the corresponding relation of derivability ($\vdash$), a set of sentences $\Sigma$ is consistent if it does not contain a contradiction.

Thus, $\Sigma$ is inconsistent if $\Sigma \vdash P \land \lnot P$, for some formula $P$.

In some treatments of logic, the logical constant $\bot$ is used, representing a proposition that is always false, i.e. a contradiction.

Thus, inconsistency of $\Sigma$ can be equivalently formulated as : $\Sigma \vdash \bot$.

From a semantical point of view, a set $\Sigma$ of sentences is consistent if and only if it has a model, i.e., there exists an interpretation under which all formulas in the set are true.

In this case, we say also that the set is satisfiable.

To say that a proof system is sound means that :

only valid formulas can be derived with it. In symbols : $\text { if } \vdash \varphi, \text { then } \vDash \varphi$.

More generally : $\text { if } \Gamma \vdash \varphi, \text { then } \Gamma \vDash \varphi$.

Thus, soundness implies consistency, because $\bot$ is not valid.

(Semantic) completeness of a proof system is the "twin" property of soundness. It means that :

all valid formulas of the calculus are provable. In symbols : $\text { if } \vDash \varphi, \text { then } \vdash \varphi$.

So-called Strong completeness formalize the concept of logical consequence.

A proof system is strongly complete iff for every set of formulas $Γ$, any formula that semantically follows from $Γ$ is derivable from $Γ$. That is: $\text { if } \Gamma \vDash \varphi, \text { then } \Gamma \vdash \varphi$.

In classical logic, where Ex falso holds, an inconsistent set of sentences is obviously unsound but trivially complete : being inconsistent, it proves every formula, and thus also the valid ones.

Strictly related to completeness is the Model Existence Theorem :

If a set $\Sigma$ of sentences is consistent, then $\Sigma$ is satisfiable (i.e. it has a model).

From Model Existence Theorem, strong completeness follows :

(i) $\text {if } \Gamma \nvdash \varphi, \text { then } \Gamma \cup \{ \lnot \varphi \} \text { is consistent}$.

Thus,

(ii) $\Gamma \cup \{ \lnot \varphi \} \text { has a model}$.

This means that

(iii) $\Gamma \nvDash \varphi$.

$\endgroup$

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.