W. J. Blok and Don Pigozzi set out to try to answer the question of what it means for a logic to have algebraic semantics. In this seminal book they transformed the study of algebraic logic by giving a general framework for the study of logics by algebraic means. The Dutch mathematician W. J. Blok (1947-2003) received his doctorate from the University of Amsterdam in 1979 and was Professor of Mathematics at the University of Illinois, Chicago until his death in (...) an automobile accident. Don Pigozzi (1935- ) grew up in Oakland, California, received his doctorate from the University of California, Berkeley in 1970, and was Professor of Mathematics at Iowa State University until his retirement in 2002. The Advanced Reasoning Forum is pleased to make available in its Classic Reprints series this exact reproduction of the 1989 text, with a new errata sheet prepared by Don Pigozzi. (shrink)

Volume I provides a detailed analysis of cylindric algebras, starting with a formulation of their axioms and a development of their elementary properties, and proceeding to a deeper study of their interrelationships by means of general algebraic notions such as subalgebras, homomorphisms, direct products, free algebras, reducts and relativized algebras.

N´emeti remarked that the notion of compactness of cylindric of algebras corresponds to the notion of universality of models in logic [5]. The purpose of this paper is to formulate this correspondence in a purely algebraic setting.

Vorlesungen über die Algebra der Logik ist ein unveränderter, hochwertiger Nachdruck der Originalausgabe aus dem Jahr 1890. Hansebooks ist Herausgeber von Literatur zu unterschiedlichen Themengebieten wie Forschung und Wissenschaft, Reisen und Expeditionen, Kochen und Ernährung, Medizin und weiteren Genres. Der Schwerpunkt des Verlages liegt auf dem Erhalt historischer Literatur. Viele Werke historischer Schriftsteller und Wissenschaftler sind heute nur noch als Antiquitäten erhältlich. Hansebooks verlegt diese Bücher neu und trägt damit zum Erhalt selten gewordener Literatur und historischem Wissen auch für die (...) Zukunft bei. (shrink)

Dynamic algebras combine the classes of Boolean (B 0) and regular (R ; *) algebras into a single finitely axiomatized variety (B R ) resembling an R-module with scalar multiplication . The basic result is that * is reflexive transitive closure, contrary to the intuition that this concept should require quantifiers for its definition. Using this result we give several examples of dynamic algebras arising naturally in connection with additive functions, binary relations, state trajectories, languages, and flowcharts. The main result (...) is that free dynamic algebras are residually finite (i.e. factor as a subdirect product of finite dynamic algebras), important because finite separable dynamic algebras are isomorphic to Kripke structures. Applications include a new completeness proof for the Segerberg axiomatization of prepositional dynamic logic, and yet another notion of regular algebra. (shrink)

We consider the problem of finding and classifying representations in algebraic logic. This is approached by letting two players build a representation using a game. Homogeneous and universal representations are characterized according to the outcome of certain games. The Lyndon conditions defining representable relation algebras (for the finite case) and a similar schema for cylindric algebras are derived. Finite relation algebras with homogeneous representations are characterized by first order formulas. Equivalence games are defined, and are used to establish whether an (...) algebra is ω-categorical. We have a simple proof that the perfect extension of a representable relation algebra is completely representable. An important open problem from algebraic logic is addressed by devising another two-player game, and using it to derive equational axiomatisations for the classes of all representable relation algebras and representable cylindric algebras. Other instances of this approach are looked at, and include the step by step method. (shrink)

The calculus of relations was created and developed in the second half of the nineteenth century by Augustus De Morgan, Charles Sanders Peirce, and Ernst Schröder. In 1940 Alfred Tarski proposed an axiomatization for a large part of the calculus of relations. In the next decade Tarski's axiomatization led to the creation of the theory of relation algebras, and was shown to be incomplete by Roger Lyndon's discovery of nonrepresentable relation algebras. This paper introduces the calculus of relations and the (...) theory of relation algebras through a review of these historical developments. (shrink)

Completed in 1983, this work culminates nearly half a century of the late Alfred Tarski's foundational studies in logic, mathematics, and the philosophy of science. Written in collaboration with Steven Givant, the book appeals to a very broad audience, and requires only a familiarity with first-order logic. It is of great interest to logicians and mathematicians interested in the foundations of mathematics, but also to philosophers interested in logic, semantics, algebraic logic, or the methodology of the deductive sciences, and to (...) computer scientists interested in developing very simple computer languages rich enough for mathematical and scientific applications. The authors show that set theory and number theory can be developed within the framework of a new, different, and simple equational formalism, closely related to the formalism of the theory of relation algebras. There are no variables, quantifiers, or sentential connectives. Predicates are constructed from two atomic binary predicates (which denote the relations of identity and set-theoretic membership) by repeated applications of four operators that are analogues of the well-known operations of relative product, conversion, Boolean addition, and complementation. All mathematical statements are expressed as equations between predicates. There are ten logical axiom schemata and just one rule of inference: the one of replacing equals by equals, familiar from high school algebra. Though such a simple formalism may appear limited in its powers of expression and proof, this book proves quite the opposite. The authors show that it provides a framework for the formalization of practically all known systems of set theory, and hence for the development of all classical mathematics. The book contains numerous applications of the main results to diverse areas of foundational research: propositional logic; semantics; first-order logics with finitely many variables; definability and axiomatizability questions in set theory, Peano arithmetic, and real number theory; representation and decision problems in the theory of relation algebras; and decision problems in equational logic. (shrink)

Among others we will prove that the equational theory of ω dimensional representable polyadic equality algebras (RPEA ω 's) is not schema axiomatizable. This result is in interesting contrast with the Daigneault-Monk representation theorem, which states that the class of representable polyadic algebras is finite schema-axiomatizable (and hence the equational theory of this class is finite schema-axiomatizable, as well). We will also show that the complexity of the equational theory of RPEA ω is also extremely high in the recursion theoretic (...) sense. Finally, comparing the present negative results with the positive results of Ildiko Sain and Viktor Gyuris [12], the following methodological conclusions will be drawn: The negative properties of polyadic (equality) algebras can be removed by switching from what we call the "polyadic algebraic paradigm" to the "cylindric algebraic paradigm". (shrink)

We shall show that certain natural and interesting intervals in the lattice of varieties of representable relation algebras embed the lattice of all subsets of the natural numbers, and therefore must have a very complicated lattice-theoretic structure.

Treating the existential quantification ∃ν i as a diamond $\diamond_i$ and the identity ν i = ν j as a constant δ ij , we study restricted versions of first order logic as if they were modal formalisms. This approach is closely related to algebraic logic, as the Kripke frames of our system have the type of the atom structures of cylindric algebras; the full cylindric set algebras are the complex algebras of the intended multidimensional frames called cubes. The main (...) contribution of the paper is a characterization of these cube frames for the finite-dimensional case and, as a consequence of the special form of this characterization, a completeness theorem for this class. These results lead to finite, though unorthodox, derivation systems for several related formalisms, e.g. for the valid n-variable first order formulas, for type-free valid formulas and for the equational theory of representable cylindric algebras. The result for type-free valid formulas indicates a positive solution to Problem 4.16 of Henkin, Monk and Tarski [16]. (shrink)

We give an algebraic version of first order logic without equality in which the class of representable algebras forms a finitely based equational class. Further, the representables are defined in terms of set algebras, and all operations of the latter are permutation invariant. The algebraic form of this result is Theorem 1.1 , while its logical form is Corollary 5.2.For first order logic with equality we give a result weaker than the one for first order logic without equality. Namely, in (...) this case - instead of finitely axiomatizing the corresponding class of all representable algebras - we finitely axiomatize only the equational theory of that class. Subsection 6.1, especially Remark 6.6 there.The proof of Theorem 1.1 is elaborated in Sections 3 and 4. These sections contain theorems which are interesting of their own rights, too, e.g. Theorem 4.2 is a purely semigroup theoretic result. Cf. also 'Further main results' in the Introduction. (shrink)

In this work, we attempt to alleviate three equivalent negative results. These are non-axiomatizability of the valid formula schemas of first order logic, non-axiomatizability of any propositional logic equivalent with classical first order logic , and non-axiomatizability of the class of representable cylindric algebras . Here we present two finite schema axiomatizable classes of algebras that contain, as a reduct, the class of representable quasi-polyadic algebras and the class of representable cylindric algebras, respectively. We establish positive results in the direction (...) of finitary algebraization of first order logic without equality as well as that with equality. Finally, we will indicate how these constructions can be applied to turn negative results , above to positive one. (shrink)

This paper belongs to cylindric-algebraic model theory understood in the sense of algebraic logic. We show the existence of isomorphic but not lower base-isomorphic cylindric set algebras. These algebras are regular and locally finite. This solves a problem raised in [N 83] which was implicitly present also in [HMTAN 81]. This result implies that a theorem of Vaught for prime models of countable languages does not continue to hold for languages of any greater power.

Henkin and Tarski proved that an atomic cylindric algebra in which every atom is a rectangle must be representable . This theorem and its analogues for quasi-polyadic algebras with and without equality are formulated in Henkin, Monk and Tarski [13]. We introduce a natural and more general notion of rectangular density that can be applied to arbitrary cylindric and quasi-polyadic algebras, not just atomic ones. We then show that every rectangularly dense cylindric algebra is representable, and we extend this result (...) to other classes of algebras of logic, for example quasi-polyadic algebras and substitution-cylindrification algebras with and without equality, relation algebras, and special Boolean monoids. The results of op. cit. mentioned above are special cases of our general theorems. We point out an error in the proof of the Henkin-Monk-Tarski representation theorem for atomic, equality-free, quasi-polyadic algebras with rectangular atoms. The error consists in the implicit assumption of a property that does not, in general, hold. We then give a correct proof of their theorem. Henkin and Tarski also introduced the notion of a rich cylindric algebra and proved in op. cit. that every rich cylindric algebra of finite dimension satisfying certain special identities is representable. We introduce a modification of the notion of a rich algebra that, in our opinion, renders it more natural. In particular, under this modification richness becomes a density notion. Moreover, our notion of richness applies not only to algebras with equality, such as cylindric algebras, but also to algebras without equality. We show that a finite dimensional algebra is rich iff it is rectangularly dense and quasi-atomic; moreover, each of these conditions is also equivalent to a very natural condition of point density . As a consequence, every finite dimensional rich algebra of logic is representable. We do not have to assume the validity of any special identities to establish this representability. Not only does this give an improvement of the Henkin-Tarski representation theorem for rich cylindric algebras, it solves positively an open problem in op. cit. concerning the representability of finite dimensional rich quasi-polyadic algebras without equality. (shrink)