A
Gentle Introduction to Abstract Algebraic Logic
Petr Cintula
Institute of Computer Science, Academy of Sciences of the Czech Republic
Pod Vodárenskou věží 2, 182 07 Prague, Czech Republic
http://www.cs.cas.cz/cintula/
Carles Noguera
Institute of Information Theory and Automation, Academy of Sciences of the
Czech Republic
Pod Vodárenskou věží 4, 182 08 Prague, Czech Republic
http://www.carlesnoguera.cat/
Abstract
Algebraic logic is the branch of mathematical logic that studies logical
systems by giving them algebraic semantics. It mainly capitalizes on the
standard Linbenbaum–Tarski proof of completeness of classical logic w.r.t.
the two-element Boolean algebra, which can be analogously repeated in
other logical systems yielding completeness w.r.t. other kinds of
algebras. Abstract algebraic logic (AAL) determines what are the essential
elements in these proofs and develops an abstract theory of the possible
ways in which logical systems can be related to an algebraic counterpart.
The usefulness of these methods is witnessed by the fact that the study of
many logics, relevant for mathematics, computer science, linguistics or
philosophical purposes, has greatly benefited from the algebraic approach,
that allows to understand their properties in terms of equivalent
algebraic properties of their semantics.
This course is a self-contained introduction to AAL. We start from the
very basics of AAL, develop its general and systematical theory and
illustrate the results with applications to particular examples of
propositional logics.
Syllabus
- 1. Basic
notions of algebraic logic (slides)
- formulae, proofs, logical
matrices, filters, closure operators, closure systems, Schmidt
Theorem, abstract Lindenbaum Lemma; completeness theorem w.r.t. the
class of all models; (weakly) implicative logics and examples
- 2. Lindenbaum–Tarski
method for weakly implicative logics (slides)
- Leibniz congruence, reduced
matrices, and completeness theorem w.r.t. the class of reduced models;
operators on classes of matrices; relatively (finitely) subdirectly
irreducible matrices (RFSI); completeness theorem w.r.t. RFSI reduced
models; algebraizability and order algebraizability; examples
- 3. Leibniz
operator on arbitrary logics. Leibniz hierarchy (slides)
- protoalgebraic, equivalential
and (weakly) algebraizable logics; regularity and finiteness
conditions; alternative characterizations of the classes in the
hierarchy
- 4. Advanced
topics (slides)
- bridge theorems (deduction
theorems, Craig interpolation, Beth definability); non-protoalgebraic
logics, generalized matrices, Fregean hierarchy; generalized
disjunctions and proof by cases properties (PCP) and their role in AAL
- 5. Semilinear
logics (slides)
- applications of AAL to
Mathematical Fuzzy Logic: the theory of semilinear logics
Exercises
Exercises 1–2 are in the slides for lesson 1
Exercises 3–7 are in the slides for lesson 2
Exercise 8 is in the slides for lesson 3
Prerequisites
This course is intended to be highly self-contained. Students are only
assumed to have a basic knowledge on classical propositional logic,
elementary Set Theory, and some rudiments of Universal Algebra. Knowledge
of particular non-classical logics is not necessary but would be helpful
in understanding the examples used to illustrate the theory and its
applications.
Study material
Petr Cintula and Carles Noguera: A
General Framework for Mathematical Fuzzy Logic. In Petr Cintula,
Carles Noguera, and Petr Hájek (eds). Handbook
of Mathematical Fuzzy Logic. Studies in Logic, Mathematical Logic
and Foundations, vol. 37 and 38, London, College Publications,
pages 103–207,
2011.
P.
Cintula, C. Noguera. Slabě
implikativní logiky: Úvod do abstraktního studia výrokových logik
(Weakly implicative logics: An introduction to abstract study of
propositional logics; in Czech). Filozofická
fakulta Univerzity Karlovy v Praze, Praha,
2015.
Full course description
Abstract Algebraic Logic is a relatively new subfield of Mathematical
Logic. It is a natural evolution of Algebraic Logic, which is the branch
of Mathematical Logic that studies logical systems by giving them a
semantics based on some particular kind of algebraic structures. It can be
traced back to George Boole and his study of classical propositional logic
by means of a two-element algebra that became its canonical semantics.
Linbenbaum–Tarski method was introduced to show completeness of classical
logic with respect to the semantics given by Boolean algebras. This method
identifies pairs of formulae whose equivalence can be proved from a given
theory and shows that this defines a congruence in the algebra of formulae
which actually gives a Boolean algebra in the quotient. Analogous proofs
were later used to show the completeness of non-classical logics with
respect to their corresponding algebraic semantics (e.g. intuitionistic
logic w.r.t. Heyting algebras). The fact that it could be analogously
repeated in many propositional logics led to more general studies where it
was used to show completeness theorems for broad classes of logics such as
Rasiowa's implicative logics (studied in her monograph [10]). Abstract
Algebraic Logic (AAL) was born as the natural next step to be taken in
this evolution: the abstract study of logical systems through the
generalization of the Lindenbaum–Tarski process to arbitrary logics. The
last two decades have seen the florescence of this subfield of Algebraic
Logic resulting in a deep theory of the correspondence between logics and
classes of algebras (or logical matrices defined over the algebras) which
has very recently obtained its own code in the Mathematics Subject
Classification of AMS: 03G27. A very strong link between propositional
logics and algebraic semantics was identified and systematically studied
first by Blok and Pigozzi, when they introduced the notion of
algebraizable logic in [1]. In particular, they introduced the crucial
technical notion: the Leibniz operator which maps any theory of a logic to
the congruence relation of the formulae which are provably equivalent in
the presence of such theory. Then, other classes of logics have been
obtained by relaxing the link with their algebraic semantics in terms of
properties of the Leibniz operator, which gave rise to the Leibniz
hierarchy. This classification has become the core theory of AAL because
its classes have been usefully characterized and used to obtain the
so-called bridge theorems, i.e. results connecting logical properties to
equivalent algebraic properties in the semantics (see [5,7]). An extension
of the theory encompassing logics outside the hierarchy has been developed
in [6].
The aim of this course is to present an up-to-date and self-contained
introduction to AAL. We want to present the field as a collection of
useful notions and results for any researcher in non-classical logics, for
it provides a uniform approach to propositional systems and a number of
deep theorems that allow to understand their properties in terms of
equivalent algebraic properties of their semantics. In the first two
lessons, we start from very basic syntactical and semantical notions in
algebraic logic in a very elementary theory needed to obtain three
increasingly strong algebraic completeness theorems. For the sake of
simplicity we restrict these first results to the class of weakly
implicative logics, which provide a quite general framework (containing
most well-known propositional logics: classical, intuitionistic, linear,
relevant, fuzzy, and substructural logics in the sense of [8]) but still
very simple. In the next two sessions we present the core theory of AAL
(following [5,7,9]) now at its full generality by introducing the notion
of Leibniz operator for arbitrary logic and presenting its associated
hierarchy and characterizations. In this framework we survey several
bridge theorems and illustrate on particular examples their usefulness in
the algebraic study of non-classical logics. In the same level of
generality we perform an abstract study of disjunction connectives and
their associated properties and applications (see [4]). Finally, to
conclude the course as it started, in a very down-to-earth fashion, we
restrict to another particular well-known class of non-classical logics:
fuzzy logics. Following our works [2,3] we mathematically define them as
semilinear logics and use the AAL tools introduced in the previous lessons
to provide a powerful uniform approach to these logical systems.
References
[1] W.J. Blok and D. Pigozzi. Algebraizable
logics. Memoirs of the American Mathematical Society 396, vol.
77, 1989.
[2] Petr Cintula, Carles Noguera. Implicational (Semilinear) Logics I: A
New Hierarchy. Archive for
Mathematical Logic 49 (2010) 417–446.
[3] Petr Cintula, Carles Noguera. A General Framework for Mathematical
Fuzzy Logic. In Handbook of
Mathematical Fuzzy Logic – Volume 1. Studies in Logic,
Mathematical Logic and Foundations, vol. 37, London, College Publications,
pp. 103–207, 2011.
[4] Petr Cintula, Carles Noguera. The proof by cases property and its
variants in structural consequence relations. Studia
Logica, 101(4): 713–747, 2013.
[5] Janusz Czelakowski. Protoalgebraic
Logics. Trends in Logic, vol 10, Dordercht, Kluwer, 2001.
[6] Josep Maria Font and Ramon Jansana. A
General Algebraic Semantics for Sentential Logics.
Springer-Verlag, 1996.
[7] Josep Maria Font, Ramon Jansana, and Don Pigozzi. A survey of Abstract
Algebraic Logic. Studia Logica,
74(1–2, Special Issue on Abstract Algebraic Logic II):13–97, 2003.
[8] Nikolaos Galatos, Peter Jipsen, Tomasz Kowalski, and Hiroakira Ono. Residuated Lattices: An Algebraic Glimpse
at Substructural Logics, Studies in Logic and the Foundations of
Mathematics, vol. 151, Amsterdam, Elsevier, 2007.
[9] James Raftery. Order algebraizable logics. Annals
of Pure and Applied Logic 164(3): 251–283, 2013.
[10] Helena Rasiowa. An Algebraic
Approach to Non-Classical Logics. North-Holland, Amsterdam, 1974.