Non-commutative classical arithmetical sequent calculi are intuitionistic

Revantha Ramanayake*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

A non-commutative first-order sequent calculus NCLK equivalent to Gentzen's sequent calculus LJ for intuitionistic logic was recently presented such that the addition of exchange rules to NCLK yields a calculus equivalent to Gentzen's sequent calculus LK for classical logic. In Gentzen's original treatment, the intuitionistic calculus LJ was obtained from LK by restricting the sequents to at most one formula in the succedent. Distinguishing between a classical and intuitionistic calculus solely by the presence or absence of the exchange rules thus provides a new perspective on these calculi. Unfortunately, the sequent calculus NCLK is highly non-standard for several reasons. In addition, the original proof relies on a technical intermediate step utilizing a complicated induction measure. Here we present a direct proof of this result using a calculus that is almost identical to Gentzen's LK. Recent work by Tatsuta and Berardi suggests that the logic obtained by deleting the exchange rules from a sequent calculus for infinitary Peano arithmetic is not infinitary Heyting arithmetic but instead an extension of the latter by a restricted excluded middle principle. Here we show how to recover infinitary Heyting arithmetic, thus developing further the 'classical calculus minus exchange rules is the intuitionistic calculus' paradigm. Finally, we resolve an open problem posed in that work by showing that the sequent calculus for Peano arithmetic minus the exchange rules is Heyting arithmetic. Results are obtained using a uniform method of proof.

Original languageEnglish
Pages (from-to)441-452
Number of pages12
JournalLogic Journal of the IGPL
Volume24
Issue number3
DOIs
Publication statusPublished - Jun-2016
Externally publishedYes

Keywords

  • Proof theory
  • intuitionistic sequent calculus
  • exchange rules
  • Heyting arithmetic

Cite this