Relation algebras as expanded FL-algebras. (English) Zbl 1322.03047
Summary: This paper studies generalizations of relation algebras to residuated lattices with a unary De Morgan operation. Several new examples of such algebras are presented, and it is shown that many basic results on relation algebras hold in this wider setting. The variety \(\mathbf {qRA}\) of quasi relation algebras is defined and shown to be a conservative expansion of involutive FL-algebras. Our main result is that equations in \(\mathbf {qRA}\) and several of its subvarieties can be decided by a Gentzen system, and that these varieties are generated by their finite members.
MSC:
| 03G25 | Other algebras related to logic |
| 03B47 | Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) |
| 06F05 | Ordered semigroups and monoids |
| 08B15 | Lattices of varieties |
References:
| [1] | Birkhoff, G.: Lattice Theory, 3rd edn. American Mathematical Society (1967) · Zbl 0153.02501 |
| [2] | Blount K., Tsinakis C: The structure of residuated lattices. Internat. J. Algebra Comput. 13, 437–461 (2003) · Zbl 1048.06010 · doi:10.1142/S0218196703001511 |
| [3] | Brzozowski J.A: A characterization of De Morgan algebras. Internat. J. Algebra Comput. 11, 525–527 (2001) · Zbl 1025.06007 · doi:10.1142/S0218196701000681 |
| [4] | Chin L.H., Tarski A: Distributive and modular laws in the arithmetic of relation algebras. Univ. California Publ. Math. (N.S.) 1, 341–384 (1951) · Zbl 0045.31701 |
| [5] | Galatos, N., Jipsen, P.: Residuated frames with applications to decidability. Trans. Amer. Math. Soc. (in press) · Zbl 1285.03077 |
| [6] | Galatos, N., Jipsen, P., Kowalski, T., Ono, H.: Residuated Lattices: An Algebraic Glimpse at Substructural Logics. Studies in Logic and the Foundations of Mathematics, vol. 151. Elsevier (2007) · Zbl 1171.03001 |
| [7] | Jipsen P: Representable sequential algebras and observation spaces. J. Relational Methods Comput. Sci. 1, 235–250 (2004) |
| [8] | Jipsen P., Maddux R.D: Nonrepresentable sequential algebras. Log. J. IPGL 5, 565–574 (1997) · Zbl 0882.03061 |
| [9] | Jónsson, B.: A survey of Boolean algebras with operators. In: Rosenberg, I., Sabidussi, G. (eds.) Algebras and Orders, pp. 239–286. Springer (1993) · Zbl 0811.06012 |
| [10] | Jónsson B., Tarski A: Boolean algebras with operators, Part II. Amer. J. Math. 74, 127–162 (1952) · doi:10.2307/2372074 |
| [11] | Jónsson B., Tsinakis C: Relation algebras as residuated Boolean algebras. Algebra Universalis 30, 469–478 (1993) · Zbl 0792.06012 · doi:10.1007/BF01195378 |
| [12] | Kozak M: Cyclic involutive distributive full Lambek calculus is decidable. J. Logic Comput. 21, 231–252 (2011) · Zbl 1225.03022 · doi:10.1093/logcom/exq021 |
| [13] | Kurucz, Á., Németi, I., Sain, I., Simon, A.: Undecidable varieties of semilattice-ordered semigroups, of Boolean algebras with operators, and logics extending Lambek calculus. Log. J. IGPL 1, 91–98 (1993) · Zbl 0798.03009 |
| [14] | Lambek, J.: Type grammars revisited. In: Logical Aspects of Computational Linguistics (Nancy, 1997). Lecture Notes in Computer Science, vol. 1582, pp. 1–27. Springer (1999) · Zbl 0934.03043 |
| [15] | Maddux R: Some varieties containing relation algebras. Trans. Amer. Math. Soc. 272, 501–526 (1982) · Zbl 0515.03039 · doi:10.1090/S0002-9947-1982-0662049-7 |
| [16] | Ono, H.: Structural rules and a logical hierarchy. In: Petkov, P.P. (ed.) Mathematical Logic, pp. 95–104. Plenum, New York (1990) · Zbl 0790.03007 |
| [17] | Tarski, A., Givant, S.: A Formalization of Set Theory Without Variables. American Mathematical Society, Providence (1987) · Zbl 0654.03036 |
| [18] | von Karger B., Hoare C.A.R: Sequential calculus. Information Processing Letters 53, 123–130 (1995) · Zbl 0875.68202 · doi:10.1016/0020-0190(94)00205-D |
| [19] | Ward M., Dilworth R.P: Residuated lattices. Trans. Amer. Math. Soc. 45, 335–354 (1939) · JFM 65.0084.01 · doi:10.1090/S0002-9947-1939-1501995-3 |
| [20] | Wille A: A Gentzen system for involutive residuated lattices. Algebra Universalis 54, 449–463 (2005) · Zbl 1088.06012 · doi:10.1007/s00012-005-1957-6 |
| [21] | Yetter D.N: Quantales and (noncommutative) linear logic. J. Symbolic Logic 55, 41–64 (1990) · 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.
