Using a combinatorial theorem of Herwig on extending partial isomorphisms of relational structures, we give a simple proof that certain classes of algebras, including Crs, polyadic Crs, and WA, have the `finite base property' and have decidable universal theories, and that any finite algebra in each class is representable on a finite set.

Using a combinatorial theorem of Herwig on extending partial isomorphisms of relational structures, we give a simple proof that certain classes of algebras, including Crs, polyadic Crs, and WA, have the `finite base property' and have decidable universal theories, and that any finite algebra in each class is representable on a finite set.

This paper is about pairing relation algebras as well as fork algebras and related subjects. In the 1991-92 fork algebra papers it was conjectured that fork algebras admit a strong representation theorem . Then, this conjecture was disproved in the following sense: a strong representation theorem for all abstract fork algebras was proved to be impossible in most set theories including the usual one as well as most non-well-founded set theories. Here we show that the above quoted conjecture can still (...) be made true by choosing an appropriate set theory as our foundation of mathematics. Namely, we show that there are non-well-founded set theories in which every abstract fork algebra is representable in the strong sense, i.e. it is isomorphic to a set relation algebra having a fork operation which is obtained with the help of the real pairing function. Further, these non-well-founded set theories are consistent if usual set theory is consistent. Finally, we will discuss related developments in propositional multi-modal logics of quantification and substitution, in algebraic logic e.g. cylindric algebras, the so called finitization problem, and applications to a logic introduced and studied in Tarski-Givant [42]. In particular, representable, weakly higher order cylindric algebras are finitely axiomatizable in a set theory which admits the axiom of foundation for finite sets. (shrink)

This paper is a survey of recent results concerning connections between relation algebras , cylindric algebras and polyadic equality algebras . We describe exactly which subsets of the standard axioms for RA are needed for axiomatizing RA over the RA-reducts of CA3's, and we do the same for the class SA of semi-associative relation algebras. We also characterize the class of RA-reducts of PEA3's. We investigate the interconnections between the RA-axioms within CA3 in more detail, and show that only four (...) implications hold between them . In the other direction, we introduce a natural CA-theoretic equation MGR+, generalization of the well-known Merrry-Go-Round equation MGR of CA-theory. We show that MGR+ is equivalent to the RA-reduct being an SA, and that MGR+ implies that the RA-reduct determines the algebra itself, while MGR is not sufficient for either of these to hold. Then we investigate how different CA's a single RRA can 'generate' in the general case. We solve the first part of Problem 11 from the 'Problem Session Paper' of [2].While proving some of the statements, for others we give only outline of proof. The paper contains several open problems. A full version of this paper is under preparation.Keywords: relation algebras, cylindric algebras, polyadic algebras, algebraic logic, arrow logic, proof theory, finite variable fragments, provability with 3 variables, non-finitizability, twisting, non-standard models, neat reducts, representability. (shrink)

We show that the variety of n -dimensional weakly higher order cylindric algebras, introduced in Németi [9], [8], is finitely axiomatizable when n > 2. Our result implies that in certain non-well-founded set theories the finitization problem of algebraic logic admits a positive solution; and it shows that this variety is a good candidate for being the cylindric algebra theoretic counterpart of Tarski’s quasi-projective relation algebras.

We show the undecidability of the equational theories of some classes of BAOs with a non-associative, residuated binary extra-Boolean operator. These results solve problems in Jipsen [9], Pratt [21] and Roorda [22], [23]. This paper complements Andréka-Kurucz-Németi-Sain-Simon [3] where the emphasis is on BAOs with an associative binary operator.

Among others we will see that the equational theory of ω dimensional representable polyadic equality algebras. We will also see 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 [10], the following methodological conclusions will be drawn: the negative properties of polyadic algebras can be removed by switching from what we call the `polyadic algebraic paradigm' (...) to the `cylindric algebraic paradigm'. (shrink)

We prove that the equational theory of a semigroups becomes undecidable if we add a semilattice structure with a ‘touch of symmetric difference’. As a corollary we obtain that the variety of all Boolean algebras with an associative binary operator has a ‘hereditarily’ undecidable equational theory. Our results have implications in logic, e.g. they imply undecidability of modal logics extending the Lambek Calculus and undecidability of Arrow Logics with an associative arrow modality.

One of the basic theorems in universal algebra is Birkhoff's variety theorem: the smallest equationally axiomatizable class containing a class K of algebras coincides with the class obtained by taking homomorphic images of subalgebras of direct products of elements of K. G. Gratzer asked whether the variety theorem is equivalent to the Axiom of Choice. In 1980, two of the present authors proved that Birkhoff's theorem can already be derived in ZF. Surprisingly, the Axiom of Foundation plays a crucial role (...) here: we show that Birkhoff's theorem cannot be derived in ZF + AC {Foundation}. even if we add Foundation for Finite Sets. We also prove that the variety theorem is equivalent to a purely set-theoretical statement, the Collection Principle. This principle is independent of $ZF \{\operatorname{Foundation}$ . The second part of the paper deals with further connections between axioms of ZF-set theory and theorems of universal algebra. (shrink)

In this note we prove that the abstract property "weakly subdirectly indecomposable" does not characterize the class IWs α of weak cylindric set algebras. However, we give another (similar) abstract property characterizing IWs α . The original property does characterize the directed unions of members of $\mathrm{IWs}_alpha \operatorname{iff} \alpha$ is countable. Free algebras will be shown to satisfy the original property.

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.

A part of relativistic dynamics is axiomatized by simple and purely geometrical axioms formulated within first-order logic. A geometrical proof of the formula connecting relativistic and rest masses of bodies is presented, leading up to a geometric explanation of Einstein's famous E = mc² . The connection of our geometrical axioms and the usual axioms on the conservation of mass, momentum and four-momentum is also investigated.

SC , CA , QA and QEA stand for the classes of Pinter's substitution algebras, Tarski's cylindric algebras, Halmos' quasipolyadic algebras, and quasipolyadic equality algebras of dimension , respectively. Generalizing a result of Németi on cylindric algebras, we show that for K {SC, CA, QA, QEA} and ordinals , the class Nr K of -dimensional neat reducts of -dimensional K algebras, though closed under taking homomorphic images and products, is not closed under forming subalgebras (i.e. is not a variety) (...) if and only if > 1.From this it easily follows that for 1 , the operation of forming -neat reducts of algebras in K does not commute with forming subalgebras, a notion to be made precise. (shrink)

This work presents a systematic study of decision problems for equational theories of algebras of binary relations (relation algebras). For example, an easily applicable but deep method, based on von Neumann's coordinatization theorem, is developed for establishing undecidability results. The method is used to solve several outstanding problems posed by Tarski. In addition, the complexity of intervals of equational theories of relation algebras with respect to questions of decidability is investigated. Using ideas that go back to Jonsson and Lyndon, the (...) authors show that such intervals can have the same complexity as the lattice of subsets of the set of the natural numbers. Finally, some new and quite interesting examples of decidable equational theories are given. The methods developed in the monograph show promise of broad applicability. They provide researchers in algebra and logic with a new arsenal of techniques for resolving decision questions in various domains of algebraic logic. (shrink)

This is an abstract of our paper \A characterisation of Floyd-provable programs" submitted to Theoretical Computer Science. ! denotes the set of natural numbers. Y =d fyi : i 2 !g is the set of variable symbols. L denotes the set of classical rst order formulas of type t possibly with free variables , where t is the similarity type of arithmetic, i.e. it consists of \+; ; 0; 1" with arities \2; 2; 0; 0".

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)

This paper is an introduction: in particular, to algebras of relations of various ranks, and in general, to the part of algebraic logic algebraizing quantifier logics. The paper has a survey character, too. The most frequently used algebras like cylindric-, relation-, polyadic-, and quasi-polyadic algebras are carefully introduced and intuitively explained for the nonspecialist. Their variants, connections with logic, abstract model theory, and further algebraic logics are also reviewed. Efforts were made to make the review part relatively comprehensive. In some (...) directions we tried to give an overview of the most recent results and research trends, too. (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)

Among others we will prove that the equational theory of $\omega$ dimensional representable polyadic equality algebras 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. We will also show that the complexity of the equational theory of RPEA$_\omega$ 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 algebras can be removed by switching from what we call the "polyadic algebraic paradigm" to the "cylindric algebraic paradigm". (shrink)

In this paper we try to initiate a search for an explicite and direct denition of ultraproducts in categories which would share some of the attractive properties of products, coproducts, limits, and related category theoretic notions. Consider products as a motivating example.

Motivation and perspective for an exciting new research direction interconnecting logic, spacetime theory, relativity--including such revolutionary areas as black hole physics, relativistic computers, new cosmology--are presented in this paper. We would like to invite the logician reader to take part in this grand enterprise of the new century. Besides general perspective and motivation, we present initial results in this direction.

We investigate Kerr–Newman black holes in which a rotating charged ring-shaped singularity induces a region which contains closed timelike curves (CTCs). Contrary to popular belief, it turns out that the time orientation of the CTC is oppo- site to the direction in which the singularity or the ergosphere rotates. In this sense, CTCs “counter-rotate” against the rotating black hole. We have similar results for all spacetimes sufficiently familiar to us in which rotation induces CTCs. This motivates our conjecture that perhaps (...) this counter-rotation is not an accidental oddity particular to Kerr–Newman spacetimes, but instead there may be a general and intuitively comprehensible reason for this. (shrink)

We give an overview of decidability results for modal logics having a binary modality. We put an emphasis on the demonstration of proof-techniques, and hope that this will also help in finding the borderlines between decidable and undecidable fragments of usual first-order logic.