Uniqueness of normal proofs in implicational intuitionistic logic

Journal of Logic, Language and Information 8 (2):217-242 (1999)
  Copy   BIBTEX


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



    Upload a copy of this work     Papers currently archived: 93,296

External links

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

Through your library


Added to PP

7 (#1,413,139)

6 months
57 (#86,857)

Historical graph of downloads
How can I increase my 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.

Add more citations

References found in this work

Natural deduction: a proof-theoretical study.Dag Prawitz - 1965 - Mineola, N.Y.: Dover Publications.
Proof theory.Gaisi Takeuti - 1975 - New York, N.Y., U.S.A.: Sole distributors for the U.S.A. and Canada, Elsevier Science Pub. Co..
Logic and structure.D. van Dalen - 1980 - New York: Springer Verlag.
Natural Deduction: A Proof-Theoretical Study.Richmond Thomason - 1965 - Journal of Symbolic Logic 32 (2):255-256.
Proof Theory.Gaisi Takeuti - 1990 - Studia Logica 49 (1):160-161.

View all 14 references / Add more references