Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-23T03:13:16.676Z Has data issue: false hasContentIssue false
  • English
  • Français

POSITIVE FRAGMENTS OF RELEVANCE LOGIC AND ALGEBRAS OF BINARY RELATIONS

Published online by Cambridge University Press:  16 August 2010

ROBIN HIRSCH  and
SZABOLCS MIKULÁS
ROBIN HIRSCH*
Affiliation:
Department of Computer Science, University College London
SZABOLCS MIKULÁS*
Affiliation:
Department of Computer Science and Information Systems, Birkbeck, University of London
*
*DEPARTMENT OF COMPUTER SCIENCE, UNIVERSITY COLLEGE LONDON, LONDON WC1E 6BT, UK. E-mail: [email protected]
†DEPARTMENT OF COMPUTER SCIENCE AND, INFORMATION SYSTEMS, BIRKBECK, UNIVERSITY OF LONDON, MALET STREET, LONDON WC1E 7HX, UK. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that algebras of binary relations whose similarity type includes intersection, union, and one of the residuals of relation composition form a nonfinitely axiomatizable quasivariety and that the equational theory is not finitely based. We apply this result to the problem of the completeness of the positive fragment of relevance logic with respect to binary relations.

Type
Research Article
Information
The Review of Symbolic Logic , Volume 4 , Issue 1 , March 2011 , pp. 81 - 105
Copyright
Copyright © Association for Symbolic Logic 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

BIBLIOGRAPHY

Anderson, A. R., & Belnap, N. D. (1975). Entailment. The Logic of Relevance and Necessity. Vol. I. Princeton, NJ: Princeton University Press.Google Scholar
Anderson, A. R., Belnap, N. D., & Dunn, J. M. (1992). Entailment. The Logic of Relevance and Necessity. Vol. II. Princeton, NJ: Princeton University Press.Google Scholar
Andréka, H. (1988). On the representation problem of distributive semilattice-ordered semigroups. Preprint, Mathematical Institute of the Hungarian Academy of Sciences. Abstracted in Abstracts of the American Mathematical Society, 10(2), 174(March 1989).Google Scholar
Andréka, H. (1991). Representation of distributive lattice-ordered semigroups with binary relations. Algebra Universalis, 28, 12–25.CrossRefGoogle Scholar
Andréka, H., & Mikulás, Sz. (1994). Lambek calculus and its relational semantics: Completeness and incompleteness. Journal of Logic, Language and Information, 3, 1–37.CrossRefGoogle Scholar
Andréka, H., & Mikulás, Sz. (accepted for publication). Axiomatizability of positive algebras of binary relations.Google Scholar
van Benthem, J. (1996). Exploring Logical Dynamics. Stanford, CA: CSLI Publications.Google Scholar
Bimbó, K., Dunn, J. M., & Maddux, R. D. (2009). Relevance logic and relation algebras. Review of Symbolic Logic, 2(1), 102–131.CrossRefGoogle Scholar
Bredikhin, D. A., & Schein, B. M. (1978). Representation of ordered semigroups and lattices by binary relations. Colloquium Mathematicum, 39, 1–12.CrossRefGoogle Scholar
Došen, K. (1992). A brief survey of frames for the Lambek calculus. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 38, 179–187.CrossRefGoogle Scholar
Dunn, J. M. (1966). The Algebra of Intensional Logics. PhD Dissertation, University of Pittsburgh.Google Scholar
Dunn, J. M. (1982). Relational representation of quasi-Boolean algebras. Notre Dame Journal of Formal Logic, 23, 353–357.CrossRefGoogle Scholar
Dunn, J. M. (1993) Partial gaggles. In Došen, K. and Schroeder-Heister, P. editors. Substructural Logics. Oxford, UK: Clarendon, pp. 63–109.CrossRefGoogle Scholar
Gehrke, M., Dunn, M., & Palmigiano, A. (2005). Canonical extensions and relational completeness of some substructural logics. Journal of Symbolic Logic, 70(3), 713–740.Google Scholar
Hirsch, R. (1995). Completely representable relation algebras. Bulletin of the IGPL, 3(1), 77–92.CrossRefGoogle Scholar
Hirsch, R. (2005). The class of representable ordered monoids has a recursively enumerable, universal axiomatisation but it is not finitely axiomatisable. Logic Journal of the IGPL, 13, 159–171.CrossRefGoogle Scholar
Hirsch, R., & Hodkinson, I. (1997). Complete representations in algebraic logic. Journal of Symbolic Logic, 62, 816–847.CrossRefGoogle Scholar
Hirsch, R., & Hodkinson, I. (2000). Relation algebras with n-dimensional relational bases. Annals of Pure and Applied Logic, 101, 227–274.CrossRefGoogle Scholar
Hirsch, R., & Hodkinson, I. (2001a). Relation algebras from cylindric algebras, II. Annals of Pure and Applied Logic, 112, 267–297.CrossRefGoogle Scholar
Hirsch, R., & Hodkinson, I. (2001b) Representability is not decidable for finite relation algebras. Transactions of the American Mathematical Society, 353, 1403–1425.CrossRefGoogle Scholar
Hirsch, R., & Hodkinson, I. (2002). Relation Algebras by Games. Amsterdam, The Netherlands: North-Holland.Google Scholar
Hirsch, R., & Hodkinson, I. (2009). Strongly representable atom structures of cylindric algebras. Journal of Symbolic Logic, 74, 811–828.CrossRefGoogle Scholar
Hirsch, R., & Mikulás, Sz. (2007). Representable semilattice-ordered monoids. Algebra Universalis, 57, 333–370.CrossRefGoogle Scholar
Hodkinson, I. (1997) Atom structures of cylindric algebras and relation algebras. Annals of Pure and Applied Logic, 89, 117–148.CrossRefGoogle Scholar
Hodkinson, I., & Mikulás, Sz. (2000). Axiomatizability of reducts of algebras of relations. Algebra Universalis, 43, 127–156.CrossRefGoogle Scholar
Jónsson, B. & Tarski, A. (1952). Boolean algebras with operators, part II. American Journal of Mathematics, 74, 127–162.CrossRefGoogle Scholar
Kowalski, T. (2007). Weakly associative relation algebras hold the key to the universe. Bulletin of the Section of Logic, 36, 145–157.Google Scholar
Kozen, D. (1994a). A completeness theorem for Kleene algebras and the algebra of regular events. Information and Computation, 110, 366–390.CrossRefGoogle Scholar
Kozen, D. (1994b). On action algebras. In van Eijck, J. and Visser, A.. editors. Logic and Information Flow. Cambridge, MA: MIT Press, pp. 78–88.CrossRefGoogle Scholar
Maddux, R. D. (2006). Relation Algebras. Amsterdam, The Netherlands: North-Holland.Google Scholar
Maddux, R. D. (2007). Relevance logic and the calculus of relations. Paper presented at International Conference on Order, Algebra and Logics. Department of Mathematics, Vanderbilt University, June 12–16, 2007. Abstract available from: http://www.math.vanderbilt.edu/∼oal2007/submissions/submission_10.pdf. More detailed notes available from: http://www.math.iastate.edu/maddux/talk.pdf.Google Scholar
Maddux, R. D. (2010). Relevance logic and the calculus of relations. Review of Symbolic Logic, 3(01), 41–70.CrossRefGoogle Scholar
Meyer, R. K., & Routley, R. (1972). Algebraic analysis of entailment I. Logique et Analyse, 15, 407–428.Google Scholar
Mikulás, Sz. (2004). Axiomatizability of algebras of binary relations. In Löwe, B., Piwinger, B., and Räsch, T. editors. Classical and New Paradigms of Computation and Their Complexity Hierarchies. Dordrecht, The Netherlands: Kluwer Academic Publishers, pp. 187–205.CrossRefGoogle Scholar
Mikulás, Sz. (2009). Algebras of relations and relevance logic. Journal of Logic and Computation, 19, 305–321.CrossRefGoogle Scholar
Mikulás, Sz. (Submitted). On representable ordered residuated semigroups.Google Scholar
Monk, J. (1964). On representable relation algebras. Michigan Mathematics Journal, 11, 207–210.CrossRefGoogle Scholar
Pratt, V. (1990). Action logic and pure induction. In van Eijck, J. editor. Logics in AI: European Workshop JELIA ’90. Heidelberg, Germany: Springer-Verlag, pp. 97–120.Google Scholar
Routley, R., & Meyer, R. K. (1973). The semantics of entailment (I). In Leblanc, H., editor. Truth, Syntax and Modality. Amsterdam, The Netherlands: North-Holland, pp. 199–243.CrossRefGoogle Scholar
Schein, B. M. (1991). Representation of subreducts of Tarski relation algebras. In Andréka, H., Monk, J. D., and Németi, I., editors. Algebraic Logic. Amsterdam, The Netherlands: North-Holland, pp. 621–635.Google Scholar
Tarski, A. (1954). Contributions to the theory of models, I, II. Proceedings Koninklijke Nederlandse Akadedemie van Wetenschappen, 57, 572–581 (= Indagationes Mathematicae, 16, 582–588).Google Scholar