David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Logic, Language and Information 8 (2):217-242 (1999)
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 NJ
|Keywords||Natural deduction uniqueness of normal proofs coherence minimal formulas Komori's non-prime contraction|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Sylvain Salvati (2010). On the Membership Problem for Non-Linear Abstract Categorial Grammars. Journal of Logic, Language and Information 19 (2):163-183.
Similar books and articles
Yuichi Komori (1986). A New Semantics for Intuitionistic Predicate Logic. Studia Logica 45 (1):9 - 17.
Michael Zakharyaschev (1997). The Greatest Extension of S4 Into Which Intuitionistic Logic is Embeddable. Studia Logica 59 (3):345-358.
A. Avron (2000). Implicational F-Structures and Implicational Relevance Logics. Journal of Symbolic Logic 65 (2):788-802.
Diderik Batens (1987). Relevant Implication and the Weak Deduction Theorem. Studia Logica 46 (3):239 - 245.
Roy Dyckhoff & Luis Pinto (1998). Cut-Elimination and a Permutation-Free Sequent Calculus for Intuitionistic Logic. Studia Logica 60 (1):107-118.
Ryo Kashima & Norihiro Kamide (1999). Substructural Implicational Logics Including the Relevant Logic E. Studia Logica 63 (2):181-212.
M. W. Bunder (1982). Deduction Theorems for Weak Implicational Logics. Studia Logica 41 (2-3):95 - 108.
Makoto Tatsuta (1993). Uniqueness of Normal Proofs of Minimal Formulas. Journal of Symbolic Logic 58 (3):789-799.
Sachio Hirokawa, Yuichi Komori & Misao Nagayama (2000). A Lambda Proof of the P-W Theorem. Journal of Symbolic Logic 65 (4):1841-1849.
Added to index2009-01-28
Total downloads20 ( #100,246 of 1,692,744 )
Recent downloads (6 months)7 ( #32,727 of 1,692,744 )
How can I increase my downloads?