Outstanding Contributions to Logic 16 Editor Janusz Czelakowski Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science Outstanding Contributions to Logic Volume 16 Editor-in-chief Sven Ove Hansson, Royal Institute of Technology, Stockholm, Sweden Editorial Board Marcus Kracht, Universität Bielefeld Lawrence Moss, Indiana University Sonja Smets, Universiteit van Amsterdam Heinrich Wansing, Ruhr-Universität Bochum More information about this series at http://www.springer.com/series/10033 Janusz Czelakowski Editor Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science 123 Editor JanuszCzelakowski Institute of Mathematics andInformatics University of Opole Opole Poland ISSN 2211-2758 ISSN 2211-2766 (electronic) Outstanding Contributions to Logic ISBN978-3-319-74771-2 ISBN978-3-319-74772-9 (eBook) https://doi.org/10.1007/978-3-319-74772-9 LibraryofCongressControlNumber:2017964448 ©SpringerInternationalPublishingAG2018 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpart of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission orinformationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodologynowknownorhereafterdeveloped. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfrom therelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authorsortheeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinor for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictionalclaimsinpublishedmapsandinstitutionalaffiliations. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringerInternationalPublishingAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Ad multos annos, Don! Preface 1. In a most surprising way logic is connected with algebra. Each language, whether natural or artificial, possesses a complex algebraic structure. In the simplest case this structure is revealed in the languages of propositional log- ics as certain absolutely free algebras. The above linguistic perspective es- tablishes the first bridge between logic and algebra. There are more links between these two domains and they exist on a deeper level. George Boole (1854) proved that the “laws of thought” can be framed algebraically as identities of an algebra. Thus, thinking is also “algebraizable”. Boole’s work was extended in various directions by a number of researchers, beginning with William Stanley Jevons. Charles Sanders Peirce integrated his work with Boole’s during the 1870s. Other significant figures were Augustus de Morgan, Platon Sergeevich Poretskii, William Ernest Johnson, and Ernst Schr¨oder.TheconceptionofaBooleanalgebrastructureonequivalentstate- ments of a propositional calculus is credited to Hugh MacColl (a four part article from 1877–1879, see (MacColl, 1906), preceding Gottlob Frege’s Be- griffschrifft). The Fregean principle of compositionality, that the meaning of any complex expression is a function of the meanings of its constituents, to- getherwithotherprinciplesiscentralinformalsemantics.Roughlyspeaking, these principles establish a homomorphism between the algebraic structure of each language and the algebraic structure constituted by meanings of the expressions of this language. The above discoveries gave rise to algebraic logic. As a result the link be- tween logic and algebra is cemented and becomes inseparable. Studying the dependenceexistingbetweenthemisstilloneofthevitalareasofscientificac- tivity.Itisalsointhisverycontextthatthedifferentiationoftheprofessional belonging of the individual researcher—a logician or an algebraist—becomes blurred. 2. Professor Don Pigozzi, together with his colleagues who cooperated with himattheturnofthe1980sandthe1990s,managedtoeffectachangeofthe paradigm of algebraic logic. This new situation can best be illustrated with vii viii Preface thisanalogy:atthebeginningofthe20thcentury,mathematicianscarriedout extensivestudiesintheareaoffunctionspaces,e.g.,thespacesofcontinuous functions on compact topological spaces, the spaces of absolutely integrable functions on measure spaces, etc. A series of deep and detailed results was obtained regarding this sphere. Still, there was a lack of the right key to the general theory which would allow ordering the research field and deriving well-knownparticularcasesfromafewnotionsandtheorems.Obviously,the notion of a Hilbert space did order a certain section of the field. However, what was obtained then was rather a set of facts loosely connected with one another, though each separately was an original and deep mathematical the- orem. It was not until the theory of Banach spaces was put forward, along with its apparatus of notions and key theorems, that the gathered research material could be ordered and adequate mathematical arsenal was provided tomakeitpossibletolayfoundationsoffunctionalanalysis.Wecametodeal with a similar situation in algebraic logic in the second half of the last cen- tury.Thecontinuumoflogicalsystems,groupedintosomecategories(modal systems,temporalsystems,systemofdynamiclogic,relevantlogics,etc.),en- teredthestageforgood.Thethenliteratureofthesubjectaboundedindiffi- cultandsophisticatedmetalogicalresultswhichcharacterizedvariousaspects of individual systems. In the study of the systems, new semantic tools, like relational semantics, neighborhood semantics, and the like, are made use of. Still,sometypesofsemanticshavelimitations,sincenoteverysystemcanbe adequately semantically characterized in terms of an appropriate complete- nesstheorem;thereappearsthephenomenonofsemanticalincompleteness— wearefamiliarwith,e.g.,normalmodalsystems,notpossessinganadequate Kripke-style semantics. It was known that the path from a logical system to algebraic semantics leads through Lindenbaum-Tarski algebras (Linden- baum(1929),Tarski(1930),L ukasiewiczandTarski(1930)).Thatwasawell- markedandreliablerouteforclassicallogic,intuitionisticlogic,andaseriesof other logics. Helena Rasiowa, in her pioneering monograph (Rasiowa, 1974), introducedimplicativesystems,thoughttobeabroadclassoflogicalsystems forwhichthegeneralizationoftheLindenbaum-Tarskimethod,whichshein- vestigated,did“work”.Here,thekeywasthenotionofanimplication,viewed asabinaryconnectivesatisfyingnaturalassumptions,analogoustotheprop- erties of the implication of classical or intuitionistic logics. Nevertheless, the class of S-logics investigated by Rasiowa does not encompass many elemen- tary intensional systems, like the main modal logics. If one goes through the relevant literature of the 1970s, the scenery was saturated with millions of logical systems, each of which being somehow important, individually exam- inedanddescribed.However,therewerenomethodologicaltoolsavailableof sufficient generality which would allow framing theses systems from a uni- formresearchperspective.Again,thekeywhichallowedintroducinganorder were the notions of the Leibniz operator and of a protoalgebraic logics, the latter employing the above-mentioned operator. Both notions were explicitly defined by Wim Blok and Don Pigozzi (1986), (1989). Although the both Preface ix notions had been known in the literature under other names (e.g., W´ojcicki (1988)inhisearlierworkswroteaboutthelargestmatrixcongruenceswhich are the same objects as Leibniz congruences, and Czelakowski (1985, 1986) isolatedtheclassofnon-pathologicallogics,thestudieslaunchedbyWimBlok andDonPigozziintroducedauniversalnotionalnetwork,aswellasgaverise to systematic investigations conducted in the new language of abstract al- gebraic logic (AAL, in short). It is considered that the most important and indisputable achievements of them are the introduction of the notion of an algebraizablelogicinthepioneeringmonographentitledAlgebraizable Logics andalsogivingthekeypropertiescharacterizingthisclass.Algebraizabilityis arigorousmathematicalnotionsystematicallyinvestigatedbymanylogicians since then. (We omit its definition here.) 3. It can be argued that studies in the field of logic, which were carried out in the 1960s and the 1970s, whose nucleus was the notion of a consequence operation,didnotmeetwithabroaderinterestatthattime.Theconsequence theory, whose fundamentals had already been laid by Alfred Tarski after the World War I (see Tarski (1956) remained rather underestimated. It was mainly Tarski’s concept of truth in formalized languages which attracted interest as his first-rate achievement, especially in the context of later model theoretic and algebraic applications. Apparently it was so. A few causes of suchastateofthingscanbeindicated.Firstly,thethentrendsintheworld’s logic were different and the foundations of mathematics laid, in particular, byKurtG¨odelandhisdiscoveriesdevelopedrecursiontheoryandsettheory, especially upon introducing the notion of forcing by Paul Cohen. In many universities the methods of relational semantics for intensional logics were developed.Asitwasmentioned,intheWarsawschoolofAndrzejMostowski, Helena Rasiowa and Roman Sikorski the algebraic foundations were created for a broad class of non-classical logics, viz. the extended implicative calculi. Roman Suszko, Ryszard W´ojcicki and their disciples were also active at that time. What is a logical system then? In the literature, we will find several def- initions. Here, we will limit ourselves to two of them only. Logic (on the propositional level) is most often understood as a set of formulas closed with respect to substitutions and certain rules of inference. For example, an array of modal logics is defined in this way. In another approach, the basic no- tional frame is composed by structural and finitary consequence operations defined on pertinent languages. This is a more general approach than the former one. The following problem is connected with it: if one accepts the notion of logic, viewed as a certain invariant set of formulas, to be the ba- sis, what consequence operation should be attached to this set? On the level of normal modal systems, as e.g. S4, one can associate, in a natural way, two different consequence operations with each such a system: the first—the so-calledweak consequence,determinedbythegivensystem,andthedetach- ment rule, as a primitive rule of inference, as well as the so-called strong consequence, formed out of the weak one by adjoining the G¨odel rule as a x Preface primitiverule(andtherebyapplicableinallderivations!).Whichconsequence shouldbechosen?Thisdependsontheresearchpreferencesofthegivenlogi- cian.Forinstance,withintheframeworkoftherapidlydevelopingunification theory for propositional and equational logics, one investigates structurally completeoralmoststructurallycompletesystems.Naturally,therearesolely strong modal consequences in sight there. Comprehensive studies of logical systems, chiefly intensional ones, such as modal or temporal logics, etc., which have been conducted in recent years, have caused the consequence theory to be placed in the focal point. The cre- ation of the theory of entailment relation (this term can be translated as a multi-conclusion consequence relation), hybrid logics, substructural logics and the growing interest in non-monotonic reasonings has exercised a strong impact on consequence theory. The existence of a continuum of logical sys- tems, of various references and applications, be it in informatics, philosophy, or theory of language or others, resulted in the need of ordering the research field,findingafewcommonprinciples,accordingtowhichonecannotionally embrace the complex matter of contemporary logic. TheintroductionoftheLeibnizandSuszkooperatorsmarkedanewstage for metalogic. It was discovered that a uniform classification scheme encom- passingalllogicalsystemscanbebasedonsomeplausiblepropertiesofthese operators. As a result, abstract algebraic logic (AAL) has emerged. AAL offers a transparent and natural hierarchy of logical systems (and not only propositional ones); each level of the hierarchy is determined by a simple and concrete property of the above-listed operators, such as monotonicity or order-continuity.Letusunderlinethatthenotionofaconsequenceoperation is of key importance in the AAL. 4.ThecentralissuethatunderlayAALwastogetthegistofthedependence between logic and algebra from the mathematical viewpoint; the point is aboutthequestionwhichforover150yearshasbeenpermeatingthehistoryof the both disciplines. AALtakesamoreabstractandgeneralapproachthanthetraditionalalge- braic logic. In contrast to algebraic logic, where the focus is on the algebraic forms of specific deductive systems, AAL is concerned with the process of al- gebraization itself. AAL investigates degrees of algebraizability of deductive systems,makinguseofrigorousmathematicaltools.Thedegreeofalgebraiz- ability of a system is determined by the place of the system in the hierachy of logics based on the Leibniz operator. The problem area of AAL and the issue of algebraizability of logical sys- tems in particular, have set new tasks to algebra and logic, viz. to describe the algebraic semantics for deductive systems. The relation between algebra and logic is the strongest in the case of algebraizable systems. Speaking in the most general way, algebraizability of a system L consists in determining the conditions which allow replacing the process of deduction of logical for- mulas by the process of congruence generation on appropriate algebras in an equivalent manner on the ground of this equational system.