Residuated Lattices : An Algebraic Glimpse at Substructural Logics.
Title:
Residuated Lattices : An Algebraic Glimpse at Substructural Logics.
Author:
Galatos, Nikolaos.
ISBN:
9780080489643
Personal Author:
Physical Description:
1 online resource (532 pages)
Series:
Studies in Logic and the Foundations of Mathematics ; v.151
Studies in Logic and the Foundations of Mathematics
Contents:
Cover -- Copyright Page -- Table of Contents -- Detailed Contents -- List of Figures -- List of Tables -- Introduction -- Chapter 1. Getting started -- 1.1. First-order languages and semantics -- 1.1.1. Preorders -- 1.1.2. Posets -- 1.1.3. Lattices -- 1.1.4. Heyting algebras and Boolean algebras -- 1.1.5. Semigroups, monoids and other groupoids -- 1.2. Concepts from universal algebra -- 1.2.1. Homomorphisms, subalgebras, substructures, direct products -- 1.2.2. Congruences -- 1.2.3. Free algebras -- 1.2.4. More on Heyting and Boolean algebras -- 1.2.5. Mal'cev conditions -- 1.2.6. Ultraproducts and Jónsson's Lemma -- 1.2.7. Equational logic -- 1.2.8. Quasivarieties -- 1.3. Logic -- 1.3.1. Hilbert calculus for classical logic -- 1.3.2. Gentzen's sequent calculus for classical logic -- 1.3.3. Calculi for intuitionistic logic -- 1.3.4. Provability in Hilbert and Gentzen calculi -- 1.4. Logic and algebra -- 1.4.1. Validity of formulas in algebras -- 1.4.2. Lindenbaum-Tarski algebras -- 1.4.3. Algebraization -- 1.4.4. Superintuitionistic logics -- 1.5. Cut elimination in sequent calculi -- 1.5.1. Cut elimination -- 1.5.2. Decidability and subformula property -- 1.6. Consequence relations and matrices -- 1.6.1. Consequence relations -- 1.6.2. Inference rules -- 1.6.3. Proofs and theorems -- 1.6.4. Matrices -- 1.6.5. Examples -- 1.6.6. First-order and (quasi)equational logic -- Exercises -- Notes -- Chapter 2. Substructural logics and residuated lattices -- 2.1. Sequent calculi and substructural logics -- 2.1.1. Structural rules -- 2.1.2. Comma, fusion and implication -- 2.1.3. Sequent calculus for the substructural logic FL -- 2.1.4. Deducibility and substructural logics over FL -- 2.2. Residuated lattices and FL-algebras -- 2.3. Important subclasses of substructural logics -- 2.3.1. Lambek calculus -- 2.3.2. BCK logic and algebras.
2.3.3. Relevant logics -- 2.3.4. Linear logic -- 2.3.5. ukasiewicz logic and MV-algebras -- 2.3.6. Fuzzy logics and triangular norms -- 2.3.7. Superintuitionistic logics and Heyting algebras -- 2.3.8. Minimal logic and Brouwerian algebras -- 2.3.9. Fregean logics and equivalential algebras -- 2.3.10. Overview of logics over FL -- 2.4. Parametrized local deduction theorem -- 2.5. Hilbert systems -- 2.5.1. The systems HFLe and HFL -- 2.5.2. Derivable rules -- 2.5.3. Equality of two consequence relations -- 2.6. Algebraization and deductive filters -- 2.6.1. Algebraization -- 2.6.2. Deductive filters -- Exercises -- Notes -- Chapter 3. Residuation and structure theory -- 3.1. Residuation theory and Galois connections -- 3.1.1. Residuated pairs -- 3.1.2. Galois connections -- 3.1.3. Binary residuated maps -- 3.2. Residuated structures -- 3.3. Involutive residuated structures -- 3.3.1. Involutive posets -- 3.3.2. Involutive pogroupoids -- 3.3.3. Involutive division posets -- 3.3.4. Term equivalences -- 3.3.5. Constants -- 3.3.6. Dual algebras -- 3.4. Further examples of residuated structures -- 3.4.1. Boolean algebras and generalized Boolean algebras -- 3.4.2. Partially ordered and lattice ordered groups -- 3.4.3. The negative cone of a residuated lattice -- 3.4.4. Cancellative residuated lattices -- 3.4.5. MV-algebras and generalized MV-algebras -- 3.4.6. BL-algebras and generalized BL-algebras -- 3.4.7. Hoops -- 3.4.8. Relation algebras -- 3.4.9. Ideals of a ring -- 3.4.10. Powerset of a monoid -- 3.4.11. The nucleus image of a residuated lattice -- 3.4.12. The Dedekind-MacNeille completion of a residuated lattice -- 3.4.13. Order ideals of a partially ordered monoid -- 3.4.14. Quantales -- 3.4.15. Retraction to an interval -- 3.4.16. Conuclei and kernel contractions -- 3.4.17. The dual of a residuated lattice with respect to an element.
3.4.18. Translations with respect to an invertible element -- 3.5. Subvariety lattices -- 3.5.1. Some subvarieties of FL -- 3.5.2. Some subvarieties of FLw -- 3.5.3. Some subvarieties of RL -- 3.6. Structure theory -- 3.6.1. Structure theory for special cases -- 3.6.2. Convex normal subalgebras and submonoids, congruences and deductive filters -- 3.6.3. Central negative idempotents -- 3.6.4. Varieties with (equationally) definable principal congruences -- 3.6.5. The congruence extension property -- 3.6.6. Subdirectly irreducible algebras -- 3.6.7. Constants -- Exercises -- Notes -- Chapter 4. Decidability -- 4.1. Syntactic proof of cut elimination -- 4.1.1. Basic idea of cut elimination -- 4.1.2. Contraction rule and mix rule -- 4.2. Decidability as a consequence of cut elimination -- 4.2.1. Decidability of basic substructural logics without contraction rule -- 4.2.2. Decidability of intuitionistic logic „ Gentzens idea -- 4.2.3. Decidability of basic substructural logics with the contraction rule -- 4.3. Further results -- 4.4. Undecidability -- 4.4.1. The quasiequational theory of residuated lattices -- 4.4.2. The word problem -- 4.4.3. Modular lattices -- 4.4.4. Distributive residuated lattices -- Exercises -- Notes -- Chapter 5. Logical and algebraic properties -- 5.1. Syntactic approach to logical properties -- 5.1.1. Disjunction property -- 5.1.2. Craig interpolation property -- 5.1.3. Maehara's method -- 5.1.4. Variable sharing property of logics without the weakening rules -- 5.2. Maksimova's variable separation property -- 5.3. Algebraic characterizations -- 5.3.1. Disjunction property -- 5.3.2. Halldén Completeness -- 5.4. Maksimova's property and well-connected pairs -- 5.5. Deductive interpolation properties -- 5.5.1. Strong deductive interpolation property -- 5.5.2. Robinson property -- 5.5.3. Amalgamation property and Robinson property.
5.5.4. Algebraic characterization of the deductive interpolation property -- 5.6. Craig interpolation property -- 5.6.1. Extensions of Craig interpolation property -- 5.6.2. Super-amalgamation property and strong Robinson property -- 5.6.3. Algebraic characterization of Craig interpolation property -- 5.6.4. Joint embedding property -- 5.6.5. Interpolation property and pseudo-relevance property -- Exercises -- Notes -- Chapter 6. Completions and finite embeddability -- 6.1. Completions of posets -- 6.1.1. Some properties of canonical extensions -- 6.1.2. Canonical extensions of maps -- 6.1.3. Operators and preservation of identities -- 6.2. Canonical extensions of residuated groupoids -- 6.2.1. Canonicity -- 6.2.2. A counterexample for canonical extensions -- 6.3. Nuclear completions of residuated groupoids -- 6.3.1. Canonical extensions as nuclear completions -- 6.4. Negative results for completions -- 6.4.1. MV-algebras -- 6.4.2. Lattice-ordered groups -- 6.4.3. Product algebras -- 6.5. Finite embeddability property -- 6.5.1. An embedding construction -- 6.5.2. FEP for some subvarieties of FL -- 6.5.3. Counterexamples for FEP -- Exercises -- Notes -- Chapter 7. Algebraic aspects of cut elimination -- 7.1. Gentzen matrices for the sequent calculus FL -- 7.2. Quasi-completions and cut elimination -- 7.3. Cut elimination for other systems -- 7.3.1. Involutive substructural logics -- 7.3.2. Cyclic substructural modal logics -- 7.3.3. Completeness of tableau systems -- 7.4. Finite model property -- Exercises -- Notes -- Chapter 8. Glivenko theorems -- 8.1. Overview -- 8.2. Glivenko equivalence -- 8.3. Glivenko properties -- 8.3.1. The Glivenko property -- 8.3.2. The deductive Glivenko property -- 8.3.3. The equational Glivenko property -- 8.3.4. An axiomatization for the Glivenko variety of an involutive variety.
8.4. More on the equational Glivenko property -- 8.4.1. The deductive equational Glivenko property -- 8.4.2. An alternative characterization for the equational Glivenko property -- 8.5. Special cases -- 8.5.1. The cyclic case -- 8.5.2. The classical case -- 8.5.3. The basic logic case -- 8.6. Generalized Kolmogorov translation -- Exercises -- Notes -- Chapter 9. Lattices of logics and varieties -- 9.1. General facts about atoms -- 9.2. Minimal subvarieties of RL -- 9.2.1. Commutative, representable atoms -- 9.2.2. Cancellative atoms -- 9.2.3. Bounded, 3-potent, representable atoms -- 9.2.4. Idempotent, commutative atoms -- 9.2.5. Idempotent, representable atoms -- 9.3. Minimal subvarieties of FL -- 9.3.1. Minimal subvarieties of FLo and FLi -- 9.3.2. Minimal subvarieties of representable FLec and FLei -- 9.3.3. Minimal subvarieties of FLe with term-definable bounds -- 9.3.4. Minimal subvarieties of FLeco -- 9.4. Almost minimal subvarieties of FLew -- 9.4.1. General facts about almost minimal varieties -- 9.4.2. Almost minimal subvarieties of InFLew -- 9.4.3. Almost minimal subvarieties of representable FLew -- 9.4.4. Almost minimal subvarieties of 2-potent DFLew -- 9.5. Almost minimal varieties of BL-algebras -- 9.6. Translations of subvariety lattices -- 9.6.1. Generalized ordinal sums -- 9.7. Axiomatizations for joins of varieties and meets of logics -- 9.7.1. Varieties of residuated lattices generated by positive universal classes -- 9.7.2. Equational basis for joins of varieties -- 9.7.3. Direct product decompositions -- 9.8. The subvariety lattices of LG and LG- -- 9.8.1. From subvarieties of LG- to subvarieties of LG -- 9.8.2. From subvarieties of LG to subvarieties of LG- -- 9.8.3. Categorical equivalence and the functor L -> L- -- Exercises -- Notes -- Chapter 10. Splittings -- 10.1. Splittings in general.
10.2. Splittings in varieties of algebras.
Abstract:
The book is meant to serve two purposes. The first and more obvious one is to present state of the art results in algebraic research into residuated structures related to substructural logics. The second, less obvious but equally important, is to provide a reasonably gentle introduction to algebraic logic. At the beginning, the second objective is predominant. Thus, in the first few chapters the reader will find a primer of universal algebra for logicians, a crash course in nonclassical logics for algebraists, an introduction to residuated structures, an outline of Gentzen-style calculi as well as some titbits of proof theory - the celebrated Hauptsatz, or cut elimination theorem, among them. These lead naturally to a discussion of interconnections between logic and algebra, where we try to demonstrate how they form two sides of the same coin. We envisage that the initial chapters could be used as a textbook for a graduate course, perhaps entitled Algebra and Substructural Logics. As the book progresses the first objective gains predominance over the second. Although the precise point of equilibrium would be difficult to specify, it is safe to say that we enter the technical part with the discussion of various completions of residuated structures. These include Dedekind-McNeille completions and canonical extensions. Completions are used later in investigating several finiteness properties such as the finite model property, generation of varieties by their finite members, and finite embeddability. The algebraic analysis of cut elimination that follows, also takes recourse to completions. Decidability of logics, equational and quasi-equational theories comes next, where we show how proof theoretical methods like cut elimination are preferable for small logics/theories, but semantic tools like Rabin's theorem work better for big ones. Then we turn
to Glivenko's theorem, which says that a formula is an intuitionistic tautology if and only if its double negation is a classical one. We generalise it to the substructural setting, identifying for each substructural logic its Glivenko equivalence class with smallest and largest element. This is also where we begin investigating lattices of logics and varieties, rather than particular examples. We continue in this vein by presenting a number of results concerning minimal varieties/maximal logics. A typical theorem there says that for some given well-known variety its subvariety lattice has precisely such-and-such number of minimal members (where values for such-and-such include, but are not limited to, continuum, countably many and two). In the last two chapters we focus on the lattice of varieties corresponding to logics without contraction. In one we prove a negative result: that there are no nontrivial splittings in that variety. In the other, we prove a positive one: that semisimple varieties coincide with discriminator ones. Within the second, more technical part of the book another transition process may be traced. Namely, we begin with logically inclined technicalities and end with algebraically inclined ones. Here, perhaps, algebraic rendering of Glivenko theorems marks the equilibrium point, at least in the sense that finiteness properties, decidability and Glivenko theorems are of clear interest to logicians, whereas semisimplicity and discriminator varieties are universal algebra par exellence. It is for the reader to judge whether we succeeded in weaving these threads into a seamless fabric.
Local Note:
Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2017. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.
Genre:
Electronic Access:
Click to View