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)

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)

Let 1 n. We show that the class NrnCAβ of n-dimensional neat reducts of β-dimensional cylindric algebras is not closed under forming elementary subalgebras. This solves a long-standing open problem of Tarski and his co-authors Andréka, Henkin, Monk and Németi. The proof uses genuine model-theoretic arguments.

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)

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

Our concern is the axiomatisation problem for modal and algebraic logics that correspond to various fragments of two-variable first-order logic with counting quantifiers. In particular, we consider modal products with Diff, the propositional unimodal logic of the difference operator. We show that the two-dimensional product logic $Diff \times Diff$ is non-finitely axiomatisable, but can be axiomatised by infinitely many Sahlqvist axioms. We also show that its ‘square’ version (the modal counterpart of the substitution and equality free fragment of two-variable first-order (...) logic with counting to two) is non-finitely axiomatisable over $Diff \times Diff$ , but can be axiomatised by adding infinitely many Sahlqvist axioms. These are the first examples of products of finitely axiomatisable modal logics that are not finitely axiomatisable, but axiomatisable by explicit infinite sets of canonical axioms. (shrink)

We consider the problem of finding and classifying representations in algebraic logic. This is approached by letting two players build a representation using a game. Homogeneous and universal representations are characterized according to the outcome of certain games. The Lyndon conditions defining representable relation algebras (for the finite case) and a similar schema for cylindric algebras are derived. Finite relation algebras with homogeneous representations are characterized by first order formulas. Equivalence games are defined, and are used to establish whether an (...) algebra is ω-categorical. We have a simple proof that the perfect extension of a representable relation algebra is completely representable. An important open problem from algebraic logic is addressed by devising another two-player game, and using it to derive equational axiomatisations for the classes of all representable relation algebras and representable cylindric algebras. Other instances of this approach are looked at, and include the step by step method. (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)

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

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)

Looking at the operation of forming neat $\alpha $ -reducts as a functor, with $\alpha $ an infinite ordinal, we investigate when such a functor obtained by truncating $\omega $ dimensions, has a right adjoint. We show that the neat reduct functor for representable cylindric algebras does not have a right adjoint, while that of polyadic algebras is an equivalence. We relate this categorial result to several amalgamation properties for classes of representable algebras. We show that the variety of cylindric (...) algebras of infinite dimension, endowed with the merry go round identities, fails to have the amalgamation property answering a question of Németi’s. We also study two variants of the so-called cylindric polyadic algebras introduced by Ferenczi (all are reducts of polyadic equality algebras, that are also varieties). We show that one is more cylindric than polyadic, and that the other is more polyadic than cylindric. Our classification is determined by results on neat embeddings and amalgamation expressed from the point of view of category theory, thereby witnessing, and, indeed, further emphasizing, the dichotomy between the cylindric and polyadic paradigms. For example, the first class does not have the unique neat embedding property, fails to have the amalgamation property and the neat reduct functor does not have a right adjoint, while the second class has the unique neat emdedding property, the superamalgamation property and the neat reduct functor is strongly invertible. Other results, like first order definability of the class of neat reducts and the class of completely representable algebras, confirming our classification along these lines are presented. (shrink)

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 there exists an atomic polyadic equality algebra of dimension n that is elementary equivalent to a completely representable algebra, but its diagonal free reduct is not completely representable.

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 a finite ordinal \ and let \ be an arbitrary ordinal. Let \ denote the class of cylindric algebras of dimension \ and \ denote the class of relation algebras. Let \\) stand for the class of polyadic algebras of dimension \. We reprove that the class \ of completely representable \s, and the class \ of completely representable \s are not elementary, a result of Hirsch and Hodkinson. We extend this result to any variety \ between polyadic algebras (...) of dimension \ and diagonal free \s. We show that that the class of completely and strongly representable algebras in \ is not elementary either, reproving a result of Bulian and Hodkinson. For relation algebras, we can and will, go further. We show the class \ is not closed under \. In contrast, we show that given \, and an atomic \, then for any \, \ is a completely representable \. We show that for any \, the class of completely representable algebras in certain reducts of \s, that happen to be varieties, is elementary. We show that for \, the the class of polyadic-cylindric algebras dimension \, introduced by Ferenczi, the completely representable algebras coincide with the atomic ones. In the last algebras cylindrifications commute only one way, in a sense weaker than full fledged commutativity of cylindrifications enjoyed by classical cylindric and polyadic algebras. Finally, we address closure under Dedekind-MacNeille completions for cylindric-like algebras of dimension \ and \s for \ an infinite ordinal, proving negative results for the first and positive ones for the second. (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)

Following research initiated by Tarski, Craig and Nemeti, and futher pursued by Sain and others, we show that for certain subsets G of $^\omega \omega $ , atomic countable G poiyadic algebras are completely representable. G polyadic algebras are obtained by restricting the similarity type and axiomatization of ω-dimensional polyadic algebras to finite quantifiers and substitutions in G. This contrasts the cases of cylindric and relation algebras.

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