# Propositional Consequence Relations and Algebraic Logic

*First published Tue Dec 19, 2006; substantive revision Sun Jan 30, 2011*

George Boole was the first to present logic as a mathematical theory in algebraic style. In his work, and in that of the other algebraists of the algebraic tradition of logic of the nineteenth century the distinction between a formal language and a mathematically rigorous semantics for it was still not drawn. What the algebraists in this tradition did was to build algebraic theories (of Boolean algebras, and relation algebras) with among other interpretations a logical one.

The works of Frege and Russell introduced a different perspective on
the way to approach logic. In those works a logic system was given by
a formal language and a deductive calculus, namely a set of axioms and
a set of inference rules. Let us call such a pair a *logical
deduction system*, and the formulas derivable in the calculus the
*theorems* of the system (nowadays it is common practice to refer to
this kind of calculi as Hilbert style calculi). In Frege and
Russell's approach a formal (mathematical) semantics of whatever kind
(algebraic, model-theoretic, etc.) for the formal languages they used
was lacking. The only semantics present was of an intuitive informal
kind.

The systems introduced by Frege and Russell were systems of classical logic, but soon after systems of non-classical logics were considered by other logicians. The first influential attempts to introduce logics different from classical logic remained within the Frege-Russell tradition of presenting a logical deduction system without any formal semantics. They include the first modal systems of C.I. Lewis (1918) and the axiomatization of intuitionistic logic by Heyting (1930).

The idea underlying the design of Frege and Russell's logical deduction systems is that the theorems should be the formulas that correspond (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 logics that were to be designed following in the footsteps of the first modal systems of C.I. Lewis. This situation influenced the way in which the research on some non-classical logics has usually been presented and sometimes also its real evolution. However the concept of logical consequence has been the one that logic has traditionally dealt with. Tarski put it once again into the center of modern logic, both semantically and syntactically. Nowadays, a general theory of the algebraization of logics around the concept of logical consequence has grown from the different algebraic treatments of the different logics obtained during the last century.

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

It was only in the 1920s that algebras and logical matrices (an algebra plus a set of designated elements) started to be taken as models of logical deduction systems, that is, as providing a formal semantics for logical formal languages. Moreover, they were also used to define sets of formulas with similar properties to the ones the sets of theorems of the known logical deduction systems have, in particular the property of being closed under substitution instances and more recently logical matrices have also been used to define logics as consequence relations.

Algebraic logic can be described in very general terms as the discipline that studies logics by associating with them classes of algebras, classes of logical matrices and other algebra related mathematical structures and that relates the properties of logics with algebraic properties of the associated algebras (or algebra related structures), so that the understanding of these algebras can be used to better understand the logic at hand.

From the algebraic study of specific logics a general theory of the algebraization of logics slowly emerged during the last century with the aim, more or less explicitly stated during the process, of obtaining general and informative results relating the properties a logic may have with the algebraic properties the class of algebras (or algebra related structures) associated with it might posses. Those algebraic studies assumed somehow an implicit conception of what is the process by which to associate with any given logic a class of algebras as its natural class. The development of the general theory speeded up and consolidated at the beginning of the 1980s with the introduction of the notion of algebraizable logic, and at that time the assumptions about the class of algebras that deserve to be taken as the natural to associate with a given logic started to be made more and more explicit.

In this entry we concentrate on the general theory of the algebraization of propositional logics taken as consequence relations. This theory is known as Abstract Algebraic Logic (AAL).

- 1. Abstract consequence relations
- 2. Logics as consequence relations: logic systems
- 3. Some examples of logics
- 4. Algebras
- 5. Algebraic semantics
- 6. Logical matrices
- 7. The Lindenbaum-Tarski method
- 8. When is a logic algebraizable and what does this mean
- 9. The class of algebras of a logic system
- 10. A classification of logics
- 11. Replacement principles
- 12. Beyond protoalgebraic logics
- 13. Abstract logics and generalized matrices
- 14. Extending the setting
- Bibliography
- Academic Tools
- Other Internet Resources
- Related Entries

## 1. Abstract consequence relations

Tarski's work (1930a, 1930b, 1935, 1936) on the methodology of the deductive sciences of the 1920s and 1930s studies the axiomatic method abstractly and introduces for the first time the abstract concept of consequence operation. Tarski had in mind mainly the different mathematical axiomatic theories. On these theories the sentences that are proved from the axioms are consequences of them but (of course) almost all of them are not logical truths, and under a suitable formalization of these theories a logical calculus like Frege's or Russell's can be used to derive the consequences of the axioms. Tarski set the framework to study the most general properties of the operation that assigns to a set of axioms its consequences.

Given a logical deduction system *H* and an arbitrary set
*X* of formulas, a formula *a* is *deducible*
from *X* if there is a finite sequence of formulas any one of
which belongs to *X* or is an axiom of *H* or is
obtained from previous formulas in the sequence by one of the
inference rules of *H*. Such a sequence is a deduction (or
proof) of *a* with premises or hypotheses in *X*. Let
*Cn*(*X*) be the set of formulas deducible from the
formulas in *X* taken as premises or hypothesis by means of the
axioms and rules of the calculus. This set is called the set of
consequences of *X* (relative to the logical deduction system).
*Cn* is then an operation that is applied to sets of formulas
to obtain new sets of formulas. It has the following properties: For
every set *X* of formulas

*X*⊆*Cn*(*X*)*Cn*(*Cn*(*X*)) =*Cn*(*X*)*Cn*(*X*) = ∪{*Cn*(*Y*):*Y*⊆*X*,*Y*finite}

Clause 3 stipulates that *Cn*(*X*) is equal to the
union of the set of formulas derivable from finite subsets of
*X*. Tarski took these properties to define axiomatically the notion of
consequence operation. 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 finite or of the
cardinality of the natural numbers. Condition (3) implies the weaker,
and important, condition of monotonicity

- if
*X*⊆*Y*⊆*A*, then*Cn*(*X*) ⊆*Cn*(*Y*).

To encompass the whole class of logic systems one finds in the
literature, a slightly more general definition than Tarski's is
required. We will say that an *abstract consequence operation*
*C* on an arbitrary set *A* is an operation that applied
to subsets of *A* gives subsets of *A* and for all
*X*, *Y* ⊆ *A* satisfies conditions (1), (2)
and (4) above. If in addition *C* satisfies (3) we say that it
is a *finitary consequence operation*.

Consequence operations are present not only in logic but in many
areas of mathematics. Abstract consequence operations are known as
closure operators in universal algebra and lattice theory, for
instance. In topology the operation that sends a subset of a
topological space to its topological closure is a closure operator. In
fact the topologies on a set *A* can be identified with the
closure operators on *A* that satisfy the additional conditions
that *C*(∅) = ∅ and *C*(*X* ∪
*Y*) = *C*(*X*) ∪ *C*(*Y*)
for all *X*, *Y* ⊆ *A*.

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

A different, but mathematically equivalent, (formal) approach
is to consider consequence relations on a set of
formulas instead of consequence operations. A(n) (abstract)
*consequence relation* on the set of formulas of a
formal language is a relation
⊢
between sets of formulas and formulas that satisfies the following
conditions:

- if
*a*∈*X*, then*X*⊢*a* - if
*X*⊢*a*and*X*⊆*Y*, then*Y*⊢*a* - if
*X*⊢*a*and for every*b*∈*X*,*Y*⊢*b*, then*Y*⊢*a*.

It is *finitary* if in addition it satisfies

- if
*X*⊢*a*, then there is a finite set*Y*⊆*X*such that*Y*⊢*a*.

Given a logical deduction system *H* the relation
⊢
defined by *X*
⊢
*a* if *a* is deducible from *X* in *H*
is a finitary consequence relation. Nonetheless we are used not only
to syntactic definitions of consequence relations but also to semantic
definitions. For example we define classical propositional
consequence by means of truth valuations, first-order consequence
relation by means of structures, the intuitionistic consequence
relation by means of Kripke models, etc. Sometimes these
model-theoretic definitions of consequence relations define
non-finitary consequence relations, for example the consequence
relations for infinitary formal languages and the consequence relation
of second-order logic with so-called standard semantics.

In general, an *abstract consequence relation* on
a set *A* is a relation
⊢
between subsets of *A* and elements of *A* that
satisfies conditions (1)–(3) above. If it also satisfies (4) it is
said to be finitary. If
⊢
is an abstract consequence relation and *X*
⊢
*a* we can say that *X* is a set of premises or hypothesis
with conclusion *a* according to
⊢
and that *a*
follows from *X*, or is entailed by X (according to
⊢).
These relations correspond to Koslow's implication structures; see
Koslow 1992 for the closely related but different approach to logics
(in a broad sense) as consequence relations introduced by Koslow.

Consequence operations on a set *A* are in one-to-one
correspondence with consequence relations on *A*. The
move from a consequence operation *C* to a consequence
relation
⊢_{C}
and, conversely, from a consequence relation
⊢
to a consequence operation
*C*_{ ⊢}
is easy and given by the definitions:

X⊢_{C}aiffa∈C(X) anda∈C_{⊢}(X) iffX⊢a.

Moreover, if *C* is finitary, so is
⊢_{C}
and if
⊢
is finitary, so is
*C*_{⊢}.

For a general discussion on logical consequence see the entry on logical consequence.

## 2. Logics as consequence relations

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

One of the main traits of the consequence relations we study in logic
is 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 of sentences *Y*
that share the same form with *a* and *X*, then
*b* also follows from *Y*. In propositional logics this
boils down to saying that if we uniformly replace sub-sentences of the
sentences in *X* ∪ {*a*} by other sentences
obtaining *Y* and *b*, then *b* follows from
*Y*. (The reader can find more information on the idea of
formality in the entry on
logical consequence.)

To turn the idea of the formal character of logics into a rigorous definition we need to introduce the concept of propositional language and the concept of substitution.

A *propositional language* *L* is a set of connectives,
that is, a set of symbols each one of which has an arity *n*
that tells us in case that *n* = 0 that the symbol is a
propositional constant, and in case that *n* > 0 whether the
connective is unary, binary, ternary, etc. For example {∧, ∨,
→, ⊥, ⊤} is the language of several logics, like
classical and intuitionistic, (⊥ and ⊤ are 0-ary and the
other connectives are binary), {¬, ∧, ∨ →, □,
◊} is the language of several modal logics, (¬, □, ◊
are unary and the other connectives binary) and {⊥, 0, ∧,
∨, ∗, ⊤} is the language of many-valued logics and
also of relevance logic and a fragment of linear logic (⊥,
⊤ and 0 are 0-ary and the other connectives are binary).

Given a language *L* and a set of propositional variables
*V* (which does not have elements in common with *L*),
the *formulas* of *L*, or *L*-*formulas*,
are defined inductively as follows:

- Every variable is a formula.
- Every 0-ary symbol is a formula.
- If ∗ is a connective and
*n*> 0 is its arity, then for all formulas φ_{1},…, φ_{n}, ∗φ_{1}…φ_{n}also is a formula.

A *substitution* σ for *L* is a map from the set
of variables *V* to the set of formulas of *L*. It tells
us which formula must replace which variable when we perform the
substitution. If *p* is a variable, σ(*p*)
denotes the formula that the substitution σ assigns to
*p*. The result of applying a substitution σ to a formula
φ is the formula **σ**(φ) obtained from
φ by simultaneously replacing the variables in φ, say
*p*_{1}, … , *p*_{k},
by, respectively, the formulas σ(*p*_{1}),
… , σ(*p*_{k}). In this way a
substitution σ gives a unique map **σ** from
the set of formulas to itself that satisfies

**σ**(*p*) = σ(*p*), for every variable*p*,**σ**(†) = †, for every 0-ary connective †,**σ**(∗φ_{1}…φ_{n}) = ∗**σ**(φ_{1})…**σ**(φ_{n}), for every connective ∗ and formulas φ_{1}, … , φ_{n}, where*n*is the arity of ∗.

A formula ψ is a *substitution instance* of a formula
φ if there is a substitution σ such that when applied to
φ gives ψ, that is, if **σ**(φ) =
ψ.

In order to avoid unnecessary complications we will assume
in the sequel that all the logics use the same set *V* of
variables, so that the definition of formula of *L* depends
only on *L*. A *logic system* (or *logic* for
short) is given by a language *L* and a consequence relation
⊢
on the set of formulas of *L* that is *formal* in the
sense that for every substitution σ, every set of formulas
Γ and every formula φ,

if Γ⊢ φ, thenσ[Γ] ⊢σ(φ)

where **σ**[Γ] is the set of the formulas
obtained by applying the substitution σ to the formulas in
Γ. The consequence relations on the set of formulas of a
language that satisfy this property are called *structural* and
also *substitution-invariant* in the literature. They were
considered for the first time in Łós and Suszko
1958. Tarski only explicitly considered closed sets also closed under
substitution instances for some consequence relations; he never
considered (at least explicitly) the substitution invariance condition
for consequence relations.

We will refer to logic systems by the letter **L**
with possible subindices, and we set
**L** =
< *L*,
⊢_{L}
> and
**L**_{n} =
< *L*_{n},
⊢_{Ln} >
with the understanding that *L* (*L*_{n})
is the language of
**L**
(**L**_{n})
and ⊢_{L}
(⊢_{Ln})
its consequence relation. A logic system
**L** is *finitary* if
⊢_{L}
is a finitary consequence relation.

The consequence relation of a logic system can be given in several ways, some proof-theoretic, others semantic. One can define a substitution-invariant consequence relation by means of a proof system like a Hilbert style axiom system, a Gentzen calculus or a natural deduction style calculus, etc. One can also define a substitution-invariant consequence relation semantically by means of a class of mathematical objects (algebras, Kripke models, topological models, etc.) and a satisfaction relation.

If
**L**_{1} =
< *L*, ⊢_{L1} >
is a logic system with
⊢_{L1}
defined by a proof-system and
**L**_{2} =
< *L*,
⊢_{L2} >
is a logic system over the same language with
⊢_{L2}
defined
semantically, we say that the proof-system used to define
⊢_{L1}
is *sound* for the semantics used to define
⊢_{L2}
if
⊢_{L1}
is included in
⊢_{L2},
namely if Γ
⊢_{L1}
φ implies Γ
⊢_{L2}
φ. If the other inclusion holds the proof-system is said to be
*complete* with respect to the semantics that defines
⊢_{L2},
that is when Γ
⊢_{L2}
φ implies Γ
⊢_{L1}
φ.

A set of formulas Γ is called a *theory* of a logic
system
**L**, or
**L**-theory, if it is closed under
the relation
⊢_{L},
that is, if whenever Γ
⊢_{L}
φ it also holds that φ ∈ Γ. In other words, the theories of
**L**
are the closed sets of the consequence operation
*C*_{⊢L}
on the set of *L*-formulas. In order to simplify the notation we denote this consequence operation by
*C*_{L}.
A formula φ is a *theorem* (or validity) of
**L**
if ∅
⊢_{L}
φ. *C*_{L}(∅) is the
set of theorems of
**L**
and is the least theory of
**L**.
The set of all theories of
**L**
will be denoted by
Th(**L**).

Given a logic
**L**,
the consequence operation
*C*_{L}
is substitution-invariant, which means that for every Γ and
every substitution σ,
**σ**[*C*(Γ)] ⊆
*C*(**σ**[Γ]). Moreover, for every
theory *T* of
**L**
we have a new consequence operation defined as follows:

C_{L}^{T}(Γ) =C_{L}(T∪ Γ)

that is,
*C*_{L}^{T}(Γ)
is the set of formulas that follow from Γ and *T*
according to
**L**.
It turns out that *T* is closed under substitutions if and
only if
*C*_{L}^{T}
is substitution-invariant.

If
**L**
is a logic and Γ, Δ are sets of
sentences, we will use the notation
Γ⊢_{ L }
Δ to state that for every ψ ∈ Δ,
Γ
⊢_{L}
ψ. Thus Γ
⊢_{L}
Δ if and only if Δ ⊆
*C*_{L}(Γ).

If **L**
=
< *L*,
⊢_{L}
>
is a logic system and
*L*′ ⊆ *L*, the *L*′-*fragment*
of **L** is the logic system
**L**′ =
< *L*′,
⊢_{L′}
> whose language is *L*′ (hence all the
*L*′-formulas are *L*-formulas) and whose
consequence relation is defined by

Γ ⊢_{L′}φ iff Γ ⊢_{L}φ,

for every set of *L*′-formulas Γ and every
*L*′-formula φ.

## 3. Some examples of logics

We give some examples of logic systems that we will refer to in the course of this essay, which are assembled here for the reader's convenience. Whenever possible we refer to the corresponding entries.

We use the standard convention of writing (φ ∗ ψ) instead of ∗φψ for binary connectives and omit the external parenthesis in the formulas.

### 3.1 Classical propositional logic

We take the language of classical propositional logic to be the set
*L _{c}* = {∧, ∨, →, ⊤, ⊥}. We
assume the consequence relation defined by the usual truth-table
method (⊤ is interpreted as

`true`

and ⊥ as
`false`

), soΓ ⊢_{CPL}φ iff every truth valuation that assigns`true`

to all ψ ∈ Γ assigns`true`

to φ.

The formulas φ such that ∅
⊢_{CPL}
φ are the *tautologies*. For more information, see the
entry on
classical logic

### 3.2 Intuitionistic propositional logic

We take the language of Intuitionistic propositional logic to be the set {∧, ∨, →, ⊤, ⊥}. The consequence relation is defined by the following Hilbert-style calculus.

#### Axioms:

C0. ⊤ C1. φ → (ψ → φ) C2. φ → (ψ → (φ ∧ ψ)) C3. (φ ∧ ψ) → φ C4. (φ ∧ ψ) → ψ C5. φ → (φ ∨ ψ) C6. ψ → (φ ∨ ψ) C7. (φ ∨ ψ) → ((φ → δ) → ((ψ →δ) →δ))C8. (φ → ψ) → ((φ → (ψ → δ)) → (φ →δ))C9. ⊥ → φ

#### Rule of inference

φ, φ → ψ / ψ (Modus Ponens)

For more information, see the entry on intuitionistic logic

### 3.3 Local Normal Modal logics

The language of modal logic we consider here is the set
*L _{m}* = {∧, ∨, →, ¬, □,
⊤, ⊥}. 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. A normal modal logic is a set
Λ of formulas of

*L*which contains all the tautologies of the language of classical logic, the formulas of the form

_{m}□(φ → ψ) → (□ φ → □ ψ)

and is closed under the rules

φ, φ → ψ / ψ (Modus Ponens)

φ / □ φ (Modal Generalization)

φ /

σ(φ) for every substitution σ (Substitution)

The least normal modal logic is called *K* and can be
axiomatized by the Hilbert calculus that contains as axioms the
tautologies of classical logic and the formulas □(φ →
ψ) → (□ φ → □ ψ) and as rules of
inference Modus Ponens, Modal Generalization and Substitution.

With a normal modal logic Λ it is associated the consequence
relation defined by the calculus that takes as axioms all the formulas
in Λ and as the only rule of inference Modus Ponens. The logic
system given by this consequence relation is called the *local
consequence* of Λ. We denote it by
**lΛ**.
Its theorems are the elements of Λ. It holds that

Γ ⊢_{ lΛ}φ iff φ ∈ Λ or there are φ_{1}, … , φ_{n}∈ Γ such that (φ_{1}∧ … ∧ φ_{n}) → φ ∈ Λ.

### 3.4 Global Normal Modal logics

Another consequence relation is associated with each normal modal
logic Λ. It is defined by the calculus that has as axioms the
formulas of Λ and as rules of inference Modus Ponens and Modal
Generalization. The logic system given by this consequence relation is
called the *global consequence* of Λ and will be denoted by
**gΛ**.
It has the same theorems as the local
**lΛ**,
namely the elements of Λ. The difference between
**lΛ**
and
**gΛ**
lies in the consequences they allow to draw from
nonempty sets of premises. This difference has an enormous
effect on their algebraic behaviour.

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

### 3.5 Intuitionistic Linear Logic without exponentials

We take as the language of Intuitionistic Linear Logic without
exponentials the set {∧, ∨, →, ∗, 0, 1, ⊤,
⊥}. We denote the logic by **ILL**. The axioms and
rule of inference below provide a Hilbert-style axiomatization of this
logic.

#### Axioms:

L1. 1 L2. (φ → ψ) → (ψ → δ) → (φ →δ))L3. (φ → (ψ → δ)) → (ψ → (φ →δ))L4. φ → (ψ → (φ ∗ ψ)) L5. (φ → (ψ → δ)) → ((φ ∗ ψ) →δ)L6. (φ → ψ) → (ψ → δ) → (φ →δ))L7. 1 → (φ → φ)) L8. (φ ∧ ψ) → φ L9. (φ ∧ ψ) → ψ L10. (φ ∧ ψ) → φ L11. ψ → (φ ∨ ψ) L12. φ → (φ ∨ ψ) L13. ((φ → ψ) ∧ (ψ → δ)) → (φ → (ψ ∧δ))L14. ((φ → δ) ∧ (ψ →δ)) → ((φ ∨ ψ) →δ)L15. φ → ⊤ L16. ⊥ → ψ

#### Rules of inference:

φ, φ → ψ / ψ (Modus Ponens)

φ, ψ / φ ∗ ψ (Adjunction)

The 0-ary connective 0 is used to define a negation by ¬ φ := φ → 0. No specific axiom schema deals with 0.

For more information, see the entry on linear logic

### 3.6 The system **R** of Relevance Logic

The language is the set {∧, ∨, →, ∗, 0}.
A Hilbert style axiomatization for
**R**
can be given by the
rules of Intuitionistic Linear Logic without exponentials
and the axioms L1-L4 of this logic plus the axioms

1. (φ → (φ → ψ)) → (φ → ψ) 2. (φ ∧ (ψ ∨ δ)) → ((φ ∧ ψ) ∨ φ ∧δ))3. ((φ ∨ ψ) ∧ (φ ∨ δ)) → (φ ∨ (ψ ∧δ))4. ¬ ¬ φ → φ

Negation is defined as in Intuitionistic Linear Logic without exponentials.

For more information, see the entry on relevance logic.

## 4. Algebras

The algebraic study of a specific logic has to provide first of all the formal language of the logic with an algebraic semantics using a class of algebras whose properties are exploited to understand which properties the logic has. In this section we present how the formal languages of propositional logics are given an algebraic interpretation. In the next section we address the question of what is an algebraic semantics for a logic system.

We start by describing the first two steps involved in the
algebraic study of propositional logics. Both are needed in
order to endow propositional languages with algebraic
interpretations. To expound them we will assume knowledge of
first-order logic (see the entries on
classical logic
and
first-order model theory)
and we will call *algebraic first-order languages*, or simply
*algebraic languages*, the first-order languages with equality and
without any relational symbols, so that these languages have only
operation symbols, if any, among their non-logical symbols.

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

Propositional formulas are terms.

The *first step* consist in looking at the formulas of any
propositional language *L* as the terms of the algebraic
first-order language with *L* as its set of operation symbols.
This means that (i) every connective of *L* of arity *n*
is taken as an operation symbol of arity *n* and that (ii) the
propositional formulas of *L* are taken as the terms of this
first-order language. From this point of view the definition of
*L*-formula is exactly the definition of *L*-term. We
will refer to the algebraic language with *L* as its set of
operation symbols as the *L*-*algebraic language*.

The *second step* is to interpret the propositional formulas
in the same manner in which terms of a first-order language are interpreted in
a structure. In this way the concept of *L*-algebra comes into
play. On a given set *A*, an *n*-ary connective is
interpreted by a *n*-ary function on *A* (a map that
assigns an element of *A* to every sequence <
*a*_{1}, … , *a*_{n}>
of elements of *A*). This procedure is a generalization of the
truth-table interpretations of the languages of logic systems like
classical logic and Łukasiewicz and Post's finite-valued
logics. In those cases, given the set of truth-values at play the
function that interprets a connective is given by its truth-table.

A way to introduce algebras is as the models of some algebraic
first-order language. We follow an equivalent route and give the
definition of algebra using the setting of propositional languages.
Let *L* be a propositional language. An *algebra*
**A** of type *L*, or *L*-algebra for
short, is a set *A*, called the carrier of **A**,
together with a function ∗^{A} on
*A* of the arity of ∗, for every connective ∗ in
*L* (if ∗ is 0-ary,
∗^{A} is an element of *A*). A
*valuation* on an algebra **A** is a map
*v* from the set of variables into its carrier
*A*. Algebras together with valuations are used to interpret in
a compositional way the formulas of *L*, assuming that a
connective ∗ of *L* is interpreted in an
*L*-algebra **A** by the function
∗^{A}. Let **A** be an
algebra of type *L* and *v* a valuation on
**A**. The value of a compound formula
∗φ_{1}…φ_{n}
is computed by applying the function
∗^{A} that interprets ∗ in
**A** to the previously computed values
** v**(φ

_{1}), … ,

**(φ**

*v*_{n}) of the formulas φ

_{1},… ,φ

_{n}. Precisely speaking the value

**(φ) of a formula φ is defined inductively as follows:**

*v*(*v**p*) =*v*(*p*), for each variable*p*,(†) = †*v*^{A}, if † is a 0-ary connective(∗φ*v*_{1}…φ_{n}) = ∗^{A}((φ*v*_{1}), …,(φ*v*_{n})), if ∗ is a*n*-ary (*n*> 0) connective.

In fact, the value of a formula under a valuation depends only on the
propositional variables that actually appear in the
formula. Accordingly, if φ is a formula we use the notation
φ(*p*_{1}, …,
*p*_{n}) to indicate that the variables that
appear in φ are in the list *p*_{1}, …,
*p*_{n}, and given elements
*a*_{1}, …, *a*_{n} of
an algebra **A** by
φ^{A}[*a*_{1}, …,
*a*_{n}] we refer to the value of
φ(*p*_{1}, …,
*p*_{n}) under any valuation *v* on
**A** such that *v*(*p*_{1}) =
*a*_{1}, …,
*v*(*p*_{n}) =
*a*_{n}.

A third and fundamental step in the algebraic study of logics is to
turn the set of formulas of a language *L* into an algebra, the
*algebra of formulas* of *L*, denoted by
**Fm**_{L}. This algebra has the set of
*L*-formulas as carrier and the operations are defined as
follows. For every *n*-ary connective ∗ with *n*
> 0, the function
∗^{FmL} is the map
that sends each tuple of formulas (φ_{1}, …,
φ_{n}) (where *n* is the arity of
∗) to the formula
∗φ_{1}…φ_{n}, and for
every 0-ary connective †,
†^{FmL} is
†. If no confusion is likely we suppress the subindex
in **Fm**_{L} and
write **Fm** instead.

### 4.1 Some concepts of universal algebra and model theory

Algebras are a particular type of structure or model. An
*L*-algebra is a structure or model for the *L*-algebraic
first-order language. Therefore the concepts of model
theory for the first-order languages apply to them (see the entries
on
classical logic
and
first-order model theory).
We need some of these concepts. They are also used in universal
algebra, a field that to some extent can be considered the model
theory of the algebraic languages. We introduce the definitions of the
concepts we need.

Given an algebra **A** of type *L*, a
*congruence* of **A** is an equivalence relation
θ on the carrier of **A** that satisfies
for every *n*-ary connective ∗ ∈ *L* the
following compatibility property: for every *a*_{1},
…, *a*_{n}, *b*_{1},
…, *b*_{n} ∈ A,

ifa_{1}θb_{1}, …,a_{n}θb_{1}, then ∗^{A}(a_{1},…,a_{n}) θ ∗^{A}(b_{1},…,b_{n}).

Given a congruence θ of **A** we can reduce the
algebra by identifying the elements which are related by θ. The
algebra obtained is the *quotient algebra* of
**A** modulo θ. It is denoted by
**A**/θ, its carrier is the set A/θ of
equivalence classes [*a*] of the elements *a* of
*A* modulo the equivalence relation θ, and the operations
are defined as follows

- †
^{A/θ}= [†^{A}], for every 0-ary connective †, - ∗
^{A/θ}([*a*_{1}], …, [*a*_{n}]) = [∗^{A}(*a*_{1},…,*a*_{n})], for every connective ∗ whose arity is*n*and*n*> 0.

The compatibility property ensures that the definition is sound.

Let **A** and **B** be
*L*-algebras. A *homomorphism* *h* from
**A** to **B** is a map *h* from
*A* to *B* such that for every 0-ary symbol †
∈ *L* and every *n*-ary connective ∗ ∈
*L*

h(†^{A}) = †^{B}

h(∗^{A}(a_{1},…,a_{n})) = ∗^{B}(h(b_{1}),…,h(b_{n})), for alla_{1}, …,a_{n}∈ A.

We say that **B** is a *homomorphic image* of
**A** if there is a homomorphism from **A**
to **B** which is an onto map from *A* to
*B*.

Let **A** and **B** be
*L*-algebras. **A** is a *subalgebra* of
**B** if (1) *A* ⊆ *B*, (2) the
interpretations of the 0-ary symbols of *L* in
**B** belong to *A* and *A* is closed under
the functions of **B** that interpret the non 0-ary
symbols, and (3) the interpretations of the 0-ary symbols
in **A** coincide with their interpretations in
**B** and the interpretations on **A** of
the other symbols in *L* are the restrictions to
**A** of their interpretations in **B**.

We refer the reader to the entry on first-order model theory for the notions of direct product (called product there) and ultraproduct.

### 4.2 Varieties and quasivarieties

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

A variety of *L*-algebras is a class of *L*-algebras
that is definable in a very simple way (by equations) using the
*L*-algebraic language. An *L*-*equation* is a
formula φ ≈ ψ where φ and ψ are terms of the
*L*-algebraic language (that is, *L*-formulas if we take
the propositional logics point of view). An equation φ ≈
ψ is *valid* in an algebra **A**, or
**A** is a *model* of φ ≈ ψ, if for
every valuation *v* on **A**,
** v**(φ) =

**(ψ). This is exactly the same as to saying that the universal closure of φ ≈ ψ is a sentence true in**

*v***A**according to the usual semantics for first-order logic with equality. A

*variety*of

*L*-algebras is a class of

*L*-algebras which is the class of all the models of some set of

*L*-equations.

Quasivarieties of *L*-algebras are classes of *L*-algebras
definable using the *L*-algebraic language in a slightly more
complex way than in varieties. A *proper L-quasiequation*
is a formula of the form

∧_{i ≤ n}φ_{i}≈ ψ_{i}→ φ ≈ ψ.

An *L*-*quasiequation* is a formula of the above form
but possibly with an empty antecedent, in which case it is just the
equation φ ≈ ψ. Hence, the *L*-quasiequations are
the proper *L*-quasiequations and the *L*-equations. An
*L*-quasiequation is *valid* in an *L*-algebra
**A**, or the algebra is a model of it, if the universal
closure of the quasiequation is true in **A**. A
*quasivariety* of *L*-algebras is a class of algebras
which is the class of the models of some set of
*L*-quasiequations. Since equations are quasiequations, each
variety is a quasivariety. The converse is false.

Varieties and quasivarieties can be characterized by the closure
properties they enjoy. A class of *L*-algebras is a variety if
and only if it is closed under subalgebras, direct products and
homomorphic images. The variety generated by a class
**K** of *L*-algebras is the least class of
*L*-algebras that includes **K** and is closed
under subalgebras, direct products and homomorphic images. It is also
the class of the algebras that are models of the equations valid in
**K**. For example, the variety generated by the algebra
of the two truth-values for classical logic is the class of Boolean
algebras. If we restrict that algebra to the operations for
conjunction and disjunction only, it generates the variety of
distributive lattices and if we restrict it to the operations for
conjunction and disjunction and the interpretations of ⊤ and
⊥, it generates the variety of bounded distributive lattices.

A class of *L*-algebras is a quasivariety if and only if it is
closed under subalgebras, direct products and ultraproducts. The
quasivariety generated by a class **K** of
*L*-algebras is the least class of *L*-algebras that
includes **K** and is closed under subalgebras, direct
products and ultraproducts.

An SP-*class* of *L*-algebras is a class of
*L*-algebras closed under subalgebras and direct products. Thus
quasivarieties and varieties are all SP-classes. The SP-class
generated by a class **K** of *L*-algebras is the
least class of *L*-algebras that includes **K**
and is closed under subalgebras and direct products.

## 5. Algebraic semantics

The term ‘algebraic semantics’ was (and many times still is) used in the literature in a loose way. To provide a logic with an algebraic semantics was to interpret its language in a class of algebras, define a notion of satisfaction of a formula in an algebra of the class and prove a soundness and completeness theorem, usually for the theorems of the logic only. Nowadays there is a precise concept of algebraic semantics for a logic system. It was introduced by Blok and Pigozzi in Blok & Pigozzi 1989. In it we find a general way to state in mathematically precise terms what is common to the many cases of purported algebraic semantics for specific logic systems found in the literature. We expose the notion in this section. To motivate the definition we discuss several examples first, stressing what is common to all of them. The reader does not need to know about the classes of algebras that provide algebraic semantics we refer to in the examples. Its existence is what is important.

The prototypical examples of algebraic semantics for propositional
logics are the class **BA** of
Boolean algebras,
which is the algebraic
semantics for classical logic, and the class **HA** of
Heyting algebras, which is the algebraic semantics for
intuitionistic logic.
Every Boolean algebra and every Heyting algebra **A**
has a greatest element according to their natural order, that is
denoted usually by 1^{A} and interprets the
symbol ⊤. This element is taken as the designated element
relative to which the algebraic semantics is given. The algebraic
semantics of these two logics works as follows:

Let
**L**
be classical or intuitionistic logic and let
**K**(**L**)
be the corresponding class of algebras **BA** or
**HA**. It holds that

Γ ⊢_{L}φ iff for everyA∈K(L) and every valuationvonA, if for all ψ ∈ Γ(ψ) = 1v^{A}, then(φ) = 1v^{A}.

This is the precise content of the statement that **BA**
and **HA** are an algebraic semantics for classical logic
and for intuitionistic logic respectively. The implication from left
to right in the expression above is an algebraic soundness theorem and
the implication from right to left an algebraic completeness theorem.

There are logics for which an algebraic semantics is provided in
the literature in a slightly different way from the one given by the
schema above. Let us consider the example in Section 3 of
Intuitionistic Linear Logic without exponentials. We denote by
**IL _{0}** the class of IL-algebras with zero
defined in Troelstra 1992. On each one of these algebras

**A**there is a designated element 1

^{A}that may be different from the greatest element. The greatest element is the interpretation of ⊤ and 1

^{A}the interpretation of 1. Moreover, each

**A**∈

**IL**is a lattice with extra operations and thus has its lattice order ≤

_{0}^{A}. It holds:

Γ ⊢_{ILL}φ iff for everyA∈ILand every valuation_{0}vonA, if for all ψ ∈ Γ 1^{A}≤^{A}(ψ), then 1v^{A}≤^{A}(φ).v

In this case one does not consider only a designated element in every
algebra **A** but a set of designated elements, namely
the elements of **A** equal to or greater than
1^{A}. Let us denote this set by
D(**A**), and notice that D(**A**) =
{*a* ∈ *A*: 1^{A}
∧^{A} a =
1^{A}}. Hence,

Γ ⊢_{ILL}φ iff for everyA∈ILand every valuation_{0}vonA, if[Γ] ⊆ D(vA), then(φ) ∈ D(vA).

Still there are even more complex situations. One of them is
the system
**R**
of relevance logic. Consider the class of algebras
**Ral** defined in (Font, Rodríguez, 1990) and
denoted there by ‘**R**’. Let us consider for
every **A** ∈ **Ral** the set

E(A) := {a∈A:a→^{A}(a→^{A}a) =a→^{A}a}.

Then **Ral** is said to be an algebraic semantics for
**R**
because the following holds:

Γ ⊢_{R}φ iff for everyA∈Raland every valuationvonA, if[Γ] ⊆ E(vA), then(φ) ∈ E(vA).

The common pattern in the examples above is that the algebraic semantics is given by

- a class of algebras
**K**, - in each algebra in
**K**a set of designated elements that plays the role 1^{A}(more precisely the set {1^{A}}) plays in the cases of classical and intuitionistic logic, and - this set of designated elements is definable (in the same manner
on every algebra) by an equation in the sense that it is the set of
elements that satisfy the equation. For
**BA**and**HA**the equation is*p*≈ ⊤. For**Ral**it is*p*→ (*p*→*p*) ≈*p*→*p*, and for**IL**it is 1 ∧_{0}*p*≈ 1.

The main point in Blok and Pigozzi's concept of algebraic semantics comes from the realization, mentioned in (3) above, that the set of designated elements considered in the algebraic semantics of known logics is in fact the set of solutions of an equation, and that what practice forced reserachers to look for when they tried to obtain algebraic semantics for new logics was in fact, although not explicitly formulated in these terms, an equational way to define uniformly in every algebra a set of designated elements in order to obtain an algebraic soundness and completeness theorem.

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

Before stating Blok and Pigozzi's definition let us introduce a
notational convention. Given an algebra **A** and a set
of equations *Eq* in one variable, we denote by
*Eq*(**A**) the set of elements of
**A** that satisfy all the equations in *Eq*. Then
a logic
**L**
is said to have an *algebraic semantics* if there is a class
of algebras **K** and a set of equations *Eq* in
one variable such that

(**) Γ ⊢_{L}φ iff for everyA∈Kand every valuationvonA, if[Γ] ⊆vEq(A), then(φ) ∈vEq(A).

In this situation we say that the class of algebras
**K** is an *Eq*-*algebraic semantics* for
**L**,
or that the pair (**K**, *Eq*) is an
*algebraic semantics* for
**L**. If *Eq* consists of a single
equation *δ*(*p*) ≈
*ε*(*p*) we will simply say that
**K** is a *δ*(*p*) ≈
*ε*(*p*)-algebraic semantics for
**L**.
In fact, Blok and Pigozzi required that *Eq* should be finite
in their definition of algebraic semantics. But it is better
to be more general. The definition clearly encompasses the
situations encountered in the examples.

If **K** is an *Eq*-algebraic semantics for a
finitary logic
**L**
and *Eq* is finite, then the quasivariety generated by
**K** is also an *Eq*-algebraic
semantics. The
same does not hold in general if we consider the generated
variety. For this reason it is customary and useful when developing
the theory of the algebraization of finitary logics to consider
quasivarieties of algebras as algebraic semantics instead of arbitrary
subclasses that generate them. Conversely, if a quasivariety is an *Eq*-algebraic
semantics for a finitary
**L**
and *Eq* is finite, so is any subclass that generates it.

In the best behaved cases the typical algebraic semantics of a logic is a variety, for instance in all the examples discussed above. But there are cases in which it is not.

A quasivariety can be an *Eq*-algebraic semantics for a logic
and an *Eq*′-algebraic semantics for another logic (with
*Eq* and *Eq*′ different). For example, due to
Glivenko's theorem (see the entry on
intuitionistic logic)
the class of Heyting algebras is a {¬ ¬ *p* ≈
1}-algebraic semantics for classical logic and it is the standard
{*p* ≈ 1}-algebraic semantics for intuitionistic logic.
Moreover, different quasivarieties of algebras can be a
*Eq*-algebraic semantics for the same logic. It is known that
there is a quasivariety that properly includes the variety of Boolean
algebras and is a {*p* ≈ 1}-algebraic semantics for
classical propositional logic. It is also known that for some logics
with an algebraic semantics (relative to some set of equations), the
natural class of algebras that corresponds to the logic is not an
algebraic semantics (for any set of equations) of it. One example
where this situation holds is in the local normal modal
logic **lK**. Finally, there are logics that do not have
any algebraic semantics.

These facts highlight the need for some criteria of the goodness of a
pair (**K**, *Eq*) to provide a natural algebraic
semantics for a logic
**L** when some exists.
One such criterion would be that
**L**
is an algebraizable logic with (**K**, *Eq*) as
an algebraic semantics. Another that **K** is the natural
class of algebras associated with the logic. The notion of the
natural class of algebras of a logic system will be discussed in
Section 8 and the concept of algebraizable logic in Section 9.

## 6. Logical matrices

In the last section we saw that in order to provide a logic with an
algebraic semantics we need in many cases to consider in every algebra
a set of designated elements instead of a single designated one. In
the examples we discussed, the set of designated elements was
definable in the algebras by one equation. This motivated the
definition of algebraic semantics in Section 5. For many logics, to
obtain a semantics similar to an algebraic semantics using the class
of algebras naturally associated with them one needs for every algebra
a set of designated elements that cannot be defined using only the
equations of the algebraic language or is not even definable by using
only this language. As we already mentioned, one example where this
happens is the local consequence of the normal modal logic *K*.

To endow *every* logic with a semantics of an algebraic kind
one has to consider, at least, algebras together with a set of designated
elements, without any requirement about its definability using the
corresponding algebraic language. These pairs are the logical
matrices. Tarski defined the general concept of logical matrix in the
1920's 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 from
classical logic. A *logical matrix* is a pair <
**A**, *D* > where **A** is an
algebra and *D* a subset of the carrier *A* of
**A**; the elements of *D* are called the
*designated elements* of the matrix and accordingly *D* is called
*the set of designated elements*. Logical matrices where first
used as models of the theorems of specific logic systems, for instance
in the work of McKinsey and Tarski, and also to define sets of
formulas with similar properties to the set of theorems of a logic
system, namely closure under substitution instances. This was the case
of the *n*-valued logics of Łukasiewicz and of his
infinite-valued logic. It was Tarski who first considered logical
matrices as a general tool to define this kind of sets.

The general theory of logical matrices explained in this entry is due mainly to Polish logicians, starting with Łós 1949 and continuing in Łós & Suszko 1958, building on previous work by Lindenbaum. In Łós and Suszko's paper matrices are used for the first time both as models of logic systems (in our sense) and to define these kinds of systems.

In the rest of this section we present the relevant concepts of the theory of logical matrices using modern terminology.

Given a logic
**L**,
a logical matrix < **A**, *D* > is said to
be a *model* of
**L** if wherever Γ
⊢_{L}
φ then every valuation *v* on **A** that maps the
elements of Γ to some designated value (i.e. an element
of *D*) also maps φ to a designated value. When
< **A**, *D* > is a model of
**L** it is said that *D* is an
**L**-*filter*
of the algebra **A**. The set of
**L**-filters
of an algebra **A** plays a crucial role in the theory
of the algebraization of logic systems. We will come to this point
later.

A class **M** of logical matrices is said to be a
*matrix semantics* for a logic
**L** if

(*) Γ ⊢_{L}φ iff for every <A, D > ∈Mand every valuationvonA, if[Γ] ⊆vD, then(φ) ∈vD.

The implication from right to left says that
**L** is sound
relative to **M**, and the other implication says that
it is complete. In other words, **M** is a matrix
semantics for
**L** if every
matrix in **M** is a model of
**L** and moreover for every
Γ and φ such that Γ
⊬_{L}
φ there is a model of
**L**
in **M** that witnesses the fact, namely there is a
valuation on the model that sends the formulas in Γ to
designated elements and φ to a non-designated one.

Logical matrices are also used to define logics semantically.
If M =
< **A**, *D* > is a logical matrix, the
relation defined by

Γ ⊢_{M}φ iff for every valuationvonAif(ψ) ∈vDfor all ψ ∈ Γ, then(φ) ∈vD

is a consequence relation which is substitution-invariant;
therefore < *L*,
⊢_{M} >
is a logic system. Similarly
we can define the logic of a class of matrices **M** by taking
condition (*) as a definition of a consequence relation. In the entry
on
many-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
< **A**, *D* > is *reduced* if there
are no two different elements of *A* that behave in the same
way. We say that *a*, *b* ∈ A behave in the same
way in < **A**, *D* > if for every formula
*φ *(*q*, *p*_{1}, …,
*p*_{n}) and all elements
*d*_{1}, …, *d*_{n}
∈ *A*

φ^{A}[a,d_{1}, …,d_{n}] ∈Diff φ^{A}[b,d_{1}, …,d_{n}] ∈D.

Thus *a*, *b* ∈ *A*
behave differently if there is a formula
φ(*q*, *p*_{1},
…, *p*_{n}) and elements
*d*_{1}, …,
*d*_{n} ∈ A
such that one of φ^{A}[*a*,
*d*_{1}, …, *d*_{n}] and
φ^{A}[*b*,
*d*_{1}, …, *d*_{n}]
belongs to *D* but not both.
The relation of behaving in the same way in
< **A**, *D* > is a congruence relation of
**A**. This relation is known after (Blok-Pigozzi, 1986,
1989) as the *Leibniz congruence* of the matrix <
**A**, *D* > and is denoted by
**Ω**_{A}(*D*). It
can be characterized as the greatest congruence relation of
**A** that is *compatible* 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 1980's 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
M
can be turned into a new reduced matrix by
identifying the elements related by its Leibniz congruence. This
matrix is called the reduction of
M
and is usually denoted by
M^{*}.
A matrix and its reduction are models of exactly the same logic
systems, and since reduced matrices have no redundant elements, the
classes of reduced matrices that are matrix semantics for logic
systems are usually taken as the classes of matrices that deserve
study; they are better suited to encoding in algebraic-like terms the
properties of the logics of which they are the semantics.

The proof that every logic system has a reduced matrix semantics
is as follows. Let
**L** be a logic system. Consider the matrices
< **Fm**_{L},
*T* > over the formula algebra, where *T* is a
theory of
**L**. These matrices are known as the *Lindenbaum
matrices* of **L**. It is not difficult to see that the class of those
matrices is a matrix semantics for
**L**. Since a matrix and its
reduction are models of the same logics, the reductions of the
Lindenbaum matrices of
**L** constitute a reduced matrix semantics
for
**L** too. Moreover, any class of reduced
matrix models of
**L** that includes the reduced Lindenbaum
matrices of **L** automatically is a complete matrix semantics for
**L**. In particular, the class of all
reduced matrix models of
**L** is a complete matrix semantics for
**L**.
We denote this class by
**RMatr**(**L**).

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

The class of the algebras of the matrices in
**RMatr**(**L**)
plays a prominent role in the theory of the
algebraization of logics and it is denoted by
**Alg**^{*}**L**.
It has been considered for a long time the natural class of
algebras that has to be associated with a given logic
**L**.
For instance, in the examples considered above, the classes
of algebras that were given as algebraic semantics of the
different logics (Boolean algebras, Heyting algebras, etc.)
are exactly the class
**Alg**^{*}**L**
of the corresponding logic
**L**.
And in fact
**Alg**^{*}**L**
coincides with what was taken
to be the natural class of algebras for all the logics
**L**
studied up to the 1990's. In the 1990's, due to the knowledge
adquired of several logics not studied before, some authors proposed
another way to define what has to be counted as the natural class of
algebras to be associated with a given logic. For many logics
**L**
it leads exactly to the class
**Alg**^{*}**L**
but for others it gives a class that extends it properly.

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

We now discuss the method that is most commonly used to prove
that a class of algebras **K** is a *δ*(*p*)
≈
*ε*(*p*)-algebraic semantics for a logic
**L**, namely
the Lindenbaum-Tarski method. This method is the standard
method to prove that the classes of algebras of the examples
mentioned in Section 5 are algebraic semantics for
the corresponding logics.

The Lindenbaum-Tarski method contributed in two respects to the elaboration of important notions in the theory of the algebraization of logics. It underlies Blok and Pigozzi's notion of algebraizable logic and reflecting on it some ways to define for each logic a class of algebras can be justified as providing a natural class. We will consider this issue on Section 8.

The Lindenbaum-Tarski method can be outlined as follows. To prove
that a class of algebras **K** is a
*δ*(*p*) ≈
*ε*(*p*)-algebraic semantics for a logic
**L**
first it is shown that **K** gives a sound
*δ*(*p*) ≈
*ε*(*p*)-semantics for
**L**, namely that if
Γ
⊢_{L}
φ, then for every **A** ∈ **K**
and every valuation *v* in **A** if the values of
the formulas in Γ satisfy *δ*(*p*) ≈
*ε*(*p*), then the value of φ does
too. Secondly, the other direction, that is, the completeness part, is
proved by what is really known as the Lindenbaum-Tarski method. This
method uses the theories of
**L** to obtain
matrices on the algebra of formulas and then reduces these matrices
in order to get for each one a matrix whose algebra is in
**K** and whose set of designated elements is the set of
elements of the algebra that satisfy *δ*(*p*)
≈ *ε*(*p*). We describe the method step by
step in the sequel.

Let
**L**
be one of the logics discussed in the examples in Section 5. Let
**K** be the corresponding class of algebras we
considered there and let *δ*(*p*) ≈
*ε*(*p*) be the equation in one variable
involved in the soundness and completeness theorem. To prove the
completeness theorem one proceeds as follows. Given any set of
formulas Γ:

- The theory
*C*_{L}(Γ) = {φ: Γ ⊢_{L}φ} of Γ, which we denote by*T*, is considered and the binary relation θ(*T*) on the set of formulas using the formula*p*↔*q*is defined as follows:< φ, ψ > ∈ θ(

*T*) iff φ ↔ ψ ∈*T*. - It is shown that θ(
*T*) is a congruence relation on**Fm**_{L}. The set [φ] of the formulas related to the formula φ is called the equivalence class of φ. - A new matrix <
**Fm**/θ(*T*),*T*/θ(*T*) > is obtained by identifying the formulas related by θ(*T*), that is,**Fm**/θ(*T*) is the quotient algebra of**Fm**modulo θ(*T*) and*T*/θ(*T*) is the set of equivalence classes of the elements of*T*. Recall that the algebraic operations of the quotient algebra are defined by:∗

^{Fm/θ(T)}([φ_{1}],…,[φ_{n}]) = [∗φ_{1}…φ_{n}] †^{Fm/θ(T)}= [†] - It is shown that if < φ, ψ > ∈
θ(
*T*) and φ ∈*T*, then ψ ∈*T*. That is, it is shown that θ(*T*) is a relation compatible with*T*. This implies thatφ ∈

*T*iff [φ] ⊆*T*iff [φ] ∈*T*/θ(*T*). - It is proved that the matrix <
**Fm**/θ(*T*),*T*/θ(*T*) > is reduced, that**Fm**/θ(*T*) belongs to**K**and that*T*/θ(*T*) is the set of elements of**Fm**/θ(*T*) that satisfy the equation*δ*(*p*) ≈*ε*(*p*) in**Fm**/θ(*T*).

The proof of the completeness theorem then goes as follows.
(4) and (5) imply that for every formula ψ, Γ
⊢_{L}
ψ if and only if [ψ] satisfies the equation
*δ*(*p*) ≈ *ε*(*p*) in
the algebra **Fm**/θ(*T*). Thus,
considering the identity valuation *id* mapping every variable
*p* to its equivalence class [*p*], whose extension
* id* to the set of all formulas is such that

*(φ) = [φ] for every formula φ, we have for every formula ψ,*

**id**Γ ⊢_{L}ψ iff(ψ) satisfies the equationidδ(p) ≈ε(p) inFm/θ(T).

Hence, since by (6) **Fm**/θ(*T*) ∈
**K**, it follows that if Γ
⊬_{L
}φ, then there is an algebra **A** (namely
**Fm**/θ(*T*)) and a valuation *v*
(namely *id*) such that the elements of
* v*[Γ] satisfy the equation on

**A**but

*(φ) does not.*

**v**
The Lindenbaum-Tarski method, when successful, shows that the
class of algebras {**Fm**/θ(*T*): *T* is a theory of
**L**}
is a *δ*(*p*) ≈ *ε*(*p*)-algebraic semantics for
**L**.
Therefore it also shows that every class of algebras **K** which
is *δ*(*p*) ≈ *ε*(*p*)-sound for
**L** and includes
{**Fm**/θ(*T*): *T* is a theory of
**L**} is also a
*δ*(*p*) ≈ *ε*(*p*)-algebraic semantics for
**L**.

Let us make some remarks on the Lindenbaum-Tarski method just described. The first is important for the generalizations leading to the classes of algebras associated with a logic. The other to obtain the conditions in the definition of the concept of algebraizable logic.

1. Conditions (4) and (5) imply that θ(*T*) is in fact the
Leibniz congruence of < **Fm**_{L}, *T*
>.

2. When the Lindenbaum-Tarski method succeeds, it usually holds
that in every algebra **A** ∈ **K**,
the relation defined by the equation

δ(p↔q) ≈ε(p↔q),

which is the result of replacing in *δ*(*p*) ≈
*ε*(*p*) the letter *p* by the formula
*p* ↔ *q*
that defines the congruence relation of a theory, is the identity
relation on *A*.

3. For every formula φ, the formulas *δ*(*p*/φ)
↔ *ε*(*p*/φ) and φ are interderivable
in
**L**
(i.e. φ ⊢_{L}
*δ*(*p*/φ) ↔
*ε*(*p*/φ) and *δ*(*p*/φ) ↔
*ε*(*p*/φ)
⊢_{L} φ).

The concept of algebraizable logic introduced by Blok and Pigozzi,
which we will discuss in Section 9, can be described
roughly by saying that a logic
**L** is algebraizable if it has
an algebraic semantics (**K**, *Eq*) such
that (1) **K** is included
in the natural class of algebras associated with
**L** and (2) the
fact that (**K**, *Eq*) is an algebraic semantics
can be proved by using the Lindenbaum-Tarski method slightly
generalized.

## 8. The natural class of algebras of a logic system

We shall now expose for each logic
**L**
the two definitions that have been considered as providing
natural classes of algebras associated with
**L**.
Both definitions can be seen as arising from an abstraction of the
Lindenbaum-Tarski method and we follow this path in introducing them.
The common feature of these abstractions is that in them the specific way
in which the relation θ(*T*) is defined in the
Lindenbaum-Tarski method is disregarded.

It has to be remarked that, nonetheless, for many logics both definitions lead to the same class. But both classes obtained from the definitions have been considered in the algebraic studies of many specific logics (for some logics one, for other the other) the natural class to study.

We already encountered the first generalization in Section 6 when we
showed that every logic has a reduced matrix semantics. It leads to
the class of algebras **Alg**^{*}**L**
and it comes from the realization that the
relation θ(*T*) defined in the different completeness
proofs in the literature using the Lindenbaum-Tarski method is in fact
the Leibniz congruence of the matrix <
**Fm**_{L}, *T* > and that
then the matrix < **Fm**/θ(*T*),
*T*/θ(*T*) > is its reduction. As we mentioned
in Section 6, for every logic
**L** every
**L**-sound
class of matrices **M** that contains all the matrices
<
**Fm**/**Ω**_{FmL}(*T*),
**Ω**_{FmL}(*T*)
>, where *T* is a theory of
**L**, is a complete reduced matrix semantics for
**L**.
From this perspective the notion of the Leibniz congruence of a
matrix can be taken as a generalization to arbitrary matrices of the
idea that comes from the Lindenbaum-Tarski procedure of proving
completeness. Following this course of reasoning the class
**Alg**^{*}**L**
of the algebras of the reduced matrix models of a
logic
**L**
is the natural class of algebras to associate with
**L**. This class is

{A/Ω_{A}(F):Ais anL-algebra andFis aL-filter ofA}.

The second way of generalizing the Lindenbaum-Tarski method uses
another fact, namely the fact that in the examples discussed in Section 3 the
relation θ(*T*) is also the relation
**Ω**̃_{FmL}(*T*)
defined by the condition

< φ, ψ > ∈Ω̃_{FmL}(T) iff ∀T′ ∈ Th(L), ∀p∈V, ∀γ(p) ∈Fm_{L}(T⊆T′ ⇒ (γ(p/φ) ∈T′ ⇔ γ(p/ψ) ∈T′)).

For every logic
**L** and every
**L**-theory *T* the relation
**Ω**̃_{FmL}(*T*) defined in this way
is the greatest congruence compatible
with all the
**L**-theories
that extend *T*.
Therefore it holds that

Ω̃_{FmL}(T) = ∩_{T ′ ∈ Th(L)T}Ω_{FmL}(T′)

where
Th(**L**)^{T} =
{*T* ′
∈ Th(**L**): *T* ⊆
*T* ′}. The
relation
**Ω**̃_{FmL}(*T*)
is known as the
*Suszko congruence* of *T*. Suszko defined it (in an
equivalent way) in 1977.

For every logic
**L**, the notion of the Suszko congruence can be
extended to its matrix models. The *Suszko congruence* of
a matrix model < **A**, *D* > of
**L** is the greatest congruence
of **A** compatible with every
**L**-filter of **A** that includes
*D*, that is, it is the relation given by

Ω̃_{A}^{L}(D) = ∩_{D′ ∈ Fi L (A)D}Ω_{A}(D′)

where
Fi_{L}(**A**)^{D}
= {*D*′: *D*′ is a
**L**-filter
of **A** and *D* ⊆
*D*′}. Notice that unlike the intrinsic notion of Leibniz
congruence,
the Suszko congruence of a matrix model of
**L** 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.

In the same manner that the concept of Leibniz congruence leads
to the concept of reduced matrix, the notion of Suszko congruence
leads to the notion of Suszko-reduced matrix. A matrix model
of
**L** is *Suszko-reduced*
if its Suszko congruence is the
identity. Then the class of algebras of the
Suszko-reduced matrix models of a logic
**L** is another class of algebras that is taken as a natural class of
algebras to associate with
**L**. It is the class of algebras

AlgL= {A/Ω̃_{A}(F):Ais anL-algebra andFis aL-filter ofA}.

According to some authors, this class of algebras is *the* natural
class to be associated with
**L**.

For an arbitrary logic
**L** the relation between the classes **Alg****L** and
**Alg**^{*}**L**
is that
**Alg****L**
is the closure of **Alg**^{*}**L**
under subdirect products, in particular
**Alg**^{*}**L**
⊆
**Alg****L**.
In general both classes may be different. For example, if
**L** is
the (∧, ∨)-fragment of classical propositional logic,
**Alg****L**
is the variety of distributive lattices (the class that
has been always taken to be the natural class of algebras
associated with
**L**)
but **Alg**^{*}**L**
is not this class — in fact it is not even a
quasivariety. Nonetheless, for many logics **L**, in particular for the algebraizable and
the protoalgebraic ones to be discussed in the next sections, and also
when
**Alg**^{*}**L**
is a variety, the classes
**Alg****L** and
**Alg**^{*}**L**
are equal. This fact can explain why in the
1980s, before the algebraic study of non-protoalgebraic logics was
considered worth pursuing, the conceptual difference between both
definitions of the natural class of algebras of a logic
was not needed and so it was not considered (or even discovered).

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

The algebraizable logics are purported to be the logics with the strongest possible link with their natural class of algebras. This demands that the natural class of algebras should be an algebraic semantics but also something else, present in the best behaved specific logics known. The mathematically precise concept of algebraizable logic characterizes this type of link. Blok and Pigozzi introduced that fundamental concept in Blok & Pigozzi 1989 and its introduction can be considered the starting point of the unification and growth of the field of abstract algebraic logic in the 1980s. Blok and Pigozzi defined the notion of algebraizable logic only for finitary logics. Later Czelakowski and Herrmann generalized it to arbitrary logics and also weakened some conditions in the definition. We present here the generalized concept.

We said in Section 7 that, roughly speaking, a logic
**L**
is algebraizable when it has an algebraic semantics, i.e. a class of
algebras **K** and a set of equations
*Eq*(*p*) such that **K** is a
*Eq*-algebraic semantics, this fact can be proved by using the
Lindenbaum-Tarski method slightly generalized and, moreover,
**K**
⊆ **Alg**^{*}**L**. The
generalization of the Lindenbaum-Tarski method (as we described it in
Section 7) consists in allowing in step (5) (as in the definition of
algebraic semantics) a set of equations
*Eq*(*p*) in one variable instead of a single equation
*δ*(*p*) ≈ *ε*(*p*)
and in allowing in a similar manner a set of sentences
Δ(*p*, *q*) in at most two variables to play the
role of the formula *p* ↔ *q* in the definition of
the congruence of a theory. Then, given a theory *T*, the
relation θ(*T*), which has to be the greatest congruence
on the formula algebra compatible with *T* (i.e. the Leibniz
congruence of *T*), is defined by

< φ, ψ > ∈ θ(T) iff Δ(p/φ,q/ψ) ⊆T.

We need some notational conventions before engaging in the precise definition
of algebraizable logic. Given a set of equations
*Eq*(*p*) and a formula φ, let *Eq*(φ) be
the set of equations obtained by replacing in all the equations in
*Eq* the variable *p* by φ. If Γ is a set of
formulas, let

Eq(Γ) := ∪_{φ ∈ Γ}Eq(φ).

Similarly, given a set of formulas in two variables
Δ(*p*, *q*) and an equation *δ*
≈ *ε*, let Δ(*δ*,
*ε*) denote the set of formulas obtained by replacing
*p* by *δ* and *q* by *ε* in
all the formulas in Δ. Moreover, if *Eq* is a set of
equations, let

Δ(Eq) = ∪_{δ ≈ ε ∈ Eq}Δ(δ,ε).

Given a set of equations *Eq*(*p*, *q*) in two
variables, this set defines on every algebra **A** a
binary relation, namely the set of pairs < *a*,
*b*> of elements of *A* that satisfy in
**A** all the equations in *Eq*(*p*,
*q*). In standard model-theoretic notation, this set is the
relation

{<a,b>:a,b∈AandA⊨Eq(p,q)[a,b]}.

The formal definition of algebraizable logic is as follows. A
logic
**L**
is *algebraizable* if there is a class of algebras
**K**, a set of equations *Eq*(*p*) in one
variable and a set of formulas Δ(*p*, *q*) in two
variables such that

**K**is an*Eq*-algebraic semantics for**L**, namelyΓ ⊢

_{L}φ iff for every**A**∈**K**and every valuation*v*on**A**, if[Γ] ⊆ Eq(*v***A**), then(φ) ∈ Eq(*v***A**).- For every
**A**∈**K**, the relation defined by the set of equations in two variables*Eq*(Δ(*p*,*q*)) is the identity relation on*A*.

A class of algebras **K** for which there are sets
*Eq* and Δ with these two properties is said to be an
*equivalent algebraic semantics* for
**L**. The set of
formulas Δ is called a *set of equivalence formulas*
and the set of equations *Eq* a *set of defining equations*.

The conditions of the definition imply:

*p*is inter-derivable in**L**with the set of formulas Δ(*Eq*), that isΔ(

*Eq*) ⊢_{L}*p*and*p*⊢_{L}Δ(*Eq*).- For every
**L**-theory*T*, the Leibniz congruence of <**Fm**_{L},*T*> is the relation defined by Δ(*p*,*q*), namely< φ, ψ > ∈

**Ω**_{Fm}(*T*) iff Δ(*p*/φ,*q*/ψ) ⊆*T*. - If Δ and Δ′ are two sets of equivalence
formulas, Δ
⊢
_{L}Δ′ and Δ′ ⊢_{L}Δ. Similarly, if*Eq*(*p*) and*Eq*′(*p*) are two sets of defining equations, for every algebra**A**∈**K**,*Eq*(**A**) =*Eq*′(**A**). - The class of algebras
**Alg**^{*}**L**also satisfies conditions (1) and (2) and is the largest equivalent algebraic semantics of**L**. It is called*the greatest equivalent algebraic semantics*of**L**. - For every
**A**∈**Alg**^{*}**L**there is exactly one**L**-filter*F*such that the matrix <**A**,*F*> is reduced, and this filter is the set*Eq*(**A**). Or, to put it in other terms, the class of reduced matrix models of**L**is {<**A**,*Eq*(**A**) >:**A**∈**Alg**^{*}**L**}. **Alg**^{*}**L**is an SP-class and includes any class of algebras**K**which is an equivalent algebraic semantics for**L**.

Blok and Pigozzi's definition in Blok &Pigozzi 1989 was given
only for finitary logics and moreover they imposed that the sets of
defining equations and of equivalence formulas should be finite.
Today we say that an algebraizable logic is *finitely
algebraizable* if the sets of equivalence formulas Δ and of
defining equations *Eq* can both be taken finite.

If
**L**
is finitary and finitely algebraizable, then
**Alg**^{*}**L**
is not only an SP-class, but a quasivariety and it is the
quasivariety generated by any class of algebras **K** which is
an equivalent algebraic semantics for
**L**.

We have just seen that in algebraizable logics the class of
algebras
**Alg**^{*}**L**
plays a prominent role. Moreover, in
these logics the classes of algebras obtained by the two ways of
generalizing the Lindenbaum-Tarski method coincide, that is,
**Alg**^{*}**L**
= **Alg****L**.
Hence for every algebraizable logic
**L** its natural class of algebras
**Alg****L** is its greatest
equivalent algebraic semantics, whatever perspective is taken.

Conditions (1) and (2) of the definition of algebraizable logic
encode the fact that there is a very strong link between an
algebraizable logic
**L** and its class of algebras
**Alg****L**,
so that this class of algebras reflects the metalogical properties
of
**L**
by algebraic properties of
**Alg****L** and conversely.

The definition of algebraizable logic can be formulated in terms of
translations between the logic and an equational consequence relation
associated with any equivalent algebraic semantics
⊨_{K} fot it, which is the same no
matter what equivalent algebraic semantics we choose.

The equational consequence ⊨_{K} of
a class of algebras **K** is defined as follows.

{φ_{i}≈ ψ_{i}: i ∈ I} ⊨_{K}φ ≈ ψ iff for everyA∈Kand every valuationvonA, if(φv_{i}) =(ψv_{i}), for all i ∈ I, then(φ) =v(ψ).v

The translations are given by the set of defining equations and the
set of equivalence formulas. A set of equations *Eq* in one
variable defines a translation from formulas to sets of equations:
each formula is translated into the set of equations
*Eq*(φ). Similarly, a set of formulas Δ(*p*,
*q*) in two variables defines a translation from equations to
sets of formulas: each equation φ ≈ ψ is translated into
the set of formulas Δ(φ, ψ).

Condition (1) in the definition of algebraizable logic can be reformulated as

Γ ⊢_{L}φ iffEq(Γ) ⊨_{K}Eq(φ)

and condition (2) as

p≈q⊨_{K}Eq(Δ(p,q)) andEq(Δ(p,q)) ⊨_{K}p≈q.

These two conditions imply

- {φ
_{i}≈ ψ_{i}:*i*∈ I} ⊨_{K}φ ≈ ψ iff Δ({φ_{i}≈ ψ_{i}:*i*∈ I}) ⊢_{L}Δ(φ, ψ)

and (3) above is

p⊢_{L}Δ(Eq(p)) and Δ(Eq(p)) ⊢_{L}p.

Thus an algebraizable logic
**L** is faithfully interpreted in
the equational logic of its equivalent algebraic semantics
(condition (2)) by means of the translation of formulas into sets
of equations given by a set of defining equations, and the
equational logic of its equivalent algebraic semantics is
faithfully interpreted in the logic
**L** (condition (9)) by
means of the translation of equations into sets of formulas
given by an equivalence set of formulas. Moreover, both
translations are inverses of each other (conditions (2) and (3))
modulo logical equivalence. In this way we see that the link
between
**L** and its greatest equivalent algebraic semantics
is really very strong and that the properties of
**L** should
translate into properties of the associated equational consequence
relation. The properties that this relation actually has depend
on the properties of the class of algebras
**Alg****L**.

Given an algebraic semantics (**K**, *Eq*) for a logic
**L**,
a way to stress the difference between it being merely an
algebraic semantics and being an algebraic semantics that makes
**L** algebraizable is that the translation of formulas
into equations given by the set of equations *Eq* is
invertible in the sense that there is a translation, say Δ, of
equations into formulas given by a set of formulas in two variables
that satisfies condition (9) above, and such that *Eq* and
Δ provide mutually inverses translations (i.e. conditions (2)
and (3) hold).

This link between an algebraizable logic and its greatest equivalent algebraic semantics allows us to prove a series of general theorems that relate the properties of an algebraizable logic with the properties of its greatest equivalent algebraic semantics. We will mention as a sample only three of them.

The first concerns the deduction theorem. To prove a general theorem
relating the existence of a deduction theorem with an algebraic
property requires first that a concept of deduction theorem applicable to any
logic has to be defined. A logic
**L** has the
*deduction-detachment property* if there is a finite set of
formulas Δ(*p*, *q*) such that for every set of formulas
Γ and all formulas φ, ψ

Γ ∪ {φ} ⊢_{L}ψ iff Γ ⊢_{L}Δ(φ, ψ)

Note that this is a generalization of the standard deduction theorem
plus Modus Ponens that several logics have for a connective →. In
those cases Δ(*p*, *q*) = {*p* →
*q*}.

Theorem 1. A finitary and finitely algebraizable logicLhas the deduction-detachment property if and only if the principal relative congruences of the algebras inAlgLare equationally definable.

The second theorem refers to Craig interpolation.
Several notions of interpolation are applicable to arbitrary logics.
We consider only one of them. A logic
**L** has the
*Craig interpolation property* for the consequence relation
if whenever Γ
⊢_{L}
φ there is a finite set of
formulas Γ' with variables shared by φ and the formulas
in Γ such that Γ
⊢_{L}
Γ′ and
Γ′
⊢_{L}
φ.

Theorem 2. LetLbe a finitary and finitely algebraizable logic with the deduction-detachment property. ThenLhas the Craig interpolation property if and only ifAlgLhas the amalgamation property.

Finally, the third theorem deals with the Beth definability property. The interested reader can find the definition in (Font, Jansana, Pigozzi, 2003). It is too involved in the general setting we are in to give it here.

Theorem 3. A finitary and finitely algebraizable logic has the Beth property if and only if all the epimorphisms of the category with objects the algebras inAlgLand morphisms the algebraic homomorphisms are surjective homomorphisms.

For several classes of algebras that are the equivalent algebraic
semantics of some algebraizable logic it has been known for a long
time that for every algebra in the class there is an isomorphism
between the lattice of congruences of the algebra and a lattice of
subsets of the algebra with important algebraic meaning. For example,
in Boolean algebras and Heyting algebras these sets are the lattice
filters and in modal algebras they are the lattice filters that are
closed under the operation that interprets □. In all those
cases, those sets are exactly the
**L**-filters of the
corresponding algebraizable logic
**L**.

Algebraizable logics can be characterized by the existence of this
kind of isomorphism between congruences and logic filters. To
spell out this characterization we need a couple of definitions.
Let
**L**
be a logic. The *Leibniz operator* on an algebra
**A** (relative to
**L**)
is the map from the
**L**-filters of
**A**
to the set of congruences of **A** that sends every
**L**-filter
*D* of **A**
to its Leibniz congruence
**Ω**_{A}(*D*).
We say that the Leibniz operator of a logic
**L** *commutes with the inverses of
homomorphisms* between algebras in a class **K** if
for every homomorphism *h* from an algebra **A**
∈ **K** to an algebra **B** ∈
**K** and every
**L**-filter
*D* of **B**,
*h*^{−1}[**Ω**_{B}(*D*)]
=
**Ω**_{A}(*h*^{−1}[*D*]).

Theorem 4. A logicLis algebraizable if and only if for every algebraA∈AlgLthe Leibniz operator commutes with inverse homomorphisms between algebras inAlgLand is an isomorphism between the set of allL-filters ofA, ordered by inclusion, and the set of congruences θ ofAsuch thatA/θ ∈AlgL, ordered also by inclusion.

The theorem provides a logical explanation of the known
isomorphisms mentioned above and similar ones for other classes
of algebras. For example the isomorphism between the congruences
and the normal subgroups of a group can be explained by the
existence of an algebraizable logic
**L** of which the class of
groups is its greatest equivalent algebraic semantics and the normal
subgroups of a group are its
**L**-filters.

A different but related characterization of algebraizable logics is this:

Theorem 5A logicLis algebraizable if and only if on the algebra of formulasFm_{L}, the map that sends every theoryTto its Leibniz congruence is an isomorphism that commutes with the inverses of homomorphisms fromFm_{L}toFm_{L }between the set Th(L) of theories ofL, ordered by inclusion, and the set of congruences θ ofFm_{L}such thatFm_{L}/θ ∈AlgL, also ordered by inclusion.

## 10. A classification of logics

Unfortunately not every logic is algebraizable. A typical example
of a non-algebraizable logic is the local consequence of the normal
modal logic *K*. Let us discuss this example.

The local modal logic
**lK** and the corresponding global
one
**gK** are not only different,
but their metalogical properties differ. For example
**lK** has the deduction-detachment
property for →:

Γ ∪ {φ} ⊢_{lK}ψ iff Γ ⊢_{lK}φ→ ψ.

But
**gK**
does not have the deduction-detachment property
(at all).

The logic
**gK** is algebraizable and
**lK** is not. The
equivalent algebraic semantics of
**gK** is the variety
**MA** of modal algebras, the set of equivalence formulas
is the set {*p* ↔ *q*} and the set of defining
equations is {*p* ≈ 1}. Interestingly,
**lK** and
**gK**
have the same associated class of algebras (i.e.,
**Alg** **lK** =
**Alg** **lK**),
namely, the variety of modal algebras.

A lesson to draw from this example is that the class of algebras
**Alg****L** of a logic
**L** does not necessarily fully encode the
properties of
**L**. The class of modal algebras encodes the
properties of
**gK** because this logic
is algebraizable and so the link between
**gK** and **Alg**
**gK** is as strong as possible.
But **Alg** **lK**, the classs of modal algebras,
cannot
completely encode the properties of
**lK**.

What causes this difference between
**gK** and
**lK** is that the
class of reduced matrix models of
**gK** is

{<A, {1^{A}}>:A∈MA},

but the class of reduced matrix models of
**lK** properly
includes this class so that for some algebras **A** ∈
**MA**, in addition to
{1^{A}} there is some other
**lK**-filter
*F* with < **A**, *F* >
reduced. This
fact provides a way to show that
**lK** can not be algebraizable
by showing that the
**lK**-filters
of the reduced matrices are not
equationally definable from the algebras, because if they where,
then for every **A** ∈
**Alg** **lK**
there would exists exactly one
**lK**-filter
*F* of **A** such that < **A**,
*F* > is reduced.

Nonetheless we can perform some of the steps of the
Lindenbaum-Tarski method in the logic
**lK**. We can define the
Leibniz congruence of every
**lK**-theory in a uniform way by
using formulas in two variables. But in this
case the set of formulas has to be infinite. Let
Δ(*p*, *q*) =
{□^{n}(*p* ↔ *q*): *n*
a natural number}, where for every formula *φ*,
□^{0}*φ* is *φ* and
□^{n}*φ* for *n* > 0 is the
formula *φ* with a sequence of *n* boxes in front
(□ … ^{n} … □ φ).
Then, for every
**lK**-theory
*T* the relation θ(*T*) defined by

<φ, ψ > ∈ θ(T) iff {□^{n}(φ↔ ψ):na natural number } ⊆T

is the Leibniz congruence of *T*. In this case it happens that there are
two different
**lK**-theories
with the same Leibniz congruence,
something that does not hold for
**gK**.

The logics
**L** with the property that there is a set
of formulas (possibly infinite)
Δ(*p*, *q*) in two variables which defines
in every
**L**-theory its Leibniz congruence are known
as the *equivalential logics*. If Δ(*p*,
*q*) is finite, the logic is said to be *finitely
equivalential*. A set Δ(*p*, *q*) that defines
in every
**L**-theory its Leibniz congruence is called a
*set of equivalence formulas* for **L**. It is
clear that every algebraizable logic is equivalential and every
finitely algebraizable logic is finitely equivalential.

The logic
**lK**
is, according to the definition, equivalential,
and it can be shown that it is not finitely equivalential. The
local modal logic
**lS4** is an example of a
non-algebraizable logic that is finitely equivalential. A set
of equivalence formulas for
**lS4** is
{□ (*p*↔ *q*)}.

A set of equivalence formulas for a logic
**L** should be considered as a generalized
biconditional, in the sense that collectively the formulas in the set
have the relevant properties of the biconditional that make it
suitable to define the Leibniz congruences of theories, for example in
classical logic. This comes out very clearly from the following
syntactic characterization of the sets of equivalence formulas.

A set Δ(*p*, *q*) of *L*-formulas
is a set of equivalence formulas for a logic
**L** if and only if

- ⊢
_{L}Δ(*p*,*p*) *p*, Δ(*p*,*q*) ⊢_{L}*q*- Δ(
*p*,*q*) ⊢_{L}Δ(*q*,*p*) - Δ(
*p*,*q*) ∪ Δ(*q*,*r*) ⊢_{L}Δ(*p*,*r*) - Δ(
*p*_{1},*q*_{1}) ∪ … ∪ Δ(*p*_{n},*q*_{n}) ⊢_{L}Δ(∗*p*_{1}…*p*_{n}, ∗*q*_{1}…*q*_{n}), for every connective ∗ of*L*of arity*n*greater that 0.

Equivalential logics were first considered as a class of logics deserving to be studied in Prucnal & Wrónski 1974, and they have been studied extensively in Czelakowski 1981; see also Czelakowski 2001.

There are logics that are not equivalential but have the property
of having a set of formulas [*p* ⇒ *q*] which collectively
behave in a very weak sense as the implication → does in many
logics. Namely, it has the properties (1) and (2) in the syntactic
characterization of a set of equivalence formulas, i.e.

- ⊢
_{L}[*p*⇒*p*] *p*, [*p*⇒*q*] ⊢_{L}*q*

If a logic is finitary and has a set of formulas with these
properties, 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 called *protoalgebraic*. So,
in particular, every equivalential logic and every algebraizable logic
are protoalgebraic.

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

The class of protoalgebraic logics turned out to be the class of logics for which the theory of logical matrices works really well in the sense that many results of universal algebra have counterparts for the classes of reduced matrix models of these logics; consequently the algebraic study of protoalgebraic logics using their matrix semantics has been very fruitful. But, as we will see, some interesting logics are not protoalgebraic.

An important characterization of protoalgebraic logics is via the behaviour of the Leibniz operator. The following conditions are equivalent:

**L**is protoalgebraic.- The Leibniz operator
**Ω**_{FmL}is monotone on the set of**L**-theories with respect to the inclusion relation, that is, if*T*⊆*T*′ are**L**-theories, then**Ω**_{FmL}(*T*) ⊆**Ω**_{FmL}(*T*′). - For every algebra
**A**, the Leibniz operator**Ω**_{A}is monotone on the set of**L**-filters of**A**with respect to the inclusion relation.

Due to the monotonicity property of the Leibniz operator, for any
protoalgebraic logic
**L** the classes of algebras
**Alg**^{*}**L**
and
**Alg****L** coincide.

There are also characterizations of equivalential and finitely equivalential logics by the behaviour of the Leibniz operator. The reader is referred to Czelakowski 2001 and Font, Jansana, & Pigozzi 2003.

The classes of logics we have considered so far are the main classes
in what has come to be known as the *Leibniz hierarchy* because
it members are classes of logics that can be characterized by the
behaviour of the Leibniz operator. We described only the most
important classes of logics in the hierarchy. The reader is referred
to Czelakowski 2001 and Font, Jansana, & Pigozzi 2003 for more
information. In particular, Czelakowski 2001 gathers extensively the
information on the different classes of the Leibniz hierarchy known at
the time of its publication. The relations between the classes of the
Leibniz hierarchy considered in this entry are sumarized as
follows:

Finitely Algebraizable ⊊ Finitely Equivalential ⊊ Equivalential ⊊ Protoalgebraic

and

Finitely Algebraizable ⊊ Algebraizable ⊊ Equivalential ⊊ Protoalgebraic.Recently the Leibniz hierarchy has been refined in Cintula & Noguera 2010.

## 11. Replacement principles

Two classes of logics not in the Leibniz hierarchy have been extensively studied in AAL. They are defined from a completely different perspective from the one provided by the behaviour of the Leibniz operator, namely from the perspective given by the replacement principles a logic might enjoy.

The strongest replacement principle that a logic system
**L**
might have, shared for example by classical logic, intuitionistic logic and all
its axiomatic extensionss, says that for any set of
formulas Γ, any formulas φ, ψ, δ and any variable
*p*

if Γ, φ ⊢_{L}ψ and Γ, ψ ⊢_{L}φ, then Γ, δ(p/φ) ⊢_{L}δ(p/ψ) and Γ, δ(p/ψ) ⊢_{L}δ(p/φ),

where δ(*p*/φ) and δ(*p*/ψ) are
the formulas obtained by substituting respectively φ and ψ for
*p* in δ. This replacement property is taken by some
authors as the formal counterpart of Frege's compositionality
principle for truth. Logics satisfying this strong replacement
property are called *Fregean* in Czelakowski & Pigozzi
2004a. Such logics are studied thoroughly in that paper and in
Czelakowski & Pigozzi 2004b.

Many important logics do not satisfy this strong replacement property, for instance almost all the logics (local or global) of the modal family, but some, like the local consequence relation of a normal modal logic, satisfy a weaker replacement principle: for all formulas φ, ψ, δ,

if φ ⊢_{L}ψ and ψ ⊢_{L}φ, then δ(p/φ) ⊢_{L}δ(p/ψ) and δ(p/ψ) ⊢_{L}δ(p/φ).

A logic satisfying this weaker replacement property is called
*selfextensional* by Wójcicki and *congruential*
in Humberston 2005. We will use the first terminology
because it seems more common.

Selfextensional logics have a very good behaviour from several points of view. Their systematic study started in Wóojcicki 1969 and has recently been continued in the context of AAL in Font & Jansana 1996, Jansana 2005, 2006, and Jansana & Palmigiano 2006.

There are selfextensional and non-selfextensional logics in any of
the classes of the Leibniz hierarchy and also in the class of
non-protoalgebraic logics. This shows that the perspective that leads
to the consideration of the classes in the Leibniz hierarchy and the
perspective that leads to the definition of the selfextensional and
the Fregean logics as classes of logics worthy of study as a whole are
really different. Nonetheless, one of the trends of today's research
in AAL is to determine the interplay between the two perspectives and
study the classes of logics that arise when crossing both
classifications. In fact there is a connection between the replacement
principles and the Suszko congruence (and thus with the Leibniz
congruence). A logic
**L**
satisfies the strong replacement principle if and only if for every
**L**-theory
*T* its Suszko congruence is the interderivability relation
relative to *T*, namely the relation {< φ, ψ>:
*T*, φ
⊢_{L}
ψ and *T*, ψ
⊢_{L} φ}.
And a logic
**L**
satisfies the weak replacement principle if and only if the Suszko
congruence of the set of theorems of
**L**
is the interderivability relation {< φ, ψ>: φ
⊢_{L}
ψ and ψ
⊢_{L}
φ}.

## 12. Beyond protoalgebraic logics

Not all interesting logics are protoalgebraic. In this section we
will briefly discuss four examples of non-protoalgebraic logics: the
logic of conjunction and disjunction, positive modal logic, the strict
implication fragment of
**lK**
and Visser's subintuitionistic logic. All of them are
selfextensional. In the next section we will expound the semantics of
abstract logics and generalized matrices that serves to develop a
really general theory of the algebraization of logic systems. As we
will see the perspective changes in an important respect from the
perspective taken by logical matrix model theory.

### 12.1 The logic of conjunction and disjunction

This logic is the {∧, ∨, ⊥, ⊤}-fragment of Classical Propositional Logic. Hence its language is the set {∧, ∨, ⊤, ⊥} and its consequence relation is given by

Γ ⊢ φ iff Γ ⊢_{CPL}φ.

It turns out that it is also the {∧, ∨, ⊥,
⊤}-fragment of Intuitionistic Propositional Logic. Let us denote
it by
**L**^{{∧, ∨}}.

The logic
**L**^{{∧,
∨}} is not protoalgebraic and it is Fregean. Its classes of algebras
**Alg**^{*}**L**^{{∧,
∨}} and
**Alg****L**^{{∧,
∨}} are different. Moreover
**Alg****L**^{{∧, ∨}}
is the variety of bounded distributive lattices, the natural class of algebras
expected to be the associated with **L**^{{∧,
∨}}, but
**Alg**^{*}**L**^{{∧,
∨}} is strictly included in it. In fact this last class of
algebras is not a quasivariety, but it is first-order definable
still.

The logic
**L**^{{∧, ∨}} is a natural example of
logic where the class of its reduced matrix models is not the right class
of algebras expected to correpond it (see Font & Verdú
1991). This example motivated the systematic study, in Font & Jansana
1986, of the kind of model for sentential logics considered
in Brown & Suszko 1973, namely, abstract logics.

### 12.2 Positive Modal Logic

It is the {∧, ∨, □, ◊, ⊥, ⊤}-fragment of
the local normal modal logic
**lK**. We denote it by
**PML**.

The logic
**PML** is not protoalgebraic, it is
selfextensional and it is non-Fregean. Its class of algebras
**Alg** **PML**
is the class of positive modal algebras introduced by Dunn in (Dunn,
1995). The logic is studied, in Jansana 2002, from the
perspective of algebraic logic.
**Alg****PML** is different from
**Alg**^{*}**PML**.
**PML** has some interest in Computer Science.

### 12.3 Visser's subintuitionistic logic

This logic is the logic in the language of intuitionistic logic that
has to the least normal modal logic *K* the same relation that
intutitionistic logic has to the normal modal logic *S4*.
It was introduced in Visser 1981 and has been studied by several
authors, such as Ardeshir, Alizadeh and Ruitenburg. It is not
protoalgebraic and is not Fregean.

### 12.4 The strict implication fragment of the local modal logic **lK**

The strict implication of the language of modal logic is defined
using the □ operator and the material implication →. We
will use ⇒ for the strict implication. Its definition is φ
⇒ ψ := □(φ → ψ). The language of the logic
**SilK**, that
we call the strict implication fragment of the local modal logic
**lK**, is the language *L* =
{∧, ∨, ⊥, ⊤, ⇒}. We can translate the formulas
of *L* to formulas of the modal language by systematically
replacing in a *L*-formula φ every subformula of the form
ψ ⇒ δ by □ (ψ → δ) and repeating
the process until no appearence of ⇒ is left. Let us denote by
φ^{*} the translation of φ and by Γ^{*}
the set of the translations of the formulas in Γ. Then the
definition of the consequence relation of
**SilK** is:

Γ ⊢_{SilK}φ iff Γ^{*}⊢_{ lK}φ^{*}.

The logic
**SilK** is not protoalgebraic. It is
selfextensional and non-Fregean. Its natural class of algebras
**Alg**
**SilK** is the class of bounded distributive
lattices with a binary operation with the properties of the strict
implication of
**lK**. This class of algebras is introduced and
studied in Celani & Jansana 2005, where its members are called
Weakly Heyting algebras. **Alg**
**SilK** does not coincide with
**Alg**^{*}
**SilK**.

## 13. Abstract logics and generalized matrices

The matrix models of a logic can be thought of as algebraic generalizations of its theories, more precisely, of its Lindenbaum matrices. They come from a local perspective that is centered around the theories one by one, and its analogues, the logic filters. But, as we will see, the properties of a logic depend in general on the global behaviour of the set of its theories as a bunch, or — to put it otherwise — on its consequence relation due to the duality between the family of closed sets (the theories) and the consequence operation. The consideration of this global behaviour introduces a global perspective on the semantics for logic systems. The abstract logics that we 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 that global perspective seriously.

Let *L* be a propositional language. An *L*-*abstract
logic* is a pair
A
= < **A**, C > where **A** is an
*L*-algebra and *C* an abstract consequence operation on
*A*.

Given a logic
**L**, an *L*-abstract logic
A =
< **A**, *C* > is a *model* of
**L** if for every set
of formulas Γ and every formula φ

Γ ⊢_{L}φ iff for every valuationvonA,(φ) ∈vC([Γ]).v

This definition has an equivalent in terms of the closed sets
of *C*: an abstract logic
A =
< **A**, *C* >
is a model of
**L**
if and only if for every *C*-closed set *X*
the matrix < **A**, *X* > is a model of
**L** (i.e. X is an **L**-filter).

This observation leads to another point of view on abstract
logics as models of a logic system. It transforms them into
a collection of logical matrices (given by the closed sets)
over the same algebra, or, put more simply,
into a pair
< **A**, B >
where B is
a collection of subsets of *A*. A structure of this type is
called in the literature a *generalized matrix*
(Wójcicki [1973]) and more recently has been called *atlas*
in (Dunn, Hardegree, 2001). It is said to be a model of a logic
**L** if
for every *X* ∈ B,
< **A**, *X* > is a matrix model
of
**L**.

A logic system
**L** = <
*L*,
⊢_{L}
> straightforwardly provides us with an
equivalent abstract logic < **Fm**_{L},
*C*_{⊢L}
> and
an equivalent generalized matrix < **Fm**_{L},
Th(**L**) >,
where Th(**L**) is the set of
*C*_{⊢L}-closed
sets of formulas (i.e. the
**L**-theories). We will move freely
from one to the other.

The generalized matrices < **A**,
B > that correspond
to abstract logics have the properties that *A* ∈
B
and that
B
is closed under intersections of arbitrary
nonempty families. A family
B of subsets of a set *A* with
these two properties is known as a *closed-set system* and also
as a *closure system*. There is a dual correspondence between
abstract consequence operations on a set *A* and closed-set
system on *A*. Given an abstract consequence operation
*C* on *A*, the
set C(*C*) of *C*-closed
sets is a closed-set system and given a closed-set
system C the
operation *C*(C) defined by
*C*(C)(*X*) =
∩ {*Y* ∈
C: *X* ⊆ *Y*}, for every
*X* ⊆ *A*, is an abstract consequence operation. In general, every generalized matrix
< **A**,
B >
can be turned into a closed-set system by adding to
B ∪ {*A*}
the intersections
of arbitrary nonempty families, and therefore into an abstract
logic, which we denote by < **A**,
*C*(B)>. In that
situation we say that B
is a *base* for
*C*(B).
It is obvious that an abstract logic can have more than one base. Any family of
closed sets with the property that every closed set is an intersections of
elements of the family is a base. The study of bases for the
closed set system of the theories of a logic usually plays an
important role in its study. For example, in classical logic
an important base for the family of theories is the family of
maximal consistent theories and in intuitionistic logic the
family of prime theories. In a similar way the systematic study of bases
for generalized matrix models of a logic becomes important.

In order to make the exposition smooth we will now move from
abstract logics to generalized matrices. Let
A =
< **A**, B >
be a generalized matrix. There exists the
greatest congruence of **A** compatible with all the sets in
B, and it is
is known as the
*Tarski congruence* of
A. We denote it by
**Ω**̃_{A}(B).
It has the following characterization using the
Leibniz operator

Ω̃_{A}(B) = ∩_{X ∈ B}Ω_{A}(X).

It can also be characterized by the condition:

<a,b> ∈Ω̃_{A}(B) iff for every φ(p,q_{1}, …,q_{n}), everyc_{1}, …,c_{n}∈Aand allX∈ B

φ^{A}[a,c_{1}, …,c_{n}] ∈X⇔ φ^{A}[b,c_{1}, …,c_{n}] ∈X

or equivalently by

<a,b> ∈Ω̃_{A}(B) iff for every φ(p,q_{1}, …,q_{n}) and everyc_{1}, …,c_{n}∈A,C(B)(φ^{A}[a,c_{1}, …,c_{n}]) =C(B)(φ^{A}[b,c_{1}, …,c_{n}]).

A generalized matrix is *reduced* if its Tarski congruence
is the identity. Every generalized matrix < **A**,
B >
can be turned into an equivalent reduced one by identifying the
elements related by its Tarski congruence. The result is the
quotient <
**A**/**Ω**̃_{A}(B),
B/**Ω**̃_{A}(B)
>, where
B/**Ω**̃_{A}(B)
=
{*X*/**Ω**̃_{A}(B):
*X* ∈ B} and for
*X* ∈ B,
*X*/**Ω**̃_{A}(B)
is the set of
equivalence classes of the elements of *X*.

The properties of a logic
**L** depend in general, as we already
said, on the global behaviour of the family of its theories.
In some logics this behaviour is reflected in the behaviour of
its set of theorems, as in classical and intuitionistic logic
due to the deduction-detachment property, but this is by no means
the most general situation, as it is witnessed by the example of
the local and global modal logic of the normal modal logic *K*:
both have the same theorems but do not share the same properties. In a similar way, the
properties of a logic are *in general* better encoded
in an algebraic setting if we consider families of
**L**-filters
on the algebras than if we consider a single
**L**-filter as is
done in the logical matrix model theory.

The generalized matrix models that have naturally attracted most of
the attention in the research on the algebraization of logics are the
generalized matrices of the form <
**A**,
Fi_{L}**A** >
where
Fi_{L}**A** is the set of all the
**L**-filters of **A**.
An example of a property of logics encoded
in the structure of the lattices of
**L**-filters of the
*L*-algebras is that (see (Czelakowski, 2001)) for every finitary
protoalgebraic logic
**L**,
**L** has the deduction-detachment
property if and only if for every algebra **A** the
join-subsemilattice of the lattice of all
**L**-filters of **A**
that consists of the finitely generated
**L**-filters is dually
residuated.

The generalized matrices of the form < **A**,
Fi_{L}**A** >
are the *basic full models* of
**L**. The interest in these models lead to a
consideration of the class of generalized matrix that the quotient by
its Tarski congruence is a basic full model. These generalized
matrices (and their corresponding abstract logics) are called *full
models*. The theory of the full models of an arbitrary logic is
developed in Font & Jansana 1996. We will mention some of the main
results obtained there.

Let
**L** be a logic system.

**L**is protoalgebraic if and only if for every full model <**A**, C > there is an**L**-filter*F*of**A**such that C = {*G*∈ Fi_{L}**A**:*F*⊆*G*}.- If
**L**is finitary,**L**is finitely algebraizable if and only if for every algebra**A**and every**L**-filter*F*of**A**, the generalized matrix <**A**, {*G*∈ Fi_{L}**A**:*F*⊆*G*} > is a full model and**Alg****L**is a quasivariety. - The class
**Alg****L**is both the class of algebras of the reduced generalized matrix models of**L**, and the class {**A**: <**A**, Fi_{L}**A**> is reduced}. - For every algebra
**A**there is an isomorphism between the family of closed-set systems C on*A*such that <**A**, C > is a full model of**L**and the family of congruences θ of**A**such that**A**/θ ∈**Alg****L**. The isomorphism is given by the Tarski operator that sends a generalized matrix to its Tarski congruence.

The isomorphism theorem (4) above is a generalization of the isomorphism theorems we encountered earlier for algebraizable logics. What is interesting here is that the theorem holds for every logic system. Using (2), theorem (4) entails the isomorphism theorem for finitary and finitely algebraizable logics. Thus theorem (4) can be seen as the most general formulation of the mathematical logical phenomena that underlies the isomorphism theorems between the congruences of the algebras in a certain class and some kind of subsets of them we mentioned in Section 9.

The use of generalized matrices and abstract logics as models
for logic systems has proved very useful for the study of
selfextensional logics in general and more in particular for
the study of the non-protoalgebraic and selfextensional logics
such as the logics in Section 12. In particular,
they have proved very useful for the study of the class of
finitary selfextensional logics with a conjunction and the
class of finitary selfextensional logics with the
deduction-detachment property for a single term, say
*p* → *q*;
the logics in this last class are nevertheless protoalgebraic.
A logic
**L** has a *conjunction*
if there is a formula
in two variables φ(*p*, *q*) such that

φ(p,q) ⊢_{L}p, φ(p,q)⊢_{L}q,p,q⊢_{L}φ(p,q)

The logics in those two classes have the following property: for
every full model < **A**, C > its Tarski relation
is the relation {< *a*, *b* > ∈ A × A:
*C*(*a*) = *C*(*b*)}. A way of saying it
is to say that for these logics the property that defines
selfextensionality, namely that the interderivability condition is a
congruence, lifts or transfers to every full model. The
selfextensional logics with this property are called *fully
selfextensional*. This notion was introduced in (Font, Jansana,
1996) under the name 'strongly selfextensional'. All the known and
natural selfextensional logics are fully selfextensional, in
particular the logics discussed in Section 12, but Babyonyshev showed
(2005) an *ad hoc* example of a selfextensional
logic that is not fully selfextensional.

An interesting result on the finitary logics in the classes
of fully selfextensional logics with conjunction and the ones
with the deduction-detachment property for a single term is
that their class of algebras
**Alg****L** is always a variety.
The researchers in AAL are somehow surprised by the fact that
several finitary and finitely algebraizable logics have a variety
as its equivalent algebraic semantics, when the theory of
algebraizable logics allows us in general to prove only that
the equivalent algebraic semantics of a finitary and finitely
algebraizable logic is a quasivariety. The result explains
this phenomenon for the finitary and finitely algebraizable
logics to which it applies. For many other finitary and finitely
algebraizable logics to find a convincing explanation is still
an open area of research.

Every abstract logic
A =
< **A**, *C* >
determines a quasi-order (a reflexive and transitive relation) on
*A*. It is the relation defined by

a≤_{A}biffC(b) ⊆C(a) iffb∈C(a).

Thus *a*
≤_{A}
*b* if and only if *b* belongs to every
*C*-closed set to which *A* belongs. For a fully
selfextensional logic
**L**
this quasi-order turns into a partial order in the
reduced full models, which are in fact the reduced basic full
models, that is, the abstract logics < **A**,
Fi_{L}**A**
>
with **A** ∈
**Alg****L**. Consequently,
in a fully selfextensional logic
**L**
every algebra **A** ∈
**Alg****L** carries a partial
order definable in terms of the family of the
**L**-filters.
If the logic is fully selfextensional with a conjunction this
partial order is definable by an equation of the *L*-algebraic
language alone because in this case for every algebra
**A** ∈
**Alg****L**

a≤biffC(b) ⊆C(a) iffC(a∧b) =C(a) iffa∧b=a

A similar situation holds for fully selfextensional logics with the
deduction-detachment property for a single term, say *p* →
*q*, for then for every algebra **A** ∈
**Alg****L**

a≤biffC(b) ⊆C(a) iffC(a→b) =C(∅) =C(a→a) iffa→b=a→a.

These observations lead us to view the finitary fully selfextensional
logics
**L** with conjunction and those with the
deduction-detachment property for a single term as logics
definable by an order which is definable in the algebras in
**Alg****L** by using an equation of the
**L**-algebraic language. Related to this,
the following result is known.

Theorem 6. A finitary logic with conjunctionLis fully selfextensional iff there is a class of algebrasKsuch that for everyA∈Kthe reduct < A, ∧^{A}> is a meet-semilattice and if ≤ is the order of the semilattice thenφ_{1}, …, φ_{n}⊢_{L}φ iff for allA∈Kand every valuationvonA(φv_{1}) ∧^{A}… ∧^{A}(φv_{n}) ≤(φ)vand

⊢_{L}φ iff for allA∈Kand every valuationvonAa≤(φ), for everyva∈ A.Moreover, in this case the class of algebras

AlgLis the variety generated byK.

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

## 14. Extending the setting

The research on logic systems described in the previous sections has been extended to encompass other consequence relations that go beyond propositional logics, like equational logics and the consequence relations between sequents built from the formulas of a propositional language definable using sequent calculi. The interested reader can consult the excellent paper Raftery 2006.

This research arose from the need for an even more abstract way of developing the theory of consequence relations. This has lead to a reformulation (in a category-theoretic setting) of the theory of logic systems as explained in this entry. The work has been done mainly by G. Voutsadakis in a series of papers, e.g., Voutsadakis 2002. Voutsadakis approach uses the notion of pi-institution, introduced by Fiadeiro and Sernadas, as the analogue of the logic systems in his category theoretic setting. Some work in this direction is also found in Gil-Férez 2006. A different approach to a generalization of the studies encompassing the work done for logic systems and for sequent calculi is found in Galatos & Tsinakis 2009; Gil-Férez 2011 is also in this line. The work in both papers originates in Blok & Jónsson 2006. The Galatos-Tsinakis approach has been recently extended in a way that encompasses also the setting of Voutsadakis by N. Galatos and J. Gil-Férez in still unpublished work.

Another recent line of research that extends the framework described in this entry develops a theory of algebraization of many sorted logic systems using instead of the equational consequence relation of the natural class of algebras a many sorted behavioral equational consequence (a notion coming from computer science) and a weaker concept that algebraizable logic: behaviorally algebraizable logic. See Caleiro, Gonçalvez, & Martins 2009.

## Bibliography

- Babyonyshev, S., 2003, “Strongly Fregean
logics”,
*Reports on Mathematical Logic*, 37: 59–77. - Blackburn, P., J. van Benthem, and F. Wolter (eds.),
2006,
*Handbook of Modal Logic*, Amsterdam: Elsevier. - Blok, W., and Hoogland, E., 2006, “The Beth property in
algebraic logic”,
*Studia Logica*, 83 (Special Issue in memory of Willem Johannes Blok): 49–90. - Blok, W., and Jónsson, B., 2006, “Equivalence of
consequence operations”,
*Studia Logica*, 83: 91–110. - Blok, W., and Pigozzi, D., 1986, “Protoalgebraic logics”,
*Studia Logica*, 45: 337–369. - Blok, W., and Pigozzi, D., 1989,
*Algebraizable logics*, (Mem. Amer. Math. Soc., Volume 396), Providence: A.M.S. - Blok, W., and Pigozzi, D., “Local deduction theorems in algebraic
logic”, in
*Algebraic Logic*(Colloq. Math. Soc. János Bolyai: Volume 54), H. Andréka, J.D. Monk, and I. Németi (eds.), Amsterdam: North Holland, 75–109. - Blok, W., and Pigozzi, D., “Algebraic semantics for universal Horn
logic without equality”, in
*Universal Algebra and Quasigroup Theory*, A. Romanowska and J.D.H. Smith (eds.). Berlin: Heldermann, 1–56. - Bloom, S.L., 1975, “Some theorems on structural consequence
operations”,
*Studia Logica*, 34: 1–9. - Brown, D.J., and Suszko, R., 1973, “Abstract logics”,
*Dissertationes Mathematicae Rozprawy Mat.*, 102: 9–42. - Caleiro, C., Gonçalves, R., Martins, M., 2009, “Behavioral
algebraization of logics”,
*Studia Logica*, 91: 63–111. - Celani, S., and Jansana, R., 2003, “A closer look at some
subintuitionistic logics”,
*Notre Dame Journal of Formal Logic*, 42: 225–255. - Celani, S., and Jansana, R., 2005, “Bounded distributive
lattices with strict implication”,
*Mathematical Logic Quarterly*, 51: 219–246. - Cintula, P., and Noguera, C., 2010 “ Implicational
(semilinear) logics: a new hierarchy”,
*Archive for mathematical Logic*, 49: 417–446. - Czelakowski, J., 1980, “Reduced products of logical matrices”,
*Studia Logica*, 39: 19–43. - Czelakowski, J., 1981, “Equivalential logics, I and
II”,
*Studia Logica*, 40: 227–236 and 355–372. - Czelakowski, J., 2001,
*Protoalgebraic Logics*(Trends in Logic, Studia Logica Library, Volume 10), Dordrecht: Kluwer Academic Publishers. - Czelakowski, J., 2003, “The Suszko operator. Part I”,
*Studia Logica*, 74: 181–231. - Czelakowski, J., and Jansana, R., 2000, “Weakly algebraizable
logics”,
*The Journal of Symbolic Logic*, 65: 641–668. - Czelakowski, J., and Pigozzi, D., 2004a, “Fregean logics”,
*Annals of Pure and Applied Logic*, 127: 17–76. - Czelakowski, J., and Pigozzi, D., 2004b, “Fregean logics with the
multiterm deduction theorem and their algebraization”,
*Studia Logica*, 78: 171–212. - Dośen, K., and P. Schroeder-Heister (eds.), 1993,
*Substructural Logics*(Studies in Logic and Computation: Volume 2), Oxford: Oxford University Press. - Dunn, M., 1995, “Positive Modal Logic”,
*Studia Logica*, 55: 301–317. - Dunn, J.M. and Hardegree, G.M., 2001,
*Algebraic methods in philosophical logic*(Oxford Logic Guides, Oxford Science Publications, Volume 41), New York: Oxford University Press. - Font, J.M., 1997, “Belnap's four-valued logic and De Morgan
lattices”,
*Logic Journal of the I.G.P.L*, 5: 413–440. - Font, J.M. and Jansana, R., 1996
*A general algebraic semantics for sentential logics*(Lecture Notes in Logic, Volume 7), Berlin: Springer-Verlag. (Currently distributed by the Association for Symbolic Logic.) - Font, J.M., Jansana, R. and Pigozzi, D. 2003, “A Survey of
Abstract Algebraic Logic”,
*Studia Logica*, 74 (Special Issue on Abstract Algebraic Logic — Part II): 13–97. - Font, J.M. and Rodríguez, G., 1990, “Note on
algebraic models for relevance logic”,
*Zeitschrift für Mathematische Logik und Grundlagen der Mathematik*, 36: 535–540. - Font, J.M. and Rodríguez, G., 1994, “Algebraic study of two
deductive systems of relevance logic”,
*Notre Dame Journal of Formal Logic*, 35: 369–397. - Font, J.M., and Verdú, V., 1991, “Algebraic logic for
classical conjunction and disjunction”,
*Studia Logica*, 65 (Special Issue on Abstract Algebraic Logic): 391–419. - Galatos, N., Tsinakis, C., 2009, “Equivalence of consequence
relations: an order-theoretic and categorical
perspective”,
*The Journal of Symbolic Logic*, 74: 780–810 - Gil-Férez, J., 2006, “Multi-term pi-institutions and
their equivalence”,
*Mathematical Logic Quarterly*, 52: 505–526. - Gil-Férez, J., 2011, “Representations of structural
closure operators”,
*Archive for Mathematical Logic*, forthcoming. - Herrmann, B., 1996, “Equivalential and algebraizable logics”,
*Studia Logica*, 57: 419–436. - Herrmann, B., 1997, “Characterizing equivalential and
algebraizable logics by the Leibniz operator”,
*Studia Logica*, 58: 305–323. - Hoogland, E., 2000, “Algebraic characterizations of various Beth
definability properties”,
*Studia Logica*, 65 (Special Issue on Abstract Algebraic Logic. Part I): 91–112. - Humberstone, LL., 2005, “Logical Discrimination”, in
J.-Y. Béziau (ed.),
*Logica Universalis*, Basel: Birkhäuser. - Jansana, R., 2002, “Full models for positive modal logic”,
*Mathematical Logic Quarterly*, 48: 427–445. - Jansana, R., 2005, “Selfextensional logics with implication”, in
J.-Y. Béziau (ed.),
*Logica Universalis*, Basel: Birkhäuser. - Jansana, R., 2006, “Selfextensional logics with conjunction”,
*Studia Logica*, 84: 63–104. - Jansana, R. and Palmigiano, A., 2006, “Referential algebras:
duality and applications”,
*Reports on Mathematical Logic*, 41: 63–93. - Koslow, A., 1992,
*A structuralist approach to logic*, Cambridge: Cambridge University Press. - Kracht, M., 2006, “Modal Consequence Relations”, in P. Blackburn, J. van Benthem, and F. Wolter (eds.) 2006, 497–549.
- Łós, J., 1949,
*O matrycach logicznych*, Ser. B. Prace Wrocławskiego Towarzystwa Naukowege (Travaux de la Société et des Lettres de Wrocław), Volume 19. - Łós, J., and Suszko, R., 1958, “Remarks on sentential
logics”,
*Indagationes Mathenmaticae*, 20: 177–183. - Łukasiewicz, J., and Tarski, A., 1930, “Untersuchungen
über den Aussagenkalkül”,
*Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie*, Cl.III 23: 30–50. English translation in Tarski 1983: “Investigations into the sentential calculus”. - McKinsey, J. C.C., 1941, “A solution of the decision problem for
the Lewis systems S2 and S4, with an application to topology”,
*The Journal of Symbolic Logic*, 6: 117–134. - McKinsey, J. C.C., and Tarski, A., 1948, “Some theorems about the
sentential calculi of Lewis and Heyting”,
*The Journal of Symbolic Logic*, 13: 1–15. - Pigozzi, D., 1991, “Fregean algebraic logic”, in
H. Andréka, J.D. Monk, and I. Németi (eds.),
*Algebraic Logic*(Colloq. Math. Soc. János Bolyai, Volume 54), Amsterdam: North-Holland, 473-502. - Prucnal, T., and Wroński, A., 1974, “An algebraic
characterization of the notion of structural completeness”,
*Bulletin of the Section of Logic*, 3: 30–33. - Raftery, J., 2006, “Correspondence between Gentzen and
Hilbert systems” ,
*The Journal of Symbolic Logic*, 71: 903–957 - Rasiowa, H., 1974,
*An algebraic approach to non-classical logics*(Studies in Logic and the Foundations of Mathematics, Volume 78), Amsterdam: North-Holland. - Suszko, R., 1977, “Congruences in sentential calculus”,
in
*A report from the Autumn School of Logic*(Miedzygorze, Poland, November 21–29, 1977). Mimeographed notes, edited and compiled by J. Zygmunt and G. Malinowski. Restricted distribution. - Tarski, A., 1930a, “Über einige fundamentale Begriffe der
Metamathematik”,
*C. R. Soc. Sci. Lettr. Varsovie*, Cl. III 23: 22–29. English translation in Tarski 1983: “On some fundamental concepts of metamathematics”, 30–37. - Tarski, A. 1930b, “Fundamentale Begriffe der Methodologie der
deduktiven Wissenschaften I”,
*Monatfshefte für Mathematik und Physik*, 37: 361–404. English translation in Tarski 1983: “Fundamental concepts of the methodology of the deductive sciences”, 60–109. - Tarski, A., 1935, “Grundzüge der Systemenkalküls. Erster
Teil”,
*Fundamenta Mathematicae*, 25: 503–526, 1935. English translation in Tarski 1983: “Foundations of the calculus of systems”, 342–383. - Tarski, A., 1936, “Grundzüge der
Systemenkalküls. Zweiter Teil”,
*Fundamenta Mathematicae*, 26: 283–301, 1936. English translation in Tarski 1983: “Foundations of the calculus of systems”, 342–383. - Tarski, A., 1983,
*Logic, Semantics, Metamathematics. Papers from 1923 to 1938*, J. Corcoran (ed.), Indianapolis: Hackett, second edition. - Troelstra, A.S., 1992,
*Lecture Notes in Linear Logic*(CSLI Lecture Notes 29), Stanford: CSLI Publications. - Visser, A., 1981, “A Propositional Logic with Explicit Fixed
Points”,
*Studia Logica*, XL: 155–175. - Voutsadakis, G., 2002, “Categorical Abstract Algebraic
Logic: Algebraizable Institutions”,
*Applied Categorical Structures*10: 531–568. - Wójcicki, R., 1969, “Logical matrices strongly adequate for
structural sentential calculi”,
*Bulletin de l'Académie Polonaise des Sciences*, Classe III XVII: 333–335. - Wójcicki, R., 1973, “Matrix approach in the methodology of
sentential calculi”,
*Studia Logica*, 32: 7–37. - Wójcicki, R., 1988,
*Theory of logical calculi. Basic theory 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 the Friends of the SEP Society. Look up this entry topic at the Indiana Philosophy Ontology Project (InPhO). Enhanced bibliography for this entry at PhilPapers, with links to its database.

## Other Internet Resources

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

## Related Entries

algebra | Boole, George | Boolean algebra: the mathematics of | logic: classical | logic: intuitionistic | logic: linear | logic: many-valued | logic: modal | logic: relevance | logical consequence | model theory: first-order | Tarski, Alfred