This volume is dedicated to our friend, colleague, and teacher Joachim (Jim) Lambek.
On December 5, 1997, a small conference was held at McGill on the occasion of Jim Lambek's 75th birthday. Subsequently it was decided to publish two volumes of papers contributed in his honour to mark this occasion; this issue of Mathematical Structures in Computer Science is one of the volumes, the other is Volume 6 of the journal Theory and Applications of Categories . At the December 1997 conference, a brief biographical essay was presented by Michael Barr; that essay appears in the TAC volume. But we wish to make some further remarks here.
Jim completed his Ph.D. at McGill under Hans Zassenhaus in 1950, and has remained at McGill since then. But it is of interest to note that Jim wrote two theses: the second involved biquaternions in mathematical physics, and so forshadows a significant feature of his career: Jim has consistently shown a remarkable range of interests, from physics to linguistics, from algebra to logic, from the history and philosophy of mathematics to the theory of computing science (although he never touches a computer, to this day!). Let us just review a small sample of his more than 100 published papers.
In the early part of his career, he worked in combinatorics, algebra, and elementary number theory, often in collaboration with Leo Moser. By the late 1950's he was working primarily in algebra and ring theory, from which his book "Lectures on Rings and Modules" (1966) came some years later. In the period 1958-1960 he produced several remarkably influential works in different areas. His first paper in mathematical linguistics, "The mathematics of sentence structure", was published in 1958. This, together with subsequent papers, developed into an autonomous discipline ("Lambek grammars"). Now, in hindsight, we can also recognize that Lambek was actually describing certain Gentzen logical systems, but without Gentzen's structural rules. Thirty years later, these systems are considered as precursors to the theory of non-commutative linear logics, in the sense of J-Y Girard. Another paper, "How to program an Infinite Abacus" in the Canadian Bulletin of Math. (1960), developed a kind of abstract computing device now known as a register machine, an important Turing-complete model of computation. This model was simultaneously developed by Minsky and Shepherdson & Sturgis around the same time and is now a standard concept in computation theory.
In the mid 1960's Lambek became increasingly interested in category theory. His first monograph, "Completions of Categories" (Springer LNM 24), dates from that time. By the end of the 1960's, he was working in several areas of category theory which would later be of fundamental importance in theoretical computer science. Thus, for example, in 1968 he published a paper "A fixpoint theorem for complete categories" (Math. Zeitschrift), in which he generalized the Tarski fixed point theorem to finding fixed points of endofunctors. His insight was to look for initial T-algebras, for certain endofunctors T, since he observed these necessarily satisfy that T(A) is isomorphic to A. This viewpoint has been seminal in subsequent work on categorical data types. Starting in 1969 in a series of papers, Lambek introduced one of his most influential bodies of work: his introduction of categorical proof theory (in which categories could be thought of as labelled deductive systems). As an application, Lambek applied Gentzen's proof-theoretic techniques, notably cut-elimination, to solving categorical coherence problems. Major advances to these ideas in coherence theory, inspired by Lambek's insights, were later achieved by G. Mints and his student S. Soloviev. Also, the formalism he introduced, "multi-categories", is having a major revival in current higher-dimensional category theory.
In the 1970's, Lambek continued his work in ring theory and categorical algebra (often in collaboration with B. Rattray) while simultaneously expanding his research into categorical aspects of lambda calculus and higher-order logics. There then followed a fruitful collaboration on categorical logic with P. Scott, culminating in their book "Introduction to Higher Order Categorical Logic" in 1986. Meanwhile, starting in the mid 1970's, Lambek returned to his former interests in mathematical linguistics, working in formal grammars for verb conjugation in French and Latin, for kinship terminology in anthropology, and, more recently, the use of type theory in modern linguistics.
In recent years, far from slowing down, Lambek has in fact increased his research productivity. He has devoted a large part of his research towards so-called substructural logics-logics without Gentzen's structural rules. This includes his work in bilinear logic and its applications to algebra and linguistics. However he has also continued to keep a hand in his many other interests, notably history and philosophy of mathematics, and mathematical physics. In that regard, he has returned to some of his original work in 1950, speculating in a paper "If Hamilton Had Prevailed" (Math. Intelligencer, 1995) how theoretical physics might have developed if Hamilton's quaternionic methods had prevailed over vectorial ones. And his recent philosophical papers have argued for a reconciliation of various competing philosophies of mathematics (formalism, logicism, Platonism, intuitionism), using categorical models developed in the Lambek-Scott book.
Finally, we should point out that Jim has a great stock of stories about his many colleagues in different disciplines. One of his favourites recalls taking mathematicians and linguists out to a restaurant in Montreal. As he points out "the mathematicians couldn't figure out the bill, and the linguists couldn't speak French".
As friends, collegues, and students of Jim's for many years, we are pleased to be able to present to him this collection of papers, whose span covers much (unfortunately not all) of the territory Jim's own work has influenced so profoundly. We join the authors of these papers in wishing him well, and hoping to derive further inspiration from his research for many years to come.