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...

This is a survey article on algebraic logic. It gives a historical background leading up to a modern perspective. Central problems in algebraic logic (like the representation problem) are discussed in connection to other branches of logic, like modal logic, proof theory, model-theoretic forcing, finite combinatorics, and Gödel’s incompleteness results. We focus on cylindric algebras. Relation algebras and polyadic algebras are mostly covered only insofar as they relate to cylindric algebras, and even there we have not told the whole story. (...) We relate the algebraic notion of neat embeddings (a notion special to cylindric algebras) to the metalogical ones of provability, interpolation and omitting types in variants of first logic. Another novelty that occurs here is relating the algebraic notion of atom-canonicity for a class of boolean algebras with operators to the metalogical one of omitting types for the corresponding logic. A hitherto unpublished application of algebraic logic to omitting types of first order logic is given. Proofs are included when they serve to illustrate certain concepts. Several open problems are posed. We have tried as much as possible to avoid exploring territory already explored in the survey articles of Monk [93] and Németi [97] in the subject. (shrink)

Letn > 2. A weakly representable relation algebra that is not strongly representable is constructed. It is proved that the set of all n by n basic matrices forms a cylindric basis that is also a weakly but not a strongly representable atom structure. This gives an example of a binary generated atomic representable cylindric algebra with no complete representation. An application to first order logic is given.

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)

We prove an Omitting Types Theorem for certain algebraizable extensions of first order logic without equality studied in [SAI 00] and [SAY 04]. This is done by proving a representation theorem preserving given countable sets of infinite meets for certain reducts of ?- dimensional polyadic algebras, the so-called G polyadic algebras (Theorem 5). Here G is a special subsemigroup of (?, ? o) that specifies the signature of the algebras in question. We state and prove an independence result connecting our (...) representation theorem to Martin's axiom (Theorem 6). Also we show that the countable atomic G polyadic algebras are completely representable (Corollary 16) contrasting results on cylindric algebras. Several related results are surveyed. (shrink)

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)

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)

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)

A variety V of Boolean algebras with operators is singleton-persistent if it contains a complex algebra whenever it contains the subalgebra generated by the singletons. V is atom-canonical if it contains the complex algebra of the atom structure of any of the atomic members of V.This paper explores relationships between these "persistence" properties and questions of whether V is generated by its complex algebras or its atomic members, or is closed under canonical embedding algebras or completions. It also develops a (...) general theory of when operations involving complex algebras lead to the construction of elementary classes of relational structures. (shrink)

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 < ω. Let CA n denote the class of cylindric algebras of dimension n, and let RCA n denote the variety of representable CA n ’s. Let L n denote first-order logic restricted to the first n variables. Roughly, CA n, an instance of Boolean algebras with operators, is the algebraic counterpart of the syntax of L n, namely, its proof theory, while RCA n algebraically and geometrically represents the Tarskian semantics of L n. Unlike Boolean (...) algebras having a Stone representation theorem, RCA n ⊊ CA n. Using combinatorial game theory, we show that the existence of certain finite relation algebras RA, which are algebras whose domain consists of binary relations, implies that the celebrated Henkin omitting types theorem fails in a very strong sense for L n. Using special cases of such finite RA ’s, we recover the classical nonfinite axiomatizability results of Monk, Maddux, and Biro on RCA n and we re-prove Hirsch and Hodkinson’s result that the class of completely representable CA n ’s is not first-order definable. We show that if T is an L n countable theory that admits elimination of quantifiers, λ is a cardinal < 2 ℵ 0, and F = 〈 Γ i : i < λ 〉 is a family of complete nonprincipal types, then F can be omitted in an ordinary countable model of T. (shrink)

We give a simple new construction of representable relation algebras with non-representable completions. Using variations on our construction, we show that the elementary closure of the class of completely representable relation algebras is not finitely axiomatizable.

We survey various results on the relationship among neat embeddings (a notion special to cylindric algebras), complete representations, omitting types, and amalgamation. A hitherto unpublished application of algebraic logic to omitting types of first-order logic is given.

Fix \. Let \ denote first order logic restricted to the first n variables. Using the machinery of algebraic logic, positive and negative results on omitting types are obtained for \ and for infinitary variants and extensions of \.

Let \(2 (...) It is shown that \(\mathbf{K_n}\) is not finitely axiomatizable and that it coincides with the class of atomic algebras in the elementary closure of \(\mathbf{S_c}{\sf Nr}_n{\sf CA}_{\omega}\) where \(\mathbf{S_c}\) is the operation of forming complete subalgebras. For any class \(\mathbf{L}\) such that \({\sf At}{\sf Nr}_n{\sf CA}_{\omega}\subseteq \mathbf{L}\subseteq {\sf At}\mathbf{K_n}\), it is proved that \({\bf SP}\mathfrak{Cm}\mathbf{L}={\sf RCA}_n\), where \({\sf Cm}\) is the dual operator to \(\sf At\); that of forming complex algebras. It is also shown that any class \(\mathbf{K}\) between \({\sf CRCA}_n\cap \mathbf{S_d}{\sf Nr}_n{\sf CA}_{\omega}\) and \(\mathbf{S_c}{\sf Nr}_n{\sf CA}_{n+3}\) is not first order definable, where \(\mathbf{S_d}\) is the operation of forming dense subalgebras, and that for any \(2shrink)

We prove that algebras of binary relations whose similarity type includes intersection, union, and one of the residuals of relation composition form a nonfinitely axiomatizable quasivariety and that the equational theory is not finitely based. We apply this result to the problem of the completeness of the positive fragment of relevance logic with respect to binary relations.

We show that the variety of weakly representable relation algebras is neither canonical nor closed under Monk completions.