Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-08T21:37:10.988Z Has data issue: false hasContentIssue false
  • English
  • Français

ON EQUATIONAL COMPLETENESS THEOREMS

Part of: Varieties General logic Algebraic logic

Published online by Cambridge University Press:  13 September 2021

TOMMASO MORASCHINI
TOMMASO MORASCHINI*
Affiliation:
DEPARTMENT OF PHILOSOPHY UNIVERSITY OF BARCELONA CARRER DE MONTALEGRE 6 08001BARCELONA, SPAIN
*
E-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A logic is said to admit an equational completeness theorem when it can be interpreted into the equational consequence relative to some class of algebras. We characterize logics admitting an equational completeness theorem that are either locally tabular or have some tautology. In particular, it is shown that a protoalgebraic logic admits an equational completeness theorem precisely when it has two distinct logically equivalent formulas. While the problem of determining whether a logic admits an equational completeness theorem is shown to be decidable both for logics presented by a finite set of finite matrices and for locally tabular logics presented by a finite Hilbert calculus, it becomes undecidable for arbitrary logics presented by finite Hilbert calculi.

Keywords

abstract algebraic logicalgebraic semanticscompleteness theoremequational consequenceprotoalgebraic logicalgebraizable logic

MSC classification

Primary: 03G27: Abstract algebraic logic
Secondary: 08B05: Equational logic, Mal′cev (Mal′tsev) conditions 03B55: Intermediate logics 03B45: Modal logic (including the logic of norms) 03B47: Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics)
Type
Article
Information
The Journal of Symbolic Logic , Volume 87 , Issue 4 , December 2022 , pp. 1522 - 1575
Check for updates
Copyright
© The Author(s), 2021. Published by Cambridge University Press on behalf of The Association for Symbolic Logic

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.)

Footnotes

Dedicated to Professor Ramon Jansana on the occasion of his retirement

References

Albuquerque, H., Font, J. M., Jansana, R., and Moraschini, T., Assertional logics, truth-equational logics, and the hierarchies of abstract algebraic logic , Don Pigozzi on Abstract Algebraic Logic and Universal Algebra (J. Czelakowski, editor), Outstanding Contributions, vol. 16, Springer, Cham, 2018.Google Scholar
Bergman, C., Universal Algebra: Fundamentals and Selected Topics, Chapman and Hall/CRC, Boca Raton, FL, 2011.Google Scholar
Blok, W. J. and Pigozzi, D., Protoalgebraic logics . Studia Logica, vol. 45 (1986), pp. 337–369.CrossRefGoogle Scholar
Blok, W. J. and Pigozzi, D., Algebraizable Logics, Memoirs of the American Mathematical Society, vol. 396, American Mathematical Society, Providence, 1989.Google Scholar
Blok, W. J. and Pigozzi, D., Algebraic semantics for universal horn logic without equality , Universal Algebra and Quasigroup Theory (A. Romanowska and J. D. H. Smith, editors), Heldermann, Berlin, 1992, pp. 1–56.Google Scholar
Blok, W. J. and Raftery, J. G., Assertionally equivalent quasivarieties . International Journal of Algebra and Computation, vol. 18 (2008), no. 4, pp. 589–681.CrossRefGoogle Scholar
Blok, W. J. and Rebagliato, J., Algebraic semantics for deductive systems . Studia Logica, Special Issue on Abstract Algebraic Logic, Part II, vol. 74 (2003), no. 5, pp. 153–180.Google Scholar
Burris, S. and Sankappanavar, H. P., A Course in Universal Algebra, Springer, New York, 1981.CrossRefGoogle Scholar
Celani, S. and Jansana, R., A closer look at some subintuitionistic logics . Notre Dame Journal of Formal Logic, vol. 42 (2001), no. 4, pp. 225–255.Google Scholar
Chagrov, A. and Zakharyaschev, M., Modal Logic, Oxford Logic Guides, vol. 35, Oxford University Press, Oxford, 1997.Google Scholar
Cintula, P. and Noguera, C., Logic and Implication: An Introduction to the General Algebraic Study of Non-Classical Logics , Trends in Logic, Springer, Cham, to appear.Google Scholar
Czelakowski, J., Algebraic aspects of deduction theorems . Studia Logica, vol. 44 (1985), pp. 369–387.CrossRefGoogle Scholar
Czelakowski, J., Local deductions theorems . Studia Logica, vol. 45 (1986), pp. 377–391.CrossRefGoogle Scholar
Czelakowski, J., Protoalgebraic Logics, Trends in Logic—Studia Logica Library, vol. 10, Kluwer Academic, Dordrecht, 2001.CrossRefGoogle Scholar
Czelakowski, J., The Suszko operator. Part I . Studia Logica, Special Issue on Abstract Algebraic Logic, Part II, vol. 74 (2003), no. 5, pp. 181–231.Google Scholar
Czelakowski, J. and Jansana, R., Weakly algebraizable logics, this Journal, vol. 65 (2000), no. 2, pp. 641–668.Google Scholar
Dunn, J. M., Positive modal logic . Studia Logica, vol. 55 (1995), no. 2, pp. 301–317.CrossRefGoogle Scholar
Font, J. M., The simplest protoalgebraic logic . Mathematical Logic Quaterly, vol. 59 (2013), no. 6, pp. 435–451.Google Scholar
Font, J. M., Ordering protoalgebraic logics . Journal of Logic and Computation, vol. 26 (2014), no. 5, pp. 1395–1419.CrossRefGoogle Scholar
Font, J. M., Abstract Algebraic Logic—An Introductory Textbook, Studies in Logic—Mathematical Logic and Foundations, vol. 60, College Publications, London, 2016.Google Scholar
Font, J. M. and Jansana, R., A General Algebraic Semantics for Sentential Logics, second ed., Lecture Notes in Logic, vol. 7, Association for Symbolic Logic, 2017.CrossRefGoogle Scholar
Font, J. M., Jansana, R., and Pigozzi, D., A survey on abstract algebraic logic . Studia Logica, Special Issue on Abstract Algebraic Logic, Part II, vol. 74 (2003), nos. 1–2, pp. 13–97. With an “Update” in vol. 91 (2009), pp. 125–130.Google Scholar
Galatos, N., Jipsen, P., Kowalski, T., and Ono, H., Residuated Lattices: An Algebraic Glimpse at Substructural Logics, Studies in Logic and the Foundations of Mathematics, vol. 151, Elsevier, Amsterdam, 2007.Google Scholar
Glivenko, V. I., Sur quelques points de la logique de M. Brouwer . Academie Royal de Belgique Bulletin, vol. 15 (1929), pp. 183–188.Google Scholar
Herrmann, B., Algebraizability and Beth’s theorem for equivalential logics . Bulletin of the Section of Logic, vol. 22 (1993), no. 2, pp. 85–88.Google Scholar
Jansana, R., Full models for positive modal logic . Mathematical Logic Quarterly, vol. 48 (2002), no. 3, pp. 427–445.3.0.CO;2-T>CrossRefGoogle Scholar
Jansana, R. and Moraschini, T., The poset of all logics I: Interpretations and lattice structure, this Journal, 2021, to appear.CrossRefGoogle Scholar
Jansana, R. and Moraschini, T., The poset of all logics II: Leibniz classes and hierarchy, this Journal, 2021, to appear.CrossRefGoogle Scholar
Jansana, R. and Moraschini, T., The poset of all logics III: Finitely presentable logics . Studia Logica, vol. 109 (2021), pp. 539–580.CrossRefGoogle Scholar
Komori, Y., Syntactical investigations into BI logic and BB’I logic . Studia Logica, vol. 53 (1994), pp. 397–416.CrossRefGoogle Scholar
Kracht, M., Tools and Techniques in Modal Logic, Studies in Logic and the Foundations of Mathematics, vol. 142, North-Holland, Amsterdam, 1999.CrossRefGoogle Scholar
Kracht, M., Modal consequence relations , Handbook of Modal Logic, vol. 3 (P. Blackburn, J. van Benthem, and F. Wolter, editors), Elsevier, New York, 2006, Chapter 8.Google Scholar
Martin, E. P. and Meyer, R. K., Solution to the P–W problem, this Journal, vol. 47 (1982), pp. 869–886.Google Scholar
Moraschini, T., A computational glimpse at the Leibniz and Frege hierarchies . Annals of Pure and Applied Logic, vol. 169 (2018), no. 1, pp. 1–20.CrossRefGoogle Scholar
Moraschini, T., A study of the truth predicates of matrix semantics . The Review of Symbolic Logic, vol. 11 (2018), no. 4, pp. 780–804.CrossRefGoogle Scholar
Moraschini, T., On the complexity of the Leibniz hierarchy . Annals of Pure and Applied Logic, vol. 170 (2019), no. 7, pp. 805–824.CrossRefGoogle Scholar
Pigozzi, D., Fregean algebraic logic , Algebraic Logic (H. Andréka, J. D. Monk, and I. Németi, editors), Colloquia Mathematica Societatis János Bolyai, vol. 54, North-Holland, Amsterdam, 1991, pp. 473–502.Google Scholar
Raftery, J. G., The equational definability of truth predicates . Reports on Mathematical Logic, vol. 41 (2006), pp. 95–149.Google Scholar
Raftery, J. G., A perspective on the algebra of logic . Quaestiones Mathematicae, vol. 34 (2011), pp. 275–325.CrossRefGoogle Scholar
Rautenberg, W., On reduced matrices . Studia Logica, vol. 52 (1993), pp. 63–72.Google Scholar
Suzuki, Y., Wolter, F., and Zakharyashev, M., Speaking about transitive frames in propositional languages . Journal of Logic, Language and Information, vol. 7 (1998), pp. 317–339.CrossRefGoogle Scholar
Turing, A. M., On computable numbers, with and application to the Entscheidungs problem . Proceedings of the London Mathematical Society, vol. 42 (1936–1937), no. 2, pp. 230–265. A correction, vol. 43 (1937), pp. 544–546.Google Scholar
Visser, A., A propositional logic with explicit fixed points . Studia Logica, vol. 40 (1981), pp. 155–175.CrossRefGoogle Scholar