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)

We show, for any ordinal γ ≥ 3, that the class RaCAγ is pseudo-elementary and has a recursively enumerable elementary theory. ScK denotes the class of strong subalgebras of members of the class K. We devise games, Fⁿ (3 ≤ n ≤ ω), G, H, and show, for an atomic relation algebra A with countably many atoms, that Ǝ has a winning strategy in Fω(At(A)) ⇔ A ∈ ScRaCAω, Ǝ has a winning strategy in Fⁿ(At(A)) ⇐ A ∈ ScRaCAn, Ǝ (...) has a winning strategy in G(At(A)) ⇐ A ∈ RaCAω, Ǝ has a winning strategy in H(At(A)) ⇒ A ∈ RaRCAω for 3 ≤ n < ω. We use these games to show, for γ ≥ 5 and any class K of relation algebras satisfying RaRCAγ ⊆ K ⊆ ScRaCA₅, that K is not closed under subalgebras and is not elementary. For infinite γ, the inclusion RaCAγ ⊂ ScRaCAγ is strict. For infinite γ and for a countable relation algebra A we show that A has a complete representation if and only if A is atomic and Ǝ has a winning strategy in F(At(A)) if and only if A is atomic and A ∈ ScRaCAγ. (shrink)

For any finite n 3 there are two atomic n-dimensional cylindric algebras with the same atom structure, with one representable, the other, not.Hence, the complex algebra of the atom structure of a representable atomic cylindric algebra is not always representable, so that the class RCAn of representable n-dimensional cylindric algebras is not closed under completions. Further, it follows by an argument of Venema that RCAn is not axiomatisable by Sahlqvist equations, and hence nor by equations where negation can only occur (...) in constant terms.Similar results hold for relation algebras. (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.

We give a novel application of algebraic logic to first order logic. A new, flexible construction is presented for representable but not completely representable atomic relation and cylindric algebras of dimension n (for finite n > 2) with the additional property that they are one-generated and the set of all n by n atomic matrices forms a cylindric basis. We use this construction to show that the classical Henkin-Orey omitting types theorem fails for the finite variable fragments of first order (...) logic as long as the number of variables available is > 2 and we have a binary relation symbol in our language. We also prove a stronger result to the effect that there is no finite upper bound for the extra variables needed in the witness formulas. This result further emphasizes the ongoing interplay between algebraic logic and first order logic. (shrink)

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.

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)

We show that for infinite ordinals α the class of polyadic algebras of dimension α has the super amalgamation property.

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.