Unifiability and Structural Completeness in Relation Algebras and in Products of Modal Logic S5

Wojciech Dzik; Beniamin Wróbel

doi:10.18778/0138-0680.44.1.2.01

Authors

Wojciech Dzik University of Silesia, Institute of Mathematics, Bankowa 12, 40 007 Katowice, Poland Author
Beniamin Wróbel University of Silesia, Institute of Mathematics, Bankowa 12, 40 007 Katowice, Poland Author

DOI:

https://doi.org/10.18778/0138-0680.44.1.2.01

Keywords:

admissible rules, passive rules, unification, projective unification, almost structural completeness, n-modal logic S5ⁿ, relation algebras, representable diagonal-free cylindric algebras

Abstract

Unifiability of terms (and formulas) and structural completeness in the variety of relation algebras RA and in the products of modal logic S5 is investigated. Nonunifiable terms (formulas) which are satisfiable in varieties (in logics) are exhibited. Consequently, RA and products of S5 as well as representable diagonal-free n-dimensional cylindric algebras, RDfn, are almost structurally complete but not structurally complete. In case of S5ⁿ a basis for admissible rules and the form of all passive rules are provided.

References

Andreka H., Maddux R., Representations for Small Relation Algebras, Notre Dame Journal of Formal Logic 35 (4),(1994), pp. 550–562. DOI: https://doi.org/10.1305/ndjfl/1040408612

Baader F., Ghilardi S., Unification in Modal and Description Logics, Logic Journal of the IGPL, vol. 19 (6), (2011), pp. 705–730. DOI: https://doi.org/10.1093/jigpal/jzq008

Baader F., Snyder W., Unification Theory, [in:] A. Robinson, A. Voronkov, (eds.) Handbook of Automated Reasoning, Elsevier Science Publisher, 2001. DOI: https://doi.org/10.1016/B978-044450813-3/50010-2

Burris S., Discriminator Varieties and Symbolic Computation, Journal of Symbolic Computation, Volume 13 (1992), pp. 175-207. DOI: https://doi.org/10.1016/S0747-7171(08)80089-2

Dzik W., Unification Types in Logic, Silesian University Press, Katowice 2007.

Dzik W., Remarks on projective unifiers, Bulletin of the Section of Logic 40:1/2 (2011), pp. 37–46.

Dzik W., Wojtylak P., Projective Unification in Modal Logic, Logic Journal of the IGPL 20(1), (2012), pp. 121–153. DOI: https://doi.org/10.1093/jigpal/jzr028

Dzik W., Wojtylak P., Modal consequence relations extending S4.3, Notre Dame Journal of Formal Logic, 2015 (in print).

Gabbay D. M., Kurucz A., Wolter F., Zakharyaschev M., Manydimensional Modal Logic, Elsevier Science Publisher, 2003.

Ghilardi S., Unification through Projectivity, Journal of Symbolic Computation 7 (1997), pp. 733–752. DOI: https://doi.org/10.1093/logcom/7.6.733

Ghilardi S., Unification in Intuitionistic Logic, Journal of Symbolic Logic 64(2), (1999), pp. 859–880. DOI: https://doi.org/10.2307/2586506

Ghilardi S., Best Solving Modal Equations, Annals of Pure and Applied Logic 102 (2000), pp. 183–198. DOI: https://doi.org/10.1016/S0168-0072(99)00032-9

Henkin L., Monk J., Tarski A., Cylindric algebras. Part II, The foundations of Mathematics, Volume 115, Elsevier Science Publishers (1985).

Hirsch R., Hodkinson I., Relation Algebras by Games, North-Holland, 2002.

Maddux R. D., Relation Algebras, Elsevier Science Publishers (2006).

Pogorzelski W. A. and Wojtylak P., Completeness theory for propositional logics, Studies in Universal Logic, Birkhäuser, Bassel-Boston-Berlin (2008).

Rybakov V. V., Admissible Rules for Logics Containing S4.3, Sibirski Math. Journal 25 (1984), pp. 141–145. DOI: https://doi.org/10.1007/BF00968695

Rybakov V. V., Terziler M., Gencer C., An essay on unification and inference rules for modal logics, Bulletin of the Section of Logic 28 (1999), pp. 145–157.

Rybakov V. V., Terziler M., Gencer C., Unification and passive inference rules for modal logics, Journal of Applied Non-Classical Logics 10 (2000), pp. 369–377. DOI: https://doi.org/10.1080/11663081.2000.10511004

Tarski A., On the calculus of relations, Journal of Symbolic Logic 6(1941), pp. 73–89. DOI: https://doi.org/10.2307/2268577