Distributed Relation Logic

• Authors: Allwein Gerard , Harrison William L. , Reynolds Thomas
• Languages of publication: EN

Abstracts

EN

We extend the relational algebra of Chin and Tarski so that it is multisorted or, as we prefer, typed. Each type supports a local Boolean algebra outfitted with a converse operator. From Lyndon, we know that relation algebras cannot be represented as proper relation algebras where a proper relation algebra has binary relations as elements and the algebra is singly-typed. Here, the intensional conjunction, which was to represent relational composition in Chin and Tarski, spans three different local algebras, thus the term distributed in the title. Since we do not rely on proper relation algebras, we are free to re-express the algebras as typed. In doing so, we allow many different intensional conjunction operators. We construct a typed logic over these algebras, also known as heterogeneous algebras of Birkhoff and Lipson. The logic can be seen as a form of relevance logic with a classical negation connective where the Routley-Meyer star operator is reified as a converse connective in the logic. Relevance logic itself is not typed but our work shows how it can be made so. Some of the properties of classical relevance logic are weakened from Routley-Meyer’s version which is too strong for a logic over relation algebras.

Keywords

EN

relation algebra; multisorted algebra; distributed logic; Kripke frames; Kripke models

• Publisher: Uniwersytet Mikołaja Kopernika (Nicolaus Copernicus University in Toruń)
• Journal: Logic and Logical Philosophy
• Year: 2017
• Volume: 26
• Issue: 1
• Pages: 19–61

Dates

published

2017-03-15

online

2016-07-19

Contributors

author

Allwein Gerard

• Naval Research Laboratory Code 5543 Washington, DC 20375, USA

author

Harrison William L.

• Dept. of Computer Science University of Missouri Columbia, Missouri, USA

author

Reynolds Thomas

• Dept. of Computer Science University of Missouri Columbia, Missouri, USA

References

• Adámek, J., and J. Rosický, Locally Presentable and Accessible Categories, Lecture Note Series 189, London Mathematical Society, 1994. DOI: 10.1017/CBO9780511600579
• Allwein, G., H. Demir, and L. Pike, “Logics for classes of Boolean monoids”, Journal of Logic, Language and Information, 13, 3 (2004): 241–266. DOI: 10.1023/B:JLLI.0000028336.64373.f6
• Allwein, G., W. Harrison, and D. Andrews, “Simulation logic”, Logic and Logical Philosophy, 23, 3 (2014): 277–299. DOI: 10.12775/LLP.2013.027
• Allwein, G., and W.L. Harrison, “Distributed modal logic”, pages 331–362 in Katalin Bimbó (ed.), J. Michael Dunn on Information Based Logic, Outstanding Contributions to Logic, Springer-Verlag, 2016. DOI: 10.1007/978-3-319-29300-4_16
• Anderson, A.R., and N.D. Belnap, Jr., Entailment: The Logic of Relevance and Necessity, volume I, Princeton University Press, 1975.
• Birkhoff, G., Lattice Theory, Third Edition, American Mathematical Society, 1967.
• Birkhoff, G., and J.D. Lipson, “Heterogeneous algebras”, Journal of Computational Theory, 8 (1968): 115–133.
• Blackburn, P., M. de Rijke, and Y. Venema, Modal Logic, Cambridge Tracts in Theoretical Computer Science, No. 53, Cambridge University Press, 2001. DOI: 10.1017/CBO9781107050884
• Chin, L.H., and A. Tarski, “Distributive and modular laws in the arithmetic of relation algebras”, University of California Publications in Mathematics, 1951.
• Dunn, J.M., “Gaggle theory: An abstraction of Galois connections and residuation with applications to negation and various logical operations”, pages 31–51 in Logics in AI, Proceedings European Workshop JELIA, LNCS 478, Springer-Verlag, 1990. DOI: 10.1007/BFb001843
• Dunn, J.M., and G. Hardegree, Algebraic Methods in Philosophical Logic, Oxford Logic Guides 41, Oxford University Press, 2001.
• Hoare, C.A.R., and J. He, “A weakest pre-specification”, Inform. Process.
• Jónsson, B., and A. Tarski, “Boolean algebras with operators. Parts 1 and 2”, American Journal of Mathematics, 73–74 (1951–1952): 891–939, 127–162. DOI: 10.2307/2372074
• Jónsson, B., and C. Tsinakis, “Relation algebras as residuated Boolean algebras”, Algebra Universalis, 30 (1993): 469–478.
• Ng, K.C., “Relation algebras with transitive closure”, PhD thesis, University of California, Berkeley, 1984.
• Pratt, V.R., “Dynamic algebras as a well behaved fragment of relation algebras”, Chapter 5 in Proceedings, Algebra and Computer Science, Lecture Notes in Computer Science, Springer-Verlag, 1990. DOI: 10.1007/BFb0043079
• Routley, R., and R.K. Meyer, “The semantics of entailment”, pages 194–243 in H. Leblanc (ed.), Truth, Syntax, and Modality, Studies in Logic and the Foundations of Mathematics, North Holland, 1973. DOI: 10.1016/S0049-237X(08)71541-6
• Routley, R., R.K. Meyer, V. Plumwood, and R.T. Brady, Relevant Logics and Their Rivals, Ridgeview Publishing Company, 1982.
• Sahlqvist, H., “Completeness and correspondence in the first and second order semantics for modal logic”, pages 110–143 in Proceedings of the Third Scandanavian Logic Symposium, Uppsala, 1973, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Company, 1975. DOI: 10.1016/S0049-237X(08)70728-6
• Stone, M.H., “The theory of representation for Boolean algebras”, Transactions of the American Mathematical Society, 40 (1936): 37–111. DOI: 10.2307/1989664
• van Benthem, J., Modal Logic and Classical Logic, Bibliopolis, 1983.

Identifiers

DOI

10.12775/LLP.2016.017