2

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?

LoMaPh
  • 1,361

1 Answers1

3

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.)

Peter Smith
  • 54,743
  • 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). – LoMaPh Nov 24 '17 at 06:10