×

Residuated frames with applications to decidability. (English) Zbl 1285.03077

From the authors’ introduction: “In this paper we introduce residuated frames and show that they provide relational semantics for substructural logics and representations for residuated structures. Our approach is driven by the applications of the theory. As is the case with Kripke frames for modal logics, residuated frames provide a valuable tool for solving both algebraic and logical problems. Moreover, we show that there is a direct link between Gentzen-style sequent calculi and our residuated frames, which gives insight into the connection between a cut-free proof system and the finite embeddability property for the corresponding variety of algebras.”
Residuated frames are a natural generalisation of such tools as Kripke frames and phase spaces.
The authors present a common generalization of various known results on the cut-elimination property for several logical systems, decidability, the finite model property and the finite embeddability property, and use their generalization to obtain new results concerning the two latter properties. They apply the techniques of residuated frames also to prove new positive results about involutive residuated structures.

MSC:

03G25 Other algebras related to logic
03B25 Decidability of theories and sets of sentences
03B47 Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics)
03F05 Cut-elimination and normal-form theorems
06B20 Varieties of lattices
06F05 Ordered semigroups and monoids
Full Text: DOI

References:

[1] V. Michele Abrusci, Phase semantics and sequent calculus for pure noncommutative classical linear propositional logic, J. Symbolic Logic 56 (1991), no. 4, 1403 – 1451. · Zbl 0746.03044 · doi:10.2307/2275485
[2] Francesco Belardinelli, Peter Jipsen, and Hiroakira Ono, Algebraic aspects of cut elimination, Studia Logica 77 (2004), no. 2, 209 – 240. · Zbl 1064.03014 · doi:10.1023/B:STUD.0000037127.15182.2a
[3] W. J. Blok and C. J. van Alten, The finite embeddability property for residuated lattices, pocrims and BCK-algebras, Algebra Universalis 48 (2002), no. 3, 253 – 271. · Zbl 1058.06016 · doi:10.1007/s000120200000
[4] W. J. Blok and C. J. Van Alten, On the finite embeddability property for residuated ordered groupoids, Trans. Amer. Math. Soc. 357 (2005), no. 10, 4141 – 4157. · Zbl 1083.06013
[5] Kevin Kendall Blount, On the structure of residuated lattices, ProQuest LLC, Ann Arbor, MI, 1999. Thesis (Ph.D.) – Vanderbilt University.
[6] Kevin Blount and Constantine Tsinakis, The structure of residuated lattices, Internat. J. Algebra Comput. 13 (2003), no. 4, 437 – 461. · Zbl 1048.06010 · doi:10.1142/S0218196703001511
[7] Wojciech Buszkowski, Interpolation and FEP for logics of residuated algebras, Log. J. of IGPL. doi:10.1093/jigpal/jzp094. · Zbl 1259.03085
[8] Agatha Ciabattoni, Nikolaos Galatos, and Kazushige Terui, From axioms to analytic rules in nonclassical logics, Proceedings of LICS’08 (2008), 229-240.
[9] Agatha Ciabattoni, Nikolaos Galatos, and Kazushige Terui, The expressive power of structural rules for FL. submitted. · Zbl 1259.03086
[10] J. Michael Dunn, Mai Gehrke, and Alessandra Palmigiano, Canonical extensions and relational completeness of some substructural logics, J. Symbolic Logic 70 (2005), no. 3, 713 – 740. · Zbl 1101.03021 · doi:10.2178/jsl/1122038911
[11] Maciej Farulewski, Finite embeddability property for residuated groupoids, Rep. Math. Logic 43 (2008), 25 – 42. · Zbl 1156.06006
[12] Nikolaos Galatos, Peter Jipsen, Tomasz Kowalski, and Hiroakira Ono, Residuated lattices: an algebraic glimpse at substructural logics, Studies in Logic and the Foundations of Mathematics, vol. 151, Elsevier B. V., Amsterdam, 2007. · Zbl 1171.03001
[13] Nikolaos Galatos and Hiroakira Ono, Algebraization, parametrized local deduction theorem and interpolation for substructural logics over FL, Studia Logica 83 (2006), no. 1-3, 279 – 308. · Zbl 1105.03021 · doi:10.1007/s11225-006-8305-5
[14] Nikolaos Galatos and Hiroakira Ono, Cut elimination and strong separation for substructural logics: an algebraic approach, Ann. Pure Appl. Logic 161 (2010), no. 9, 1097 – 1133. · Zbl 1245.03027 · doi:10.1016/j.apal.2010.01.003
[15] Nikolaos Galatos and Constantine Tsinakis, Generalized MV-algebras, J. Algebra 283 (2005), no. 1, 254 – 291. · Zbl 1063.06008 · doi:10.1016/j.jalgebra.2004.07.002
[16] Bernhard Ganter and Rudolf Wille, Formale Begriffsanalyse, Springer-Verlag, Berlin, 1996 (German, with German summary). Mathematische Grundlagen. [Mathematical foundations]. Bernhard Ganter and Rudolf Wille, Formal concept analysis, Springer-Verlag, Berlin, 1999. Mathematical foundations; Translated from the 1996 German original by Cornelia Franzke. · Zbl 0861.06001
[17] Mai Gehrke, Generalized Kripke frames, Studia Logica 84 (2006), no. 2, 241 – 275. · Zbl 1115.03013 · doi:10.1007/s11225-006-9008-7
[18] P. Jipsen and C. Tsinakis, A survey of residuated lattices, Ordered algebraic structures, Dev. Math., vol. 7, Kluwer Acad. Publ., Dordrecht, 2002, pp. 19 – 56. · Zbl 1070.06005 · doi:10.1007/978-1-4757-3627-4_3
[19] Mitsuhiro Okada and Kazushige Terui, The finite model property for various fragments of intuitionistic linear logic, J. Symbolic Logic 64 (1999), no. 2, 790 – 802. · Zbl 0930.03021 · doi:10.2307/2586501
[20] Hiroakira Ono and Yuichi Komori, Logics without the contraction rule, J. Symbolic Logic 50 (1985), no. 1, 169 – 201. · Zbl 0583.03018 · doi:10.2307/2273798
[21] Kimmo I. Rosenthal, Quantales and their applications, Pitman Research Notes in Mathematics Series, vol. 234, Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1990. · Zbl 0703.06007
[22] Jürgen Schmidt and Constantine Tsinakis, Relative pseudo-complements, join-extensions, and meet-retractions, Math. Z. 157 (1977), no. 3, 271 – 284. · Zbl 0351.06010 · doi:10.1007/BF01214357
[23] Kazushige Terui, Which structural rules admit cut elimination? An algebraic criterion, J. Symbolic Logic 72 (2007), no. 3, 738 – 754. · Zbl 1128.03048 · doi:10.2178/jsl/1191333839
[24] C. J. van Alten, The finite model property for knotted extensions of propositional linear logic, J. Symbolic Logic 70 (2005), no. 1, 84 – 98. · Zbl 1089.03015 · doi:10.2178/jsl/1107298511
[25] Clint J. van Alten and James G. Raftery, Rule separation and embedding theorems for logics without weakening, Studia Logica 76 (2004), no. 2, 241 – 274. · Zbl 1053.03012 · doi:10.1023/B:STUD.0000032087.02579.e2
[26] Annika M. Wille, A Gentzen system for involutive residuated lattices, Algebra Universalis 54 (2005), no. 4, 449 – 463. · Zbl 1088.06012 · doi:10.1007/s00012-005-1957-6
[27] David N. Yetter, Quantales and (noncommutative) linear logic, J. Symbolic Logic 55 (1990), no. 1, 41 – 64. · Zbl 0701.03026 · doi:10.2307/2274953
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.