Noname manuscript No. (will be inserted by the editor) Soundness and Completeness Proofs by Coinductive Methods

the date of receipt and acceptance should be inserted later Abstract Codatatypes are absent from many programming languages and theorem provers, reflecting their absence from the standard repertoire of most computer scientists and logi-cians. We make a case for their usefulness by showing how they 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 es-tablish an abstract property of possibly infinite derivation trees. The abstract proof can be instantiated for a wide range of Gentzen and tableau systems as well as various flavors of first-order logic. Soundness is often easy to prove, but it 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.