Soundness and completeness proofs by coinductive methods


Blanchette, J., Popescu, A. and Traytel, D. 2017. Soundness and completeness proofs by coinductive methods. Journal of Automated Reasoning. 58 (1), pp. 149-179.
TitleSoundness and completeness proofs by coinductive methods
AuthorsBlanchette, J., Popescu, A. and Traytel, D.

We show how codatatypes can be employed to produce compact, high-level proofs of key results in logic: the soundness and completeness of proof systems for variations of first-order logic. For the classical completeness result, we first establish an abstract property of possibly infinite derivation trees. The abstract proof can be instantiated for a wide range of Gentzen and tableau systems for various flavors of first-order logic. Soundness becomes interesting as soon as one allows infinite proofs of first-order formulas. This forms the subject of several cyclic proof systems for first-order logic augmented with inductive predicate definitions studied in the literature. All the discussed results are formalized using Isabelle/HOL’s recently introduced support for codatatypes and corecursion. The development illustrates some unique features of Isabelle/HOL’s new coinductive specification language such as nesting through non-free types and mixed recursion–corecursion.

Research GroupFoundations of Computing group
JournalJournal of Automated Reasoning
Publication dates
Online18 Oct 2016
Print01 Jan 2017
Publication process dates
Deposited19 Jun 2017
Accepted07 Oct 2016
Output statusPublished
Accepted author manuscript
Copyright Statement

This is a post-peer-review, pre-copyedit version of an article published in Journal of Automated Reasoning. The final authenticated version is available online via Springer at

Digital Object Identifier (DOI)
Permalink -

Download files

Accepted author manuscript
  • 18
    total views
  • 0
    total downloads
  • 2
    views this month
  • 0
    downloads this month

Export as