The class \ of t rue p airing a lgebras is defined to be the class of relation algebras expanded with concrete set theoretical projection functions. The main results of the present paper is that neither the equational theory of \ nor the first order theory of \ are decidable. Moreover, we show that the set of all equations valid in \ is exactly on the \ level. We consider the class \ of the relation algebra reducts of \ ’s, (...) as well. We prove that the equational theory of \ is much simpler, namely, it is recursively enumerable. We also give motivation for our results and some connections to related work. (shrink)

We consider countable so‐called rich subsemigroups of ; each such semigroup T gives a variety CPEAT that is axiomatizable by a finite schema of equations taken in a countable subsignature of that of ω‐dimensional cylindric‐polyadic algebras with equality where substitutions are restricted to maps in T. It is shown that for any such T, if and only if is representable as a concrete set algebra of ω‐ary relations. The operations in the signature are set‐theoretically interpreted like in polyadic equality set (...) algebras, but such operations are relativized to a union of cartesian spaces that are not necessarily disjoint. This is a form of guarding semantics. We show that CPEAT is canonical and atom‐canonical. Imposing an extra condition on T, we prove that atomic algebras in CPEAT are completely representable and that CPEAT has the super amalgamation property. If T is rich and finitely represented, it is shown that CPEAT is term definitionally equivalent to a finitely axiomatizable Sahlqvist variety. Such semigroups exist. This can be regarded as a solution to the central finitizability problem in algebraic logic for first order logic with equality if we do not insist on full fledged commutativity of quantifiers. The finite dimensional case is approached from the view point of guarded and clique guarded (relativized) semantics of fragments of first order logic using finitely many variables. Both positive and negative results are presented. (shrink)

ABSTRACT In this paper it is shown that a broad class of propositional logics can be interpreted in an equational logic based on fork algebras. This interpetability enables us to develop a fork-algebraic formalization of these logics and, as a consequence, to simulate non-classical means of reasoning with equational theories algebras.

Familiar proof theoretical and especially automated deduction methods sometimes accept infinity where, in fact, it can be omitted. Our first example deals with the infinite supply of individual variables admitted in 1-order deductions, the second one deals with infinite-branching rules in sequent calculi with number-theoretical induction. The contents of Section 1 summarize and extend basic ideas and results published elsewhere, whereas basic ideas and results of Section 2 are exposed for the first time in the present paper. We consider classical (...) formalisms only, to which constructive formalisms can be reduced by Shanin-style interpretations. (shrink)

We study algebras whose elements are relations, and the operations are natural “manipulations” of relations. This area goes back to 140 years ago to works of De Morgan, Peirce, Schröder . Well known examples of algebras of relations are the varieties RCAn of cylindric algebras of n-ary relations, RPEAn of polyadic equality algebras of n-ary relations, and RRA of binary relations with composition. We prove that any axiomatization, say E, of RCAn has to be very complex in the following sense: (...) for every natural number k there is an equation in E containing more than k distinct variables and all the operation symbols, if 2 < n < ω. Completely analogous statement holds for the case n ω. This improves Monk's famous non-finitizability theorem for which we give here a simple proof. We prove analogous nonfinitizability properties of the larger varieties SNrnCAn + k. We prove that the complementation-free subreducts of RCAn do not form a variety. We also investigate the reason for the above “non-finite axiomatizability” behaviour of RCAn. We look at all the possible reducts of RCAn and investigate which are finitely axiomatizable. We obtain several positive results in this direction. Finally, we summarize the results and remaining questions in a figure. We carry through the same programme for RPEAn and for RRA. By looking into the reducts we also investigate what other kinds of natural algebras of relations are possible with more positive behaviour than that of the well known ones. Our investigations have direct consequences for the logical properties of the n-variable fragment Ln of first order logic. The reason for this is that RCAn and RPEAn are the natural algebraic counterparts of Ln while the varieties SNrnCAn + k are in connection with the proof theory of Ln. This paper appears in two parts. The first part contains the non-finite axiomatizability results. The present second part contains finite axiomatizations of some fragments together with a figure summarizing the finite and non-finite axiomatizability results in this area and the problems left open. (shrink)

Built on the foundations laid by Peirce, Schröder, and others in the 19th century, the modern development of relation algebras started with the work of Tarski and his colleagues [21, 22]. They showed that relation algebras can capture strong first‐order theories like ZFC, and so their equational theory is undecidable. The less expressive class WA of weakly associative relation algebras was introduced by Maddux [7]. Németi [16] showed that WA's have a decidable universal theory. There has been extensive research on (...) increasing the expressive power of WA by adding new operations [1, 4, 11, 13, 20]. Extensions of this kind usually also have decidable universal theories. Here we give an example – extending WA's with set‐theoretic projection elements – where this is not the case. These “logical” connectives are set‐theoretic counterparts of the axiomatic quasi‐projections that have been investigated in the representation theory of relation algebras [22, 6, 19]. We prove that the quasi‐equational theory of the extended class PWA is not recursively enumerable. By adding the difference operator D one can turn WA and PWA to discriminator classes where each universal formula is equivalent to some equation. Hence our result implies that the projections turn the decidable equational theory of “WA + D ” to non‐recursively enumerable (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)