1
$\begingroup$

I understand the basic concepts of soundness and completeness in logical systems. However, when I took a look at the Wikipedia pages on both concepts, I saw that it listed a seperate strong form of each.

\begin{align} & \text{Soundness: if } \vdash \phi, \text{then} \vDash \phi \\ & \text{Strong Soundness: if } \Gamma \vdash \phi, \text{then } \Gamma \vDash \phi \\ & \\ & \text{(semantic) Completeness: if } \vDash \phi, \text{then} \vdash \phi \\ & \text{Strong Completeness: if } \Gamma \vDash \phi, \text{then } \Gamma \vdash \phi \\ & \text{(where } \phi \text{ is a sentence, and } \Gamma \text{ is a set of sentences)} \end{align}

This piqued my interest as I had not heard of this notion before. Looking at the definitions, I can see that the strong forms imply the weak forms, because $\Gamma$ can be the empty set.

What I noticed is that in almost all cases, the weak forms would appear to imply the strong forms, because it seems to hold (at least in 2-valued logics) that $\vDash A \to B$ is equivalent to $A \vDash B$ and $\vdash A \to B$ is equivalent to $A \vdash B$, for any A and B.

I know it must be possible for a logic to be weakly sound but not strongly sound, or weakly complete but not strongly complete, but are there any specific examples of logics that exhibit this property?

EDIT: @Mark Savings points out that weak soundness does not imply strong soundness when $\Gamma$ is infinite; I thus refine my question to ask if there are any examples of finite logics that are weakly sound/complete, but not strongly sound/complete.

$\endgroup$
2
  • 1
    $\begingroup$ Your argument about weak soundness implying strong soundness doesn’t seem to be valid. It works only when $\Gamma$ is finite. $\endgroup$ Dec 19, 2022 at 0:41
  • $\begingroup$ @MarkSaving Good catch. I will edit my question to specifically exclude infinitely long proofs. $\endgroup$
    – Nico
    Dec 19, 2022 at 0:56

1 Answer 1

2
$\begingroup$

For the soundness part, strong and weak are of course the same for finitary deduction systems (where every proof rule has only finitely many premisses), since a proof can only use finitely many formulas from the theory $\Gamma$.

For completeness however, that argument does not work, and modal logic with Kripke semantics provides many examples of weakly but not strongly complete logics. Two famous examples are:

  • GL (K + the Gödel-Löb axiom $□(□p \rightarrow p) \rightarrow □p$)
  • Grz (K + $◻(◻(p \rightarrow ◻p) \rightarrow p) \rightarrow p$).

The proof idea is as follows: Construct an infinite $\Gamma$ of which every finite subset is consistent with GL (resp. Grz) (construct a suitable frame), but the whole $\Gamma$ is not valid on any frame of GL (resp. Grz). Since every finite subset is consistent (and the logic is finitary), $\Gamma \nvdash \bot$. Since $\Gamma$ is not valid on any frame of GL, $\Gamma \vDash \bot$. (The full proof should be most introductory modal logic books, e.g. Blackburn et al. Thm 4.43.)

Hope that helps (although it might not be so useful when you don't know about Kripke semantics).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .