Admissibility of logical inference rules (Q1309039)

This book is a systematic self-contained description of the modern theory of inference rules for formal logical systems. The basic notions of any logical system, as it is commonly understood, are axioms and inference rules defining the corresponding consequence relation. The author's primary attention in this book is focused on the fundamental theoretical results concerning inference rules and logical consequence relations in classical and non-classical logics. Derivable rules of a logical system are those whose conclusions can be derived from their premises by using axioms and inference rules of the considered system. In some cases, other, possibly non-derivable, but stronger rules, could also be consistently employed. All the rules with respect to which the considered logical system is closed are called admissible (or permissible) inference rules. The book is divided into six chapters, the first two presenting an introduction to the syntax and semantics of (classical and non-classical) logics, while in the others, in the central part of the book, a fundamental theory of admissible logical inference rules is developed. The main themes of the first chapter are: the syntax of formal logical systems, first-order semantics and universal algebra, algebraic semantics for propositional logics, admissible rules in algebraic logic, logical consequence relations, algebraizable consequence relations, admissibility for consequence relations, and lattices of logical consequences. Particular examples include the usual classical and superintuitionistic propositional logics (i.e. extensions of Heyting logic), as well as modal and temporal logics. In the second chapter, the fundamentals of algebraic and Kripke-type semantics for (super) intuitionistic, modal and temporal logics are presented. The exposition concentrates around questions concerning Kripke's possible worlds semantics and its connections with algebraic semantics through Stone theory, as well as the effective use of semantics and its applications to the study of logical systems related to the finite model property, completeness etc. In the third chapter, the author starts to examine admissibility using advanced methods and presents various criteria for recognizing admissibility. Reduced forms of inference rules in modal and temporal logics are described, providing certain canonical forms for inference rules with a very simple and uniform structure. Gödel-McKinsey-Tarski translation \(T\) of intuitionistic logic into modal systems is extended, and relationships between the admissible, valid and derivable rules of superintuitionistic logics and the corresponding properties of their \(T\)-translations in the modal counterparts of superintuitionistic logics are studied. A semantic criterion for recognizing admissibility of inference rules in modal and superintuitionistic logics is given. Through a few general statements, the author describes wide classes of modal and superintuitionistic logics for which the admissibility of inference rules is decidable. In particular, a positive answer to H. Friedman's problem concerning the determination of admissible rules of intuitionistic logic (and also to the analogous question regarding other superintuitionistic and modal logics) is given. The presented results entail, for instance, that the quasi-equational theories of free algebras from many varieties of algebras corresponding to non-classical logics are decidable. In this chapter, the admissible inference rules for classical first-order theories, some examples of decidable propositional logics which are undecidable with respect to admissibility and certain criteria determining admissibility of inference rules employing particular properties of the reduced forms of inference rules are considered. The fourth chapter includes some initial algebraic results concerning the possession or lack of finite bases for quasi-identities of arbitrary algebraic systems. Certain general propositions show that any logic from various broad classes of non-classical logics satisfying some specific conditions cannot have bases for admissible rules in finitely many variables and, consequently, all such logics have no finite basis. Herefrom, a negative solution to A. Kuznetsov's problem of whether intuitionistic logic has a finite basis for its admissible rules and a negative answer to the analogous question regarding many other superintuitionistic and modal logics are given. It is shown that although there are finite simple modal and pseudo-Boolean algebras which have no finite bases for their quasi-identities, tabular logics always have finite bases for their valid inference rules, but also even tabular logics sometimes have no finite, and even no independent bases for admissible inference rules. The main topic of the fifth chapter is the property of structural completeness. The chapter starts with the general statements concerning structural completeness and the development of the technique of quasi-characteristic inference rules allowing to present another proof for the description of structurally complete extensions of the modal system K4 and of superintuitionistic logics. The central point of this chapter is a complete description of hereditarily structurally complete superintuitionistic logics and modal logics extending K4. The last section deals with structurally complete fragments of logics. The closing, sixth chapter is devoted to some advanced topics using techniques developed in previous chapters. In the first section, the problem of recognizing solvability of logical equations and the substitution problem are observed. These problems are reduced to a problem concerning the admissibility of inference rules in a generalized form. These results can be considered as a generalization of the basic results presented in the third chapter. The following sections describe those modal logics which preserve inference rules admissible in the modal Lewis system S4 and contain analogous propositions related to the preservation of admissibility for rules admissible in Heyting logic. The remaining sections include examples of Kripke non-compact modal and superintuitionistic logics. The book is written at a level appropriate to first-year graduate students in mathematics or computer science, presupposing some knowledge of elementary logic and universal algebra only. As the study of logical consequence relations and derivability in formal logical systems is an interdisciplinary subject, the book seems to be interesting not only to those concerned with modal, temporal and intuitionistic logics, universal algebra, algebraic logic and model theory, but also to specialists in philosophical logic, computer science and information science. The author raises a number of new interesting questions and this book seems to be a reasonable basis for new further investigations. Undoubtedly, this fine and clearly written book will be an appropriate reference to the contemporary subjects of non-classical logics.