How do I prove that a proof system is complete? I mean what are the guidelines to such proof?
1
-
1$\begingroup$ This heavily depends on what kind of proof system it is, and with respect to what kind of semantics is it supposed to be proven complete. You really should include more details. $\endgroup$– Emil JeřábekCommented Jun 1, 2011 at 10:07
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It’s impossible to give anything but vague answer to such a vague question, but on a hand-waving high level, there are basically two common approaches to completeness proofs:
Show that any set of formulas can be extended to a maximally consistent set or a prime theory or an appropriate analogue for the given logic, and then build a model from these MCS in such a way that a formula is true wrt a particular MCS iff it belongs to the MCS. This strategy is generally used for logics with Kripke semantics. Typically, the extension to a MCS can be obtained from Zorn’s lemma. For quantified logics, this usually has to be coupled with introduction of Henkin constants to have quantifiers witnessed. For cut-free calculi, one uses some sort of “saturated” sets instead of MCS which only satisfy the relevant properties “downwards”.
Take the Lindenbaum–Tarski algebra of the logic, and use it to define a model. This is normally used for logics with algebraic semantics. It often includes some algebraic manipulation to make the underlying algebra nicer, such as making it subdirectly irreducible, or even embedding it in some canonically chosen algebra.
answered Jun 1, 2011 at 10:31