Abstract Algebraic Logic

This chapter is a brief introduction to abstract algebraic logic. It is organized around the central notion of algebraizability, with particular emphasis on its connections with the techniques of traditional algebraic logic, and especially with the so-called Lindenbaum–Tarski process. It then goes beyond algebraizability in order to offer a more general overview of several classifications of sentential logics which have emerged in recent decades (basically, the Leibniz hierarchy and the Frege hierarchy) and to show how the classification of a logic into any of these hierarchies provides some knowledge regarding its algebraic or its metalogical properties. In the final section, a more abstract view of algebraizability is introduced.

1. 1.

   The term algebraic semantics, which has been much used for years in informal comments in the same vague sense as my “algebra-based semantics”, has acquired a formal meaning in the modern theory (Definition 3.4). I consider it to be good practice to limit its usage to this strictly technical sense.

2. 2.

   This feature has also been highlighted as distinctive of (some of) the modern studies of non-classical logics, notably of modal logics; see for instance [22, p. 109].

3. 3.

   Looking back at history, it is easy to see that finding useful classifications has been one major driving force in the development of several areas of mathematics, and of all sciences.

4. 4.

   The references given here for each case are just pointers to facilitate contact with the topic, rather than the earliest or the main work on it.

5. 5.

   See the comment on usage of \(\mathbin {\pmb {\pmb {\wedge }}}\) and \(\mathbin {\pmb {\pmb {\mathbin {\rightarrow }}}}\) on p. xxx.

6. 6.

   Set-theoretically, it is a relation on the set of formulas, but since condition (S) takes the algebraic structure of formulas into account, it makes sense to say it is a relation on the algebra of formulas.

7. 7.

   This exemplifies why it is imperative that algebra-based semantics that are more general than just plain algebras be considered in some domains, and hence in the general theory.

8. 8.

   Two modern treatises where this strategy is explicitly adopted, and where algebraizability plays some rôle, are [67] and [54, pp. 72,88].

9. 9.

   Quite a different issue is whether one is able or not, or whether it is easy, to prove that a given logic is algebraizable, or to disprove this. This indeed may depend heavily on its presentation. Indeed, there are better tools to achieve this for syntactically presented logics (see Theorems 4.1 and 5.3) than for semantically presented ones (see Theorem 4.14); but, more generally, [71] it is proved that the general classification problem, either in the Leibniz hierarchy or in the Frege hierarchy, is undecidable for axiomatically presented logics (hence a fortiori for arbitrary logics), while it is decidable for logics defined by a finite set of finite matrices of finite type.

10. 10.

    To the best of my knowledge, the term “abstract algebraic logic” first appears in the literature in the title of Sect. 5.6 of Henkin, Monk and Tarski’s [59], which is devoted to a general study of the connections between theories of classical first-order logic and classes of cylindric algebras. A related approach, through polyadic algebras, is offered in [57] by Halmos, who is generally credited for having coined the term “algebraic logic”. A third, essentially different approach to the algebraic study of predicate logics exploits Mostowski’s idea of interpreting quantifiers as infinite meets and joins in ordered structures (rather than as independent algebraic operations); over time this has become the most popular choice for the algebraic study of particular first-order non-classical logics for which a successful algebraic study of their sentential fragment exists: see [25, 56, 91].

11. 11.

    This warning complements the very pertinent one in [54, pp. 68–69] concerning the relation between Birkhoff’s consequence and first-order consequence.

12. 12.

    For simplicity, closure under the product operator includes the case of the product of an empty family, which is defined to be a trivial algebra.

13. 13.

    The term “translation” is much overused in the literature.

14. 14.

    Considering the natural lattice structure of these power sets (with set inclusion as the order relation), a function that commutes with unions is just a residuated function from \(\mathcal {P}(Fm)\) to \(\mathcal {P}(Eq)\). The residuation view is the key to the more abstract approaches to the notion of algebraizability that are briefly touched upon in Sect. 8.

15. 15.

    This is actually an extension of Blok and Pigozzi’s original notion [8]; see Sect. 5 for details.

16. 16.

    In the original notion, any class \(\mathsf {K}\) satisfying the four conditions was called an equivalent algebraic semantics of \(\mathcal {L}\). Raftery [84] started the practice of reserving the name for the largest of all such classes, which is hence unique; see the observations on its existence and character at the end of this section.

17. 17.

    A logic \(\mathcal {L}'\) is an extension of a logic \(\mathcal {L}\) when they have the same language and \({\vdash _{\!\!\mathcal {L}}} \subseteq {\vdash _{\!\mathcal {L}'}}\).

18. 18.

    If \(\mathcal {L}\) and \(\mathcal {L}'\) are logics in languages \(\mathbf {L}\) and \(\mathbf {L}'\) respectively, with \({\mathbf {L}} \subseteq {\mathbf {L}'}\), then \(\mathcal {L}'\) is an expansion of \(\mathcal {L}\) when \({\vdash _{\!\!\mathcal {L}}} \subseteq {\vdash _{\!\mathcal {L}'}}\). A conservative expansion is an expansion such that \({\vdash _{\!\!\mathcal {L}}} = {\vdash _{\!\mathcal {L}'}} \cap \bigl (\mathcal {P}(Fm_{\mathbf {L}})\times Fm_{\mathbf {L}}\bigr )\); in this case, it is also said that \(\mathcal {L}\) is the \(\mathbf {L}\)-fragment of \(\mathcal {L}'\).

19. 19.

    Generalized quasivarieties are also called “\(\sigma \)-quasivarieties” in the literature. Due to the fact that we have assumed a fixed set \(V\!\) of variables, generalized quasivarieties as defined above are characterized as the classes of algebras that are closed under isomorphisms, subalgebras, products, and the operation \(\mathbb {U}\) introduced in [12]:

    \( \mathbb {U}(\mathsf {K}) := \bigl \{ {{\boldsymbol{A}}}: \text { If }\, {{\boldsymbol{B}}}\text { is a subalgebra of } {{\boldsymbol{A}}}\text { generated by a set of cardinality} \leqslant |V\!\,|,\text { then } {{\boldsymbol{B}}}\in \mathsf {K}\bigr \}. \)

    Thus, in particular, generalized quasivarieties are “SP-classes” or prevarieties: these are the classes that are closed under just isomorphisms, subalgebras and products, and can be characterized as those defined by (a possibly proper class of) generalized quasi-equations in a language having a proper class of variables (see for instance [62], Sect. 9.2). Note that the term implicational (or implicative) class has been used in the literature for ordinary quasivarieties, for generalized quasivarieties, and for prevarieties.

20. 20.

    This can be proved directly, just from the definition of algebraizability; but see also Corollary 4.15.

21. 21.

    Examples of this strategy are the completeness of the basic fuzzy logic BL with respect to linear BL-algebras [56] and its generalization to the so-called implicational semilinear logics [23], which include all the usual fuzzy logics.

22. 22.

    This argument only shows that \(\mathsf {K}(\mathcal {L},\pmb {\tau },\pmb {\rho })\) is the largest class for \(\pmb {\tau }\) and \(\pmb {\rho }\); Corollary 4.15 shows that this class is actually independent of the transformers, so it is the absolute largest. Notice that (6) describes \(\mathsf {K}(\mathcal {L},\pmb {\tau },\pmb {\rho })\) as the class of all algebras that satisfy a certain set of generalized quasi-equations; thus, this class is indeed a generalized quasivariety, as claimed on p. xxx.

23. 23.

    The logical usage of the term “filter” is undoubtedly inspired by its algebraic and topological origins. Sometimes the term “deductive filter” is used to emphasize the difference.

24. 24.

    Actually, of a stronger one, formulated in the framework where \(\mathbf {L}\)-matrices are considered as structures for a first-order language whose constants and function symbols are those in \(\mathbf {L}\), and which has only one relation symbol, a unary one, interpreted as the filter of the matrix. This deeply influential idea, due to [13], is further explained on p. xxx.

25. 25.

    Sometimes the algebras in \(\mathsf {Alg}^{\mathchoice{\textstyle *}{\textstyle *}{\textstyle *}{\scriptstyle *}}\!\!\mathcal {L}\) are called the Leibniz-reduced algebras of \(\mathcal {L}\).

26. 26.

    They are also called “congruence formulas”, for obvious reasons.

27. 27.

    Actually, the logic is BP-algebraizable, in the sense of Definition 5.1.

28. 28.

    In the sense that they are uniquely determined by \(\mathcal {L}\). In the reverse sense, only \(\mathsf {Mod}^{\mathchoice{\textstyle *}{\textstyle *}{\textstyle *}{\scriptstyle *}}\!\!\mathcal {L}\) determines \(\mathcal {L}\), by Theorem 4.9; \(\mathsf {Alg}^{\mathchoice{\textstyle *}{\textstyle *}{\textstyle *}{\scriptstyle *}}\!\!\mathcal {L}\) does not, as already mentioned at the end of Sect. 4.3.

29. 29.

    Rasiowa’s notion assumes two inessential requirements for the language: that it contains no connectives of arity greater than 2, and that \(\mathbin {\rightarrow }\) is a primitive connective (rather than an arbitrary term in two variables). Moreover, she considers finitarity as part of the definition of a logic. All these restrictions are usually removed in later studies.

30. 30.

    This phrase is also used to refer, in a more general way, to the idea of characterizing algebraizability as a relation between the consequence of a logic and the equational consequence of a class of algebras through transformers, when compared with more distant approaches.

31. 31.

    This approach gave rise to other classes of (non-algebraizable) logics, forming the so-called implicational hierarchy, which is not described here.

32. 32.

    Although this is clearly one kind of algebra-based semantics, it departs from the general framework of this chapter, and its exposition would exceed current space constraints. Let me just add that order algebraizable logics in general need not be algebraizable; and that they are so if and only if the order relation in their equivalent “ordered algebraic semantics” is equationally definable. They are, though, stronger than equivalential, a significant class in the Leibniz hierarchy that appears in Sect. 6.1.

33. 33.

    Finitely equivalential logics appeared earlier than finitely algebraizable ones. Thus, “finitely” applied to algebraizable logics was adopted to indicate the finiteness only of \(\Delta \), in order to obtain the mentioned equivalence. A dual notion of a “finitely truth-equational logic” is not considered in the literature.

34. 34.

    They were first considered by Czelakowski, in unpublished lectures in 1993, under the name “algebraizable in the weak sense”; a term also used in [31].

35. 35.

    Other classes might be considered in the hierarchy, though in a looser sense. These include those obtained by restricting all the classes to their finitary members (among them is the class of BP-algebraizable logics), and some of the classes of Definition 5.2, for instance the “Rasiowa” classes.

36. 36.

    And also if and only if it is order algebraizable (see p. xxx).

37. 37.

    According to [27], this fact was first stated, essentially, by Suszko in unpublished lectures (here it is expressed in modern terms). Using the Suszko operator , to be defined in (17) on p. xxx, the condition can be more compactly written as .

38. 38.

    The condition in the last row is equivalent to saying that the truth filter in \(\mathsf {Mod}^{\mathchoice{\textstyle *}{\textstyle *}{\textstyle *}{\scriptstyle *}}\!\!\mathcal {L}\) is a singleton; but as a “definability” property this formulation looks weaker.

39. 39.

    There is no class of “finitely protoalgebraic” logics in the literature. One partial reason may be that for finitary logics, the set \(\Delta (x,y)\) of  Table  4 can always be chosen as finite in the protoalgebraic case, but not necessarily in the other cases. There is also the technical issue mentioned in footnote 40.

40. 40.

    Observe that the set \(\Delta ^{\!p}\) is always infinite, irrespective of whether \(\Delta \) is finite or not. Even if a protoalgebraic logic is finitary, the existence of a finite set defining the Leibniz congruence with parameters cannot be guaranteed. Compare this with the fact mentioned in footnote 39.

41. 41.

    This includes almost all the non-protoalgebraic logics mentioned on p. xxx. A strikingly simple example is that of \(CPC_{\!\wedge }\), the fragment of classical logic with only conjunction: while this logic is naturally associated with the variety of semilattices, it is not difficult to show that \(\mathsf {Alg}^{\mathchoice{\textstyle *}{\textstyle *}{\textstyle *}{\scriptstyle *}}CPC_{\!\wedge }\) contains just the one- and two-element semilattices [46, Corollary 5.3].

42. 42.

    A closure system on a set A is a family \(\mathcal {C}\) of subsets of A that contains A and is closed under intersections of arbitrary non-empty families. The sets \(\mathcal {F} i _{\!\mathcal {L}}^{}{{\boldsymbol{A}}}\) and \(Th\mathcal {L}\) are always closure systems. Originally, the \(\mathcal {C}\) in a generalized matrix was not assumed to be a closure system, but an arbitrary (non-empty) family of subsets; in this form they were rediscovered in [38], where they are called “atlases”. There is no essential difference between the two alternatives as far as their rôle as models of logics is concerned.

43. 43.

    A closure operator on a set A is a function \(C:\mathcal {P}(A)\rightarrow \mathcal {P}(A)\) that satisfies, for all \(X,Y\subseteq A\), that \(X\subseteq C(X) = C\bigl (C(X)\bigr ) \subseteq C(X\cup Y)\). Several notational shortcuts are popular, such as writing C(a) for \(C\bigl (\{a\}\bigr )\), or \(C(X,a)\) for \(C\bigl (X\cup \{a\}\bigr )\), and so on; recalling that the argument of C should always be a subset of A helps to avoid misunderstandings. The closure operator associated with the closure system \(\mathcal {F} i _{\!\mathcal {L}}^{}{{\boldsymbol{A}}}\) is denoted by \(F\!g_{\!\mathcal {L}}^{{{\boldsymbol{A}}}}\); thus, for any \(X\subseteq A\,,\;F\!g_{\!\mathcal {L}}^{{{\boldsymbol{A}}}}(X)\) is the smallest \(\mathcal {L}\)-filter of \({{\boldsymbol{A}}}\) containing X. The closure operator associated with \(Th\mathcal {L}\) is denoted by \(C_{\!\mathcal {L}}\). A closure operator C is finitary when for any \(X\subseteq A\,,\; C(X) = \bigcup \{C(Y): Y\subseteq X, \,Y\text { finite}\}\).

44. 44.

    That author attributes the definition and first characterization of this operator to Suszko, in unpublished lectures.

45. 45.

    To the best of my knowledge, the earliest example of this kind in the literature is Wójcicki’s “weak relevance” logic \(W\!R\) [44].

46. 46.

    This name was first used in [83].

47. 47.

    Recall that the equivalent algebraic semantics of a BP-algebraizable logic is in general a quasivariety. The best-known example of a BP-algebraizable logic whose equivalent algebraic semantics is not a variety is BCK logic [105].

48. 48.

    In a few early papers the term “Fregean” means the same as “protoalgebraic and Fregean” in the present terminology.

49. 49.

    Equivalently, for all full g-models; hence the “fully” in the names.

50. 50.

    Of course, this is not exactly a technical problem that admits a definite answer, but rather one of methodology, of understanding the algebraic behaviour of logics and the limits of existing techniques and results. Often these problems are more interesting than other, purely technical ones.

51. 51.

    The algebraizable logics whose equivalent algebraic semantics is a variety are sometimes called strongly algebraizable in the literature.

52. 52.

    There is a protoalgebraic logic without theorems, but only one (in each language) and it is rather trivial: it is the so-called almost inconsistent logic, defined as the logic without theorems such that \(\alpha \vdash _{\!\!\mathcal {L}}\beta \) for all \(\alpha ,\beta \in Fm\). This logic is protoalgebraic and Fregean in a trivial way, but is not algebraizable.

53. 53.

    This dual character of generalized matrices, as g-models of sentential logics and as models of Gentzen-style rules or systems, is one of the features that give generalized matrices their special interest.

54. 54.

    The operator \(C_{\!\mathcal {L}}\) is defined as \(\varphi \in C_{\!\mathcal {L}}(\Gamma )\) if and only if \(\Gamma \vdash _{\!\!\mathcal {L}}\varphi \) for any \(\Gamma \cup \{\varphi \}\subseteq Fm\). Thus, essentially, the closure operator associated with a logic is just another way of expressing the consequence relation. The properties formulated in its terms, such as those in Definition 7.3, are more naturally stated in terms of the relation; but the general definition uses a closure operator to facilitate application to both the logic and the algebras.

55. 55.

    This qualification certainly applies to the (easy) equivalence between (i) and (iii); the equivalence between (i) and (ii) seems to have first been published in [106].

56. 56.

    It does not make sense to say, literally, that the definability of the truth filter in reduced models of the logic (which appears in the third and fourth rows of Table 3) holds in the formula algebra, because in general there are no reduced models on the formula algebra itself. But it can be reformulated so that there is a transfer result for it: by Theorem 25 of [84], it holds in all models that are reductions of arbitrary models of the logic (that is, in all its reduced models) if and only if it holds in the models that are reductions of models on the formula algebra.

57. 57.

    Other, weaker versions of a DDT have been considered in the literature: The parameterized one, which allows the terms of the set I to have parameters; the local one, which deals with a (possibly infinite) family of sets of terms in such a way that only one set is used in each particular application of the theorem; and obviously, the one that is both local and parameterized, which turns out to characterize protoalgebraic logics. A fortiori, this implies that any logic satisfying a DDT is protoalgebraic. The newest kinds of DDT are the graded ones [49] and the contextual ones [87]; they have either local or parameterized variants as well.

58. 58.

    An obvious generalization of this property is obtained when the single binary term is replaced by a set of binary terms (as in the formulation given for the DDT); even more general is the parameterized version, where a finite number of parameters are allowed in the set of terms. In both cases the property is basically the same.

59. 59.

    A set X is C-inconsistent when \(C(X) = A\). The inconsistency lemma is a generalization of the intuitionistic form of reductio ad absurdum, where \(\Psi _n(x_1,\dots ,x_n):= \{\lnot (x_1\wedge \dots \wedge x_n)\}\).

60. 60.

    This generalization corresponds, essentially, to the “operation on rules” considered, at the proof-theoretic level, in [80]; see also [81].

61. 61.

    In some cases where by tradition only finitary logics were considered, the properties may turn out to hold in general. One example is the DDT (Theorem 7.4): Czelakowski’s original proof [30] needs finitarity, but Theorem 3.5 of [87] in particular shows the transfer for arbitrary logics. In other cases finitarity seems to be unavoidable; the removal of finitarity from some transfer or bridge theorems where it appears is an interesting open problem.

62. 62.

    Dually residuated join-semilattices are sometimes called Brouwerian semilattices.

63. 63.

    Not only in the context of protoalgebraic logics: any finitary logic having a disjunction is filter distributive [29].

64. 64.

    The notion of weak completeness, as opposed to ordinary or strong completeness, refers to the theorems of the logic rather than to the consequence relation.

65. 65.

    Transfer to basic full g-models is due to both Czelakowski and Pigozzi; point (i) was published in [31], and point (ii) in [37]. The transfer to arbitrary full g-models follows from the basic case and several results in [45].

66. 66.

    Roughly speaking, a Gentzen-style rule is accumulative when an arbitrary set of “side assumptions” occurs (the same set) in the antecedent (left-hand side) of all the sequents in the rule.

67. 67.

    In this situation, the two lattices are lattices of closed sets of certain finitary closure operators, therefore their compact elements are the finitely generated closed sets.

68. 68.

    EDPRC is the analogue, for quasivarieties and relative congruences, of the property of having equationally definable principal congruences (EDPC) for varieties, defined in Sect. 8 of Raftery’s chapter in this volume. The property EDPC has been extensively studied in universal algebra.

69. 69.

    The relations between (the different forms of) interpolation and amalgamation have also been studied in other frameworks, such as equational logic, abstract model theory, and the theory of institutions. The computational applications of interpolation seem to be partly responsible for such interest in this property.

70. 70.

    For instance: in the traditional versions of interpolation, the relation to be interpolated is either consequence or a connective of implication. In some recent papers, it is equivalence that is interpolated, either understood as a connective or as the more abstract Leibniz congruence. Cabrer and Gil-Férez [19] study up to eleven different versions of interpolation of all these kinds.

71. 71.

    This idea was first pursued in [52], where, thanks to a category equivalence between a class of integral residuated lattices and its non-integral counterpart, some metalogical properties of certain logics having both a fuzzy and a substructural character were indirectly obtained.

72. 72.

    Observe that properties concerning the class of all algebras, such as those in points (ii) in Theorems 7.13 and 7.14, offer more flexibility when it comes to attaining the first goal, while those restricted to the class \(\mathsf {K}\), such as points (iii), may better support the second.

73. 73.

    The work done by Blok in the 1970s on several lattices of modal logics (see [93] for a survey) is noteworthy, besides its intrinsic interest, for two reasons: he was the first to develop this kind of application, and it was one of his main sources of inspiration for the general theory of algebraizability.

74. 74.

    In the literature, a relation between two sentential logics expressed by means of a transformer in a way similar to (ALG1) has been named in a variety of ways; the term translation is popular, sometimes with either conservative or faithful prepended to it, but these are not used in a uniform way. Notice that the equivalence to which I refer here is stronger than this (the transformer is “invertible”), and that some translations considered in the literature are not structural.

75. 75.

    This is a particular case, tailored for this point of the present exposition, of a more general and abstract result, which should be easy to guess [42, Theorem 1.56].

76. 76.

    Recall that in this case, \(\mathcal {F} i _{\!\mathcal {L}}^{}{{\boldsymbol{Fm}}}= Th\mathcal {L}\) and hence that \(F\!g_{\!\mathcal {L}}^{{{\boldsymbol{Fm}}}} = C_{\!\mathcal {L}}\), and that the endomorphisms of \({{\boldsymbol{Fm}}}\) are the substitutions.

77. 77.

    The relative congruences of the formula algebra, \(\mathrm {Con}_\mathsf {K}{{\boldsymbol{Fm}}}\), are the closed sets (the “theories”) of the equational consequence \(\vDash _{\mathsf {K}}\).

78. 78.

    Now in the purely order-theoretic sense, as opposed to closure operators on power sets as described in footnote 43.

I am heavily indebted to Hiroakira Ono for his support in the early stages of my career and for his continuing kindness in regard to my work and my proposals. As to the present paper, I am most grateful to Tommaso Moraschini and to an anonymous referee, whose many observations concerning details as well as more substantial remarks decidedly improved the exposition presented here. While writing this chapter, I was partially funded by the research project MTM2011-25747 from the government of Spain, which includes feder funds from the European Union, and the research grant 2009SGR-1433 from the government of Catalonia.

Authors and Affiliations

1. Departament of Mathematics and Computer Engineering, Universitat de Barcelona (UB), Gran Via de les Corts Catalanes 585, 08007, Barcelona, Spain

   Josep Maria Font

Corresponding author

Correspondence to Josep Maria Font .

Editors and Affiliations

1. Department of Mathematics, University of Denver, Denver, CO, USA

   Nikolaos Galatos

2. Research Institute for Mathematical Sciences, Kyoto University, Kyoto, Japan

   Kazushige Terui

Reprints and permissions

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics