Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

How do I prove that a proof system is complete? I mean what are the guidelines to such proof?

share|improve this question
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. –  Emil Jeřábek Jun 1 '11 at 10:07
add comment

1 Answer

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:

  1. 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”.

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

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.