Algebraic Propositional Logic

First published Mon Dec 12, 2016; substantive revision Fri May 20, 2022

George Boole was the first to present logic as a mathematical theoryin algebraic style. In his work, and in that of the other algebraistsof the algebraic tradition of logic of the nineteenth century, thedistinction between a formal language and a mathematically rigoroussemantics for it was still not drawn. What the algebraists in thistradition did was to build algebraic theories (of Boolean algebras,and relation algebras) with among other interpretations a logicalone.

The works of Frege and Russell introduced a different perspective onthe way to approach logic. In those works, a logic system was given bya formal language and a deductive calculus, namely a set of axioms anda set of inference rules. Let us (for this entry) call such a pair alogical deduction system, and the formulas derivable in thecalculus itstheorems (nowadays it is common practice inalgebraic logic to refer to this type of calculi as Hilbert-style andin proof complexity theory as Frege systems). In Frege andRussell’s approach, a formal (mathematical) semantics ofwhatever kind (algebraic, model-theoretic, etc.) for the formallanguages they used was lacking. The only semantics present was of anintuitive, informal kind.

The systems introduced by Frege and Russell were systems of classicallogic, but soon after systems of non-classical logics were consideredby other logicians. The first influential attempts to introduce logicsdifferent from classical logic remained within the Frege-Russelltradition of presenting a logical deduction system without any formalsemantics. These attempts lead to the first modal systems of C.I.Lewis (1918, 1932) and to the axiomatization of intuitionistic logicby Heyting (1930).

The idea underlying the design of Frege and Russell’s logicaldeduction systems is that the theorems should be the formulas thatcorrespond (intuitively) to the logical truths or logical validities.The concept of logical consequence was not central to the development,and this was also the case in the many systems of non-classical logicsthat were to be designed following in the footsteps of the first modalsystems of C.I. Lewis. This situation influenced the way in which theresearch on some non-classical logics has usually been presented andsometimes also its real evolution. However, the concept of logicalconsequence has been the one that logic has traditionally dealt with.Tarski put it once again into the center of modern logic, bothsemantically and syntactically. Nowadays, a general theory of thealgebraization of logics around the concept of logical consequence hasgrown from the different algebraic treatments of the different logicsobtained during the last century.

The concept of logical consequence has proved much more fruitful thanthose of theorem and of logical validity for the development of such ageneral theory. The first attempts in the process of building thegeneral theory of the algebraization of logics can be found in thestudy of the class of implicative logics by Rasiowa (1974) and in thesystematic presentation by Wójcicki (1988) of theinvestigations of a general nature on propositional logics asconsequence operations carried out mainly by Polish logicians,following the studies of Tarski, Lindenbaum, Łukasiewicz andothers in the first part of the twentieth century.

It was only in the 1920s that algebras and logical matrices (analgebra together with a set of designated elements) started to betaken as models of logical deduction systems, that is, as providing aformal semantics for formal languages of logic. Moreover, they werealso used to define sets of formulas with similar properties to theones the sets of theorems of the known logical deduction systems have,in particular the property of being closed under substitutioninstances; soon after logical matrices were also used todefine logics as consequence relations.

Algebraic logic can be described in very general terms as thediscipline that studies logics by associating with them classes ofalgebras, classes of logical matrices and other algebra relatedmathematical structures and that relates the properties that thelogics may have with properties of the associated algebras (or algebrarelated structures) with the purpose that the understanding of thesealgebras can be used to better understand the logic at hand.

From the algebraic study of particular logics, a general theory of thealgebraization of logics slowly emerged during the last century withthe aim, more or less explicitly stated during the process, ofobtaining general and informative results relating the properties alogic may have with the algebraic properties the class of algebras (oralgebra related structures) associated with it might enjoy. Thosealgebraic studies assumed somehow an implicit conception of what isthe process by which to associate with any given logic a class ofalgebras as its natural algebraic counterpart. The development of thatgeneral theory speeded up and consolidated at the beginning of the1980s with the introduction of the notion of algebraizable logic, andat that time also the assumptions about the class of algebras thatdeserves to be taken as the natural one to associate with a given logicstarted to be made more and more explicit.

In this entry we concentrate on the general theory of thealgebraization of propositional logics taken as consequence relations.This theory has evolved into the field known as Abstract AlgebraicLogic (AAL). The entry can be taken as a mild introduction to thisfield.

1. Abstract consequence relations

Tarski’s work (1930a, 1930b, 1935, 1936) on the methodology ofthe deductive sciences of the 1920s and 1930s studies the axiomaticmethod abstractly and introduces for the first time the abstractconcept of consequence operation. Tarski had mainly in mind thedifferent mathematical axiomatic theories. On these theories, thesentences that are proved from the axioms are consequences of them but(of course) almost all of them are not logical truths; under asuitable formalization of these theories, a logical calculus likeFrege’s or Russell’s can be used to derive theconsequences of the axioms. Tarski set the framework to study the mostgeneral properties of the operation that assigns to a set of axiomsits consequences.

Given a logical deduction system \(H\) and an arbitraryset of formulas \(X\), a formula \(a\)isdeducible in \(H\) from \(X\)if there is a finite sequence of formulas any one ofwhich belongs to \(X\) or is an axiom of \(H\)or is obtained from previous formulas in the sequenceby one of the inference rules of \(H\). Such a sequenceis a deduction (or proof) in \(H\) of \(a\)with premises or hypotheses in \(X\).Let \(Cn(X)\) be the set of formulas deducible in \(H\)from the formulas in \(X\) taken as premises orhypothesis. This set is called the set of consequences of \(X\)(relative to the logical deduction system \(H\)).\(Cn\) is then an operation that is applied to setsof formulas to obtain new sets of formulas. It has the followingproperties: For every set of formulas \(X\)

\(X \subseteq Cn(X)\)
\(Cn(Cn(X)) = Cn(X)\)
\(Cn(X) = \bigcup\{Cn(Y): Y \subseteq X, Y \textrm{finite}\}\)

The third condition stipulates that \(Cn(X)\) is equal to the union of the set offormulas derivable from finite subsets of \(X\). Tarskitook these properties to define the notion of consequence operationaxiomatically. In fact, he added that there is a formula \(x\)such that \(Cn(\{x\})\) is the set \(A\)of all the formulas and that this set must be finiteor of the cardinality of the set of the natural numbers. Condition (3)implies the weaker, and important, condition of monotonicity

if \(X \subseteq Y \subseteq A\), then \(Cn(X)\subseteq Cn(Y)\).

To encompass the whole class of logic systems one finds in theliterature, a slightly more general definition than Tarski’s isrequired. We will say that anabstract consequence operation\(C\) on an arbitrary set \(A\) is anoperation that applied to subsets of \(A\) givessubsets of \(A\) and for all \(X, Y \subseteq A\)satisfies the conditions (1), (2) and (4) above. If in addition \(C\)satisfies (3) we say that it is afinitaryconsequence operation.

Consequence operations are present not only in logic but in many areasof mathematics. Abstract consequence operations are known as closureoperators in universal algebra and lattice theory, for instance. Intopology the operation that sends a subset of a topological space toits topological closure is a closure operator. In fact, the topologieson a set \(A\) can be identified with the closureoperators on \(A\) that satisfy the additionalconditions that \(C(\varnothing) = \varnothing\) and \(C(X \cup Y) =C(X) \cup C(Y)\) for all \(X, Y \subseteq A\).

Given a consequence operation \(C\) on a set \(A\),a subset \(X\) of \(A\)is said to be \(C\)-closed,or aclosed set of \(C\), if \(C(X) = X\).

A different, but mathematically equivalent, (formal) approach is toconsider consequence relations on a set of formulas instead ofconsequence operations. A(n) (abstract)consequence relationon the set of formulas of a formal language is a relation \(\vdash\)between sets of formulas and formulas that satisfies the followingconditions:

if \(a \in X\), then \(X \vdash a\)
if \(X \vdash a\) and \(X \subseteq Y\), then \(Y \vdash a\)
if \(X \vdash a\) and for every \(b \in X, Y \vdash b\), then \(Y\vdash a\).

It isfinitary if in addition it satisfies

if \(X \vdash a\), then there is a finite set \(Y \subseteq X\)such that \(Y \vdash a\).

Given a logical deduction system \(H\), the relation\(\vdash\) defined by \(X \vdash a\) if \(a\) isdeducible from \(X\) in \(H\) is (according to all we have already seen) afinitary consequence relation. Nonetheless, we are used not only tosyntactic definitions of consequence relations but also to semanticdefinitions. For example, we define classical propositionalconsequence using truth valuations, first-order consequence relationusing structures, intuitionistic consequence relation using Kripkemodels, etc. Sometimes these model-theoretic definitions ofconsequence relations define non-finitary consequence relations, forexample, the consequence relations for infinitary formal languages andthe consequence relation of second-order logic with the so-calledstandard semantics.

In general, anabstract consequence relation on a set \(A\)(not necessarily the set of formulas of some formallanguage) is a relation \(\vdash\) between subsets of \(A\)and elements of \(A\) that satisfiesconditions (1)–(3) above. If it also satisfies (4) it is said tobe finitary. If \(\vdash\) is an abstract consequence relation and \(X\vdash a\), then we can say that \(X\) is a set ofpremises or hypothesis with conclusion \(a\) accordingto \(\vdash\) and that \(a\) follows from \(X\),or is entailed by \(X\) (according to\(\vdash)\). The abstract consequence relations correspond toKoslow’s implication structures; see Koslow 1992 for the closelyrelated but different approach to logics (in a broad sense) asconsequence relations introduced by that author.

The consequence operations on a set \(A\) are inone-to-one correspondence with the abstract consequence relations on\(A\). The move from a consequence operation \(C\)to a consequence relation \(\vdash_C\) and,conversely, from a consequence relation \(\vdash\) to a consequenceoperation \(C_{\vdash}\) is easy and given by the definitions:

\[ X \vdash_C a \txtiff a \in C(X) \hspace{3mm} \textrm{ and } \hspace{3mm} a \in C_{\vdash}(X) \txtiff X \vdash a. \]

Moreover, if \(C\) is finitary, so is \(\vdash_C\) andif \(\vdash\) is finitary, so is \(C_{\vdash}\).

For a general discussion on logical consequence see the entryLogical Consequence.

2. Logics as consequence relations

In this section we define what propositional logics are and explainthe basic concepts relating to them. We will call the propositionallogics (as defined below) simplylogic systems.

One of the main traits of the consequence relations we study in logicis their formal character. This roughly means that if a sentence \(a\)follows from a set of sentences \(X\)and we have another sentence \(b\) and another set ofsentences \(Y\) that share the same form with \(a\)and \(X\) respectively, then \(b\)also follows from \(Y\). Inpropositional logics this boils down to saying that if we uniformlyreplace basic sub-sentences of the sentences in \(X \cup \{a\}\) byother sentences obtaining \(Y\) and \(b\),then \(b\) follows from \(Y\).(The reader can find more information on the idea offormality in the entryLogical Consequence.)

To turn the idea of the formal character of logics into a rigorousdefinition we need to introduce the concept of propositional languageand the concept of substitution.

Apropositional language (a language, for short) \(L\) is a set ofconnectives, that is, a set of symbols each one of which has an arity\(n\) that tells us in case that \(n = 0\) that thesymbol is a propositional constant, and in case that \(n \gt 0\)whether the connective is unary, binary, ternary, etc. For example\(\{\wedge , \vee , \rightarrow , \bot , \top \}\) is (or can be) thelanguage of several logics, like classical and intuitionistic,\((\bot\) and \(\top\) are 0-ary and the other connectives arebinary), \(\{\neg , \wedge , \vee \rightarrow , \Box , \Diamond \}\)is the language of several modal logics, \((\neg , \Box , \Diamond\)are unary and the other connectives binary) and \(\{ \wedge , \vee ,\rightarrow , * , \top , \bot , 1, 0\}\) is the language ofmany-valued logics and also of a fragment of linear logic \((\bot ,\top , 1\), and 0 are propositional constants and the other symbolsbinary connectives).

Given a language \(L\) and a set of propositionalvariables \(V\) (which is disjoint from \(L)\), theformulas of \(L\), or \(L\)-formulas,are defined inductively asfollows:

Every variable is a formula.
Every 0-ary symbol is a formula.
If \(*\) is a connective and \(n \gt 0\) is itsarity, then for all formulas \(\phi_1 ,\ldots ,\phi_n, * \phi_1 \ldots\phi_n\) is also a formula.

Asubstitution \(\sigma\) for \(L\) is a mapfrom the set of variables \(V\) to the set of formulasof \(L\). It tells us which formula must replace whichvariable when we perform the substitution. If \(p\) isa variable, then \(\sigma(p)\) denotes the formula that thesubstitution \(\sigma\) assigns to \(p\). The result ofapplying a substitution \(\sigma\) to a formula \(\phi\) is theformula \(\bsigma(\phi)\) obtained from \(\phi\) by simultaneouslyreplacing the variables in \(\phi\), say \(p_1 , \ldots ,p_k\), by,respectively, the formulas \(\sigma(p_1), \ldots ,\sigma(p_k)\). Inthis way, a substitution \(\sigma\) gives a unique map \(\bsigma\)from the set of formulas to itself that satisfies

\(\bsigma(p) = \sigma(p)\), for every variable \(p\),
\(\bsigma(\dagger) = \dagger\), for every 0-ary connective\(\dagger\),
\(\bsigma(* \phi_1 \ldots \phi_n) = * \bsigma(\phi_1)\ldots\bsigma(\phi_n)\), for every connective \(*\) of arity\(n \gt 0\) and formulas \(\phi_1 , \ldots ,\phi_n\).

A formula \(\psi\) is asubstitution instance of a formula\(\phi\) if there is a substitution \(\sigma\) such that when appliedto \(\phi\) gives \(\psi\), that is, if \(\bsigma(\phi) = \psi\).

In order to avoid unnecessary complications we will assume in thesequel that all the logics use the same denumerable set \(V\) ofvariables, so that the definition of formula of \(L\)depends only on \(L\). Alogic system (orlogic for short) is given by a language \(L\)and a consequence relation \(\vdash\) on the set of formulas of \(L\)that isformal in the sense that for everysubstitution \(\sigma\), every set of formulas \(\Gamma\) and everyformula \(\phi\),

\[ \textrm{if } \Gamma \vdash \phi, \textrm{ then } \bsigma[\Gamma] \vdash\bsigma(\phi) \]

where \(\bsigma[\Gamma]\) is the set of the formulas obtained byapplying the substitution \(\sigma\) to the formulas in \(\Gamma\).The consequence relations on the set of formulas of a language thatsatisfy this property are calledstructural and alsosubstitution-invariant in the literature. They wereconsidered for the first time in Łoś & Suszko 1958.Tarski only explicitly considered closed sets also closed undersubstitution instances for some consequence relations; he neverconsidered (at least explicitly) the substitution invariance conditionfor consequence relations.

We will refer to logic systems by the letter \(\bL\) with possiblesubindices, and we set \(\bL = \langle L, \vdash_{\bL } \rangle\) and\(\bL_n = \langle L_n, \vdash_{\bL_n } \rangle\) with theunderstanding that \(L \; (L_n)\) is the language of \(\bL \;(\bL_n)\)and \(\vdash_{\bL }\; (\vdash_{\bL_n })\) its consequence relation. Alogic system \(\bL\) isfinitary if \(\vdash_{\bL}\) is afinitary consequence relation.

The consequence relation of a logic system can be given in severalways, some using proof-theoretic tools, others semantic means. Asubstitution-invariant consequence relation can be defined using aproof system like a Hilbert-style axiom system, a Gentzen-stylesequent calculus or a natural deduction style calculus, etc. One canalso define a substitution-invariant consequence relation semanticallyusing a class of mathematical objects (algebras, Kripke models,topological models, etc.) and a satisfaction relation.

If \(\bL_1 = \langle L,\vdash_{\bL_1 } \rangle\) is a logic systemwith \(\vdash_{\bL_1}\) defined by a proof-system and \(\bL_2 =\langle L, \vdash_{\bL_2 } \rangle\) is a logic system over the samelanguage with \(\vdash_{\bL_2}\) defined semantically, we say that theproof-system used to define \(\vdash_{\bL_1}\) issound forthe semantics used to define \(\vdash_{\bL_2}\) if \(\vdash_{\bL_1}\)is included in \(\vdash_{\bL_2}\), namely if \(\Gamma \vdash_{\bL_1 }\phi\) implies \(\Gamma \vdash_{\bL_2 } \phi\). If the other inclusionholds the proof-system is said to becomplete with respect tothe semantics that defines \(\vdash_{\bL_2}\), that is, when \(\Gamma\vdash_{\bL_2 } \phi\) implies \(\Gamma \vdash_{\bL_1 } \phi\).

A set of \(L\)-formulas \(\Gamma\) is called atheory of a logic system \(\bL\), or \(\bL\)-theory, if it isclosed under the relation \(\vdash_{\bL}\), that is, if whenever\(\Gamma \vdash_{\bL } \phi\) it also holds that \(\phi \in \Gamma\).In other words, the theories of \(\bL\) are the closed sets of theconsequence operation \(C_{\vdash_{ \bL}}\) on the set of \(L\)-formulas.In order to simplify the notation we denotethis consequence operation by \(C_{\bL}\). A formula \(\phi\) is atheorem (or validity) of \(\bL\) if \(\varnothing \vdash_{\bL} \phi\). Then \(C_{\bL }(\varnothing)\) is the set of theorems of\(\bL\) and is the least theory of \(\bL\). The set of all theories of\(\bL\) will be denoted by \(\tTH(\bL)\).

Given a logic system \(\bL\), the consequence operation \(C_{\bL}\) is substitution-invariant, which means that for every set of \(L\)-formulas \(\Gamma\) and every substitution \(\sigma, \bsigma[C_{\bL}(\Gamma)] \subseteq C_{\bL}(\bsigma[\Gamma]\)). Moreover, for every theory \(T\) of \(\bL\) we have a new consequence \(C_{\bL }^T\) operation defined as follows: \[C_{\bL }^T (\Gamma) = C_{\bL }(T \cup \Gamma)\] that is, \(C_{\bL }^T (\Gamma)\) is the set of formulas that follow from \(\Gamma\) and \(T\) according to \(\bL\). It turns out that \(T\) is closed under substitutions if and only if \(C_{\bL }^T\) is substitution-invariant.

If \(\bL\) is a logic system and \(\Gamma , \Delta\) are sets of \(L\)-formulas,we will use the notation \(\Gamma\vdash_{\bL } \Delta\) to state that for every \(\psi \in \Delta ,\Gamma \vdash_{\bL } \psi\). Thus \(\Gamma \vdash_{\bL } \Delta\) ifand only if \(\Delta \subseteq C_{\bL }(\Gamma)\).

If \(\bL = \langle L, \vdash_{\bL } \rangle\) and \(\bL' = \langle L', \vdash_{\bL' } \rangle\) are logic systems whose languages satisfy that \(L'\subseteq L\) (hence all the \(L'\)-formulas are \(L\)-formulas) and \[\Gamma \vdash_{\bL' } \phi \txtiff \Gamma \vdash_{\bL } \phi,\] for every set of \(L'\)-formulas \(\Gamma\) and every \(L'\)-formula \(\phi\) we say that \(\bL'\) is afragment \(\bL\) (in fact, the \(\bL'\)-fragment) and that \(\bL\) is anexpansion of \(\bL'\).

3. Some examples of logics

We present some examples of logic systems that we will refer to in thecourse of this essay, that are assembled here for the reader’sconvenience. Whenever possible we refer to the correspondingentries.

We use the standard convention of writing \((\phi * \psi)\) instead of\(* \phi \psi\) for binary connectives and omit the externalparenthesis in the formulas.

3.1 Classical propositional logic

We take the language of Classical propositional logic \(\bCPL\) to bethe set \(L_c = \{\wedge , \vee , \rightarrow , \top , \bot \},\)where \(\wedge , \vee , \rightarrow\) are binary connectives and\(\top , \bot\) propositional constants. We assume that theconsequence relation is defined by the usual truth-table method\((\top\) is interpreted astrue and\(\bot\) asfalse) as follows,

\(\Gamma \vdash_{\bCPL } \phi\txtiff\) every truth valuation thatassignstrue to all \(\psi \in \Gamma\)assignstrue to \(\phi\).

The formulas \(\phi\) such that \(\varnothing \vdash_{\bCPL } \phi\)are thetautologies. Note that using the language \(L_c\),the negation of a formula \(\phi\) is defined as \(\phi \rightarrow\bot\). For more information, see the entry onclassical logic.

3.2 Intuitionistic propositional logic

We take the language of Intuitionistic propositional logic to be thesame as that of classical propositional logic, namely the set\(\{\wedge , \vee , \rightarrow , \top , \bot \}\). The consequencerelation is defined by the following Hilbert-style calculus.

Axioms:

All the formulas of the forms

C0.: \(\top\)
C1.
\(\phi \rightarrow(\psi \rightarrow \phi)\)
C2.: \(\phi \rightarrow(\psi \rightarrow(\phi \wedge \psi))\)
C3.: \((\phi \wedge \psi) \rightarrow \phi\)
C4.: \((\phi \wedge \psi) \rightarrow \psi\)
C5.: \(\phi \rightarrow(\phi \vee \psi)\)
C6.: \(\psi \rightarrow(\phi \vee \psi)\)
C7.: \((\phi \vee \psi) \rightarrow((\phi \rightarrow \delta)\rightarrow((\psi \rightarrow \delta) \rightarrow \delta))\)
C8.: \((\phi \rightarrow \psi) \rightarrow((\phi \rightarrow(\psi\rightarrow \delta)) \rightarrow(\phi \rightarrow \delta))\)
C9.: \(\bot \rightarrow \phi\)

Rule of inference

\[\phi , \phi \rightarrow \psi / \psi \tag{Modus Ponens}\]

For more information, see the entry onintuitionistic logic.

3.3 Local Normal Modal logics

The language of modal logic we consider here is the set \(L_m = \{\wedge , \vee , \rightarrow , \neg , \Box , \top , \bot \}\) that expands \(L_c\) by adding the unary connective \(\Box\). In the standard literature on modal logic a normal modal logic is defined not as a consequence relation but as a set of formulas with certain properties. Anormal modal logic is a set \(\Lambda\) of formulas of \(L_m\) that contains all the tautologies of the language of classical logic, the formulas of the form \[\Box(\phi \rightarrow \psi) \rightarrow(\Box \phi \rightarrow \Box \psi)\] and is closed under the rules

\[ \begin{align*} \phi , \phi \rightarrow \psi / \psi \tag{Modus Ponens}\\ \phi / \Box \phi \tag{Modal Generalization}\\ \phi/ \bsigma(\phi), \textrm{ for every substitution } \sigma \tag{Substitution}\\ \end{align*} \]

Note that the set \(\Lambda\) is closed under substitution instances,namely for every substitution \(\sigma\), if \(\phi \in L_m\), then\(\bsigma(\phi) \in L_m\).

The least normal modal logic is called \(K\) and can beaxiomatized by the Hilbert-style calculus with axioms the tautologiesof classical logic and the formulas \(\Box(\phi \rightarrow \psi)\rightarrow(\Box \phi \rightarrow \Box \psi)\), and with rules ofinference Modus Ponens and Modal Generalization. Note that since we use schemas in the presentation of the axioms, the set of derivable formulas is closed under the Substitution rule.

With a normal modal logic \(\Lambda\) it is associated the consequencerelation defined by the calculus that takes as axioms all the formulasin \(\Lambda\) and as the only rule of inference Modus Ponens. Thelogic system given by this consequence relation is called thelocal consequence of \(\Lambda\). We denote it by\(\blLambda\). Its theorems are the elements of \(\Lambda\) and itholds that

\(\Gamma \vdash_{\blLambda} \phi\txtiff\phi \in \Lambda\) or there are\(\phi_1 , \ldots ,\phi_n \in \Gamma\) such that \((\phi_1 \wedge\ldots \wedge \phi_n) \rightarrow \phi \in \Lambda\).

3.4 Global Normal Modal logics

Another consequence relation is associated naturally with each normal modallogic \(\Lambda\), defined by the calculus that has as axiomsthe formulas of \(\Lambda\) and as rules of inference Modus Ponens andModal Generalization. The logic system given by this consequencerelation is called theglobal consequence of \(\Lambda\) andwill be denoted by \(\bgLambda\). It has the same theorems as thelocal \(\blLambda\), namely the elements of \(\Lambda\). Thedifference between \(\blLambda\) and \(\bgLambda\) lies in theconsequences they allow to draw from nonempty sets of premises. For example we have \(p \vdash_{\bgK} \Box p\) but \(p \not\vdash_{\blK} \Box p\). Thisdifference has an enormous effect on their algebraic behavior.

For more information on modal logic, see the entry onmodal logic. The reader can find specific information on modal logics asconsequence relations in Kracht 2006.

3.5 Intuitionistic Linear Logic without exponentials

We take as the language of Intuitionistic Linear Logic withoutexponentials the set \(\{\wedge , \vee , \rightarrow , * , 0, 1, \top, \bot \}\), where \(\wedge , \vee , \rightarrow, *\) are binaryconnectives and \(0, 1,\top , \bot\) propositional constants. Wedenote the logic by \(\bILL\). The axioms and rule of inference belowprovide a Hilbert-style axiomatization of this logic.

Axioms:

L1.: 1
L2.: \((\phi \rightarrow \psi) \rightarrow((\psi \rightarrow \delta)\rightarrow(\phi \rightarrow \delta))\)
L3.: \((\phi \rightarrow(\psi \rightarrow \delta)) \rightarrow(\psi\rightarrow(\phi \rightarrow \delta))\)
L4.: \(\phi \rightarrow(\psi \rightarrow(\phi * \psi))\)
L5.: \((\phi \rightarrow(\psi \rightarrow \delta)) \rightarrow((\phi *\psi) \rightarrow \delta)\)
L6.: \(1 \rightarrow(\phi \rightarrow \phi)\)
L7.: \((\phi \wedge \psi) \rightarrow \phi\)
L8.: \((\phi \wedge \psi) \rightarrow \psi\)
L9.: \(\psi \rightarrow(\phi \vee \psi)\)
L10.: \(\phi \rightarrow(\phi \vee \psi)\)
L11.: \(((\phi \rightarrow \psi) \wedge(\phi \rightarrow \delta))\rightarrow(\phi \rightarrow(\psi \wedge \delta))\)
L12.: \(((\phi \rightarrow \delta) \wedge(\psi \rightarrow \delta))\rightarrow((\phi \vee \psi) \rightarrow \delta)\)
L13.: \(\phi \rightarrow \top\)
L14.: \(\bot \rightarrow \psi\)

Rules of inference:

\[ \begin{align*} \phi , \phi \rightarrow \psi / \psi \tag{Modus Ponens}\\ \phi , \psi / \phi \wedge \psi \tag{Adjunction}\\ \end{align*} \]

The 0-ary connective 0 is used to define a negation by \(\neg \phi :=\phi \rightarrow 0\). No specific axiom schema deals with 0.

For more information, see the entry onlinear logic.

3.6 The system \(\bR\) of Relevance Logic

The language we consider is the set \(\{\wedge , \vee , \rightarrow ,\neg \}\), where \(\wedge , \vee , \rightarrow\) are binaryconnectives and \(\neg\) a unary connective. A Hilbert styleaxiomatization for \(\bR\) can be given by the rules of IntuitionisticLinear Logic without exponentials and the axioms L2, L3, L7-L12 ofthis logic together with the axioms

\((\phi \rightarrow(\phi \rightarrow \psi)) \rightarrow(\phi\rightarrow \psi)\)
\((\phi \rightarrow \neg \psi) \rightarrow(\psi \rightarrow \neg\psi)\)
\((\phi \wedge(\psi \vee \delta)) \rightarrow((\phi \wedge \psi)\vee \phi \wedge \delta))\)
\(\neg \neg \phi \rightarrow \phi\)

For more information, see the entry onrelevance logic.

4. Algebras

The algebraic study of a particular logic has to provide first of allits formal language with an algebraic semantics using a class ofalgebras whose properties are exploited to understand which propertiesthe logic has. In this section, we present how the formal languages ofpropositional logics are given an algebraic interpretation. In thenext section, we address the question of what is an algebraicsemantics for a logic system.

We start by describing the first two steps involved in the algebraicstudy of propositional logics. Both are needed in order to endowpropositional languages with algebraic interpretations. To expoundthem we will assume knowledge of first-order logic (see the entries onclassical logic andfirst-order model theory) and we will callalgebraic first-order languages, or simplyalgebraic languages, the first-order languages with equalityand without any relational symbols, so that these languages have onlyoperation symbols (also called function symbols), if any, in the setof their non-logical symbols.

The two steps we are about to expound can be summarized in theslogan:

Propositional formulas are terms.

Thefirst step consist in looking at the formulas of anypropositional language \(L\) as the terms of thealgebraic first-order language with \(L\) as its set ofoperation symbols. This means that (i) every connective of \(L\)of arity \(n\) is taken as anoperation symbol of arity \(n\) (thus every 0-arysymbol of \(L\) is taken as an individual constant) andthat (ii) the propositional formulas of \(L\) are takenas the terms of this first-order language; in particular thepropositional variables are the variables of the first-order language.From this point of view the definition of \(L\)-formulais exactly the definition of \(L\)-term. We will referto the algebraic language with \(L\) as its set ofoperation symbols as the \(L\)-algebraiclanguage.

Thesecond step is to interpret the propositional formulas inthe same manner in which terms of a first-order language areinterpreted in a structure. In this way the concept of \(L\)-algebracomes into play. On a given set \(A\),an \(n\)-ary connective isinterpreted by an \(n\)-ary function on \(A\)(a map that assigns an element of \(A\)to every sequence \(\langle a_1 , \ldots,a_n\rangle\) of elements of \(A)\). This procedure is ageneralization of the truth-table interpretations of the languages oflogic systems like classical logic and Łukasiewicz andPost’s finite-valued logics. In those cases, given the set oftruth-values at play the function that interprets a connective isgiven by its truth-table.

A way to introduce algebras is as the models of some algebraicfirst-order language. We follow an equivalent route and give thedefinition of algebra using the setting of propositional languages.Let \(L\) be a propositional language. Analgebra \(\bA\) of type \(L\), or \(L\)-algebrafor short, is a set \(A\),called the carrier or the universe of \(\bA\), together with afunction \(* ^{\bA}\) on \(A\) of the arity of \(*\),for every connective \(*\) in \(L\) (if \(*\) is 0-ary,\(* ^{\bA}\) is an element of \(A)\). An algebra \(\bA\) istrivial if its carrier is a one element set.

Avaluation on an \(L\)-algebra \(\bA\) is amap \(v\) from the set of variables into its carrier\(A\). Algebras together with valuations are used tointerpret in a compositional way the formulas of \(L\),assuming that a connective \(*\) of \(L\) isinterpreted in an \(L\)-algebra \(\bA\) by the function\(* ^{\bA}\). Let \(\bA\) be an algebra of type \(L\)and \(v\) a valuation on \(\bA\). The value of acompound formula \(* \phi_1 \ldots \phi_n\) is computed by applyingthe function \(* ^{\bA}\) that interprets \(*\) in \(\bA\) to thepreviously computed values \(\bv(\phi_1), \ldots,\bv(\phi_n)\) of theformulas \(\phi_1,\ldots,\phi_n\). Precisely speaking, the value\(\bv(\phi)\) of a formula \(\phi\) is defined inductively asfollows:

\(\bv(p) = v(p)\), for each variable \(p\),
\(\bv(\dagger) = \dagger^{\bA}\), if \(\dagger\) is a 0-aryconnective
\(\bv(* \phi_1 \ldots \phi_n) = * ^{\bA }(\bv(\phi_1), \ldots,\bv(\phi_n))\), if \(*\) is a \(n\)-ary \((n \gt 0)\)connective.

Note that in this way we have obtained a map \(\bv\) from the set of\(L\)-formulas to the carrier of \(\bA\). It isimportant to notice that the value of a formula under a valuationdepends only on the propositional variables that actually appear inthe formula. Accordingly, if \(\phi\) is a formula, then we use thenotation \(\phi(p_1 , \ldots ,p_n)\) to indicate that the variablesthat appear in \(\phi\) are in the list \(p_1 , \ldots ,p_n\), andgiven elements \(a_1 , \ldots ,a_n\) of an algebra \(\bA\) we refer by\(\phi^{\bA }[a_1 , \ldots ,a_n]\) to the value of \(\phi(p_1 , \ldots,p_n)\) under any valuation \(v\) on \(\bA\) such that\(v(p_1) = a_1 , \ldots ,v(p_n) = a_n\).

Athird and fundamentalstep in the algebraic studyof logics is to turn the set of formulas of a language \(L\)into an algebra, thealgebra of formulas of\(L\), denoted by \(\bFm_L\). This algebra has the setof \(L\)-formulas as carrier and the operations aredefined as follows. For every \(n\)-ary connective \(*\)with \(n \gt 0\), the function \(* ^{\bFm_L}\) is themap that sends each tuple of formulas \((\phi_1 , \ldots ,\phi_n)\)(where \(n\) is the arity of \(*\)) to the formula \(*\phi_1 \ldots \phi_n\), and for every 0-ary connective \(\dagger ,\dagger^{\bFm_L}\) is \(\dagger\). If no confusion is likely wesuppress the subindex in \(\bFm_L\) and write \(\bFm\) instead.

4.1 Some concepts of universal algebra and model theory

Algebras are a particular type of structure or model. An \(L\)-algebrais a structure or model for the \(L\)-algebraicfirst-order language. Therefore theconcepts of model theory for the first-order languages apply to them(see the entries onclassical logic andfirst-order model theory). We need some of these concepts. They are also used in universalalgebra, a field that to some extent can be considered the modeltheory of the algebraic languages. We introduce the definitions of theconcepts we need.

Given an algebra \(\bA\) of type \(L\), acongruence of \(\bA\) is an equivalence relation \(\theta\)on the carrier of \(\bA\) that satisfies for every \(n\)-aryconnective \(* \in L\) the followingcompatibility property: for every \(a_1 , \ldots ,a_n, b_1 , \ldots,b_n \in A\),

\[ \textrm{if } a_1\theta b_1 , \ldots ,a_n \theta b_1, \textrm{ then } *^{\bA}(a_1 ,\ldots ,a_n)\ \theta *^{\bA}(b_1 ,\ldots ,b_n). \]

Given a congruence \(\theta\) of \(\bA\) we can reduce the algebra byidentifying the elements which are related by \(\theta\). The algebraobtained is thequotient algebra of \(\bA\) modulo\(\theta\). It is denoted by \(\bA/\theta\), its carrier is the set\(A/\theta\) of equivalence classes \([a]\) of the elements \(a\)of \(A\) modulo the equivalencerelation \(\theta\), and the operations are defined as follows:

\(\dagger^{\bA/\theta} = [\dagger^{\bA}]\), for every 0-aryconnective \(\dagger\),
\(* ^{\bA/\theta}([a_1], \ldots, [a_n]) = [* ^{\bA }(a_1 ,\ldots,a_n)]\), for every connective \(*\) whose arity is \(n\)and \(n \gt 0\).

The compatibility property ensures that the definition is sound.

Let \(\bA\) and \(\bB\) be \(L\)-algebras. Ahomomorphism \(h\) from \(\bA\) to \(\bB\) isa map \(h\) from \(A\) to \(B\)such that for every 0-ary symbol \(\dagger \in L\)and every \(n\)-ary connective \(* \in L\)

\(h(\dagger^{\bA }) = \dagger^{\bB}\)
\(h(* ^{\bA }(a_1 ,\ldots ,a_n)) = * ^{\bB }(h(b_1),\ldots,h(b_n))\), for all \(a_1 , \ldots ,a_n \in A\).

We say that \(\bB\) is ahomomorphic image of \(\bA\) ifthere is a homomorphism from \(\bA\) to \(\bB\) which is an onto mapfrom \(A\) to \(B\). An homomorphismfrom \(\bA\) to \(\bB\) is anisomorphism if it is aone-to-one and onto map from \(A\) to \(B\).If an isomorphism from \(\bA\) to \(\bB\) exists, wesay that \(\bA\) and \(\bB\) areisomorphic and that \(\bB\)is anisomorphic image (or a copy) of \(\bA\).

Let \(\bA\) and \(\bB\) be \(L\)-algebras. \(\bA\) is asubalgebra of \(\bB\) if (1) \(A \subseteq B\), (2) theinterpretations of the 0-ary symbols of \(L\) in\(\bB\) belong to \(A\) and \(A\) isclosed under the functions of \(\bB\) that interpret the non 0-arysymbols, and (3) the interpretations of the 0-ary symbols in \(\bA\)coincide with their interpretations in \(\bB\) and the interpretationson \(\bA\) of the other symbols in \(L\) are therestrictions to \(\bA\) of their interpretations in \(\bB\).

We refer the reader to the entry onfirst-order model theory for the notions of direct product (called product there) andultraproduct.

4.2 Varieties and quasivarieties

The majority of classes of algebras that provide semantics forpropositional logics are quasivarieties and in most cases varieties.The theory of varieties and quasivarieties is one of the main subjectsof universal algebra.

An equational class of \(L\)-algebras is a class of \(L\)-algebrasthat is definable in a very simple way (byequations) using the \(L\)-algebraic language. An \(L\)-equationis a formula \(\phi \approx \psi\)where \(\phi\) and \(\psi\) are terms of the \(L\)-algebraiclanguage (that is, \(L\)-formulasif we take the propositional logic's point ofview) and '\(\approx\)' is the formal symbol for the equality (always to be interpreted as the identity relation). An equation \(\phi \approx \psi\) isvalid in analgebra \(\bA\), or \(\bA\) is amodel of \(\phi \approx\psi\), if for every valuation \(v\) on \(\bA,\bv(\phi) = \bv(\psi)\). This is exactly the same as to saying thatthe universal closure of \(\phi \approx \psi\) is a sentence true in\(\bA\) according to the usual semantics for first-order logic withequality. Anequational class of \(L\)-algebras is aclass of \(L\)-algebras which is the class of all themodels of a given set of \(L\)-equations.

A quasi-equational class of \(L\)-algebras is a class of \(L\)-algebras definable using the \(L\)-algebraic language in a slightly more complex way than in equational.classes. Aproper \(L\)-quasiequation is a formula of the form \[\bigwedge_{i \le n} \phi_i \approx \psi_i \rightarrow \phi \approx \psi.\] An \(L\)-quasiequation is a formula of the above form but possibly with an empty antecedent, in which case it is just the equation \(\phi \approx \psi\). Hence, the \(L\)-quasiequations are the proper \(L\)-quasiequations and the \(L\)-equations. An \(L\)-quasiequation isvalid in an \(L\)-algebra \(\bA\), or the algebra is a model of it, if the universal closure of the quasiequation is sentence true in \(\bA\). Aquasi-equational class of \(L\)-algebras is a class of algebras that is the class of the models of a given set of \(L\)-quasiequations. Since equations are quasiequations, every equational class is quasi-equational. The converse is false. Moreover, since in the trivial algebras all the equations and all the quasiequations of the appropriate algebraic language are valid, equational and quasi-equational classes are nonempty.

Equational and quasi-equational classes of algebras can be characterized by the closureproperties they enjoy. A nonempty class of \(L\)-algebrasis avariety if it is closedunder subalgebras, direct products, and homomorphic images. It is aquasivariety if it is closed under subalgebras, direct products, ultraproducts,isomorphic images, and contains a trivial algebra. It is easily seen that equational classes are varieties and that quasi-equational classes are quasiviarities. Birkhoff's theorem states that all varieties are equational classes and Malcev's theorem that all quasivarieties are quasi-equational classes.

Thevariety generated by a nonempty class \(\bK\) of \(L\)-algebrasis the least class of \(L\)-algebrasthat includes \(\bK\) and is closed undersubalgebras, direct products and homomorphic images. It is also theclass of the algebras that are models of the equations valid in\(\bK\). For example, the variety generated by the algebra of the twotruth-values for classical logic is the class of Boolean algebras. Ifwe restrict that algebra to the operations for conjunction anddisjunction only, it generates the variety of distributive latticesand if we restrict it to the operations for conjunction anddisjunction and the interpretations of \(\top\) and \(\bot\), itgenerates the variety of bounded distributive lattices.

The quasivarietygenerated by a class \(\bK\) of \(L\)-algebras is theleast class of \(L\)-algebras that includes \(\bK\),the trivial algebras and is closed under subalgebras, direct products,ultraproducts, and isomorphic images.

An SP-class of \(L\)-algebras is a class of\(L\)-algebras that contains a trivial algebra and isclosed under isomorphic images, subalgebras, and direct products. Thusquasivarieties and varieties are all SP-classes. The SP-classgenerated by a class \(\bK\) of \(L\)-algebras is theleast class of \(L\)-algebras that includes \(\bK\),the trivial algebras and is closed under subalgebras, direct productsand isomorphic images.

5. Algebraic semantics

The term ‘algebraic semantics’ was (and many times stillis) used in the literature in a loose way. To provide a logic with analgebraic semantics was to interpret its language in a class ofalgebras, define a notion of satisfaction of a formula (under avaluation) in an algebra of the class and prove a soundness andcompleteness theorem, usually for the theorems of the logic only.Nowadays there is a precise concept of algebraic semantics for a logicsystem. It was introduced by Blok and Pigozzi in Blok & Pigozzi1989. In this concept we find a general way to state in mathematicallyprecise terms what is common to the many cases of purported algebraicsemantics for specific logic systems found in the literature. Weexpose the notion in this section. To motivate the definition wediscuss several examples first, stressing the relevant properties thatthey share. The reader does not need to know about the classes ofalgebras that provide algebraic semantics we refer to in the examples.Its existence is what is important.

The prototypical examples of algebraic semantics for propositionallogics are the classBA ofBoolean algebras, which is the algebraic semantics for classical logic, and the classHA of Heyting algebras, which is the algebraicsemantics forintuitionistic logic. Every Boolean algebra and every Heyting algebra \(\bA\) has agreatest element according to their natural order; this element isdenoted usually by \(1^{\bA}\) and interprets the propositionalconstant symbol \(\top\). It is taken as the distinguished elementrelative to which the algebraic semantics is given. The algebraicsemantics of these two logics works as follows:

Let \(\bL\) be classical or intuitionistic logic and let \(\bK(\bL)\)be the corresponding class of algebrasBA orHA. It holds that

\(\Gamma \vdash_{\bL } \phi \txtiff\) for every \(\bA \in \bK(\bL)\)and every valuation \(v\) on \(\bA\), if \(\bv(\psi) =1^{\bA}\) for all \(\psi \in \Gamma \), then \(\bv(\phi) =1^{\bA}\).

This is the precise content of the statement thatBAandHA are an algebraic semantics for classical logicand for intuitionistic logic, respectively. The implication from leftto right in the expression above is an algebraic soundness theorem andthe implication from right to left an algebraic completenesstheorem.

There are logics for which an algebraic semantics is provided in theliterature in a slightly different way from the one given by theschema above. Let us consider the example inSection 3.5 of Intuitionistic Linear Logic without exponentials. We denote by\(\bILsubZ\) the class of IL-algebras with zero defined in Troelstra1992 (but adapted to the language of \(\bILL)\). Each \(\bA \in\bILsubZ\) is a lattice with extra operations and thus has its latticeorder \(\le^{\bA}\). This lattice order has a greatest element whichwe take as the interpretation of \(\top\). On each one of thesealgebras \(\bA\) there is a designated element \(1^{\bA}\) (theinterpretation of the constant 1) that may be different from thegreatest element. It holds:

\(\Gamma \vdash_{\bILL } \phi \txtiff\) for every \(\bA \in \bILsubZ\)and every valuation \(v\) on \(\bA\), if \(1^{\bA }\le^{\bA } \bv(\psi)\) for all \(\psi \in \Gamma \), then \(1^{\bA }\le^{\bA } \bv(\phi)\).

In this case one does not consider only a designated element in everyalgebra \(\bA\) but a set of designated elements, namely the elementsof \(\bA\) greater than or equal to \(1^{\bA}\), to provide thedefinition. Let us denote this set by \(\tD (\bA)\), and notice that\(\tD (\bA) = \{a \in A: 1^{\bA } \wedge^{\bA} a = 1^{\bA }\}\).Hence,

\(\Gamma \vdash_{\bILL } \phi \txtiff\) for every \(\bA \in \bILsubZ\)if \(\bv[\Gamma] \subseteq \tD (\bA)\), then \(\bv(\phi) \in \tD(\bA)\).

Still there are even more complex situations. One of them is the system \(\bR\) of relevance logic. Consider the class of algebras \(\bRal\) defined in Font & Rodríguez 1990 (see also Font & Rodríguez 1994) and denoted there by ‘\(\bR\)’. Let us consider for every \(\bA \in \bRal\) the set \[\tE(\bA) := \{a \in A: a \wedge^{\bA }(a \rightarrow^{\bA } a) = a \rightarrow^{\bA } a\}.\] Then \(\bRal\) is said to be an algebraic semantics for \(\bR\) because the following holds:

\(\Gamma \vdash_{\bR } \phi\txtiff\) for every \(\bA \in \bRal\) andevery valuation \(v\) on \(\bA\), if \(\bv[\Gamma]\subseteq \tE (\bA)\), then \(\bv(\phi) \in \tE (\bA)\).

The common pattern in the examples above is that the algebraicsemantics is given by

a class of algebras \(\bK\),
in each algebra in \(\bK\) a set of designated elements that playsthe role \(1^{\bA}\) (more precisely the set \(\{1^{\bA }\})\) playsin the cases of classical and intuitionistic logic, and
this set of designated elements is definable (in the same manneron every algebra) by an equation in the sense that it is the set ofelements of the algebra that satisfy the equation (i.e., itssolutions). ForBA andHA theequation is \(p \approx \top\). For \(\bRal\) it is \(p \rightarrow(p\wedge p) \approx p \rightarrow p\), and for \(\bILsubZ\) it is \(1\wedge p \approx 1\).

The main point in Blok and Pigozzi’s concept of algebraicsemantics comes from the realization, mentioned in (3) above, that theset of designated elements considered in the algebraic semantics ofknown logics is in fact the set of solutions of an equation, and thatwhat practice forced researchers to look for when they tried to obtainalgebraic semantics for new logics was in fact, although notexplicitly formulated in these terms, an equational way to defineuniformly in every algebra a set of designated elements in order toobtain an algebraic soundness and completeness theorem.

We are now in a position to expose the mathematically precise conceptof algebraic semantics. To develop a fruitful and general theory ofthe algebraization of logics some generalizations beyond thewell-known concrete examples have to be made. In the definition ofalgebraic semantics, one takes the move from a single equation to aset of them in the definability condition for the set of designatedelements.

Before stating Blok and Pigozzi’s definition we need tointroduce a notational convention. Given an algebra \(\bA\) and a setof equations \(\iEq\) in one variable, we denote by \(\tEq(\bA)\) theset of elements of \(\bA\) that satisfy all the equations in \(\iEq\).Then a logic \(\bL\) is said to have analgebraic semanticsif there is a class of algebras \(\bK\) and a set of equations\(\iEq\) in one variable such that

(**): \( \Gamma \vdash_{\bL } \phi \txtiff\) for every \(\bA \in \bK\)and every valuation \(v\) on \(\bA\), if \(\bv[\Gamma] \subseteq\iEq(\bA)\), then \(\bv(\phi) \in \tEq(\bA)\).

In this situation we say that the class of algebras \(\bK\) is an\(\iEq\)-algebraic semantics for \(\bL\), or that the pair\((\bK, \iEq)\) is analgebraic semantics for \(\bL\). If\(\iEq\) consists of a single equation \(\delta(p) \approx\varepsilon(p)\) we will simply say that \(\bK\) is a \(\delta(p)\approx \varepsilon(p)\)-algebraic semantics for \(\bL\). In fact,Blok and Pigozzi required that \(\iEq\) should be finite in theirdefinition of algebraic semantics. But it is better to be moregeneral. The definition clearly encompasses the situations encounteredin the examples.

If \(\bK\) is an \(\iEq\)-algebraic semantics for a finitary logic\(\bL\) and \(\iEq\) is finite, then the quasivariety generated by\(\bK\) is also an \(\iEq\)-algebraic semantics. The same does nothold in general if we consider the generated variety. For this reason,it is customary and useful when developing the theory of thealgebraization of finitary logics to consider quasivarieties ofalgebras as algebraic semantics instead of arbitrary subclasses thatgenerate them. Conversely, if a quasivariety is an \(\iEq\)-algebraicsemantics for a finitary \(\bL\) and \(\iEq\) is finite, then so isany subclass of the quasivariety that generates it.

In the best-behaved cases, the typical algebraic semantics of a logicis a variety, for instance in all the examples discussed above. Butthere are cases in which it is not (see Blok & Pigozzi 1989).

A quasivariety can be an \(\iEq\)-algebraic semantics for a logic andan \(\iEq'\)-algebraic semantics for another logic (with \(\iEq\) and\(\iEq'\) different). For example, due to Glivenko’s theorem(see the entry onintuitionistic logic) the class of Heyting algebras is a \(\{\neg \neg p \approx1\}\)-algebraic semantics for classical logic and it is the standard\(\{p \approx 1\}\)-algebraic semantics for intuitionistic logic.Moreover, different quasivarieties of algebras can be an\(\iEq\)-algebraic semantics for the same logic. It is known thatthere is a quasivariety that properly includes the variety of Booleanalgebras that is also a \(\{p \approx 1\}\)-algebraic semantics forclassical propositional logic. It is also known that for some logicswith an algebraic semantics (relative to some set of equations), thenatural class of algebras that corresponds to the logic is not analgebraic semantics (for any set of equations) of it. One examplewhere this situation holds is in the local normal modal logic\(\blK\). Finally, there are logics that do not have any algebraicsemantics.

These facts highlight the need for some criteria of the goodness of apair \((\bK, \iEq)\) to provide a natural algebraic semantics for alogic \(\bL\) when some exists. One such criterion would be that\(\bL\) is an algebraizable logic with \((\bK, \iEq)\) as an algebraicsemantics. Another that \(\bK\) is the natural class of algebrasassociated with the logic \(\bL\). The notion of the natural class ofalgebras of a logic system will be discussed inSection 8 and the concept of algebraizable logic inSection 9.

The interested reader can examine Blok & Rebagliato 2003 for astudy devoted to algebraic semantics of logics and Moraschiniforthcoming for the most recent results on the topic (in this paperthere is a proof of the fact that the natural class of algebras of thelocal normal modal logic \(\blK\), namely the class of modal algebras,is not an algebraic semantics (for any set of equations) for it).

There is a particular, and important, kind of logics with an algebraicsemantics that includes classical and intuitionistic logics. It is theclass of the so-called assertional logics.

Let \(\bK\) be a class of algebras in an algebraic language with aconstant term for \(\bK\), i.e., a formula \(\phi(p_1 , \ldots ,p_n)\)such that for every algebra \(\bA\in \bK\) and elements \(a_1 , \ldots,a_n, b_1, \ldots, b_n\) of \(\bA\), \(\phi^{\bA }[a_1 , \ldots ,a_n] =\phi^{\bA }[b_1 , \ldots ,b_n]\), that is, in every algebra in\(\bK\), \(\phi\) takes the same value whatever is the way weinterpret the variable in \(\phi\) on \(\bA\). We denote this value by\(\phi^{\bA}\). Thus \(\phi\) acts as a constant (relative to thealgebras in \(\bK\)) and \(\phi^{\bA}\) (for \(\bA\in \bK\)) can betaken as a designated element.

Given a class of algebras \(\bK\) in an algebraic language with aconstant term \(\phi\) for \(\bK\), theassertional logic\(\bL_{\bK}^{\phi}\)of (\(\bK, \phi\)) is defined by

\(\Gamma \vdash_{\bL_{\bK}^{\phi} } \phi \txtiff\) for every \(\bA \in\bK(\bL)\) and every valuation v on \(\bA\), if \(\bv(\psi) =\phi^{\bA}\) for all \(\psi \in \Gamma \), then \(\bv(\phi) =\phi^{\bA}\).

A logic system \(\bL\) isassertional when there exists aclass of algebras \(\bK\) in the algebraic language of \(\bL\) and aconstant term \(\phi\) for \(\bK\) such that \(\bL\) =\(\bL_{\bK}^{\phi}\).

The most recent study of assertional logics is Albuquerque et al. 2018.We address the reader to this paper where the classification of theassertional logics in the Leibniz and Frege hierarchies of logicsystems that we present in later sections is addressed and severalexamples are discussed.

6. Logical matrices

In the last section, we saw that to provide a logic with an algebraicsemantics we need in many cases to consider in every algebra a set ofdesignated elements instead of a single designated one. In theexamples we discussed, the set of designated elements was definable inthe algebras by one equation. This motivated the definition ofalgebraic semantics inSection 5. For many logics, to obtain a semantics similar to an algebraicsemantics using the class of algebras naturally associated with themone needs for every algebra a set of designated elements that cannotbe defined using only the equations of the algebraic language or isnot even definable by using this language only. As we alreadymentioned, one example where this happens is the local consequence ofthe normal modal logic \(K\). Also, recall that there are logics with no algebraic semantics at all.

To endowevery logic with a semantics of an algebraic kindone has to consider, at least, algebras together with a set ofdesignated elements, without any requirement about its definabilityusing the corresponding algebraic language. These pairs are thelogical matrices. Tarski defined the general concept of logical matrixin the 1920s but the concept was already implicit in previous work byŁukasiewicz, Bernays, Post and others, who used truth-tables,either in independence proofs or to define logics different fromclassical logic. Alogical matrix is a pair \(\langle \bA, D\rangle\) where \(\bA\) is an algebra and \(D\) asubset of the universe \(A\) of \(\bA\); the elementsof \(D\) are called thedesignated elements ofthe matrix and accordingly \(D\) is calledthe setof designated elements (and some authors call it thetruthset of the matrix). Logical matrices were first used as models ofthe theorems of specific logic systems, for instance in the work ofMcKinsey and Tarski, and also to define sets of formulas with similarproperties to those of the set of theorems of a logic system, namelyclosure under substitution instances. This was the case of the \(n\)-valuedlogics of Łukasiewicz and of hisinfinite-valued logic. And it was Tarski who first considered logicalmatrices as a general tool to define this kind of sets.

The general theory of logical matrices explained in this entry is duemainly to Polish logicians, starting with Łoś 1949 andcontinuing in Łoś & Suszko 1958, building on previouswork by Lindenbaum. In Łoś and Suszko’s paper matricesare used for the first time both as models of logic systems (in oursense) and to define systems of these kind.

In the rest of the section, we present the relevant concepts of thetheory of logical matrices using modern terminology.

Given a logic \(\bL\), a logical matrix \(\langle \bA, D \rangle\) issaid to be amodel of \(\bL\) if wherever \(\Gamma\vdash_{\bL } \phi\), then every valuation \(v\) on\(\bA\) that maps the elements of \(\Gamma\) to some designated value(i.e., an element of \(D)\) also maps \(\phi\) to a designated value.When \(\langle \bA, D \rangle\) is a model of \(\bL\) it is said that\(D\) is an \(\bL\)-filter of the algebra\(\bA\). The set of \(\bL\)-filters of an algebra \(\bA\) plays acrucial role in the theory of the algebraization of logic systems. Wewill come to this point later.

A class \(\bM\) of logical matrices is said to be amatrixsemantics for a logic \(\bL\) if

(*): \( \Gamma \vdash_{\bL } \phi\txtiff\) for every \(\langle \bA, \tD\rangle \in \bM\) and every valuation \(v\) on \(\bA\), if\(\bv[\Gamma] \subseteq D\), then \(\bv(\phi) \in D\).

The implication from left to right says that \(\bL\) is sound relativeto \(\bM\), and the other implication says that it is complete. Inother words, \(\bM\) is a matrix semantics for \(\bL\) if and only ifevery matrix in \(\bM\) is a model of \(\bL\) and moreover for every\(\Gamma\) and \(\phi\) such that \(\Gamma \not\vdash_{\bL } \phi\)there is a model \(\langle \bA, \tD \rangle\) of \(\bL\) in \(\bM\)that witnesses the fact, namely there is a valuation on the model thatsends the formulas in \(\Gamma\) to designated elements and \(\phi\)to a non-designated one.

Logical matrices are also used to define logics semantically. If \(\cM= \langle \bA, D \rangle\) is a logical matrix, the relation definedby

\(\Gamma \vdash_{\cM } \phi\txtiff\) for every valuation \(v\)on \(\bA\) if \(\bv(\psi) \in D\) for all \(\psi \in\Gamma\), then \(\bv(\phi) \in D\)

is a consequence relation which is substitution-invariant; therefore\(\langle L, \vdash_{\cM } \rangle\) is a logic system. Similarly, wecan define the logic of a class of matrices \(\bM\) by takingcondition (*) as a definition of a consequence relation. In the entryonmany-valued logic the reader can find several logics defined in this way.

Every logic (independently of how it is defined) has a matrix semantics. Moreover, every logic has a matrix semantics whose elements have the property of being reduced in the following sense: A matrix \(\langle \bA, D \rangle\) isreduced if there are no two different elements of \(A\) that behave in the same way. We say that \(a, b \in A\)behave in the same way in \(\langle \bA, D \rangle\) if for every formula \(\phi (q, p_1 , \ldots ,p_n)\) and all elements \(d_1 , \ldots ,d_n \in A\) \[\phi^{\bA }[a, d_1 , \ldots ,d_n] \in D \txtiff \phi^{\bA }[b, d_1 , \ldots ,d_n] \in D.\] Thus \(a, b \in A\) behave differently if there is a formula \(\phi(q, p_1 , \ldots ,p_n)\) and elements \(d_1 , \ldots ,d_n \in A\) such that one of \(\phi^{\bA }[a, d_1 , \ldots ,d_n]\) and \(\phi^{\bA }[b, d_1 , \ldots ,d_n]\) belongs to \(D\) but not both. The relation of behaving in the same way in \(\langle \bA, D \rangle\) is a congruence relation of \(\bA\). This relation is known after Blok & Pigozzi 1986, 1989 as theLeibniz congruence of the matrix \(\langle \bA, D \rangle\) and is denoted by \(\bOmega_{\bA }(D)\). It can be characterized as the greatest congruence relation of \(\bA\) that iscompatible with \(D\), that is, that does not relate elements in \(D\) with elements not in \(D\). The concept of Leibniz congruence plays a fundamental role in the general theory of the algebraization of the logic systems developed during the 1980s by Blok and Pigozzi. The reader is referred to Font, Jansana, & Pigozzi 2003 and Czelakowski 2001 for extensive information on the developments around the concept of Leibniz congruence during this period.

Every matrix \(\cM\) can be turned into a reduced matrix byidentifying the elements related by its Leibniz congruence. Thismatrix is called thereduction of \(\cM\) and is usuallydenoted by \(\cM^*\). A matrix and its reduction are models of thesame logic systems, and since reduced matrices have no redundantelements, the classes of reduced matrices that are matrix semanticsfor logic systems are usually taken as the classes of matrices thatdeserve study; they are better suited to encoding in algebraic-liketerms the properties of the logics that have them as their matrixsemantics.

The proof that every logic system has a reduced matrix semantics(i.e., a matrix semantics consisting of reduced matrices) is asfollows. Let \(\bL\) be a logic system. Consider the matrices\(\langle \bFm_L, T \rangle\) over the formula algebra, where \(T\)is a theory of \(\bL\). These matrices are known astheLindenbaum matrices of \(\bL\). It is not difficult tosee that the class of those matrices is a matrix semantics for\(\bL\). Since a matrix and its reduction are models of the samelogics, the reductions of the Lindenbaum matrices of \(\bL\)constitute a matrix semantics for \(\bL\) too, and indeed a reducedone. Moreover, any class of reduced matrix models of \(\bL\) thatincludes the reduced Lindenbaum matrices of \(\bL\) is automatically acomplete matrix semantics for \(\bL\). In particular, the class of allreduced matrix models of \(\bL\) is a complete matrix semantics for\(\bL\). We denote this class by \(\bRMatr(\bL)\).

The above proof can be seen as a generalization of theLindenbaum-Tarski method for proving algebraic completeness theoremsthat we will discuss in the next section.

The class of the algebras of the matrices in \(\bRMatr(\bL)\) plays aprominent role in the theory of the algebraization of logics and it isdenoted by \(\bAlg^*\bL\). It has been considered for a long time thenatural class of algebras that has to be associated with a given logic\(\bL\) as its algebraic counterpart. For instance, in the examplesconsidered above the classes of algebras that were given as algebraicsemantics of the different logics (Boolean algebras, Heyting algebras,etc.) are exactly the class \(\bAlg^*\bL\) of the corresponding logic\(\bL\). And in fact, the class \(\bAlg^*\bL\) coincides with what wastaken to be the natural class of algebras for all the logics \(\bL\)studied up to the 1990s. In the 1990s, due to the knowledge acquiredof several logics not studied before, some authors proposed anotherway to define the class of algebras that has to be counted as thealgebraic counterpart to be associated with a given logic \(\bL\). Formany logics \(\bL\), it leads exactly to the class \(\bAlg^*\bL\) butfor others it gives a class that extends it properly. We will discussit inSection 8.

7. The Lindenbaum-Tarski method for proving algebraic completeness theorems

We now discuss the method that is most commonly used to prove that aclass of algebras \(\bK\) is a \(\delta(p) \approx\varepsilon(p)\)-algebraic semantics for a logic \(\bL\), namely theLindenbaum-Tarski method. It is the standard method used to prove thatthe classes of algebras of the examples mentioned inSection 5 are algebraic semantics for the corresponding logics.

The Lindenbaum-Tarski method contributed in two respects to theelaboration of important notions in the theory of the algebraizationof logics. It underlies Blok and Pigozzi’s notion ofalgebraizable logic and reflecting on it some ways to define for eachlogic a class of algebras can be justified as providing a naturalclass. We will consider this issue inSection 8.

The Lindenbaum-Tarski method can be outlined as follows. To prove thata class of algebras \(\bK\) is a \(\delta(p) \approx\varepsilon(p)\)-algebraic semantics for a logic \(\bL\) first it isshown that \(\bK\) gives a sound \(\delta(p) \approx\varepsilon(p)\)-semantics for \(\bL\), namely that if \(\Gamma\vdash_{\bL } \phi\), then for every \(\bA \in \bK\) and everyvaluation \(v\) in \(\bA\) if the values of theformulas in \(\Gamma\) satisfy \(\delta(p) \approx \varepsilon(p)\),then the value of \(\phi\) does too. Secondly, the other direction,that is, the completeness part, is proved by what is properly known asthe Lindenbaum-Tarski method. This method uses the theories of \(\bL\)to obtain matrices on the algebra of formulas and then reduces thesematrices in order to get for each one a matrix whose algebra is in\(\bK\) and whose set of designated elements is the set of elements ofthe algebra that satisfy \(\delta(p) \approx \varepsilon(p)\). Weproceed to describe the method step by step.

Let \(\bL\) be one of the logics discussed in the examples inSection 5. Let \(\bK\) be the corresponding class of algebras we consideredthere and let \(\delta(p) \approx \varepsilon(p)\) be the equation inone variable involved in the soundness and completeness theorem. Toprove the completeness theorem one proceeds as follows. Given any setof formulas \(\Gamma\):

The theory \(C_{\bL }(\Gamma) = \{\phi : \Gamma \vdash_{\bL } \phi \}\) of \(\Gamma\), which we denote by \(T\), is considered and the binary relation \(\theta(T)\) on the set of formulas is defined using the formula \(p \leftrightarrow q\) as follows: \[\langle \phi , \psi \rangle \in \theta(T) \txtiff \phi \leftrightarrow \psi \in T.\]
It is shown that \(\theta(T)\) is a congruence relationon \(\bFm_L\). The set \([\phi]\) of the formulas related to theformula \(\phi\) by \(\theta(T)\) is called the equivalence class of\(\phi\).
A new matrix \(\langle \bFm/\theta(T), T/\theta(T) \rangle\) is obtained by identifying the formulas related by \(\theta(T)\), that is, \(\bFm/\theta(T)\) is the quotient algebra of \(\bFm\) modulo \(\theta(T)\) and \(T/\theta(T)\) is the set of equivalence classes of the elements of \(T\). Recall that the algebraic operations of the quotient algebra are defined by: \[* ^{\bFm/\theta(T) }([\phi_1],\ldots ,[\phi_n]) = [* \phi_1 \ldots \phi_n ] \;\;\; \text{and} \;\;\; \dagger^{\bFm/\theta(T) } = [\dagger]\]
It is shown that \(\theta(T)\) is a relation compatible with \(T\), i.e., that if \(\langle \phi , \psi \rangle \in \theta(T)\) and \(\phi \in T\), then \(\psi \in T\). This implies that \[\phi \in T \txtiff [\phi] \subseteq T \txtiff [\phi] \in T/\theta(T).\]
It is proved that the matrix \(\langle \bFm/\theta(T),T/\theta(T) \rangle\) is reduced, that \(\bFm/\theta(T)\) belongs to\(\bK\) and that \(T/\theta(T)\) is the set of elements of\(\bFm/\theta(T)\) that satisfy the equation \(\delta(p) \approx\varepsilon(p)\) in \(\bFm/\theta(T)\).

The proof of the completeness theorem then proceeds as follows.(4) and(5) imply that for every formula \(\psi , \Gamma \vdash_{\bL } \psi\) ifand only if \([\psi]\) satisfies the equation \(\delta(p) \approx\varepsilon(p)\) in the algebra \(\bFm/\theta(T)\). Thus, consideringthe valuation \(id\) mapping every variable \(p\) toits equivalence class \([p]\), whose extension \(\boldsymbol{id}\) tothe set of all formulas is such that \(\boldsymbol{id}(\phi) =[\phi]\) for every formula \(\phi\), we have for every formula\(\psi\),

\(\Gamma \vdash_{\bL } \psi \txtiff\boldsymbol{id}(\psi)\) satisfiesthe equation \(\delta(p) \approx \varepsilon(p)\) in\(\bFm/\theta(T)\).

Hence, since by(5), \(\bFm/\theta(T) \in \bK\), it follows that if \(\Gamma\not\vdash_{\bL }\phi\), then there is an algebra \(\bA \in \bK\)(namely \(\bFm/\theta(T))\) and a valuation \(v\)(namely \(id)\) such that the elements of \(\bv[\Gamma]\) satisfy theequation on \(\bA\) but \(\bv(\phi)\) does not.

The Lindenbaum-Tarski method, when successful, shows that the class ofalgebras \(\{\bFm/\theta(T): T\) is a theory of \(\bL\}\) is a\(\delta(p) \approx \varepsilon(p)\)-algebraic semantics for \(\bL\).Therefore it also shows that every class of algebras \(\bK\) which is\(\delta(p) \approx \varepsilon(p)\)-sound for \(\bL\) and includesthe set \(\{\bFm/\theta(T): T\) is a theory of \(\bL\}\) is also a\(\delta(p) \approx \varepsilon(p)\)-algebraic semantics for\(\bL\).

Let us make some remarks on the Lindenbaum-Tarski method justdescribed. The first is important for the generalizations leading tothe classes of algebras associated with a logic. The others, to obtainthe conditions in the definition of the concept of algebraizablelogic.

Conditions(4) and(5) imply that \(\theta(T)\) is in fact the Leibniz congruence of\(\langle \bFm_L, T \rangle\).
When the Lindenbaum-Tarski method succeeds, it usually holds that in every algebra \(\bA \in \bK\), the relation defined by the equation \[\delta(p \leftrightarrow q) \approx \varepsilon(p \leftrightarrow q),\] which is the result of replacing in \(\delta(p) \approx \varepsilon(p)\) the letter \(p\) by the formula \(p \leftrightarrow q\) that defines the congruence relation of a theory, is the identity relation on \(A\).
For every formula \(\phi\), the formulas \(\delta(p/\phi)\leftrightarrow \varepsilon(p/\phi)\) and \(\phi\) are interderivablein \(\bL\) (i.e., \(\phi \vdash_{\bL } \delta(p/\phi) \leftrightarrow\varepsilon(p/\phi)\) and \(\delta(p/\phi) \leftrightarrow\varepsilon(p/\phi) \vdash_{\bL } \phi)\).

The concept of algebraizable logic introduced by Blok and Pigozzi,which we will discuss inSection 9, can be described roughly by saying that a logic \(\bL\) isalgebraizable if it has an algebraic semantics \((\bK, \iEq)\) suchthat (1) \(\bK\) is included in the natural class of algebras\(\bAlg^*\bL\) associated with \(\bL\) and (2) the fact that \((\bK,\iEq)\) is an algebraic semantics can be proved by using theLindenbaum-Tarski method slightly generalized.

8. The natural class of algebras of a logic system

We shall now discuss the two definitions that have been considered asproviding natural classes of algebras associated with a logic \(\bL\).Both definitions can be seen as arising from an abstraction of theLindenbaum-Tarski method and we follow this path in introducing them.The common feature of these abstractions is that in them the specificway in which the relation \(\theta(T)\) is defined in theLindenbaum-Tarski method is disregarded.

It has to be remarked that, nonetheless, for many logics bothdefinitions lead to the same class. The classes obtained from bothdefinitions have been taken in the algebraic studies of manyparticular logics (for some logics one, for others the other) as thenatural class that deserves to be studied.

We already encountered the first generalization inSection 6 when we showed that every logic has a reduced matrix semantics. Itleads to the class of algebras \(\bAlg^*\bL\). That its definition isa generalization of the Lindenbaum-Tarski method comes from therealization that the relation \(\theta(T)\), associated with an\(\bL\)-theory, defined in the different completeness proofs in theliterature that use the Lindenbaum-Tarski method is in fact theLeibniz congruence of the matrix \(\langle \bFm_L, T \rangle\) andthat therefore the matrix \(\langle \bFm/\theta(T), T/\theta(T)\rangle\) is its reduction. As we mentioned inSection 6, for every logic \(\bL\), every \(\bL\)-sound class of matrices\(\bM\) that contains all the matrices \(\langle \bFm/\bOmega_{\bFm_L}(T), T/ \bOmega_{\bFm_L }(T) \rangle\), where \(T\) isa theory of \(\bL\), is a complete reduced matrix semantics for\(\bL\). From this perspective the notion of the Leibniz congruence ofa matrix can be taken as a generalization to arbitrary matrices of theidea that comes from the Lindenbaum-Tarski procedure of provingcompleteness. Following this course of reasoning, the class\(\bAlg^*\bL\) of the algebras of the reduced matrix models of a logic\(\bL\) is a very natural class of algebras to associate with \(\bL\).It is the class

\(\{\bA/\bOmega_{\bA }(F): \bA\) is an \(\bL\)-algebra and \(F\)is a \(\bL\)-filter of \(\bA\}\).

The second way of generalizing the Lindenbaum-Tarski method uses adifferent fact, namely that in the examples discussed inSection 3 the relation \(\theta(T)\) is also the relation\(\bOmega^{\sim}_{\bFm_L }(T)\) defined by the condition

\[\begin{align*} \langle \phi , \psi \rangle \in \bOmega^{\sim}_{\bFm_L }(T)\txtiff & \forall T' \in \tTH(\bL),\\ & \forall p \in V, \\ &\forall \gamma(p) \in \bFm_L (T \subseteq T' \Rightarrow (\gamma(p/\phi) \in T' \Leftrightarrow \gamma(p/\psi) \in T')). \end{align*}\]

For every logic \(\bL\) and every \(\bL\)-theory \(T\) the relation \(\bOmega^{\sim}_{\bFm_L }(T)\) defined in this way is the greatest congruence compatible with all the \(\bL\)-theories that extend \(T\). Therefore, it holds that \[\bOmega^{\sim}_{\bFm_L }(T) = \bigcap_{T' \in \tTH(\bL)^T} \bOmega_{\bFm_L }(T'),\] where \(\tTH(\bL)^T = \{T' \in \tTH(\bL): T \subseteq T'\}\). The relation \(\bOmega^{\sim}_{\bFm_L }(T)\) is known as theSuszko congruence of \(T\) (w.r.t. \(\bL)\). Suszko defined it —in an equivalent way— in 1977.

For every logic \(\bL\), the notion of the Suszko congruence can be extended to its matrix models. TheSuszko congruence of a matrix model \(\langle \bA, D \rangle\) of \(\bL\) (w.r.t. \(\bL)\) is the greatest congruence of \(\bA\) compatible with every \(\bL\)-filter of \(\bA\) that includes \(D\), that is, it is the relation given by \[{\bOmega^{\sim}_{\bA}}^{\bL}(D) = \bigcap_{D' \in \tFi_{\bL}(\bA)^D} \bOmega_{\bA}(D')\] where \(\tFi_{\bL}(\bA)^D = \{D': D'\) is a \(\bL\)-filter of \(\bA\) and \(D \subseteq D'\}\). Notice that unlike the intrinsic notion of Leibniz congruence, the Suszko congruence of a matrix model of \(\bL\) is not intrinsic to the matrix: it depends in an essential way on the logic under consideration. The theory of the Suszko congruence of matrices has been developed in Czelakowski 2003 and continued in Albuquerque & Font & Jansana 2016.

In the same manner that the concept of Leibniz congruence leads to theconcept of reduced matrix, the notion of Suszko congruence leads tothe notion of Suszko-reduced matrix. A matrix model of \(\bL\) isSuszko-reduced if its Suszko congruence is the identity. Thenthe class of algebras of the Suszko-reduced matrix models of a logic\(\bL\) is another class of algebras that is taken as a natural classof algebras to associate with \(\bL\). It is the class

\(\bAlg\bL = \{\bA / {\bOmega^{\sim}_{\bA}}^{\bL}(F): \bA\) is an\(\bL\)-algebra and \(F\) is a \(\bL\)-filter of\(\bA\}\).

This class is nowadays taken in abstract algebraic logic asthe natural class of algebras to be associated with \(\bL\)and it called itsalgebraic counterpart.

For an arbitrary logic \(\bL\), the relation between the classes\(\bAlg\bL\) and \(\bAlg^*\bL\) is that \(\bAlg\bL\) is the closure of\(\bAlg^*\bL\) under subdirect products, in particular \(\bAlg^*\bL\subseteq \bAlg\bL\). In general, the two classes may be different. Forexample, if \(\bL\) is the \((\wedge , \vee)\)-fragment of classicalpropositional logic, \(\bAlg\bL\) is the variety of distributivelattices (the class that has been always taken to be the natural classof algebras associated with \(\bL)\) while \(\bAlg^*\bL\) is properlyincluded in it —in fact \(\bAlg^*\bL\) is not a quasivariety.Nonetheless, for many logics \(\bL\), in particular for thealgebraizable and the protoalgebraic ones to be discussed in the nextsections, and also when \(\bAlg^*\bL\) is a variety, the classes\(\bAlg\bL\) and \(\bAlg^*\bL\) are equal. This fact can explain whyin the 1980s, before the algebraic study of non-protoalgebraic logicswas considered worth to be pursued, the conceptual difference betweenthe two definitions was not needed and, accordingly, it was notconsidered (or even discovered).

9. When a logic is algebraizable and what does this mean?

The algebraizable logics are purported to be the logics with thestrongest possible link with their algebraic counterpart. Thisrequirement demands that the algebraic counterpart of the logic shouldbe an algebraic semantics but requires a more robust connectionbetween the logic and the algebraic counterpart than that. This morerobust connection is present in the best behaved particular logicsknown. The mathematically precise concept of algebraizable logiccharacterizes this type of link. Blok and Pigozzi introduced thatfundamental concept in Blok & Pigozzi 1989 and its introductioncan be considered the starting point of the unification and growth ofthe field of abstract algebraic logic in the 1980s. Blok and Pigozzidefined the notion of algebraizable logic only for finitary logics.Later, Czelakowski and Herrmann generalized it to arbitrary logics andalso weakened some conditions in the definition. We present here thegeneralized concept.

We said inSection 7 that, roughly speaking, a logic \(\bL\) is algebraizable when 1) ithas an algebraic semantics, i.e., a class of algebras \(\bK\) and aset of equations \(\iEq(p)\) such that \(\bK\) is a \(\iEq\)-algebraicsemantics for \(\bL\), 2) this fact can be proved by using theLindenbaum-Tarski method slightly generalized and, moreover, 3) \(\bK\subseteq \bAlg^*\bL\). The generalization of the Lindenbaum-Tarskimethod (as we described it inSection 7) consists in allowing in step (5) (as already done in the definitionof algebraic semantics) a set of equations \(\iEq(p)\) in one variableinstead of a single equation \(\delta(p) \approx \varepsilon(p)\) andin allowing in a similar manner a set of formulas \(\Delta(p, q)\) inat most two variables to play the role of the formula \(p\leftrightarrow q\) in the definition of the congruence of a theory.Then, given a theory \(T\), the relation \(\theta(T)\),which has to be the greatest congruence on the formula algebracompatible with \(T\) (i.e., the Leibniz congruence of\(T)\), is defined by

\[\langle \phi , \psi \rangle \in \theta(T) \txtiff \Delta(p/\phi , q/\psi) \subseteq T.\]

We need some notational conventions before engaging in the precisedefinition of algebraizable logic. Given a set of equations\(\iEq(p)\) in one variable and a formula \(\phi\), let \(\iEq(\phi)\)be the set of equations obtained by replacing in all the equations in\(\iEq\) the variable \(p\) by \(\phi\). If \(\Gamma\)is a set of formulas, let

\[\iEq(\Gamma) := \bigcup_{\phi \in \Gamma}\iEq(\phi).\]

Similarly, given a set of formulas in two variables \(\Delta(p, q)\)and an equation \(\delta \approx \varepsilon\), let \(\Delta(\delta ,\varepsilon)\) denote the set of formulas obtained by replacing \(p\)by \(\delta\) and \(q\) by\(\varepsilon\) in all the formulas in \(\Delta\). Moreover, if\(\iEq\) is a set of equations, let

\[\Delta(\iEq) = \bigcup_{\delta \approx \varepsilon \in \iEq} \Delta(\delta , \varepsilon).\]

Given a set of equations \(\iEq(p, q)\) in two variables, this setdefines on every algebra \(\bA\) a binary relation, namely the set ofpairs \(\langle a, b\rangle\) of elements of \(A\) thatsatisfy in \(\bA\) all the equations in \(\iEq(p, q)\). In standardmodel-theoretic notation, this set is the relation

\[\{\langle a, b \rangle : a, b \in A \textrm{ and } \bA \vDash \iEq(p, q)[a, b]\}.\]

The formal definition of algebraizable logic is as follows. A logic\(\bL\) isalgebraizable if there is a class of algebras\(\bK\), a set of equations \(\iEq(p)\) in one variable and a set offormulas \(\Delta(p, q)\) in two variables such that

\(\bK\) is an \(\iEq\)-algebraic semantics for\(\bL\), namely
\(\Gamma \vdash_{\bL } \phi\txtiff\) for every \(\bA \in \bK\) andevery valuation \(v\) on \(\bA\), if \(\bv[\Gamma]\subseteq \tEq(\bA)\), then \(\bv(\phi) \in \tEq(\bA)\).
For every \(\bA \in \bK\), the relation defined by theset of equations in two variables \(\iEq(\Delta(p, q))\) is theidentity relation on \(A\).

A class of algebras \(\bK\) for which there are sets \(\iEq(p)\) and\(\Delta(p, q)\) with these two properties is said to be anequivalent algebraic semantics for \(\bL\). The set offormulas \(\Delta\) is called aset of equivalence formulasand the set of equations \(\iEq\) aset of definingequations.

The conditions of the definition imply:

\(p\) is inter-derivable in \(\bL\) with the set of formulas \(\Delta(\iEq)\), that is \[\Delta(\iEq) \vdash_{\bL } p \textrm{ and } p \vdash_{\bL } \Delta(\iEq).\]
For every \(\bL\)-theory \(T\), the Leibniz congruence of \(\langle \bFm_L, T\rangle\) is the relation defined by \(\Delta(p, q)\), namely \[\langle \phi , \psi \rangle \in \bOmega_{\bFm }(T)\txtiff\Delta(p/\phi , q/\psi) \subseteq T.\]
If \(\Delta\) and \(\Delta '\) are two sets ofequivalence formulas, \(\Delta \vdash_{\bL } \Delta '\) and \(\Delta '\vdash_{\bL } \Delta\). Similarly, if \(\iEq(p)\) and \(\iEq'(p)\) aretwo sets of defining equations, for every algebra \(\bA \in \bK,\iEq(\bA) = \iEq'(\bA)\).
The class of algebras \(\bAlg^*\bL\) also satisfiesconditions(1) and(2), and hence it is an equivalent algebraic semantics for \(\bL\).Moreover, it is an SP-class and includes every other class of algebrasthat is an equivalent algebraic semantics for \(\bL\). Accordingly, itis calledthe greatest equivalent algebraic semantics of\(\bL\).
For every \(\bA \in \bAlg^*\bL\) there is exactly one\(\bL\)-filter \(F\) such that the matrix \(\langle\bA, F\rangle\) is reduced, and this filter is the set \(\iEq(\bA)\).Or, to put it in other terms, the class of reduced matrix models of\(\bL\) is \(\{\langle \bA, \iEq(\bA) \rangle : \bA \in\bAlg^*\bL\}\).

Blok and Pigozzi’s definition of algebraizable logic in Blok& Pigozzi 1989 was given only for finitary logics and, moreover,they imposed that the sets of defining equations and of equivalenceformulas should be finite. Today we say that an algebraizable logic isfinitely algebraizable if the sets of equivalence formulas\(\Delta\) and of defining equations \(\iEq\) can both be takenfinite. And we say that a logic is Blok-Pigozzi algebraizable(BP-algebraizable) if it is finitary and finitely algebraizable.

If \(\bL\) is finitary and finitely algebraizable, then \(\bAlg^*\bL\)is not only an SP-class, but a quasivariety and it is the quasivarietygenerated by any class of algebras \(\bK\) which is an equivalentalgebraic semantics for \(\bL\).

We have just seen that in algebraizable logics the class of algebras\(\bAlg^*\bL\) plays a prominent role. Moreover, in these logics theclasses of algebras obtained by the two ways of generalizing theLindenbaum-Tarski method coincide, that is, \(\bAlg^*\bL = \bAlg\bL\)—this is due to the fact that for any algebraizable logic\(\bL\), \(\bAlg^*\bL\) is closed under subdirect products. Hence, forevery algebraizable logic \(\bL\) its algebraic counterpart\(\bAlg\bL\) is its greatest equivalent algebraic semantics, whateverperspective is taken on the generalization of the Lindenbaum-Tarskimethod.

Conditions(1) and(2) of the definition of algebraizable logic (instantiated to\(\bAlg^*\bL\)) encode the fact that there is a very strong linkbetween an algebraizable logic \(\bL\) and its class of algebras\(\bAlg\bL\), so that this class of algebras reflects the metalogicalproperties of \(\bL\) by algebraic properties of \(\bAlg\bL\) andconversely.

The definition of algebraizable logic can be stated, equivalently, in terms oftranslations between the logic and an equational consequence relation\(\vDash_{\bK}\) associated with any equivalent algebraic semantics\(\bK\) for it —that turns to be the same relation no matterwhat equivalent algebraic semantics we choose.

The equational consequence \(\vDash_{\bK}\) of a class of algebras\(\bK\) is defined as follows.

\(\{\phi_i \approx \psi_i: i \in I\} \vDash_{\bK } \phi \approx \psi\txtiff\)for every \(\bA \in \bK\) and every valuation \(v\)on \(\bA\), if \(\bv(\phi_i) = \bv(\psi_i)\), for all\(i \in I\), then \(\bv(\phi) = \bv(\psi)\).

The translations needed are given by the set of defining equations andthe set of equivalence formulas. A set of equations \(\iEq(p)\) in onevariable defines atranslation from formulas to sets ofequations: each formula is translated into the set of equations\(\iEq(\phi).\) Similarly, a set of formulas \(\Delta(p, q)\) in twovariables defines atranslation from equations to sets offormulas: each equation \(\phi \approx \psi\) is translated intothe set of formulas \(\Delta(\phi , \psi)\).

Condition(1) in the definition of algebraizable logic can be reformulated as \[\Gamma \vdash_{\bL } \phi\txtiff \iEq(\Gamma) \vDash_{\bK } \iEq(\phi)\] and condition(2) as \[p \approx q \vDash_{\bK } \iEq(\Delta(p, q)) \textrm{ and } \iEq(\Delta(p, q)) \vDash_{\bK } p \approx q.\]

These two conditions imply

\(\{\phi_i \approx \psi_i : i \in I \} \vDash_{\bK }\phi \approx \psi \txtiff \Delta(\{\phi_i \approx \psi_i : i \in I\})\vdash_{\bL } \Delta(\phi , \psi)\)

and condition(3) above is

\[p \vdash_{\bL } \Delta(\iEq(p)) \textrm{ and } \Delta(\iEq(p)) \vdash_{\bL } p.\]

Thus, an algebraizable logic \(\bL\) is faithfully interpreted in theequational logic of its equivalent algebraic semantics (condition(1)) by means of the translation of formulas into sets of equations givenby a set of defining equations, and the equational logic of itsequivalent algebraic semantics is faithfully interpreted in the logic\(\bL\) (condition(9)) by means of the translation of equations into sets of formulas givenby an equivalence set of formulas. Moreover, both translations areinverses of each other (conditions(2) and(3)) modulo logical equivalence. In this way we see that the link between\(\bL\) and its greatest equivalent algebraic semantics is very strongand that the properties of \(\bL\) should translate into properties ofthe associated equational consequence relation. The properties thatthis relation actually has of course depend on the properties of theclass of algebras \(\bAlg\bL\).

Given an algebraic semantics \((\bK, \iEq)\) for a logic \(\bL\), away to stress the difference between it being merely an algebraicsemantics and being an algebraic semantics that makes \(\bL\)algebraizable is that the translation of formulas into equations givenby the set of equations \(\iEq\) is invertible in the sense that thereis a translation, say \(\Delta\), of equations into formulas given bya set of formulas in two variables that satisfies condition(9) above, and such that \(\iEq\) and \(\Delta\) provide mutuallyinverses translations (i.e., conditions(2) and(3) hold).

The link between an algebraizable logic \(\bL\) and its greatestequivalent algebraic semantics given by the set of defining equationsand the set of equivalence formulas allows us to prove a series ofgeneral theorems that relate the properties of \(\bL\) with theproperties of \(\bAlg\bL\). These kinds of theorems are calledfrequently bridge theorems. We will mention as a sample three ofthem.

The first concerns the deduction theorem. To prove a general theoremrelating the existence of a deduction theorem with an algebraicproperty requires first that a concept of deduction theorem applicableto any logic has to be defined. A logic \(\bL\) has thededuction-detachment property if there is a finite set offormulas \(\Sigma(p, q)\) such that for every set of formulas\(\Gamma\) and all formulas \(\phi , \psi\)

\[\Gamma \cup \{\phi \} \vdash_{\bL } \psi\txtiff\Gamma \vdash_{\bL } \Sigma(\phi , \psi).\]

Note that this is a generalization of the standard deduction theorem(the direction from left to right in the above expression) and ModusPonens (equivalent to the implication from right to left) that severallogics have for a connective \(\rightarrow\). In those cases\(\Sigma(p, q) = \{p \rightarrow q\}\).

Theorem 1.
A finitary and finitely algebraizable logic \(\bL\) has thededuction-detachment property if and only if the principal relativecongruences of the algebras in \(\bAlg\bL\) are equationallydefinable.

The second theorem refers to Craig interpolation. Several notions ofinterpolation are applicable to arbitrary logics. We consider only oneof them. A logic \(\bL\) has theCraig interpolation propertyfor the consequence relation if whenever \(\Gamma \vdash_{\bL } \phi\) and the set of variables of \(\phi\) has nonempty intersection with the set of variables of formulas in \(\Gamma\), there is a finite set of formulas \(\Gamma '\) whose set of variables is included in the set of variablesshared by \(\phi\) and the formulas in \(\Gamma\) such that \(\Gamma\vdash_{\bL } \Gamma '\) and \(\Gamma ' \vdash_{\bL } \phi\).

Theorem 2.
Let \(\bL\) be a finitary and finitely algebraizable logic with thededuction-detachment property. Then \(\bL\) has the Craiginterpolation property if and only if \(\bAlg\bL\) has theamalgamation property.

Finally, the third theorem concerns the Beth definability property.The interested reader can find the definition in Font, Jansana &Pigozzi 2003. In the general setting we are in, the property is too involved to state it here.

Theorem 3.
A finitary and finitely algebraizable logic has the Beth property ifand only if all the epimorphisms of the category with objects thealgebras in \(\bAlg\bL\) and morphisms the algebraic homomorphisms aresurjective homomorphisms.

Other results relating properties of an algebraizable logic with aproperty of its natural class of algebras can be found in Raftery2011, 2013. They concern respectively a generalization of the propertyof having the deduction-detachment property and the property thatgeneralize the inconsistency lemmas of classical and intuitionisticlogic. Also an abstract notion of having a theorem likeGlivenko’s theorem relating classical and intuitionistic logichas been proposed and related to an algebraic property in the case ofalgebraizable logics in Torrens 2008. More recently Raftery 2016presents bridge theorems related to admissible rules and to structuralcompleteness and Lávička et al. 2021 studies bridge theorems forthe property of the weak excluded middle.

For several classes of algebras that are the equivalent algebraicsemantics of some algebraizable logic it has been known for a longtime that for every algebra in the class there is an isomorphismbetween the lattice of congruences of the algebra and a lattice ofsubsets of the algebra with important algebraic meaning. For example,in Boolean algebras and Heyting algebras these subsets are the latticefilters and in modal algebras they are the lattice filters that areclosed under the operation that interprets \(\Box\). In all thosecases, the sets are exactly the \(\bL\)-filters of the correspondingalgebraizable logic \(\bL\).

Algebraizable logics can be characterized by the existence of thiskind of isomorphism between congruences and logic filters on thealgebras of their algebraic counterpart. To spell out thischaracterization we need a couple of definitions. Let \(\bL\) be alogic. TheLeibniz operator on an algebra \(\bA\) (relativeto \(\bL)\) is the map from the \(\bL\)-filters of \(\bA\) to the setof congruences of \(\bA\) that sends every \(\bL\)-filter \(D\)of \(\bA\) to its Leibniz congruence \(\bOmega_{\bA}(D)\). We say that the Leibniz operator of a logic \(\bL\)commutes with the inverses of homomorphisms between algebrasin a class \(\bK\) if for every homomorphism \(h\) froman algebra \(\bA \in \bK\) to an algebra \(\bB \in \bK\) and every\(\bL\)-filter \(D\) of \(\bB, h^{-1}[\bOmega_{\bB}(D)] = \bOmega_{\bA }(h^{-1}[D]\)).

Theorem 4.
A logic \(\bL\) is algebraizable if and only if for every algebra\(\bA \in \bAlg\bL\) the Leibniz operator commutes with the inversesof homomorphisms between algebras in \(\bAlg\bL\) and is anisomorphism between the set of all \(\bL\)-filters of \(\bA\), orderedby inclusion, and the set of congruences \(\theta\) of \(\bA\) suchthat \(\bA/\theta \in \bAlg\bL\), ordered also by inclusion.

The theorem provides a logical explanation of the known isomorphismsmentioned above and similar ones for other classes of algebras. Forexample, the isomorphism between the congruences and the normalsubgroups of a group can be explained by the existence of analgebraizable logic \(\bL\) of which the class of groups is itsgreatest equivalent algebraic semantics and the normal subgroups of agroup are its \(\bL\)-filters.

A different but related characterization of algebraizable logics isthis:

Theorem 5.
A logic \(\bL\) is algebraizable if and only if on the algebra offormulas \(\bFm_L\), the map that sends every theory \(T\)to its Leibniz congruence commutes with the inversesof homomorphisms from \(\bFm_L\) to \(\bFm_L\) and it is anisomorphism between the set \(\tTH(\bL)\) of theories of \(\bL\),ordered by inclusion, and the set of congruences \(\theta\) of\(\bFm_L\) such that \(\bFm_L /\theta \in \bAlg\bL\), also ordered byinclusion.

10. A classification of logics

Unfortunately, not every logic is algebraizable. A typical example of anon-algebraizable logic is the local consequence of the normal modallogic \(K\). Let us discuss this example.

The local modal logic \(\blK\) and the corresponding global one\(\bgK\) are not only different, but their metalogical propertiesdiffer. For example, \(\blK\) has the deduction-detachment propertyfor \(\rightarrow\):

\[\Gamma \cup \{\phi \} \vdash_{\blK } \psi\txtiff \Gamma \vdash_{\blK } \phi \rightarrow \psi.\]

But \(\bgK\) does not have the deduction-detachment property (atall).

The logic \(\bgK\) is algebraizable and \(\blK\) is not. Theequivalent algebraic semantics of \(\bgK\) is the variety \(\bMA\) ofmodal algebras, the set of equivalence formulas is the set \(\{p\leftrightarrow q\}\) and the set of defining equations is \(\{p\approx \top \}\). Interestingly, \(\blK\) and \(\bgK\) have the samealgebraic counterpart (i.e., \(\bAlg \blK = \bAlg \bgK)\), namely, thevariety of modal algebras.

A lesson to draw from this example is that the algebraic counterpart\(\bAlg\bL\) of a logic \(\bL\) does not necessarily fully encode theproperties of \(\bL\). The class of modal algebras encodes theproperties of \(\bgK\) because this logic is algebraizable andtherefore the link between \(\bgK\) and \(\bAlg \bgK\) is as strong aspossible. But \(\bAlg \blK\), the class of modal algebras, cannot byitself completely encode the properties of \(\blK\).

What causes this difference between \(\bgK\) and \(\blK\) is that the class of reduced matrix models of \(\bgK\) is \[\{\langle \bA, \{1^{\bA }\}\rangle : \bA \in \bMA\},\] but the class of reduced matrix models of \(\blK\) properly includes this class so that for some algebras \(\bA \in \bMA\), in addition to \(\{1^{\bA }\}\) there is some other \(\blK\)-filter \(F\) with \(\langle \bA, F \rangle\) reduced. This fact provides a way to show that \(\blK\) can not be algebraizable by showing that the \(\blK\)-filters of the reduced matrices are not equationally definable from the algebras; if they where, then for every \(\bA \in \bAlg \blK\) there would exist exactly one \(\blK\)-filter \(F\) of \(\bA\) such that \(\langle \bA, F \rangle\) is reduced.

Nonetheless, we can perform some of the steps of the Lindenbaum-Tarskimethod in the logic \(\blK\). We can define the Leibniz congruence ofevery \(\blK\)-theory in a uniform way by using formulas in twovariables. But in this particular case the set of formulas has to beinfinite. Let \(\Delta(p, q) = \{\Box^n (p \leftrightarrow q): n\) anatural number\(\}\), where for every formula \(\phi , \Box^0\phi\) is\(\phi\) and \(\Box^n\phi\) for \(n \gt 0\) is the formula \(\phi\)with a sequence of \(n\) boxes in front \((\Box\ldots \Box \phi)\). Then, for every \(\blK\)-theory \(T\)the relation \(\theta(T)\) defined by

\[\langle \phi , \psi \rangle \in \theta(T)\txtiff \{\Box^n (\phi \leftrightarrow \psi): n \textrm{ a natural number}\} \subseteq T\]

is the Leibniz congruence of \(T\). In this case, ithappens though that there are two different \(\blK\)-theories with thesame Leibniz congruence, something that does not hold for\(\bgK\).

The logics \(\bL\) with the property that there is a set of formulas (possibly infinite) \(\Delta(p, q)\) in two variables that defines in every \(\bL\)-theory \(T\) its Leibniz congruence, that is, that for all \(L\)-formulas \(\phi , \psi\) it holds \[\langle \phi , \psi \rangle \in \bOmega_{\bFm }(T)\txtiff \Delta(\phi , \psi) \subseteq T,\] are known as theequivalential logics. If \(\Delta(p, q)\) is finite, the logic is said to befinitely equivalential. A set \(\Delta(p, q)\) that defines in every \(\bL\)-theory its Leibniz congruence is called aset of equivalence formulas for \(\bL\). It is clear that every algebraizable logic is equivalential and that every finitely algebraizable logic is finitely equivalential.

The logic \(\blK\) is, according to the definition, equivalential, andit can be shown that it is not finitely equivalential. The local modallogiclS4 is an example of a non-algebraizable logicthat is finitely equivalential. A set of equivalence formulas forlS4 is \(\{\Box(p\leftrightarrow q)\}\).

A set of equivalence formulas for a logic \(\bL\) should be consideredas a generalized biconditional, in the sense that collectively theformulas in the set have the relevant properties of the biconditional,for example in classical logic, that makes it suitable to define theLeibniz congruences of its theories. This comes out very clearly fromthe following syntactic characterization of the sets of equivalenceformulas.

Theorem 6.
A set \(\Delta(p, q)\) of \(L\)-formulas is a set ofequivalence formulas for a logic \(\bL\) if and only if

\((\tR_{\Delta})\): \(\vdash_{\bL } \Delta(p, p)\)
\((\tMP_{\Delta})\): \(p, \Delta(p, q) \vdash_{\bL } q\)
\((\tS_{\Delta})\): \(\Delta(p, q) \vdash_{\bL } \Delta(q, p)\)
\((\tT_{\Delta})\): \(\Delta(p, q) \cup \Delta(q, r) \vdash_{\bL } \Delta(p,r)\)
\((\tRe_{\Delta})\): \(\Delta(p_1, q_1) \cup \ldots \cup \Delta(p_n, q_n) \vdash_{\bL }\Delta(* p_1 \ldots p_n, * q_1 \ldots q_n)\), for every connective\(*\) of \(L\) of arity \(n\) greater that 0.

There is some redundancy in the theorem. Conditions \((\tS_{\Delta})\)and \((\tT_{\Delta})\) follow from \((\tR_{\Delta}),(\tMP_{\Delta})\)and \((\tRe_{\Delta})\).

Equivalential logics were first considered as a class of logicsdeserving to be studied in Prucnal & Wroński 1974, and theywere studied extensively in Czelakowski 1981; see also Czelakowski2001.

We already mentioned that the algebraizable logics are equivalential.The difference between an equivalential logic and an algebraizable onecan be seen in the following syntactic characterization ofalgebraizable logics:

Theorem 7.
A logic \(\bL\) is algebraizable if and only if there exists a set \(\Delta(p, q)\) of \(L\)-formulas and a set \(\iEq(p)\) of \(L\)-equations such that the conditions \((\tR_{\Delta})\)–\((\tRe_{\Delta})\) above hold for \(\Delta(p, q)\) and \[p \vdash_{\bL } \Delta(\iEq(p)) \textrm{ and } \Delta(\iEq(p)) \vdash_{\bL } p.\]

The set \(\Delta(p, q)\) in the theorem is then an equivalence set offormulas for \(\bL\) and the set \(\iEq(p)\) a set of definingequations.

There are logics that are not equivalential but have the property ofhaving a set of formulas \([p \Rightarrow q]\) which collectivelybehave in a very weak sense as the implication \(\rightarrow\) does inmany logics. Namely, that has the properties \((\tR_{\Delta})\) and\((\tMP_{\Delta})\) in the syntactic characterization of a set ofequivalence formulas, i.e.,

\((\tR_{\Rightarrow})\): \(\vdash_{\bL } [p \Rightarrow p]\)
\((\tMP_{\Rightarrow})\): \(p, [p \Rightarrow q] \vdash_{\bL } q\)

If a logic is finitary and has a set of formulas with theseproperties, there is always a finite subset with the same properties.The logics with a set of formulas (finite or not) with properties(1) and(2) above are calledprotoalgebraic. Thus, every equivalentiallogic and every algebraizable logic are protoalgebraic.

Protoalgebraic logics were first studied by Czelakowski, who calledthem non-pathological, and slightly later by Blok and Pigozzi inBlok & Pigozzi 1986. The label ‘protoalgebraic logic’is due to these last two authors.

The class of protoalgebraic logics turned out to be the class oflogics for which the theory of logical matrices works really well inthe sense that many results of universal algebra have counterparts forthe classes of reduced matrix models of these logics and many methodsof universal algebra can be adapted to its study; consequently thealgebraic study of protoalgebraic logics using their matrix semanticshas been extensively and very fruitfully pursued. But, as we will see,some interesting logics are not protoalgebraic.

An important characterization of protoalgebraic logics is via thebehavior of the Leibniz operator. The following conditions areequivalent:

\(\bL\) is protoalgebraic.
The Leibniz operator \(\bOmega_{\bFm_L}\) is monotone on the setof \(\bL\)-theories with respect to the inclusion relation, that is,if \(T \subseteq T'\) are \(\bL\)-theories, then \(\bOmega_{\bFm_L}(T) \subseteq \bOmega_{\bFm_L }(T')\).
For every algebra \(\bA\), the Leibniz operator \(\bOmega_{\bA}\)is monotone on the set of \(\bL\)-filters of \(\bA\) with respect tothe inclusion relation.

Due to the monotonicity property of the Leibniz operator, for everyprotoalgebraic logic \(\bL\) the class of algebras \(\bAlg^*\bL\) isclosed under subdirect products and therefore it is equal to\(\bAlg\bL\). Hence, for protoalgebraic logics the two ways weencountered to associate a class of algebras with a logic produce, aswe already mentioned, the same result.

There are also characterizations of equivalential and finitelyequivalential logics by the behavior of the Leibniz operator. Thereader is referred to Czelakowski 2001 and Font & Jansana &Pigozzi 2003.

In his Raftery 2006b, Raftery studies Condition 7 in the list ofproperties of an algebraizable logic we gave just after thedefinition. The condition says:

For every \(\bA \in \bAlg^*\bL\) the class of reduced matrix models of\(\bL\) is \(\{\langle \bA, \iEq(\bA) \rangle : \bA \in\bAlg^*\bL\}\), where \(\iEq(p)\) is the set of defining equations for\(\bL\).

The logics with a set of equations \(\iEq(p)\) with this property,namely such that for every \(\bA \in \bAlg^*\bL\) the class of reducedmatrix models of \(\bL\) is \(\{\langle \bA, \iEq(\bA) \rangle : \bA\in \bAlg^*\bL\}\), are calledtruth-equational, a nameintroduced in Raftery 2006b. Some truth-equational logics areprotoalgebraic but others are not. We will see later an example of thelast ones.

The protoalgebraic logics that are truth-equational are in fact theweakly algebraizable logics studied already in Czelakowski& Jansana 2000. Every algebraizable logic is weakly algebraizable.In fact, the algebraizable logics are the equivalential logics thatare truth-equational. But not every weakly algebraizable logic isequivalential. An example is the logic determined by theortholattices, namely by the class of the matrices \(\langle \bA, \{1\}\rangle\) where \(\bA\) is an ortholattice and 1 is its greatestelement (see Czelakowski & Jansana 2000 and Malinowski 1990).

The classes of logics we have considered so far are the main classesin what has come to be known as theLeibniz hierarchy becauseits members are classes of logics that can be characterized by thebehavior of the Leibniz operator. We described only the most importantclasses of logics in the hierarchy. The reader is referred toCzelakowski 2001, Font, Jansana & Pigozzi 2003, Font 2016 and2022, for more information. In particular, Czelakowski 2001 gathersextensively the information on the different classes of the Leibnizhierarchy known at the time of its publication and Font 2016 is anintroduction to abstract algebraic logic very well suited to learn themost important facts about the Leibniz hierarchy and of abstractalgebraic logic in general.

The relations between the classes of the Leibniz hierarchy consideredin this entry are summarized in the following diagram:

A diagram of four levels level 1: 'finitely algebraizable' with arrows pointing to level 2 objects: 'finitely equivalential' and 'algebraizable'; both of these have arrows pointing to level 3 object 'equivalential' and the latter also has an arrow pointing to level 3 object 'weakly algebraizable' both level 3 objects have arrows to level 4 object: 'protoalgebraic' and the second also points to 'truth-equational'

Figure. The Leibniz Hierarchy

Recently, the Leibniz hierarchy has been refined in Cintula &Noguera 2010, 2016. The idea is to consider instead of a set ofequivalence formulas \(\Delta\) (that corresponds to the biconditional)a set of formulas \([p\Rightarrow q]\) that has several properties of theusual conditional \((\rightarrow)\). Among these properties we have \((\tR_{\Rightarrow})\) and\((\tMP_{\Rightarrow})\) in the definition of protoalgebraic logic. The set \([p\Rightarrow q]\) should be such that its symetrization \([p\Rightarrow q]\cup[q\Rightarrow p]\) is a set of equivalence formulas. New classesarise when the set \([p\Rightarrow q]\) has a single element.Extensive information can be found in the recent book Cintula &Noguera 2021. This book can also be taken as an introduction toabstract algebraic logic written from the perspective of theimplication.

11. Replacement principles

Two classes of logics that are not classes of the Leibniz hierarchyhave been extensively studied in abstract algebraic logic. They aredefined from a completely different perspective from the one providedby the behavior of the Leibniz operator, namely from the perspectivegiven by the replacement principles a logic might enjoy.

The strongest replacement principle that a logic system \(\bL\) mighthave, shared for example by classical logic, intuitionistic logic andall its axiomatic extensions, says that for any set of formulas\(\Gamma\), any formulas \(\phi , \psi , \delta\) and any variable \(p\)

if \(\Gamma , \phi \vdash_{\bL } \psi\) and \(\Gamma , \psi\vdash_{\bL } \phi\), then \(\Gamma , \delta(p/\phi) \vdash_{\bL }\delta(p/\psi)\) and \(\Gamma , \delta(p/\psi) \vdash_{\bL }\delta(p/\phi)\),

where \(\delta(p/\phi)\) and \(\delta(p/\psi)\) are the formulasobtained by substituting respectively \(\phi\) and \(\psi\) for \(p\)in \(\delta\). This replacement property is taken bysome authors as the formal counterpart of Frege’s principle ofcompositionality for truth. Logics satisfying this strong replacementproperty are calledFregean in Font & Jansana 1996 andare thoroughly studied in Czelakowski & Pigozzi 2004a, 2004b.

Many important logics do not satisfy the strong replacement property,for instance almost all the logics (local or global) of the modalfamily, but some, like the local consequence relation of a normalmodal logic, satisfy a weaker replacement principle: for all formulas\(\phi , \psi , \delta\),

if \(\phi \vdash_{\bL }\psi\) and \(\psi \vdash_{\bL }\phi\), then\(\delta(p/\phi) \vdash_{\bL } \delta(p/\psi)\) and \(\delta(p/\psi)\vdash_{\bL } \delta(p/\phi)\).

A logic satisfying this weaker replacement property is calledselfextensional by Wójcicki (e.g., in Wójcicki1969, 1988) andcongruential in Humberstone 2005. We will usethe first terminology because it seems more common —at least inthe abstract algebraic logic literature. It has to be mentioned thatall fragments of a selfextensional logic are selfextensional and thatthe analogous fact also holds for Fregean logics. Moreover, the differencebetween being selfextensional and being Fregean is not onlyencountered among protoalgebraic logics like the mentioned localconsequence relations of normal modal logics, it is also encounteredamong non protoalgebraic logics. The four-valued logic of Belnap andDunn (see Font 1997 for information) is selfextensional,non-protoalgebraic, and non-Fregean.

Selfextensional logics have a very good behavior from several pointsof view. Their systematic study started in Wójcicki 1969 andhas been continued in the context of abstract algebraic logicin Font & Jansana 1996; Jansana 2005, 2006; and Jansana &Palmigiano 2006.

There are selfextensional and non-selfextensional logics in any one ofthe classes of the Leibniz hierarchy and also in the class ofnon-protoalgebraic logics. These facts show that the perspective thatleads to the consideration of the classes in the Leibniz hierarchy andthe perspective that leads to the definition of the selfextensionaland the Fregean logics as classes of logics worthy of study as a wholeare to a large extent different. Nonetheless, one of the trends oftoday’s research in abstract algebraic logic is to determine theinterplay between the two perspectives and study the classes of logicsthat arise when crossing both classifications. In fact, there is aconnection between the replacement principles and the Suszkocongruence (and thus with the Leibniz congruence). A logic \(\bL\)satisfies the strong replacement principle if and only if for every\(\bL\)-theory \(T\) its Suszko congruence is theinterderivability relation relative to \(T\), namelythe relation \(\{\langle \phi , \psi \rangle : T, \phi \vdash_{\bL }\psi\) and \(T, \psi \vdash_{\bL } \phi \}\). And a logic \(\bL\)satisfies the weak replacement principle if and only if the Suszkocongruence of the set of theorems of \(\bL\) is the interderivabilityrelation \(\{\langle \phi , \psi \rangle : \phi \vdash_{\bL } \psi\)and \(\psi \vdash_{\bL } \phi \}\).

The study of logic systems from the perspective of the replacementprinciples lead to the so called Frege hierarchy we expound in Section14.

12. Beyond protoalgebraic logics

Not all interesting logics are protoalgebraic. In this section we willbriefly discuss four examples of non-protoalgebraic logics: the logicof conjunction and disjunction, positive modal logic, the strictimplication fragment of \(\blK\) and Visser’s subintuitionisticlogic. All of them are selfextensional. In the next section, we willexpound the semantics of abstract logics and generalized matrices thatserves to develop a really general theory of the algebraization oflogic systems. As we will see, the perspective changes in an importantrespect from the perspective taken in logical matrix model theory.

12.1 The logic of conjunction and disjunction

This logic is the \(\{\wedge , \vee , \bot , \top \}\)-fragment ofClassical Propositional Logic. Hence its language is the set\(\{\wedge , \vee , \top , \bot \}\) and its consequence relation isgiven by

\[\Gamma \vdash \phi\txtiff\Gamma \vdash_{\bCPL} \phi.\]

It turns out that it is also the \(\{\wedge , \vee , \bot , \top\}\)-fragment of Intuitionistic Propositional Logic. Let us denote itby \(\bL^{\{\wedge , \vee \}}\).

The logic \(\bL^{ \{\wedge , \vee \}}\) is not protoalgebraic but itis Fregean. The class of algebras \(\bAlg\bL^{\{\wedge , \vee \}}\) isthe variety of bounded distributive lattices, which is the class ofalgebras naturally expected to be the associated with \(\bL^{ \{\wedge, \vee \}}\), but the class \(\bAlg^*\bL^{ \{\wedge , \vee \}}\) isstrictly included in it. In fact, this last class of algebras is not aquasivariety, but still it is good enough to be first-orderdefinable.

The logic \(\bL^{\{\wedge , \vee \}}\) is thus a natural example of alogic where the class of algebras of its reduced matrix models is notthe right class of algebras expected to correspond to it (see Font& Verdú 1991 where the logic is studied at length). Theproperties of this example and its treatment in Font &Verdú 1991 motivated the systematic study in Font & Jansana1996 of the kind of models for sentential logics considered in Brown& Suszko 1973, namely, abstract logics.

12.2 Positive Modal Logic

Positive Modal Logic is the \(\{\wedge , \vee , \Box , \Diamond , \bot, \top \}\)-fragment of the local normal modal logic \(\blK\). Wedenote it by \(\bPML\). This logic has some interest in ComputerScience.

The logic \(\bPML\) is not protoalgebraic, it is not truth-equational,it is selfextensional and it is not Fregean. Its algebraic counterpart\(\bAlg \bPML\) is the class of positive modal algebras introduced byDunn in Dunn 1995. The logic is studied in Jansana 2002 from theperspective of abstract algebraic logic. The class of algebras\(\bAlg\bPML\) is different from \(\bAlg^*\bPML\).

12.3 Visser’s subintuitionistic logic

This logic is the logic in the language of intuitionistic logic thathas to the least normal modal logic \(K\) the samerelation that intuitionistic logic has to the normal modal logic\(S4\). It was introduced in Visser 1981 (under the name BasicPropositional Logic) and has been studied by several authors, such asArdeshir, Alizadeh, and Ruitenburg. It is not protoalgebraic, it istruth-equational and it is Fregean (hence also selfextensional).

12.4 The strict implication fragment of the local modal logiclK

The strict implication of the language of modal logic is defined usingthe \(\Box\) operator and the material implication \(\rightarrow\). Wewill use \(\Rightarrow\) for the strict implication. Its definition is\(\phi \Rightarrow \psi := \Box(\phi \rightarrow \psi)\). The languageof the logic \(\bSilK\), that we call the strict implication fragmentof the local modal logic \(\blK\), is the language \(L = \{\wedge ,\vee , \bot , \top , \Rightarrow \}\). We can translate the formulasof \(L\) to formulas of the modal language bysystematically replacing in an \(L\)-formula \(\phi\)every subformula of the form \(\psi \Rightarrow \delta\) by\(\Box(\psi \rightarrow \delta)\) and repeating the process until noappearance of \(\Rightarrow\) is left. Let us denote by \(\phi^*\) thetranslation of \(\phi\) and by \(\Gamma^*\) the set of thetranslations of the formulas in \(\Gamma\). Then the definition of theconsequence relation of \(\bSilK\) is:

\[\Gamma \vdash_{\bSilK } \phi\txtiff\Gamma^* \vdash_{\blK } \phi^*.\]

The logic \(\bSilK\) is not protoalgebraic and is nottruth-equational. It is selfextensional but it is not Fregean. Itsalgebraic counterpart \(\bAlg \bSilK\) is the class of boundeddistributive lattices with a binary operation with the properties ofthe strict implication of \(\blK\). This class of algebras isintroduced and studied in Celani & Jansana 2005, where its membersare called Weakly Heyting algebras. \(\bAlg \bSilK\) does not coincidewith \(\bAlg^* \bSilK\).

The logic \(\bSilK\) belongs, as Visser’s logic, to the familyof so-called subintuitionistic logics. A reference to look at forinformation on these logics is Celani & Jansana 2003.

The reader can find more information on interesting non-protoalgebariclogics in Albuquerque et alt. 2017.

13. Abstract logics and generalized matrices

The logical matrix models of a given logic can be thought of asalgebraic generalizations of its theories, more precisely, of itsLindenbaum matrices. They come from taking a local perspectivecentered around the theories of the logic considered one by one andits analogs the logic filters (also taken one by one). But, as we willsee, the properties of a logic depend in general on the globalbehavior of the set of its theories taken together as a bunch; or—to put it otherwise— on its consequence relation. Theconsideration of this global behavior introduces a global perspectiveon the design of semantics for logic systems. The abstract logics thatwe are going to define can be seen, in contrast to logical matrices,as algebraic generalizations of the logic itself and its extensions.They are the natural objects to consider when one takes the globalperspective seriously.

Let \(L\) be a propositional language. An \(L\)-abstractlogic is a pair \(\cA = \langle\bA\), C \(\rangle\) where \(\bA\) is an \(L\)-algebraand \(C\) an abstract consequence operation on \(A\).

Given a logic system \(\bL\), an \(L\)-abstract logic\(\cA = \langle \bA, C \rangle\) is amodel of \(\bL\) if forevery set of formulas \(\Gamma\) and every formula \(\phi\)

\(\Gamma \vdash_{\bL } \phi\txtiff\) for every valuation \(v\)on \(\bA, \bv(\phi) \in C(\bv[\Gamma])\).

This definition has an equivalent in terms of the closed sets of \(C\):an abstract logic \(\cA = \langle \bA, C \rangle\)is a model of \(\bL\) if and only if for every \(C\)-closedset \(X\) the matrix \(\langle\bA, X \rangle\) is a model of \(\bL\) (i.e., \(X\) isan \(\bL\)-filter).

This observation leads to another point of view on abstract logics asmodels of a logic system. It transforms them into a collection oflogical matrices (given by the closed sets) over the same algebra, or,to put it more simply, into a pair \(\langle \bA, \cB \rangle\) where\(\cB\) is a collection of subsets of \(A\). Astructure of this type is called in the literature ageneralizedmatrix (Wójcicki 1973) and more recently it has beencalled anatlas in Dunn & Hardegree 2001. It is said tobe a model of a logic system \(\bL\) if for every \(X \in \cB, \langle\bA, X \rangle\) is a matrix model of \(\bL\).

A logic system \(\bL = \langle L, \vdash_{\bL } \rangle\)straightforwardly provides us with an equivalent abstract logic\(\langle \bFm_L, C_{\vdash_{ \bL} } \rangle\) and an equivalentgeneralized matrix \(\langle \bFm_L,\tTH(\bL) \rangle\), where\(\tTH(\bL)\) is the set of \(C_{\vdash_{ \bL}}\)-closed sets offormulas (i.e., the \(\bL\)-theories). We will move freely from one tothe other.

The generalized matrices \(\langle \bA, \cB \rangle\) that correspondto abstract logics have the following two properties: \(A \in \cB\)and \(\cB\) is closed under intersections of arbitrary nonemptyfamilies. A family \(\cB\) of subsets of a set \(A\)with these two properties is known as aclosed-set system andalso as aclosure system. There is a dual correspondencebetween abstract consequence operations on a set \(A\)and closed-set systems on \(A\). Given an abstractconsequence operation \(C\) on \(A\),the set \(\cC_C\) of \(C\)-closed sets is a closed-setsystem and given a closed-set system \(\cC\) the operation \(C_{\cC}\)defined by \(C_{\cC }(X) = \bigcap \{Y \in \cC: X \subseteq Y\}\), forevery \(X \subseteq A\), is an abstract consequence operation. Ingeneral, every generalized matrix \(\langle \bA, \cB \rangle\) can beturned into a closed-set system by adding to \(\cB \cup \{A\}\) theintersections of arbitrary nonempty subfamilies, and therefore into anabstract logic, which we denote by \(\langle \bA, C_{\cB }\rangle\).In that situation we say that \(\cB\) is abase for\(C_{\cB}\). It is obvious that an abstract logic can have more thanone base. Any family of closed sets with the property that everyclosed set is an intersection of elements of the family is a base. Thestudy of bases for the closed set system of the theories of a logicusually plays an important role in its study. For example, inclassical logic an important base for the family of its theories isthe family of maximal consistent theories and in intuitionistic logicthe family of prime theories. In a similar way, the systematic studyof bases for generalized matrix models of a logic becomesimportant.

In order to make the exposition smooth we will now move from abstractlogics to generalized matrices. Let \(\cA = \langle \bA, \cB \rangle\)be a generalized matrix. There exists the greatest congruence of\(\bA\) compatible with all the sets in \(\cB\); it is known as theTarski congruence of \(\cA\). We denote it by\(\bOmega^{\sim}_{\bA }(\cB)\) and has the following characterizationusing the Leibniz operator

\[\bOmega^{\sim}_{\bA }(\cB) = \bigcap_{X \in \cB} \bOmega_{\bA }(X).\]

It can also be characterized by the condition:

\(\langle a, b \rangle \in \bOmega^{\sim}_{\bA }(\cB)\txtiff\) forevery \(\phi(p, q_1 , \ldots ,q_n)\), every \(c_1 , \ldots ,c_n \inA\) and all \(X \in \cB\)

\[\phi^{\bA }[a, c_1 , \ldots ,c_n] \in X \Leftrightarrow \phi^{\bA }[b, c_1 , \ldots ,c_n] \in X\]

or equivalently by

\(\langle a, b \rangle \in \bOmega^{\sim}_{\bA }(\cB)\txtiff\) forevery \(\phi(p, q_1 , \ldots ,q_n)\) and every \(c_1 , \ldots ,c_n \inA, C_{\cB }(\phi^{\bA }[a, c_1 , \ldots ,c_n]) = C_{\cB }(\phi^{\bA}[b, c_1 , \ldots ,c_n])\).

A generalized matrix isreduced if its Tarski congruence isthe identity. Every generalized matrix \(\langle \bA, \cB \rangle\)can be turned into an equivalent reduced one by identifying theelements related by its Tarski congruence. The result is the quotientgeneralized matrix \(\langle \bA / \bOmega^{\sim}_{\bA }(\cB),\cB/\bOmega^{\sim}_{\bA }(\cB) \rangle\), where\(\cB/\bOmega^{\sim}_{\bA }(\cB) = \{X/\bOmega^{\sim}_{\bA }(\cB): X\in \cB\}\) and for \(X \in \cB\), the set \(X/\bOmega^{\sim}_{\bA}(\cB)\) is that of the equivalence classes of the elements of \(X\).

The properties of a logic \(\bL\) depend in general, as we alreadysaid, on the global behavior of the family of its theories. In somelogics, this behavior is reflected in the behavior of its set oftheorems, as in classical and intuitionistic logic due to thededuction-detachment property, but this is by no means the mostgeneral situation, as it is witnessed by the example of the local andglobal modal logics of the normal modal logic \(K\).The two have the same theorems but do not share the same properties.Recall that the local logic has the deduction-detachment property butthe global one does not. In a similar way, the properties of a logicarein general better encoded in an algebraic setting if weconsider families of \(\bL\)-filters on the algebras than if weconsider a single \(\bL\)-filter as it is done in logical matricesmodel theory.

The generalized matrix models that have naturally attracted most ofthe attention in the research on the algebraization of logics are thegeneralized matrices of the form \(\langle \bA, \tFi_{\bL }\bA\rangle\) where \(\tFi_{\bL }\bA\) is the set of all the\(\bL\)-filters of \(\bA\). An example of a property of logics encodedin the structure of the lattices of \(\bL\)-filters of the \(L\)-algebrasis that for every finitary protoalgebraiclogic \(\bL, \bL\) has the deduction-detachment property if and onlyif for every algebra \(\bA\) the join-subsemilattice of the lattice ofall \(\bL\)-filters of \(\bA\) that consists of the finitely generated\(\bL\)-filters is dually residuated; see Czelakowski 2001.

The generalized matrices of the form \(\langle \bA, \tFi_{\bL }\bA\rangle\) are called thebasic full g-models of \(\bL\) (theletter ‘g’ stands for generalized matrix). The interest inthese models lead to the consideration of the class of generalizedmatrix models of a logic \(\bL\) with the property that their quotientby their Tarski congruence is a basic full g-model. These generalizedmatrices (and their corresponding abstract logics) are calledfullg-models. The theory of the full g-models of an arbitrary logicis developed in Font & Jansana 1996, where the notions of fullg-model and basic full g-model are introduced. We will mention some ofthe main results obtained there.

Let \(\bL\) be a logic system.

\(\bL\) is protoalgebraic if and only if for every fullg-model \(\langle \bA, \cC \rangle\) there exists an \(\bL\)-filter\(F\) of \(\bA\) such that \(\cC = \{G \in \tFi_{\bL}\bA: F \subseteq G\}\).
If \(\bL\) is finitary, \(\bL\) is finitelyalgebraizable if and only if for every algebra \(\bA\) and every\(\bL\)-filter \(F\) of \(\bA\), the generalized matrix\(\langle \bA, \{G \in \tFi_{\bL }\bA: F \subseteq G\} \rangle\) is afull g-model and \(\bAlg\bL\) is a quasivariety.
The class \(\bAlg\bL\) is both the class of algebras ofthe reduced generalized matrix models of \(\bL\) and the class\(\{\bA: \langle \bA, \tFi_{\bL }\bA \rangle\) is reduced\(\}\).
For every algebra \(\bA\) there is an isomorphismbetween the family of closed-set systems \(\cC\) on \(A\)such that \(\langle\bA, \cC\rangle\) is a fullg-model of \(\bL\) and the family of congruences \(\theta\) of \(\bA\)such that \(\bA/\theta \in \bAlg\bL\). The isomorphism is given by theTarski operator that sends a generalized matrix to its Tarskicongruence.

The isomorphismtheorem (4) above is a generalization of the isomorphism theorems we encounteredearlier for algebraizable logics. What is interesting here is that thetheorem holds for every logic system. Using(2) above,theorem (4) entails the isomorphism theorem for finitary and finitelyalgebraizable logics. Thustheorem (4) can be seen as the most general formulation of the mathematicallogical phenomena that underlies the isomorphism theorems between thecongruences of the algebras in a certain class and some kind ofsubsets of them we mentioned inSection 9.

The use of generalized matrices and abstract logics as models forlogic systems has proved very useful for the study of selfextensionallogics in general and more in particular for the study of theselfextensional logics that are not protoalgebraic such as the logicsdiscussed inSection 12. In particular, they have proved very useful for the study of theclass of finitary selfextensional logics with a conjunction and theclass of finitary selfextensional logics with the deduction-detachmentproperty for a single term, say \(p \rightarrow q\); the logics inthis last class are nevertheless protoalgebraic. A logic \(\bL\) has aconjunction if there is a formula in two variables \(\phi(p,q)\) such that

\[\phi(p, q) \vdash_{\bL } p,\;\;\; \phi(p, q)\vdash_{\bL } q, \;\;\; p, q \vdash_{\bL } \phi(p, q).\]

The logics in those two classes have the following property: theTarski relation of every full g-model \(\langle \bA, C \rangle\) is\(\{\langle a, b \rangle \in A \times A: C(a) = C(b)\}\). A way ofsaying it is to say that for these logics the property that definesselfextensionality, namely that the interderivability condition is acongruence, lifts or transfers to every full g-model. Theselfextensional logics with this property are calledfullyselfextensional. This notion was introduced in Font & Jansana1996 under the name ‘strongly selfextensional’. All thenatural selfextensional logics considered up to 1996 are fullyselfextensional, in particular the logics discussed inSection 12, but Babyonyshev showed (Babyonyshev 2003) anad hoc exampleof a selfextensional logic that is not fully selfextensional. A muchmore natural example discovered later of a selfextensional logic thatis not fully selfextensional is the fragment of only the negation andthe constant \(\top\) of classical logic.

An interesting result on the finitary logics which are fullyselfextensional logics with a conjunction or with thededuction-detachment property for a single term is that their class ofalgebras \(\bAlg\bL\) is always a variety. It looks surprising that manyfinitary and finitely algebraizable logics have a variety as itsequivalent algebraic semantics, when the theory of algebraizablelogics allows in general to prove only that the equivalent algebraicsemantics of a finitary and finitely algebraizable logic is aquasivariety. The result explains this phenomenon for the finitary andfinitely algebraizable logics to which it applies. For many otherfinitary and finitely algebraizable logics to find a convincingexplanation is still an open area of research.

Every abstract logic \(\cA = \langle \bA, C \rangle\) determines aquasi-order (a reflexive and transitive relation) on \(A\). It is therelation defined by \[a \le_{\cA } b\txtiff C(b) \subseteq C(a)\txtiffb \in C(a).\]

Thus, \(a \le_{\cA } b\) if and only if \(b\) belongs to every\(C\)-closed set to which \(A\) belongs. For a fully selfextensionallogic \(\bL\), this quasi-order turns into a partial order in thereduced full g-models, which are in fact the reduced basic fullg-models, namely, the abstract logics \(\langle \bA, \tFi_{\bL }\bA\rangle\) with \(\bA \in \bAlg\bL\). Consequently, in a fullyselfextensional logic \(\bL\) every algebra \(\bA \in \bAlg\bL\)carries a partial order definable in terms of the family of the\(\bL\)-filters. If the logic is fully selfextensional with aconjunction this partial order is definable by an equation of the\(L\)-algebraic language because in this case for every algebra \(\bA\in \bAlg\bL\) we have: \[a \le b\txtiff C(b) \subseteq C(a)\txtiffC(a \wedge^{\bA } b) = C(a)\txtiff a \wedge^{\bA } b = a,\] where\(C\) is the abstract consequence operation that corresponds to theclosed-set system \(\tFi_{\bL }\bA\), and \(\wedge^{\bA}\) is theoperation defined on \(\bA\) by the formula that is a conjunction forthe logic \(\bL\).

A similar situation holds for fully selfextensional logics with thededuction-detachment property for a single term, say \(p \rightarrowq\), for then for every algebra \(\bA \in \bAlg\bL\)

\[a \le b\txtiff C(b) \subseteq C(a)\txtiff C(a \rightarrow^{\bA } b) = C(\varnothing) = C(a \rightarrow^{\bA } a) \txtiff \\ a \rightarrow^{\bA } b = a \rightarrow^{\bA } a.\]

These observations lead us to view the finitary fully selfextensionallogics \(\bL\) with a conjunction and those with thededuction-detachment property for a single term as logics definable byan order which is definable in the algebras in \(\bAlg\bL\) by usingan equation of the \(\bL\)-algebraic language. Related to this, thefollowing result is known.

Theorem 8.
A finitary logic \(\bL\) with a conjunction is fully selfextensionalif and only if there is a class of algebras \(\bK\) such that forevery \(\bA \in \bK\) the reduct \(\langle A, \wedge^{\bA }\rangle\)is a meet-semilattice and if \(\le\) is the order of the semilattice,then

\(\phi_1 , \ldots ,\phi_n\vdash_{\bL } \phi\txtiff\) for all \(\bA \in\bK\) and every valuation \(v\) on \(\bA \; \bv(\phi_1)\wedge^{\bA }\ldots \wedge^{\bA } \bv(\phi_n) \le \bv(\phi)\)

and

\(\vdash_{\bL } \phi\txtiff\) for all \(\bA \in \bK\) and everyvaluation \(v\) on \(\bA \; a \le \bv(\phi)\), forevery \(a \in A\).

Moreover, in this case the class of algebras \(\bAlg\bL\) is thevariety generated by \(\bK\).

Similar results can be obtained for the selfextensional logics withthe deduction-detachment property for a single term. The reader isreferred to Jansana 2006 for a study of the selfextensional logicswith conjunction, and to Jansana 2005 for a study of theselfextensional logics with the deduction-detachment property for asingle term.

The class of selfextensional logics with a conjunction includes theso-called logics preserving degrees of truth studied in the fields ofsubstructural logics and of many-valued logics. The reader can look atBou et al. 2009 and the references therein.

14. The Frege hierarchy

A hierarchy of logic systems grounded on the replacement principlesdiscussed inSection 11 instead of on the behaviour of the Leibniz congruences is alsoconsidered in abstract algebraic logic. It is known as theFregehierarchy. Its classes are those of selfextensional logics, fullyselfextensional logics, Fregean logics and the class of fully Fregeanlogics that we define now.

In the same way as the fully selfextensional logics are theselfextensional logic systems that enjoy the property that in every oneof their full g-models the abstract version of the characteristicproperty defining selfextensionally holds, the fully Fregean logics arethe Fregean logics that in every one of their full g-models the abstractversion of the characteristic property defining being Fregean holds.The next can be taken as the best understandable definition.

A logic system \(\bL\) isfully Fregean when in every one ofits basic full g-models \(\langle \bA, \tFi_{\bL }\bA \rangle\), forevery \(F \in \tFi_{\bL }\bA\), the Suszko congruence\({\bOmega^{\sim}_{\bA}}^{\bL}(F)\) coincides with the relation ofbelonging to the same elements of \(\tFi_{\bL }\bA\) that extend\(F\). It is easy to see that the fully Fregean logics are Fregean andthat they are fully selfextensional.

Examples of fully Fregean logics are classical and intuitionisticlogic an also the logic of conjunction and disjunction discussed in12.1. The fragment of just the negation and a constant for true ofclassical logic mentioned before is a Fregean logic that is not fullyFregean.

We address the reader to Chapter 7 of Font 2016a for an introductionto the main facts of the Frege hierarchy and for examples of logicsystems in the families of the Frege hierarchy. A discussion of theFrege and Leibniz hierarchies related to assertional logics can befound in Albuquerque et al. 2018 where also several examples of logicsystems are discussed and classified.

A diagram of three levels level 1: 'fully Fregean' with arrows pointing to level 2 objects: 'Fregean logics' and 'fully selfextensional'; both of these have arrows pointing to level 1 object 'selfextensional'

Figure. The Frege Hierarchy

The reader can find a discussion of several natural examples of logicsclassified in the Leibniz and Frege hierarchies in Albuquerque et alt.2017.

15. Extending the setting

The research on logic systems described in the previous sections hasbeen extended to encompass other consequence relations that go beyondpropositional logics, like equational logics and the consequencerelations between sequents built from the formulas of a propositionallanguage definable using sequent calculi. The interested reader canconsult the excellent paper Raftery 2006a.

This research arose the need for an even more abstract way ofdeveloping the theory of consequence relations. It has lead to areformulation (in a category-theoretic setting) of the theory of logicsystems as explained in this entry. The work has been done mainly byG. Voutsadakis in a series of papers, e.g., Voutsadakis 2002.Voutsadakis’s approach uses the notion of a pi-institution,introduced by Fiadeiro and Sernadas, as the analog of the logicsystems in his category-theoretic setting. Some work in this directionis also found in Gil-Férez 2006. A different approach to ageneralization of the studies encompassing the work done for logicsystems and for sequent calculi is found in Galatos & Tsinakis2009; Gil-Férez 2011 is also in this line. The work presentedin these two papers originates in Blok & Jónsson 2006. TheGalatos-Tsinakis approach has been recently extended in a way thatalso encompasses the setting of Voutsadakis in Galatos &Gil-Férez 2017.

Another recent line of research that extends the framework describedin this entry develops a theory of algebraization of many-sorted logicsystems using instead of the equational consequence relation of thenatural class of algebras a many-sorted behavioral equationalconsequence (a notion coming from computer science) and a weakerconcept than algebraizable logic: behaviorally algebraizable logic.See Caleiro, Gonçalves & Martins 2009.

Bibliography

Albuquerque, Hugo, Josep Maria Font, and Ramon Jansana, 2016,“Compatibility operators in abstract algebraic logic”,The Journal of Symbolic Logic, 81(2): 417–462.doi:10.1017/jsl.2015.39
–––, 2017, “The strong version of asentential logic”,Studia Logica, 105: 703–760.doi: 10.1007/s11225-017-9709-0
Albuquerque, Hugo, Josep Maria Font, Ramon Jansana and TommasoMoraschini, 2018, “Assertional logics, truth-equational logicsand the hierarchies of abstract algebraic logic”, inDonPigozzi on Abstract Algebraic Logic, Universal Algebra, and ComputerScience (Outstanding Contributions to Logic: Volume 16), JanuszCzelakowski (ed.), Dordrecht: Springer: 53–79. doi:10.1007/978-3-319-74772-9
Babyonyshev, Sergei V., 2003, “Strongly Fregeanlogics”,Reports on Mathematical Logic, 37:59–77. [Babyonyshev 2003 available online]
Blackburn, Patrick, Johan van Benthem, and Frank Wolter (eds.),2006,Handbook of Modal Logic, Amsterdam: Elsevier.
Blok, W.J. and Eva Hoogland, 2006, “The Beth property inalgebraic logic”,Studia Logica (Special Issue inmemory of Willem Johannes Blok), 83: 49–90.doi:10.1007/s11225-006-8298-0
Blok, W.J. and Bjarni Jónsson, 2006, “Equivalence ofconsequence operations”,Studia Logica, 83:91–110. doi:10.1007/s11225-006-8299-z
Blok, W.J. and Don Pigozzi, 1986, “Protoalgebraiclogics”,Studia Logica, 45(4): 337–369.doi:10.1007/BF00370269
–––, 1989,Algebraizable logics, (Mem.Amer. Math. Soc., Volume 396), Providence: A.M.S.
–––, 1991, “Local deduction theorems inalgebraic logic”, inAlgebraic Logic (ColloquiaMathematica Societatis János Bolyai: Volume 54), H.Andréka, J.D. Monk, and I. Németi (eds.), Amsterdam:North Holland, 75–109.
–––, 1992, “Algebraic semantics foruniversal Horn logic without equality”, inUniversal Algebraand Quasigroup Theory, Anna B. Romanowska and Jonathan D.H. Smith(eds.). Berlin: Heldermann, 1–56.
Blok, W.J. and Jordi Rebagliato, 2003, “Algebraic semanticsfor deductive systems, ”Studia Logica, Special Issue onAbstract Algebraic Logic, Part II, 74(5): 153–180.doi:10.1023/A:1024626023417
Bloom, Stephen L., 1975, “Some theorems on structuralconsequence operations”,Studia Logica, 34(1):1–9. doi:10.1007/BF02314419
Bou, Félix, Francesc Esteva, Josep Maria Font, ÀngelJ. Gil, Lluís Godo, Antoni Torrens, and Ventura Verdú,2009, “Logics preserving degrees of truth from varieties ofresiduated lattices”,Journal of Logic and Computation,19(6): 1031–1069. doi:10.1093/logcom/exp030
Brown, Donald J. and Roman Suszko, 1973, “Abstractlogics”,Dissertationes Mathematicae: RozprawyMatematyczne, 102: 9–42.
Caleiro, Carlos, Ricardo Gonçalves, and Manuel Martins,2009, “Behavioral algebraization of logics”,StudiaLogica, 91(1): 63–111. doi:10.1007/s11225-009-9163-8
Celani, Sergio and Ramon Jansana, 2003, “A closer look atsome subintuitionistic logics”,Notre Dame Journal of FormalLogic, 42(4): 225–255. doi:10.1305/ndjfl/1063372244
–––, 2005, “Bounded distributive latticeswith strict implication”,Mathematical Logic Quarterly,51: 219–246. doi:10.1002/malq.200410022
Cintula, Petr and Carles Noguera, 2010 “Implicational(semilinear) logics I: a new hierarchy”,Archive forMathematical Logic, 49(4): 417–446.doi:10.1007/s00153-010-0178-7
–––, 2016 “Implicational (semilinear)logics II: additional connectives and characterizations ofsemilinearity”,Archive for Mathematical Logic, 55(3):353–372. doi:10.1007/s00153-015-0452-9
–––, 2021Logic and Implication. AnIntroduction to the General Algebraic Study of Non-classicalLogics (Trends in Logic: Volume 51), Cham: Springer.
Czelakowski, Janusz, 1980, “Reduced products of logicalmatrices”,Studia Logica, 39(1): 19–43.doi:10.1007/BF00373095
–––, 1981, “Equivalential logics, I andII”,Studia Logica, 40(3): 227–236 and 40(4):355–372. doi:10.1007/BF02584057 and doi:10.1007/BF00401654
–––, 2001,Protoalgebraic Logics(Trends in Logic, Studia Logica Library, Volume 10), Dordrecht: KluwerAcademic Publishers.
–––, 2003, “The Suszko operator. PartI”,Studia Logica, 74(1): 181–231.doi:10.1023/A:1024678007488
Czelakowski, Janusz and Ramon Jansana, 2000, “Weaklyalgebraizable logics”,The Journal of Symbolic Logic,65(2): 641–668. doi:10.2307/2586559
Czelakowski, Janusz and Don Pigozzi, 2004a, “Fregeanlogics”,Annals of Pure and Applied Logic, 127:17–76. doi:10.1016/j.apal.2003.11.008
–––, 2004b, “Fregean logics with themultiterm deduction theorem and their algebraization”,Studia Logica, 78: 171–212.doi:10.1007/s11225-005-1212-3
Dunn, J. Michael, 1995, “Positive Modal Logic”,Studia Logica, 55(2): 301–317.doi:10.1007/BF01061239
Dunn, J. Michael and Gary M. Hardegree, 2001,Algebraicmethods in philosophical logic (Oxford Logic Guides, OxfordScience Publications, Volume 41), New York: Oxford UniversityPress.
Font, Josep Maria, 1997, “Belnap’s four-valued logicand De Morgan lattices”,Logic Journal of the I.G.P.L,5: 413–440.
–––, 2016,Abstract Algebraic Logic. AnIntroductory Textbook, volume 60 ofStudies in Logic,London: College Publications.
–––, 2022, “Abstract AlgebraicLogic.”, inHiroakira Ono on Residuated Lattices andSubstructural Logics, Nikolaos Galatos and K. Terui (eds), seriesOutstanding Contributions to Logic 23, Springer. 72pp. doi:10.1007/978-3-030-76920-8
Font, Josep Maria and Ramon Jansana, 1996,A general algebraicsemantics for sentential logics (Lecture Notes in Logic: Volume7), Dordrecht: Springer; 2nd revised edition, Cambridge: CambridgeUniversity Press, 2016 (for the Association for Symbolic Logic).
Font, Josep Maria, Ramon Jansana, and Don Pigozzi 2003, “ASurvey of Abstract Algebraic Logic”,Studia Logica, 74(Special Issue on Abstract Algebraic Logic—Part II):13–97. doi:10.1023/A:1024621922509
Font, Josep Maria and Gonzalo Rodríguez, 1990, “Noteon algebraic models for relevance logic”,Mathematical LogicQuarterly, 36(6): 535–540.doi:10.1002/malq.19900360606
–––, 1994, “Algebraic study of twodeductive systems of relevance logic”,Notre Dame Journal ofFormal Logic, 35: 369–397.doi:10.1305/ndjfl/1040511344
Font, Josep Maria and V. Verdú, 1991, “Algebraiclogic for classical conjunction and disjunction”,StudiaLogica, 65 (Special Issue on Abstract Algebraic Logic):391–419. doi:10.1007/BF01053070
Galatos, Nikolaos and Constantine Tsinakis, 2009,“Equivalence of consequence relations: an order-theoretic andcategorical perspective”,The Journal of SymbolicLogic, 74(3): 780–810. doi:10.2178/jsl/1245158085
Galatos, Nikolaos and José Gil-Férez, 2017,“Modules over quataloids: Applications to the isomorphismproblem in algebraic logic and \(\pi\)-institutions”,Journal of Pure and Applied Algebra, 221(1): 1–24.doi:10.1016/j.jpaa.2016.05.012
Gil-Férez, José, 2006, “Multi-term\(\pi\)-institutions and their equivalence”,MathematicalLogic Quarterly, 52(5): 505–526.doi:10.1002/malq.200610010
–––, 2011, “Representations of structuralclosure operators”,Archive for Mathematical Logic,50:45–73. doi:10.1007/s00153-010-0201-z
Herrmann, Bughard, 1996, “Equivalential and algebraizablelogics”,Studia Logica, 57(2): 419–436.doi:10.1007/BF00370843
–––, 1997, “Characterizing equivalentialand algebraizable logics by the Leibniz operator”,StudiaLogica, 58(2): 305–323. doi:10.1023/A:1004979825733
Heyting, Arend, 1930, “Die formalen Reglen derIntuitionionischen Logik” (in 3 parts),Sitzungsberichte derpreussischen Akademie von Wissenschaften, 42–56,57–71, 158–169.
Hoogland, Eva, 2000, “Algebraic characterizations of variousBeth definability properties”,Studia Logica, 65(Special Issue on Abstract Algebraic Logic. Part I): 91–112.doi:10.1023/A:1005295109904
Humberstone, Lloyd, 2005, “Logical Discrimination”, inJ.-Y. Béziau (ed.),Logica Universalis, Basel:Birkhäuser. doi:10.1007/3-7643-7304-0_12
Jansana, Ramon, 2002, “Full models for positive modallogic”,Mathematical Logic Quarterly, 48(3):427–445.doi:10.1002/1521-3870(200204)48:3<427::AID-MALQ427>3.0.CO;2-T
–––, 2005, “Selfextensional logics withimplication”, in J.-Y. Béziau (ed.),LogicaUniversalis, Basel: Birkhäuser.doi:10.1007/3-7643-7304-0_4
–––, 2006, “Selfextensional logics withconjunction”,Studia Logica, 84(1): 63–104.doi:10.1007/s11225-006-9003-z
Jansana, Ramon and Alessandra Palmigiano, 2006, “Referentialalgebras: duality and applications”,Reports on MathematicalLogic (Special issue in memory of Willem Blok), 41: 63–93. [Jansana and Palmigiano 2006 available online]
Koslow, Arnold, 1992,A structuralist theory of logic,Cambridge: Cambridge University Press.doi:10.1017/CBO9780511609206
Kracht, Marcus, 2006, “Modal Consequence Relations”,in Blackburn, van Benthem, and Wolter 2006: 497–549.
Lávička, Tomáš, Tommaso Moraschini and JamesRaftery, 2021, “The algebraic significance of weak excludedmiddle laws”,Mathematical Logic Quarterly, 68(1):79–94.
Lewis, Clarence Irving, 1918,A Survey of Symbolic Logic,Berkeley: University of California Press; second edition, New YorkDover Publications, 1960.
Lewis, Clarence Irving and Langford, Cooper H., 1932SymbolicLogic, second edition, New York: Dover Publications, 1959.
Łoś, Jerzy, 1949,O matrycach logicznych, Ser.B. Prace Wrocławskiego Towarzystwa Naukowege (Travaux de laSociété et des Lettres de Wrocław), Volume 19.
Łoś, Jerzy and Roman Suszko, 1958, “Remarks onsentential logics”,Indagationes Mathematicae(Proceedings), 61: 177–183.doi:10.1016/S1385-7258(58)50024-9
Łukasiewicz, J. and Alfred Tarski, 1930,“Untersuchungen über den Aussagenkalkül”,Comptes Rendus des Séances de la Société desSciences et des Lettres de Varsovie, Cl.III 23: 30–50.English translation in Tarski 1983: “Investigations into thesentential calculus”.
Malinowski, Jacek, 1990, “The deduction theorem for quantumlogic, some negative results”,The Journal of SymbolicLogic, 55(2): 615–625. doi:10.2307/2274651
McKinsey, J.C.C., 1941, “A solution of the decision problemfor the Lewis systems S2 and S4, with an application totopology”,The Journal of Symbolic Logic, 6(4):117–134. doi:10.2307/2267105
McKinsey, J.C.C. and Alfred Tarski, 1948, “Some theoremsabout the sentential calculi of Lewis and Heyting”,TheJournal of Symbolic Logic, 13(1): 1–15.doi:10.2307/2268135
Moraschini, T., forthcoming, “On equational completenesstheorems ”,The Journal of Symbolic Logic, first online13 September 2021. doi:10.1017/jsl.2021.67
Pigozzi, Don, 1991, “Fregean algebraic logic”, in H.Andréka, J.D. Monk, and I. Németi (eds.),AlgebraicLogic (Colloq. Math. Soc. János Bolyai, Volume 54),Amsterdam: North-Holland, 473-502.
Prucnal, Tadeusz and Andrzej Wroński, 1974, “Analgebraic characterization of the notion of structuralcompleteness”,Bulletin of the Section of Logic, 3(1):30–33.
Raftery, James G., 2006a, “Correspondence between Gentzenand Hilbert systems”,The Journal of Symbolic Logic,71(3): 903–957. doi:10.2178/jsl/1154698583
–––, 2006b, “On the equationaldefinability of truth predicates”,Reports on MathematicalLogic (Special issue in memory of Willem Blok), 41: 95–149. [Raftery 2006b available online]
–––, 2011, “Contextual deductiontheorems”,Studia Logica (Special issue in honor ofRyszard Wójcicki), 99: 279–319.doi:10.1007/s11225-011-9353-z
–––, 2013, “Inconsistency lemmas inalgebraic logic”,Mathematical Logic Quarterly, 59(6):393–406. doi:10.1002/malq.201200020
–––, 2016, “Admissible rules and theLeibniz Hierarchy”,Notre Dame Journal of Formal Logic,57: 569–606.
Rasiowa, H., 1974,An algebraic approach to non-classicallogics (Studies in Logic and the Foundations of Mathematics,Volume 78), Amsterdam: North-Holland.
Schroeder-Heister, Peter and Kosta Dośen (eds), 1993,Substructural Logics (Studies in Logic and Computation:Volume 2), Oxford: Oxford University Press.
Suszko, Roman, 1977, “Congruences in sententialcalculus”, inA report from the Autumn School of Logic(Miedzygorze, Poland, November 21–29, 1977). Mimeographed notes,edited and compiled by J. Zygmunt and G. Malinowski. Restricteddistribution.
Tarski, Alfred, 1930a, “Über einige fundamentaleBegriffe der Metamathematik”,C. R. Soc. Sci. Lettr.Varsovie, Cl. III 23: 22–29. English translation in Tarski1983: “On some fundamental concepts of metamathematics”,30–37.
–––, 1930b, “Fundamentale Begriffe derMethodologie der deduktiven Wissenschaften I”,Monatfsheftefür Mathematik und Physik, 37: 361–404. Englishtranslation in Tarski 1983: “Fundamental concepts of themethodology of the deductive sciences”, 60–109.
–––, 1935, “Grundzüge derSystemenkalküls. Erster Teil”,FundamentaMathematicae, 25: 503–526, 1935. English translation inTarski 1983: “Foundations of the calculus of systems”,342–383.
–––, 1936, “Grundzüge derSystemenkalküls. Zweiter Teil”,FundamentaMathematicae, 26: 283–301, 1936. English translation inTarski 1983: “Foundations of the calculus of systems”,342–383.
–––, 1983,Logic, Semantics,Metamathematics. Papers from 1923 to 1938, J. Corcoran (ed.),Indianapolis: Hackett, second edition.
Torrens, Antoni, 2008, “An Approach to Glivenko’sTheorems in Algebraizable Logics”,Studia Logica,88(3): 349–383. doi:10.1007/s11225-008-9109-6
Troelstra, A.S., 1992,Lectures on Linear Logic (CSLILecture Notes 29), Stanford, CA: CSLI Publications.
Visser, Albert, 1981, “A Propositional Logic with ExplicitFixed Points”,Studia Logica, 40(2): 155–175. APropositional Logic with Explicit Fixed Points
Voutsadakis, George, 2002, “Categorical Abstract AlgebraicLogic: Algebraizable Institutions”,Applied CategoricalStructures, 10: 531–568. doi:10.1023/A:1020990419514
Wójcicki, Ryszard, 1969, “Logical matrices stronglyadequate for structural sentential calculi”,Bulletin del’Académie Polonaise des Sciences, Classe III XVII:333–335.
–––, 1973, “Matrix approach in themethodology of sentential calculi”,Studia Logica,32(1): 7–37. doi:10.1007/BF02123806
–––, 1988,Theory of logical calculi. Basictheory of consequence operations (Synthese Library, Volum 199),Dordrecht: D. Reidel.

Academic Tools

How to cite this entry.
Preview the PDF version of this entry at theFriends of the SEP Society.
Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO).
Enhanced bibliography for this entryatPhilPapers, with links to its database.

Other Internet Resources

Blok, Willem and Don Pigozzi, 1997, “Abstract algebraic logic and the deduction theorem,” (in PDF), unpublished manuscript.

Open access to the SEP is made possible by a world-wide funding initiative.
The Encyclopedia Now Needs Your Support
Please Read How You Can Help Keep the Encyclopedia Free

Browse

About

Support SEP

Mirror Sites

View this site from another server:

USA (Main Site)Philosophy, Stanford University

Info about mirror sites

Library of Congress Catalog Data: ISSN 1095-5054

	How to cite this entry.
	Preview the PDF version of this entry at theFriends of the SEP Society.
	Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO).
	Enhanced bibliography for this entryatPhilPapers, with links to its database.

Movatterモバイル変換

Algebraic Propositional Logic

1. Abstract consequence relations

2. Logics as consequence relations

3. Some examples of logics

3.1 Classical propositional logic

3.2 Intuitionistic propositional logic

Axioms:

Rule of inference

3.3 Local Normal Modal logics

3.4 Global Normal Modal logics

3.5 Intuitionistic Linear Logic without exponentials

Axioms:

Rules of inference:

3.6 The system \(\bR\) of Relevance Logic

4. Algebras

4.1 Some concepts of universal algebra and model theory

4.2 Varieties and quasivarieties

5. Algebraic semantics

6. Logical matrices

7. The Lindenbaum-Tarski method for proving algebraic completeness theorems

8. The natural class of algebras of a logic system

9. When a logic is algebraizable and what does this mean?

10. A classification of logics

11. Replacement principles

12. Beyond protoalgebraic logics

12.1 The logic of conjunction and disjunction

12.2 Positive Modal Logic

12.3 Visser’s subintuitionistic logic

12.4 The strict implication fragment of the local modal logiclK

13. Abstract logics and generalized matrices

14. The Frege hierarchy

15. Extending the setting

Bibliography

Academic Tools

Other Internet Resources

Related Entries

Browse

About

Support SEP

Mirror Sites