A connection between cut elimination and normalization


Mirjana Borisavljević




Sequent systems for classical anti intuitionistic logic and natural deduction systems for these logics are characterized by two important theorems. Sequent systems are characterized by cut- elimination theorems, and natural deduction systems by normalization theorems. In this paper, by means of multicategories and the typed $\lambda$-calculus we exhibit some similarities and differences between cut elimination and normalization. We consider the sequent system and the natural deduction system for intuitionistic propositional logic. We define a multicategory corresponding to the sequent system. On the other hand, a typed $\lambda$-calculus corresponds to the natural-deduction system. We show how to form a typed $\lambda$-calculus out of a multicategory and vice-versa. In some kinds of multicategory, some equations necessary for cut elimination, are not. necessary for normalization.