2
$\begingroup$

A formal system is complete with respect to a semantics, if all validities are derivable (i.e. if $\ \vDash\phi\ $ then $\ \vdash\phi$).

A formal system is strongly complete with respect to a semantics, if for every set of formulas $\Gamma$, the formulas that are semantically entailed by $\Gamma$ are derivable from $\Gamma$ (i.e. if $\ \Gamma\vDash\phi\ $ then $\ \Gamma\vdash\phi$).

What is an example of a formal system that is complete wrt a semantics but not strongly complete wrt to that semantics?

$\endgroup$
2
$\begingroup$

Segerberg's Propositional Dynamic Logic (PDL) is complete with respect to its intended semantics, but not compact so not strongly complete.

(Since completeness plus compactness gives strong completeness, you need a non-compact logic.)

$\endgroup$
  • $\begingroup$ Proof of non-compactness of PDL can be found here (Theorem 5.10). Proof of "completeness + compactness gives strong completeness" follows easily from deduction theorem (see here). $\endgroup$ – LoMaPh Nov 24 '17 at 6:10

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.