Logic, Algebra and Implication

Petr Cintula

Institute of Computer Science
Academy of Sciences of Czech Republic

Carles Noguera

Artificial Intelligence Research Institute
Spanish Council for Scientific Research

Abstract Algebraic Logic is a relatively new subfield of Mathematical Logic. It is a natural evolution of Algebraic Logic, a branch of Mathematical Logic studying logical systems by giving them an algebra-based semantics. 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. Other non-classical logics enjoy a strong connection with algebras as well intuitionistic logic and Heyting algebras, substructural logic and residuated lattices, etc.). Abstract Algebraic Logic (AAL) was born as the natural next step to be taken in this evolution: the abstract study of logical systems through their interplay with algebraic semantics.

One of the starting points of AAL is the book by Helena Rasiowa [6] where she studies logics possessing a reasonable implication connective. Her approach was later gradually generalized into a genuinely abstract theory~[1,4,5]. A crucial technical notion used is this process is 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. Logics were classified by means of properties of Leibniz operator, which gave rise to the two-dimensional Leibniz hierarchy. This classification, starting with the biggest class of protoalgebraic logics, became the core theory of AAL due to its robustness, the characterizations of its classes, and their usefulness for obtaining bridge theorems, i.e. results connecting logical properties to equivalent algebraic properties in the semantics.

The aim of this course is to present a self-contained introduction to AAL. For didactic reasons we present the full Leibniz hierarchy at the end of the tutorial only and, for most of the time, we simplify our account to yet another generalization of Rasiowa approach: the class of weakly implicative logics [2,3]. Although this can be viewed as a rather minor generalization, it provides a relatively simple framework which allows us to describe the arguably more important dimension of Leibniz hierarchy and to demonstrate the strength of existing abstract results.

Session 1
Basic notions of algebraic logic: formulae, proofs, logical matrices, filters. Completeness theorem w.r.t. the class of all models. Implications and order relations in matrices. Lindenbaum-Tarski method for weakly implicative logics: Leibniz congruence, reduced matrices, and completeness theorem w.r.t. the class of reduced models.

Session 2
Advanced semantical notions: closure operators, closure systems, Schmidt Theorem, abstract Lindenbaum Lemma, operators on classes of matrices, relatively (finitely) subdirectly irreducible matrices(RFSI). Completeness theorem w.r.t. RFSI reduced models. Algebraizability and order algebraizability. Examples.

Session 3
Leibniz operator on arbitrary logics. Leibniz hierarchy protoalgebraic, equivalential and (weakly) algebraizable logics. Regularity and finiteness conditions. Alternative characterizations of the classes in the hierarchy. Bridge theorems (deduction theorems, Craig interpolation, Beth definability).

 


 

 

 

 

 


 

References


[1] W.J. Blok and D. Pigozzi. Algebraizable logics, Memoirs of the American Mathematical Society 396, vol 77, 1989.


[2] Petr Cintula. Weakly 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, Handbook of Mathematical Fuzzy Logic, chapter II, P. Cintula, P. Hájek, C. Noguera (eds), Studies in Logic, Mathematical Logic and Foundations, vol.37, College Publications, London, 2011, pp. 103-207.


[4] Janusz Czelakowski. Protoalgebraic Logics, volume 10 of Trends in Logic. Kluwer, Dordercht, 2001.


[5] 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.

[6] Helena Rasiowa. An Algebraic Approach to Non-Classical Logics. North-Holland, Amsterdam, 1974.


Prerequisites

This is an introductory course and as such will be highly self-contained. Students will only be assumed to have a basic knowledge on classical propositional logic and elementary set theory, and some rudiments of universal algebra.


 

 

�>