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.

We obtain the class NA of noncommutative cylindric algebras from the class CA of cylindric algebras by weakening the axiom C4 of commutativity of cylindrifications . Some motivation for studying noncommutative cylindric algebras: Noncommutative cylindric algebras have the same “substitutional structure” as cylindric algebras , where substitutional structure refers to the equational behaviour of the substitution operations, the s i j ’s. For certain technical reasons, NA’s turn out to be (...) useful in the study of the substitutional structure of CA’s. Cf. Thm. 3 below. (shrink)

Three classes are introduced which are closely related to the class included in the title. It is proven that the class obtained from by replacing axiom C4 by the commutativity of single substitutions can be considered as the abstract class in the Resek–Thompson theorem, thus it is representable by set algebras. Then the class is defined and it is shown that the necessary and sufficient condition for neat embeddability of an algebra in CAα into is the validity of the (...) merry-go-round properties. Finally, the class is introduced which class is a counterpart of among the polyadic like algebras. (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.

In this note we give an interpretation of cylindric algebras as algebras of sentences of first order logic. We show that the isomorphism types of such algebras of sentences coincide with the class of neat reducts of cylindric algebras. Also we show how this interpretation sheds light on some recent results. This is done by likening Henkin's Neat Embedding Theorem to his celebrated completeness proof.

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)

We confirm a conjecture, about neat embeddings of cylindric algebras, made in 1969 by J. D. Monk, and a later conjecture by Maddux about relation algebras obtained from cylindric algebras. These results in algebraic logic have the following consequence for predicate logic: for every finite cardinal α ≥ 3 there is a logically valid sentence X, in a first-order language L with equality and exactly one nonlogical binary relation symbol E, such that X contains only (...) 3 variables (each of which may occur arbitrarily many times), X has a proof containing exactly α + 1 variables, but X has no proof containing only α variables. This solves a problem posed by Tarski and Givant in 1987. (shrink)

It is known that every α-dimensional quasi polyadic equality algebra (QPEA α ) can be considered as an α-dimensional cylindric algebra satisfying the merrygo- round properties . The converse of this proposition fails to be true. It is investigated in the paper how to get algebras in QPEA from algebras in CA. Instead of QPEA the class of the finitary polyadic equality algebras (FPEA) is investigated, this class is definitionally equivalent to QPEA. It is shown, among (...) others, that from every algebra in a β-dimensional algebra can be obtained in QPEA β where , moreover the algebra obtained is representable in a sense. (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)

We characterise the class S Ra CA n of subalgebras of relation algebra reducts of n -dimensional cylindric algebras by the notion of a ‘hyperbasis’, analogous to the cylindric basis of Maddux, and by representations. We outline a game–theoretic approximation to the existence of a representation, and how to use it to obtain a recursive axiomatisation of S Ra CA n.

In this note we give an interpretation of cylindric algebras as algebras of sentences of first order logic. We show that the isomorphism types of such algebras of sentences coincide with the class of neat reducts of cylindric algebras. Also we show how this interpretation sheds light on some recent results. This is done by likening Henkin's Neat Embedding Theorem to his celebrated completeness proof.

For an arbitrary similarity type of Boolean Algebras with Operators we define a class of Sahlqvist identities. Sahlqvist identities have two important properties. First, a Sahlqvist identity is valid in a complex algebra if and only if the underlying relational atom structure satisfies a first-order condition which can be effectively read off from the syntactic form of the identity. Second, and as a consequence of the first property, Sahlqvist identities are canonical, that is, their validity is preserved under taking (...) canonical embedding algebras. Taken together, these properties imply that results about a Sahlqvist variety V van be obtained by reasoning in the elementary class of canonical structures of algebras in V. We give an example of this strategy in the variety of Cylindric Algebras: we show that an important identity called Henkin's equation is equivalent to a simpler identity that uses only one variable. We give a conceptually simple proof by showing that the firstorder correspondents of these two equations are equivalent over the class of cylindric atom structures. (shrink)

We prove, for each 4⩽ n ω , that S Ra CA n+1 cannot be defined, using only finitely many first-order axioms, relative to S Ra CA n . The construction also shows that for 5⩽n S Ra CA n is not finitely axiomatisable over RA n , and that for 3⩽m S Nr m CA n+1 is not finitely axiomatisable over S Nr m CA n . In consequence, for a certain standard n -variable first-order proof system ⊢ m (...) , n of m -variable formulas, there is no finite set of m -variable schemata whose m -variable instances, when added to ⊢ m , n as axioms, yield ⊢ m , n +1. (shrink)

For an arbitrary similarity type of Boolean Algebras with Operators we define a class ofSahlqvist identities. Sahlqvist identities have two important properties. First, a Sahlqvist identity is valid in a complex algebra if and only if the underlying relational atom structure satisfies a first-order condition which can be effectively read off from the syntactic form of the identity. Second, and as a consequence of the first property, Sahlqvist identities arecanonical, that is, their validity is preserved under taking canonical embedding (...) algebras. Taken together, these properties imply that results about a Sahlqvist variety V van be obtained by reasoning in the elementary class of canonical structures of algebras in V.We give an example of this strategy in the variety of Cylindric Algebras: we show that an important identity calledHenkin's equation is equivalent to a simpler identity that uses only one variable. We give a conceptually simple proof by showing that the first-order correspondents of these two equations are equivalent over the class of cylindric atom structures. (shrink)

We show that it is impossible to define a substitution operator for arbitrary representable cylindric algebras that agrees in its basic properties with the notion of substitutions introduced for dimension complemented algebras.

A cylindric algebra atom structure is said to be strongly representable if all atomic cylindric algebras with that atom structure are representable. This is equivalent to saying that the full complex algebra of the atom structure is a representable cylindric algebra. We show that for any finite n >3, the class of all strongly representable n-dimensional cylindric algebra atom structures is not closed under ultraproducts and is therefore not elementary. Our proof is based on the (...) following construction. From an arbitrary undirected, loop-free graph Γ, we construct an n-dimensional atom structure E(Γ), and prove, for infinite Γ, that E(Γ) is a strongly representable cylindric algebra atom structure if and only if the chromatic number of Γ is infinite. A construction of Erdős shows that there are graphs (k < ω)with infinite chromatic number, but having a non-principal ultraproduct $\prod _D\Gamma _k $ whose chromatic number is just two. It follows that $E(\Gamma _k )$ is strongly representable (each k < ω) but $\Pi _D E(\Gamma _k)$ is not. (shrink)

ABSTRACT As is well-known, a classical representation theorem of the theory of cylindric algebras is: A ε IGwsa if and only if A ε SNrαCAα+ε. The part “only if” is trivial. Regarding to the other part “A ε SNrαCAα+ε then A ε IGwsα“ the following question arises: is it possible to replace the class CA in the hypothesis A ε SNrαCAα+ε by a larger class so that the theorem still holds. Such a larger class Kα β is defined. (...) The class Kα β is the best possible, in a sense to be made precise. Representability of set algebras is investigated, too. (shrink)

We generalize two classical results on cylindric algebra to certain expansions of cylindric algebras where the extra operations are defined via first order formulas. The first result is the Neat Embedding Theorem of Henkin and the second is Monk's classical non-finitizability result of the class of representable algebras. As a corollary we obtain known classical results of Johnson and Biro published in the Journal of Symbolic logic.

We show that the representability of cylindric algebras by relativized set algebras depends on the scope of the operation transposition which can be defined on the algebra. The existence of “partial transposition” assures this kind of representability of the cylindric algebra . Further we characterize those cylindric algebras in which the operator transposition can be introduced.

Let α be an arbitrary infinite ordinal, and. In [26] we studied—using algebraic logic—interpolation and amalgamation for an extension of first order logic, call it, with α many variables, using a modal operator of a unimodal logic that contributes to the semantics. Our algebraic apparatus was the class of modal cylindric algebras. Modal cylindric algebras, briefly, are cylindric algebras of dimension α, expanded with unary modalities inheriting their semantics from a unimodal logic such as, (...) or. When modal cylindric algebras based on are just cylindric algebras, that is to say,. This paper is a sequel to [26], where we study algebraically other properties of. We study completeness and omitting types (s) for s by proving several representability results for so‐called dimension complemented and locally finite. Furthermore, we study the notion of atom‐canonicity for, the variety of n‐dimensional modal cylindric algebras. Atom canonicity, a well known persistence property in modal logic, is studied in connection to for, which is restricted to the first n variables. We further continue our study of interpolation in [26] for algebraizable extensions of by studying using both algebraic logic and category theory. Our main results on are Theorems 3.7, 4.4 & 4.6, while our main results on amalgamation are Theorems 5.7, 5.10, 5.13 & 5.16. (shrink)

Fix 2 < n < ω and let C A n denote the class of cylindric algebras of dimension n. Roughly, C A n is the algebraic counterpart of the proof theory of first-order logic restricted to the first n var...

We outline a simple approach to axiomatising the class of representable relation algebras, using games. We discuss generalisations of the method to cylindric algebras, homogeneous and complete representations, and atom structures of relation algebras.

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)