Nikolaos Galatos Peter Jipsen Hiroakira Ono
Preface
The field of substructural logic, as a research area and a unifying subject, is relatively new. The term itself was introduced at a conference on logics with restricted structural rules in T¨ ubingen, 1990 and the proceedings were published under the title “Substructural Logics” in 1993 with P. Schr¨oder Heister and K. Doˇzen as editors. Specific substructural logics, however, have a long history. These include linear logic (1987), relevance logic (1970s, but also going back to 1950s and 1920s), Lambek calculus (1950s), L ukasiewicz many-valued logics and fuzzy logics (1920s), to name some of the most prominent ones, without forgetting, of course, the two limit cases of intuitionistic logic and classical logic. Within the more general setting of non-classical logics, substructural logics play a prominent role, but also connect to other such logics; for example to modal logics via translations and to certain paraconsistent logics via pairs constructions. Research in substructural logic tends to interweave applications and results on specific logics with the development of the general theory in a natural way. It is very common that general principles are observed only after they have been noticed on specific substructural logics, while after such general results have been obtained one may be able to vastly simplify or sharpen them in the context of a given logic. It is this interaction that provides strength to the area, with many researchers work alternating from the concrete to the abstract and back again. Other researchers specialize in certain logics or in the general theory, contributing to a vibrant community and to furthering our understanding on multiple fronts. Synthesis often takes place well after penetrating results have been proven, the intention of which was most often of quite limited and targeted scope. On the one hand, it is the wealth of different perspectives, motivations and intuitions from the various substructural logics that when combined, or when the appropriate viewpoint is adopted in the general study, yield interesting general results. These different aspects stem, for example,
Special Issue: Recent Developments related to Residuated Lattices and Substructural Logics Edited by Nikolaos Galatos, Peter Jipsen, and Hiroakira Ono
Studia Logica (2012) 100: 1059–1062 DOI: 10.1007/s11225-012-9461-4
© Springer Science+Business Media Dordrecht 2012
1060
N. Galatos, P. Jipsen and H. Ono
from grammatical, linguistic, combinatorial, computational, truth-degree, or philosophical considerations. On the other hand, results in each particular substructural logic are viewed as especially interesting when they succeed in explaining the particular and peculiar aspects and features of the logic, as separating it from other substructural logics and thus point to the adequacy or motivational content of the given logic. One of the most notable variations among different substructural logics is the presence or absence of certain structural rules in each logic, when a sequent calculus formulation is adopted. The particular mix of structural rules is often responsible for the behavior of a logic with respect to various logical properties. This observation motivates the general study of substructural logics as a useful framework for discussing properties of specific logics. The proof-theoretic study of substructural logic has been based to a great extent on cut-elimination results. The logical consequences often include a variety of applications, such as decidability of theoremhood, interpolation, etc. The difficulties that appear in the presence of the contraction rule were noticed early on, as it leads to the undecidability for certain logics. When the logics are decidable, the computational complexity is very high. Recently we have seen renewed interest in establishing complexity bounds, but there is still a lot of work to be done in this direction. On the algebraic side, the property of residuation is the key feature of the algebraic models, residuated lattices. Also, the algebraic study followed an equally long, but parallel path, until the two approaches were recognized to be two sides of the same coin, when both logicians and algebraists independently took a better look at the key features behind the common subject. Results from universal algebra and abstract algebraic logic played an important role in the formation of the particular algebraic-logic culture in the area. Categorical connections between lattice-ordered groups and (pseudo) MV-algebras have proved to be very fruitful in transporting results between these areas. In the area of fuzzy logics, generalizations of Hajek’s Basic Logic and BL-algebras to pseudo BL-algebras and generalized BL-algebras (i.e., the non-commutative and non-prelinear unbounded theories) provide further evidence that the umbrella of substructural logic and residuated lattices is a suitable framework for many results that were previously only know in much more restricted cases. As a third approach, relational semantics and duality theory, which are an integral part of the close cousins of modal logics, as well as of intermediate and relevance logics, were also developed for substructural logic. These are of a different flavor, however, mainly because they are based on (non-distributive) lattices. On the other hand, it was recently realized that
Preface
1061
such (two-sorted) relational semantics fit very well into the proof-theoretic consideration of (two-sided) sequents, as well as the partial order relation in algebra. Though still in the early stages of development, this has lead to algebraic proof theory, which discusses unexpectedly deep connections between proof theory and order-algebra. No doubt the field of substructural logics and residuated lattices will grow further as an interdisciplinary research field. The book “Residuated Lattice: An Algebraic Glimpse at Substructural Logics” (Studies in Logic and the Foundations of Mathematics, Vol 151, Elsevier, 2007) has served as an introduction to the field to both students and researchers who want to explore different aspects related to their field of study, and is now one of the standard reference sources. In this special issue of Studia Logica, following an open call, one can find papers covering several extensions of directions in the book. They are an excellent representation of the breadth, depth and vibrancy of the research within the area of residuated lattices and substructural logics. More specifically, this volume includes papers on - n-potent varieties of residuated lattices that are atoms in the lattice of all subvarieties, - the join of the varieties of Boolean algebras and lattice-ordered groups within the lattice of varieties of FL-algebras, - bounded commutative integral residuated lattices with a unary term that defines a retraction from each algebra to its Boolean skeleton, - characterizing when varieties of bounded weak-commutative residuated lattices with a S4-modal operator are discriminator varieties or have equationally definable principal congruences, - relevant modal logics and an algebraic proof of the admissibility of the material detachment rule, - metacompleteness of predicate substructural logics (including the involutive case) from which the disjunction property, the existence property and the admissibility of various rules are deduced, - equality algebras that are term equivalent to BCK algebras with meet and lead to an equational characterization of the equivalential fragment of BCK algebras with meet, - a classical relevance logic that is pretabular, i.e., has no finite matrix model but every proper extension of the logic does, - sound and complete unified display calculi for several bunched logics that arise from free combinations of additive (intuitionistic) connectives with
1062
N. Galatos, P. Jipsen and H. Ono
multiplicative connective and have found recent applications in separation logic and software analysis, - showing that Heyting algebras with successor and height ≤ n have the amalgamation property, hence the corresponding intuitionistic propositional calculi have the Craig interpolation property, - Lewis dichotomy results for Kleene logic and G¨odel logic characterizing when algebraic models of these logics have satisfiability problems that are NP-complete, and showing that they are polynomial time otherwise, - lattice effect algebras characterized in terms of Sasaki algebras and compared with Basic Logic algebras and other basic algebras. We hope that these contributions will be of interest to the readers. In our opinion, other directions of study that are worth pursuing in the area of substructural logics include modal substructural logics. Intuitionistic modal logics, relevant modal logics, as well as many-valued modal logics have been considered in recent years; however, a comprehensive study from the perspective of substructural logic is still to be provided. Algebraic semantics have been the favorite tool for substructural logics, while modal logics have capitalized on relational semantics, hence a combination of the two logics would require some ingenuity if it is to encompass both success stories. Another challenging direction is the development of quantified substructural logics, as such study is currently lacking in both its proof-theoretic and its semantical aspects. No doubt many other directions will be explored and developed by researchers in this area of logic. Based on the past success of unifying underlying principles of substructural logics and residuated lattices, we are optimistic that research in these fields will result in many new elegant general results and significant applications. N. Galatos, P. Jipsen and H. Ono October 2012