Uniqueness of normal proofs in implicational intuitionistic logic
Journal of Logic, Language and Information 8 (2):217-242 (1999)
Abstract
A minimal theorem in a logic L is an L-theorem which is not a non-trivial substitution instance of another L-theorem. Komori (1987) raised the question whether every minimal implicational theorem in intuitionistic logic has a unique normal proof in the natural deduction system NJ. The answer has been known to be partially positive and generally negative. It is shown here that a minimal implicational theorem A in intuitionistic logic has a unique -normal proof in NJ whenever A is provable without non-prime contraction. The non-prime contraction rule in NJ is the implication introduction rule whose cancelled assumption differs from a propositional variable and appears more than once in the proof. Our result improves the known partial positive solutions to Komori's problem. Also, we present another simple example of a minimal implicational theorem in intuitionistic logic which does not have a unique -normal proof in NJReprint years
2004
DOI
10.1023/a:1008254111992
My notes
Similar books and articles
A new semantics for intuitionistic predicate logic.Yuichi Komori - 1986 - Studia Logica 45 (1):9 - 17.
Uniqueness of normal proofs of minimal formulas.Makoto Tatsuta - 1993 - Journal of Symbolic Logic 58 (3):789-799.
Deduction theorems for weak implicational logics.M. W. Bunder - 1982 - Studia Logica 41 (2-3):95 - 108.
Substructural implicational logics including the relevant logic E.Ryo Kashima & Norihiro Kamide - 1999 - Studia Logica 63 (2):181-212.
Cut-elimination and a permutation-free sequent calculus for intuitionistic logic.Roy Dyckhoff & Luis Pinto - 1998 - Studia Logica 60 (1):107-118.
Relevant implication and the weak deduction theorem.Diderik Batens - 1987 - Studia Logica 46 (3):239 - 245.
Implicational f-structures and implicational relevance logics.A. Avron - 2000 - Journal of Symbolic Logic 65 (2):788-802.
The greatest extension of s4 into which intuitionistic logic is embeddable.Michael Zakharyaschev - 1997 - Studia Logica 59 (3):345-358.
A lambda proof of the p-w theorem.Sachio Hirokawa, Yuichi Komori & Misao Nagayama - 2000 - Journal of Symbolic Logic 65 (4):1841-1849.
Analytics
Added to PP
2009-01-28
Downloads
48 (#246,608)
6 months
1 (#455,463)
2009-01-28
Downloads
48 (#246,608)
6 months
1 (#455,463)
Historical graph of downloads
Citations of this work
On the membership problem for non-linear abstract categorial grammars.Sylvain Salvati - 2010 - Journal of Logic, Language and Information 19 (2):163-183.
References found in this work
Natural Deduction: A Proof-Theoretical Study.Dag Prawitz - 1965 - Stockholm, Sweden: Dover Publications.
Natural Deduction: A Proof-Theoretical Study.Richmond Thomason - 1965 - Journal of Symbolic Logic 32 (2):255-256.