Uniqueness of normal proofs in implicational intuitionistic logic


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 NJ
Keywords Natural deduction  uniqueness of normal proofs  coherence  minimal formulas  Komori's  non-prime contraction
Categories (categorize this paper)
Reprint years 2004
DOI 10.1023/A:1008254111992
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 49,096
Through your library

References found in this work BETA

Proof Theory.Gaisi Takeuti - 1987 - Elsevier.
Proof Theory.Gaisi Takeuti - 1990 - Studia Logica 49 (1):160-161.
Natural Deduction: A Proof-Theoretical Study.Richmond Thomason - 1965 - Journal of Symbolic Logic 32 (2):255-256.
Language in Action.Johan Van Benthem - 1991 - Journal of Philosophical Logic 20 (3):225-263.

View all 11 references / Add more references

Citations of this work BETA

On the Membership Problem for Non-Linear Abstract Categorial Grammars.Sylvain Salvati - 2010 - Journal of Logic, Language and Information 19 (2):163-183.

Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
48 ( #191,063 of 2,311,308 )

Recent downloads (6 months)
1 ( #753,648 of 2,311,308 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature