Paper: Complete Sequent Calculi for Induction and Infinite Descent (at LICS 2007)

Authors: James Brotherston Alex K. Simpson

Abstract

This paper compares two different styles of reasoning with inductively defined predicates, each style being encapsulated by a corresponding sequent calculus proof system. The first system supports traditional proof by induction, with induction rules formulated as sequent rules for introducing inductively defined predicates on the left of sequents. We show this system to be cut-free complete with respect to a natural class of Henkin models; the eliminability of cut follows as a corollary. The second system uses infinite (non-well-founded) proofs to represent arguments by infinite descent. In this system, the left rules for inductively defined predicates are simple case-split rules, and an infinitary, global condition on proof trees is required to ensure soundness. We show this system to be cut-free complete with respect to standard models, and again infer the eliminability of cut. The second infinitary system is unsuitable for formal reasoning. However, it has a natural restriction to proofs given by regular trees, i.e. to those proofs representable by finite graphs. This restricted "cyclic" system subsumes the first system for proof by induction. We conjecture that the two systems are in fact equivalent, i.e., that proof by induction is equivalent to regular proof by infinite descent.

BibTeX

  @InProceedings{BrotherstonSimpson-CompleteSequentCalc,
    author = 	 {James Brotherston and Alex K. Simpson},
    title = 	 {Complete Sequent Calculi for Induction and Infinite Descent},
    booktitle =  {Proceedings of the Twenty-Second Annual IEEE Symposium on Logic in Computer Science (LICS 2007)},
    year =	 {2007},
    month =	 {July}, 
    pages =      {51--60},
    location =   {Wroclaw, Poland}, 
    publisher =	 {IEEE Computer Society Press}
  }