The Naturality of Natural Deduction

Studia Logica 107 (1):195-231 (2019)
  Copy   BIBTEX

Abstract

Developing a suggestion by Russell, Prawitz showed how the usual natural deduction inference rules for disjunction, conjunction and absurdity can be derived using those for implication and the second order quantifier in propositional intuitionistic second order logic NI\. It is however well known that the translation does not preserve the relations of identity among derivations induced by the permutative conversions and immediate expansions for the definable connectives, at least when the equational theory of NI\ is assumed to consist only of \- and \-equations. On the basis of the categorial interpretation of NI\, we introduce a new class of equations expressing what in categorial terms is a naturality condition satisfied by the transformations interpreting NI\-derivations. We show that the Russell–Prawitz translation does preserve identity of proof with respect to the enriched system by highlighting the fact that naturality corresponds to a generalized permutation principle. Finally we sketch how these results could be used to investigate the properties of connectives definable in the framework of higher-level rules.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Natural deduction with general elimination rules.Jan von Plato - 2001 - Archive for Mathematical Logic 40 (7):541-567.
Translations from natural deduction to sequent calculus.Jan von Plato - 2003 - Mathematical Logic Quarterly 49 (5):435.
Expressive Power and Incompleteness of Propositional Logics.James W. Garson - 2010 - Journal of Philosophical Logic 39 (2):159-171.
Normal deduction in the intuitionistic linear logic.G. Mints - 1998 - Archive for Mathematical Logic 37 (5-6):415-425.
Sequent Calculus in Natural Deduction Style.Sara Negri & Jan von Plato - 2001 - Journal of Symbolic Logic 66 (4):1803-1816.
Sequent calculus in natural deduction style.Sara Negri & Jan von Plato - 2001 - Journal of Symbolic Logic 66 (4):1803-1816.
A Binary-conclusion Natural Deduction System.K. Fujita - 1999 - Logic Journal of the IGPL 7 (4):517-545.
Natural deduction for first-order hybrid logic.Torben BraÜner - 2005 - Journal of Logic, Language and Information 14 (2):173-198.
Substructural Logics in Natural Deduction.Ernst Zimmermann - 2007 - Logic Journal of the IGPL 15 (3):211-232.
Natural deduction for bi-intuitionistic logic.Luca Tranchini - 2017 - Journal of Applied Logic 25:S72-S96.
Gentzen's proof systems: byproducts in a work of genius.Jan von Plato - 2012 - Bulletin of Symbolic Logic 18 (3):313-367.
A normalizing system of natural deduction for intuitionistic linear logic.Sara Negri - 2002 - Archive for Mathematical Logic 41 (8):789-810.

Analytics

Added to PP
2017-12-20

Downloads
40 (#347,990)

6 months
6 (#203,358)

Historical graph of downloads
How can I increase my downloads?

Author Profiles