Skip to main content
Contribution to Book
Counting the Number of Proofs in the Commutative Lambek Calculus
JFAK. Essays Dedicated to Johan van Benthem on the Occasion of his 50th Birthday (1999)
  • Hans Joerg Tiede, Illinois Wesleyan University
Abstract

This paper is concerned with the study of the number of proofs of a sequent in the commutative Lambek calculus. We show that in order to count how many different proofs in \beta \eta -normal form a given sequent \Gamma \vdash \alpha has, it suffices to enumerate all the \Delta \vdash \beta which are “minimal”, such that \Gamma \vdash \alpha is a substitution instance of \Delta \vdash \beta. As a corollary we obtain van Benthem’s finiteness theorem for the Lambek calculus, which states that every sequent has finitely many different normal form proofs in the Lambek calculus.

Publication Date
1999
Editor
Jelle Gerbrandy, Maarten Marx, Maarten de Rijke, and Yde Venema
Publisher
Amsterdam University Press
Citation Information
Hans Joerg Tiede. "Counting the Number of Proofs in the Commutative Lambek Calculus" JFAK. Essays Dedicated to Johan van Benthem on the Occasion of his 50th Birthday (1999)
Available at: http://works.bepress.com/htiede/3/