This volume is not restricted to papers presented at the 1988 Colloquium, but instead aims to provide the reader with a (relatively) coherent reading on Algebraic Logic, with an emphasis on current research. To help the non-specialist reader, the book contains an introduction to cylindric and relation algebras by Roger D. Maddux and an introduction to Boolean Algebras by Bjarni Joacute;nsson.

Robert Burch describes Peircean Algebraic Logic as a language to express Peirce's “unitary logical vision” , which Peirce tried to formulate using different logical systems. A “correct” formulation of Peirce's vision then should allow a mathematical proof of Peirce's Reduction Thesis, that all relations can be generated from the ensemble of unary, binary, and ternary relations, but that at least some ternary relations cannot be reduced to relations of lower arity.Based on Burch's algebraization, the authors further simplify the (...) mathematical structure of PAL and remove a restriction imposed by Burch, making the resulting system in its expressiveness more similar to Peirce's system of existential graphs. The drawback, however, is that the proof of the Reduction Thesis from Burch no longer holds. A new proof was introduced in Hereth Correia, and Pöschel and was published in full detail in Hereth .In this paper, we provide proof of Peirce's Reduction Thesis using a graph notation similar to Peirce's existential graphs. (shrink)

This is a supplement to the paper “Finitary Algebraic Logic” [1]. It includes corrections for several errors and some additional results. MSC: 03G15, 03G25.

In this paper we study the relations between the fragment L of classical logic having just conjunction and disjunction and the variety D of distributive lattices, within the context of Algebraic Logic. We prove that these relations cannot be fully expressed either with the tools of Blok and Pigozzi's theory of algebraizable logics or with the use of reduced matrices for L. However, these relations can be naturally formulated when we introduce a new notion of model of (...) a sequent calculus. When applied to a certain natural calculus for L, the resulting models are equivalent to a class of abstract logics (in the sense of Brown and Suszko) which we call distributive. Among other results, we prove that D is exactly the class of the algebraic reducts of the reduced models of L, that there is an embedding of the theories of L into the theories of the equational consequence (in the sense of Blok and Pigozzi) relative to D, and that for any algebra A of type (2,2) there is an isomorphism between the D-congruences of A and the models of L over A. In the second part of this paper (which will be published separately) we will also apply some results to give proofs with a logical flavour for several new or well-known lattice-theoretical properties. (shrink)

The general aim of this article is to study the negation fragment of classical logic within the framework of contemporary (Abstract) Algebraic Logic. More precisely, we shall find the three classes of algebras that are canonically associated with a logic in Algebraic Logic, i.e. we find the classes |$\textrm{Alg}^*$|⁠, |$\textrm{Alg}$| and the intrinsic variety of the negation fragment of classical logic. In order to achieve this, firstly, we propose a Hilbert-style axiomatization for this (...) fragment. Then, we characterize the reduced matrix models and the full generalized matrix models of this logic. Also, we classify the negation fragment in the Leibniz and Frege hierarchies. (shrink)

In this paper we define the polyadic Pavelka algebras as algebraic structures for Rational Pavelka predicate calculus . We prove two representation theorems which are the algebraic counterpart of the completness theorem for RPL∀.

Protoalgebraic logics are characterized by the monotonicity of the Leibniz operator on their theory lattices and are at the lower end of the Leibniz hierarchy of abstract algebraic logic. They have been shown to be the most primitive among those logics with a strong enough algebraic character to be amenable to algebraic study techniques. Protoalgebraic π-institutions were introduced recently as an analog of protoalgebraic sentential logics with the goal of extending the Leibniz hierarchy from the sentential (...) framework to the π-institution framework. Many properties of protoalgebraic logics, studied in the sentential logic framework by Blok and Pigozzi, Czelakowski, and Font and Jansana, among others, have already been adapted in previous work by the author to the categorical level. This work aims at further advancing that study by exploring in this new level some more properties of protoalgebraic sentential logics. (shrink)

In this paper we study the relations between the fragment L of classical logic having just conjunction and disjunction and the variety D of distributive lattices, within the context of Algebraic Logic. We prove that these relations cannot be fully expressed either with the tools of Blok and Pigozzi's theory of algebraizable logics or with the use of reduced matrices for L. However, these relations can be naturally formulated when we introduce a new notion of model of (...) a sequent calculus. When applied to a certain natural calculus for L, the resulting models are equivalent to a class of abstract logics (in the sense of Brown and Suszko) which we call distributive. Among other results, we prove that D is exactly the class of the algebraic reducts of the reduced models of L, that there is an embedding of the theories of L into the theories of the equational consequence (in the sense of Blok and Pigozzi) relative to D, and that for any algebra A of type (2,2) there is an isomorphism between the D-congruences of A and the models of L over A. In the second part of this paper (which will be published separately) we will also apply some results to give proofs with a logical flavour for several new or well-known lattice-theoretical properties. (shrink)

An important part of the theory of algebraizable sentential logics consists of studying the algebraic semantics of these logics. As developed by Czelakowski, Blok, and Pigozzi and Font and Jansana, among others, it includes studying the properties of logical matrices serving as models of deductive systems and the properties of abstract logics serving as models of sentential logics. The present paper contributes to the development of the categorical theory by abstracting some of these model theoretic aspects and results from (...) the level of sentential logics to the level of π-institutions. (shrink)

Two famous negative results about da Costa’s paraconsistent logic ${\mathscr {C}}_1$ (the failure of the Lindenbaum–Tarski process [44] and its non-algebraizability [39]) have placed ${\mathscr {C}}_1$ seemingly as an exception to the scope of Abstract Algebraic Logic (AAL). In this paper we undertake a thorough AAL study of da Costa’s logic ${\mathscr {C}}_1$. On the one hand, we strengthen the negative results about ${\mathscr {C}}_1$ by proving that it does not admit any algebraic semantics whatsoever (...) in the sense of Blok and Pigozzi (a weaker notion than algebraizability also introduced in the monograph [6]). On the other hand, ${\mathscr {C}}_1$ is a protoalgebraic logic satisfying a Deduction-Detachment Theorem (DDT). We then extend our AAL study to some paraconsistent axiomatic extensions of ${\mathscr {C}}_1$ covered in the literature. We prove that for extensions ${\mathcal {S}}$ such as ${\mathcal {C}ilo}$ [26], every algebra in ${\mathsf {Alg}}^*({\mathcal {S}})$ contains a Boolean subalgebra, and for extensions ${\mathcal {S}}$ such as,, or [16, 53], every subdirectly irreducible algebra in ${\mathsf {Alg}}^*({\mathcal {S}})$ has cardinality at most 3. We also characterize the quasivariety ${\mathsf {Alg}}^*({\mathcal {S}})$ and the intrinsic variety $\mathbb {V}({\mathcal {S}})$, with,, and. (shrink)

Jones' proposed application of Optimality Theory assumes the primary kinship data are genealogical definitions of kin terms. This, however, ignores the fact that these definitions can be predicted from the computational, algebralike structural logic of kinship terminologies, as has been discussed and demonstrated in numerous publications. The richness of human kinship systems derives from the cultural knowledge embedded in kinship terminologies as symbolic computation systems, not the post hoc constraints devised by Jones.

In the first section of this paper I present a well known objection to meaning holism, according to which holism is inconsistent with natural language being learnable. Then I show that the objection fails if language acquisition includes stages of partial grasp of the meaning of at least some expressions, and I argue that standard model theoretic semantics cannot fully capture such stages. In the second section the above claims are supported through a review of current research into language acquisition. (...) Finally, in the third section it is argued that contemporary algebraic logical systems consist in a superior formal vehicle through which to capture stages of partial grasp of meaning; this claim is supported by concrete examples. (shrink)

A term td is called a ternary deductive term for a variety of algebras V if the identity td≈r holds in V and ∈θ yields td≈td for any A∈V and any principal congruence θ on A. A connective f is called td-distributive if td)≈ f,…,td). If L is a propositional logic and V is a corresponding variety that has a TD term td, then any admissible in L rule, the premises of which contain only td-distributive operations, is derivable, and (...) the substitution r↦td is a projective L-unifier for any formula containing only td-distributive connectives. The above substitution is a generalization of the substitution introduced by T. Prucnal to prove structural completeness of the implication fragment of intuitionistic propositional logic. (shrink)

The present paper is a study in abstract algebraic logic. We investigate the correspondence between the metalogical Beth property and the algebraic property of surjectivity of epimorphisms. It will be shown that this correspondence holds for the large class of equivalential logics. We apply our characterization theorem to relevance logics and many-valued logics.

This is a survey article on algebraic logic. It gives a historical background leading up to a modern perspective. Central problems in algebraic logic (like the representation problem) are discussed in connection to other branches of logic, like modal logic, proof theory, model-theoretic forcing, finite combinatorics, and Gödel’s incompleteness results. We focus on cylindric algebras. Relation algebras and polyadic algebras are mostly covered only insofar as they relate to cylindric algebras, and even there we (...) have not told the whole story. We relate the algebraic notion of neat embeddings (a notion special to cylindric algebras) to the metalogical ones of provability, interpolation and omitting types in variants of first logic. Another novelty that occurs here is relating the algebraic notion of atom-canonicity for a class of boolean algebras with operators to the metalogical one of omitting types for the corresponding logic. A hitherto unpublished application of algebraic logic to omitting types of first order logic is given. Proofs are included when they serve to illustrate certain concepts. Several open problems are posed. We have tried as much as possible to avoid exploring territory already explored in the survey articles of Monk [93] and Németi [97] in the subject. (shrink)

A boolean algebra is shown to be completely representable if and only if it is atomic, whereas it is shown that neither the class of completely representable relation algebras nor the class of completely representable cylindric algebras of any fixed dimension are elementary.

A category theoretic generalization of the theory of algebraizable deductive systems of Blok and Pigozzi is developed. The theory of institutions of Goguen and Burstall is used to provide the underlying framework which replaces and generalizes the universal algebraic framework based on the notion of a deductive system. The notion of a term -institution is introduced first. Then the notions of quasi-equivalence, strong quasi-equivalence and deductive equivalence are defined for -institutions. Necessary and sufficient conditions are given for the quasi-equivalence (...) and the deductive equivalence of two term -institutions, based on the relationship between their categories of theories. The results carry over without any complications to institutions, via their associated -institutions. The -institution associated with a deductive system and the institution of equational logic are examined in some detail and serve to illustrate the general theory. (shrink)

We review, and in the process unify two techniques , for proving results concerning amalgamation in several classes studied in algebraic logic. The logical counterpart of these results adress interpolation and definability properties in modal and algebraic logic. Presenting them in a functorial context as adjoint situations, we show that both techniques can indeed be seen as instances of the use of the Keisler-Shelah ultrapower Theorem in proving Robinson's Joint Consistency Theorem. Some new results are surveyed. (...) The results of this paper are presented in such a way that further establishes the hitherto existing well developed duality theory between boolean algebras with operators and modal logic. (shrink)

This paper contains a joint study of two sentential logics that combine a many-valued character, namely tetravalence, with a modal character; one of them is normal and the other one quasinormal. The method is to study their algebraic counterparts and their abstract models with the tools of Abstract Algebraic Logic, and particularly with those of Brown and Suszko's theory of abstract logics as recently developed by Font and Jansana in their "A General Algebraic Semantics for Sentential (...) Logics". The logics studied here arise from the algebraic and lattice-theoretical properties we review of Tetravalent Modal Algebras, a class of algebras studied mainly by Loureiro, and also by Figallo, Landini and Ziliani, at the suggestion of the late Antonio Monteiro. (shrink)

Wojcicki introduced in the late 1970s the concept of a referential semantics for propositional logics. Referential semantics incorporate features of the Kripke possible world semantics for modal logics into the realm of algebraic and matrix semantics of arbitrary sentential logics. A well-known theorem of Wojcicki asserts that a logic has a referential semantics if and only if it is selfextensional. Referential semantics was subsequently studied in detail by Malinowski and the concept of selfextensionality has played, more recently, an (...) important role in the field of abstract algebraic logic in connection with the operator approach to algebraizability. We introduce and review some of the basic definitions and results pertaining to the referential semantics of π-institutions, abstracting corresponding results from the realm of propositional logics. (shrink)

An algebraization of multi-signature first-order logic without terms is presented. Rather than following the traditional method of choosing a type of algebras and constructing an appropriate variety, as is done in the case of cylindric and polyadic algebras, a new categorical algebraization method is used: The substitutions of formulas of one signature for relation symbols in another are treated in the object language. This enables the automatic generation via an adjunction of an algebraic theory. The algebras of this (...) theory are then used to algebraize first-order logic. (shrink)

Transfer theorems are central results in abstract algebraic logic that allow to generalize properties of the lattice of theories of a logic to any algebraic model and its lattice of filters. Their proofs sometimes require the existence of a natural extension of the logic to a bigger set of variables. Constructions of such extensions have been proposed in particular settings in the literature. In this paper we show that these constructions need not always work and (...) propose a wider setting in which they can still be used. (shrink)

A boolean algebra is shown to be completely representable if and only if it is atomic, whereas it is shown that neither the class of completely representable relation algebras nor the class of completely representable cylindric algebras of any fixed dimension (at least 3) are elementary.

This paper deals with the algebraization of multi-signature equational logic in the context of the modern theory of categorical abstract algebraic logic. Two are the novelties compared to traditional treatments: First, interpretations between different algebraic types are handled in the object language rather than the metalanguage. Second, rather than constructing the type of the algebraizing class of algebras explicitly in an ad-hoc universal algebraic way, the whole clone is naturally constructed using categorical algebraic techniques.

This paper presents a unified framework that explains and extends the already successful applications of the Leibniz operator, the Suszko operator, and the Tarski operator in recent developments in abstract algebraic logic. To this end, we refine Czelakowski’s notion of an S-compatibility operator, and introduce the notion of coherent family of S-compatibility operators, for a sentential logic S. The notion of coherence is a restricted property of commutativity with inverse images by surjective homomorphisms, which is satisfied by (...) both the Leibniz and the Suszko operators. We generalize several constructions and results already existing for the mentioned operators; in particular, the well-known classes of algebras associated with a logic through each of them, and the notions of full generalized model of a logic and a special kind of S-filters. We obtain a General Correspondence Theorem, extending the well-known one from the theory of protoalgebraic logics to arbitrary logics and to more general operators, and strengthening its formulation. We apply the general results to the Leibniz and the Suszko operators, and obtain several characterizations of the main classes of logics in the Leibniz hierarchy by the form of their full generalized models, by old and new properties of the Leibniz operator, and by the behaviour of the Suszko operator. Some of these characterizations complete or extend known ones, for some classes in the hierarchy, thus offering an integrated approach to the Leibniz hierarchy that uncovers some new, nice symmetries. (shrink)

Wójcicki has provided a characterization of selfextensional logics as those that can be endowed with a complete local referential semantics. His result was extended by Jansana and Palmigiano, who developed a duality between the category of reduced congruential atlases and that of reduced referential algebras over a fixed similarity type. This duality restricts to one between reduced atlas models and reduced referential algebra models of selfextensional logics. In this paper referential algebraic systems and congruential atlas systems are introduced, which (...) abstract referential algebras and congruential atlases, respectively. This enables the formulation of an analog of Wójcicki’s Theorem for logics formalized as π-institutions. Moreover, the results of Jansana and Palmigiano are generalized to obtain a duality between congruential atlas systems and referential algebraic systems over a fixed categorical algebraic signature. In future work, the duality obtained in this paper will be used to obtain one between atlas system models and referential algebraic system models of an arbitrary selfextensional π-institution. Using this latter duality, the characterization of fully selfextensional deductive systems among the selfextensional ones, that was obtained by Jansana and Palmigiano, can be extended to a similar characterization of fully selfextensional π-institutions among appropriately chosen classes of selfextensional ones. (shrink)

This book celebrates the work of Don Pigozzi on the occasion of his 80th birthday. In addition to articles written by leading specialists and his disciples, it presents Pigozzi’s scientific output and discusses his impact on the development of science. The book both catalogues his works and offers an extensive profile of Pigozzi as a person, sketching the most important events, not only related to his scientific activity, but also from his personal life. It reflects Pigozzi's contribution to the rise (...) and development of areas such as abstract algebraic logic, universal algebra and computer science, and introduces new scientific results. Some of the papers also present chronologically ordered facts relating to the development of the disciplines he contributed to, especially abstract algebraic logic. The book offers valuable source material for historians of science, especially those interested in history of mathematics and logic. (shrink)

A category theoretic generalization of the theory of algebraizable deductive systems of Blok and Pigozzi is developed. The theory of institutions of Goguen and Burstall is used to provide the underlying framework which replaces and generalizes the universal algebraic framework based on the notion of a deductive system. The notion of a term π-institution is introduced first. Then the notions of quasi-equivalence, strong quasi-equivalence and deductive equivalence are defined for π-institutions. Necessary and sufficient conditions are given for the quasi-equivalence (...) and the deductive equivalence of two term π-institutions, based on the relationship between their categories of theories. The results carry over without any complications to institutions, via their associated π-institutions. The π-institution associated with a deductive system and the institution of equational logic are examined in some detail and serve to illustrate the general theory. (shrink)

Equivalent deductive systems were introduced in [4] with the goal of treating 1‐deductive systems and algebraic 2‐deductive systems in a uniform way. Results of [3], appropriately translated and strengthened, show that two deductive systems over the same language type are equivalent if and only if their lattices of theories are isomorphic via an isomorphism that commutes with substitutions. Deductive equivalence of π‐institutions [14, 15] generalizes the notion of equivalence of deductive systems. In [15, Theorem 10.26] this criterion for the (...) equivalence of deductive systems was generalized to a criterion for the deductive equivalence of term π‐institutions, forming a subclass of all π‐institutions that contains those π‐institutions directly corresponding to deductive systems. This criterion is generalized here to cover the case of arbitrary π‐institutions. (shrink)

Metalogical properties that have traditionally been studied in the deductive system context (see, e.g., [21]) and transferred later to the institution context [33], are here formulated in the -institution context. Preservation under deductive equivalence of -institutions is investigated. If a property is known to hold in all algebraic -institutions and is preserved under deductive equivalence, then it follows that it holds in all algebraizable -institutions in the sense of [36].

We formulate several statements in Algebraic Logic that turn out to be independent of ZFC. We relate such statements to Martin's axiom, omitting types for variants of first order logic and topological properties of Baire spaces.

Finitely algebraizable deductive systems were introduced by Blok and Pigozzi to capture the essential properties of those deductive systems that are very tightly connected to quasivarieties of universal algebras. They include the equivalential logics of Czelakowski. Based on Blok and Pigozzi’s work, Herrmann defined algebraizable deductive systems. These are the equivalential deductive systems that are also truth-equational, in the sense that the truth predicate of the class of their reduced matrix models is explicitly definable by some set of unary equations. (...) Raftery undertook the task of characterizing the property of truth-equationality for arbitrary deductive systems. In this paper, following Raftery, we extend the notion of truth-equationality for logics formalized as $\pi$-institutions and abstract several of the results that hold for deductive systems in this more general categorical context. (shrink)

Recently, Caleiro, Gon¸calves and Martins introduced the notion of behaviorally algebraizable logic. The main idea behind their work is to replace, in the traditional theory of algebraizability of Blok and Pigozzi, unsorted equational logic with multi-sorted behavioral logic. The new notion accommodates logics over many-sorted languages and with non-truth-functional connectives. Moreover, it treats logics that are not algebraizable in the traditional sense while, at the same time, shedding new light to the equivalent algebraic semantics of logics (...) that are algebraizable according to the original theory. In this paper, the notion of an abstract multi-sorted π-institution is introduced so as to transfer elements of the theory of behavioral algebraizability to the categorical setting. Institutions formalize a wider variety of logics than deductive systems, including logics involving multiple signatures and quantifiers. The framework developed has the same relation to behavioral algebraizability as the classical categorical abstract algebraic logic framework has to the original theory of algebraizability of Blok and Pigozzi. (shrink)

Equivalent deductive systems were introduced in [4] with the goal of treating 1-deductive systems and algebraic 2-deductive systems in a uniform way. Results of [3], appropriately translated and strengthened, show that two deductive systems over the same language type are equivalent if and only if their lattices of theories are isomorphic via an isomorphism that commutes with substitutions. Deductive equivalence of π-institutions [14, 15] generalizes the notion of equivalence of deductive systems. In [15, Theorem 10.26] this criterion for the (...) equivalence of deductive systems was generalized to a criterion for the deductive equivalence of term π-institutions, forming a subclass of all π-institutions that contains those π-institutions directly corresponding to deductive systems. This criterion is generalized here to cover the case of arbitrary π-institutions. (shrink)

This work adapts techniques and results first developed by Malinowski and by Marek in the context of referential semantics of sentential logics to the context of logics formalized as π-institutions. More precisely, the notion of a pseudoreferential matrix system is introduced and it is shown how this construct generalizes that of a referential matrix system. It is then shown that every π–institution has a pseudo-referential matrix system semantics. This contrasts with referential matrix system semantics which is only available for self-extensional (...) π-institutions by a previous result of the author obtained as an extension of a classical result of Wójcicki. Finally, it is shown that it is possible to replace an arbitrary pseudoreferential matrix system semantics by a discrete pseudo-referential matrix system semantics. (shrink)