Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-20T00:04:52.725Z Has data issue: false hasContentIssue false
  • English
  • Français

RELEVANCE LOGICS AND RELATION ALGEBRAS

Published online by Cambridge University Press:  01 March 2009

KATALIN BIMBÓ ,
J. MICHAEL DUNN  and
ROGER D. MADDUX
KATALIN BIMBÓ*
Affiliation:
Department of Philosophy, University of Alberta
J. MICHAEL DUNN*
Affiliation:
School of Informatics, Indiana University
ROGER D. MADDUX*
Affiliation:
Department of Mathematics, Iowa State University
*
*DEPARTMENT OF PHILOSOPHY UNIVERSITY OF ALBERTA EDMONTON, AB, CANADA T6G 2E7, E-mail:[email protected], URL:www.ualberta.ca/~bimbo
†SCHOOL OF INFORMATICS INDIANA UNIVERSITY BLOOMINGTON, IN 47408-3912, E-mail:[email protected]
‡DEPARTMENT OF MATHEMATICS IOWA STATE UNIVERSITY 396 CARVER HALL, AMES, IA 50011, E-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Relevance logics are known to be sound and complete for relational semantics with a ternary accessibility relation. This paper investigates the problem of adequacy with respect to special kinds of dynamic semantics (i.e., proper relation algebras and relevant families of relations). We prove several soundness results here. We also prove the completeness of a certain positive fragment of R as well as of the first-degree fragment of relevance logics. These results show that some core ideas are shared between relevance logics and relation algebras. Some details of certain incompleteness results, however, pinpoint where relevance logics and relation algebras diverge. To carry out these semantic investigations, we define a new tableaux formalization and new sequent calculi (with the single cut rule admissible) for various relevance logics.

Type
Research Article
Information
The Review of Symbolic Logic , Volume 2 , Issue 1 , March 2009 , pp. 102 - 131
Copyright
Copyright © Association for Symbolic Logic 2009

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
Bimbó, K. (2005). Admissibility of cut in LC with fixed point combinator. Studia Logica, 81, 399–423.CrossRefGoogle Scholar
Bimbó, K. (2007a). , LK and cutfree proofs. Journal of Philosophical Logic, 36, 557–570.CrossRefGoogle Scholar
Bimbó, K. (2007b). Relevance logics. In Gabbay, D., Thagard, P., and Woods, J. editors. Handbook of the Philosophy of Science. Vol. 5: Philosophy of Logic (Jacquette, D. editor). Amsterdam, The Netherlands: Elsevier (North-Holland), pp. 723–789.Google Scholar
Bimbó, K. (2009). Dual gaggle semantics for entailment. Notre Dame Journal of Formal Logic, 50(1), 23–41.CrossRefGoogle Scholar
Bimbó, K., & Dunn, J. M. (2005). Relational semantics for Kleene logic and action logic, Notre Dame Journal of Formal Logic, 46, 461–490.CrossRefGoogle Scholar
Bimbó, K., & Dunn, J. M. (2008). Generalized Galois Logics. Relational Semantics of Nonclassical Logical Calculi. CSLI Lecture Notes, Vol. 188. Stanford, CA: CSLI Publications.Google Scholar
Brady, R. T., editor. (2003). Relevant Logics and Their Rivals. A Continuation of the Work of R. Sylvan, R. Meyer, V. Plumwood and R. Brady, Vol. II. Burlington, VT: Ashgate.Google Scholar
Davey, B. A., & Priestley, H. A. (2002). Introduction to Lattices and Order (second edition). Cambridge, UK: Cambridge University Press.CrossRefGoogle Scholar
Dunn, J. M. (1966). The algebra of intensional logics. PhD Thesis, University of Pittsburgh, Ann Arbor, MI (UMI).Google Scholar
Dunn, J. M. (1970). Algebraic completeness results for R-mingle and its extensions. Review of Symbolic Logic, 35, 1–13.CrossRefGoogle Scholar
Dunn, J. M. (1976a). Intuitive semantics for first-degree entailment and ‘coupled trees’. Philosophical Studies, 29, 149–168.CrossRefGoogle Scholar
Dunn, J. M. (1976b). A Kripke-style semantics for R-mingle using a binary accessibility relation. Studia Logica, 35, 163–172.CrossRefGoogle Scholar
Dunn, J. M. (1980). A sieve for entailments. Journal of Philosophical Logic, 9, 41–57.CrossRefGoogle Scholar
Dunn, J. M. (1982). A relational representation of quasi-Boolean algebras. Notre Dame Journal of Formal Logic, 23(4), 353–357.CrossRefGoogle Scholar
Dunn, J. M. (1986). Relevance logic and entailment. In Gabbay, D., and Guenthner, F., editors. Handbook of Philosophical Logic (first edition), Vol. 3. Dordrecht, The Netherlands: D. Reidel, pp. 117–229.CrossRefGoogle Scholar
Dunn, J. M. (1996). Generalized ortho-negation. In Wansing, H., editor. Negation: A Notion in Focus. Berlin, Germany: Walter de Gruyter, pp. 3–26.CrossRefGoogle Scholar
Dunn, J. M. (2001). A representation of relation algebras using Routley-Meyer frames. In Anderson, C. A., and Zelëny, M., editors. Logic, Meaning and Computation. Essays in Memory of Alonzo Church. Dordrecht, The Netherlands: Kluwer, pp. 77–108.CrossRefGoogle Scholar
Givant, S. R. (1994). The structure of relation algebras generated by relativizations. Contemporary Mathematics, Vol. 156. Providence, RI: American Mathematical Society.CrossRefGoogle Scholar
Jónsson, B. (1959). Representation of modular lattices and of relation algebras. Transactions of the American Mathematical Society, 92, 449–464.CrossRefGoogle Scholar
Jónsson, B., & Tarski, A. (1948). Representation problems for relation algebras. Bulletin of the American Mathematical Society, 54, 80, 1192.Google Scholar
Jónsson, B., & Tarski, A. (1951). Boolean algebras with operators, I. American Journal of Mathematics, 73, 891–939.CrossRefGoogle Scholar
Jónsson, B., & Tarski, A. (1952). Boolean algebras with operators, 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
Lyndon, R. C. (1950). The representation of relation algebras. Annals of Mathematics, 51, 707–729.CrossRefGoogle Scholar
Maddux, R. D. (1996). Relation-algebraic semantics. Theoretical Computer Science, 160, 1–85.CrossRefGoogle Scholar
Maddux, R. D. (2006). Relation algebras. Studies in Logic and the Foundations of Mathematics, Vol. 150. Amsterdam, The Netherlands: Elsevier.Google Scholar
Maddux, R. D. (2007). Relevance logic and the calculus of relations [abstract]. International Conference on Order, Algebra and Logics, Vanderbilt University, June 13, 2007, pp. 1–3. (URL: www.math.vanderbilt.edu/~oal2007/submissions/submission_10.pdf.)Google Scholar
Mares, E. D. (2002). Relevance logic. In Jacquette, D., editor. A Companion to Philosophical Logic. Madden, MA: Blackwell, pp. 609–627.Google Scholar
Mares, E. D., & Meyer, R. K. (2001). Relevant logics. In Goble, L., editor. The Blackwell Guide to Philosophical Logic. Blackwell Philosophy Guides. Oxford, UK: Blackwell Publishers, pp. 280–308.Google Scholar
Meyer, R. K., & Routley, R. (1973). Classical relevant logics, I. Studia Logica, 32, 51–66.CrossRefGoogle Scholar
Meyer, R. K., & Routley, R. (1974). Classical relevant logics, II. Studia Logica, 33, 183–194.CrossRefGoogle Scholar
Monk, J. D. (1964). On representable relation algebras. Michigan Mathematics Journal, 11, 207–210.CrossRefGoogle Scholar
Restall, G. (2000). An Introduction to Substructural Logics. London, UK: Routledge.CrossRefGoogle Scholar
Routley, R., & Meyer, R. K. (1973). The semantics of entailment. In Leblanc, H., editor. Truth, Syntax and Modality. Proceedings of the Temple University Conference on Alternative Semantics. Amsterdam, The Netherlands: North-Holland.Google Scholar
Routley, R., Meyer, R. K., Plumwood, V., & Brady, R. T. (1982). Relevant Logics and Their Rivals, Vol. I. Atascadero, CA: Ridgeview Publishing Company.Google Scholar
Smullyan, R. M. (1968). First-Order Logic. New York, NY: Springer-Verlag (New York, NY: Dover, 1995).CrossRefGoogle Scholar
Tarski, A. (1941). On the calculus of relations. Review of Symbolic Logic, 6, 73–89.CrossRefGoogle Scholar
Tarski, A. (1955). Contributions to the theory of models, III. Indagationes Mathematicae, 17, 56–64.CrossRefGoogle Scholar
Tarski, A., & Givant, S. (1987). A Formalization of Set Theory without Variables. American Mathematical Society Colloquium Publications, Vol. 41. Providence, RI: American Mathematical Society.Google Scholar
Urquhart, A. (1983). Relevant implication and projective geometry. Logique et Analyse, 103–104, 345–357.Google Scholar
Urquhart, A. (1984). The undecidability of entailment and relevant implication. Review of Symbolic Logic, 49, 1059–1073.CrossRefGoogle Scholar
Urquhart, A. (1993). Failure of interpolation in relevant logics. Journal of Philosophical Logic, 22, 449–479.CrossRefGoogle Scholar
van Benthem, J. (1995). Language in Action, Cambridge, MA: MIT Press.Google Scholar
van Benthem, J. (1996). Exploring logical dynamics. Studies in Logic, Language and Information. Stanford, CA: CSLI Publications.Google Scholar