Deduction chains for common knowledge

✍ Scribed by Mathis Kretz; Thomas Studer

• Publisher: Elsevier Science
• Year: 2006
• Tongue: English
• Weight: 287 KB
• Volume: 4
• Category: Article
• ISSN: 1570-8683
• DOI: 10.1016/j.jal.2005.06.011

✦ Synopsis

Deduction chains represent a syntactic and in a certain sense constructive method for proving completeness of a formal system. Given a formula φ, the deduction chains of φ are built up by systematically decomposing φ into its subformulae. In the case where φ is a valid formula, the decomposition yields a (usually cut-free) proof of φ. If φ is not valid, the decomposition produces a countermodel for φ. In the current paper, we extend this technique to a semiformal system for the Logic of Common Knowledge. The presence of fixed point constructs in this logic leads to potentially infinite-length deduction chains of a non-valid formula, in which case fairness of decomposition requires special attention. An adequate order of decomposition also plays an important role in the reconstruction of the proof of a valid formula from the set of its deduction chains.