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)

An interpolation Theorem is proved for first order logic with infinitary predicates. Our proof is algebraic via cylindric algebras.1.

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.

SC, CA, QA and QEA denote the classes of Pinter's substitution algebras, Tarski's cylindric algebras, Halmos' quasi-polyadic algebras and quasi-polyadic equality algebras, respectively. Let ω ≤ α < β and let K ∈ {SC,CA,QA,QEA}. We show that the class of α -dimensional neat reducts of algebras in Kβ is not elementary. This solves a problem in [3]. Also our result generalizes results proved in [2] and [3].

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)

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.

We present a property of neat reducts commuting with forming subalgebras as a definability condition.

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 review, and in the process unify two techniques , for proving results concerning amalgamation in several classes studied in algebraic logic. The logical counterpart of these results adress interpolation and definability properties in modal and algebraic logic. Presenting them in a functorial context as adjoint situations, we show that both techniques can indeed be seen as instances of the use of the Keisler-Shelah ultrapower Theorem in proving Robinson's Joint Consistency Theorem. Some new results are surveyed. The results of this (...) paper are presented in such a way that further establishes the hitherto existing well developed duality theory between boolean algebras with operators and modal logic. (shrink)

We give a new characterization of the class of completely representable cylindric algebras of dimension 2 #lt; n ≤ w via special neat embeddings. We prove an independence result connecting cylindric algebra to Martin's axiom. Finally we apply our results to finite-variable first order logic showing that Henkin and Orey's omitting types theorem fails for Ln, the first order logic restricted to the first n variables when 2 #lt; n#lt;w. Ln has been recently (and quite extensively) studied as a many-dimensional (...) modal logic. (shrink)

SC , CA , QA and QEA stand for the classes of Pinter's substitution algebras, Tarski's cylindric algebras, Halmos' quasipolyadic algebras, and quasipolyadic equality algebras of dimension , respectively. Generalizing a result of Németi on cylindric algebras, we show that for K {SC, CA, QA, QEA} and ordinals , the class Nr K of -dimensional neat reducts of -dimensional K algebras, though closed under taking homomorphic images and products, is not closed under forming subalgebras (i.e. is not a variety) if (...) and only if > 1.From this it easily follows that for 1 , the operation of forming -neat reducts of algebras in K does not commute with forming subalgebras, a notion to be made precise. (shrink)

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)

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 formulate several statements in Algebraic Logic that turn out to be independent of ZFC. We relate such statements to Martin's axiom, omitting types for variants of first order logic and topological properties of Baire spaces.

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

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

We give a new characterization of the class of completely representable cylindric algebras of dimension 2 #lt; n w via special neat embeddings. We prove an independence result connecting cylindric algebra to Martin''s axiom. Finally we apply our results to finite-variable first order logic showing that Henkin and Orey''s omitting types theorem fails for L n, the first order logic restricted to the first n variables when 2 #lt; n#lt;w. L n has been recently (and quite extensively) studied as a (...) many-dimensional modal logic. (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 show that not all epimorphisms are surjective in certain classes of infinite dimensional cylindric algebras, Pinter's substitution algebras and Halmos' quasipolyadic algebras with and without equality. It follows that these classes fail to have the strong amalgamation property. This answers a question in [3] and a question of Pigozzi in his landmark paper on amalgamation [9]. The cylindric case was first proved by Judit Madarasz [7]. The proof presented herein is substantially different. By a result of Németi, our result (...) implies that the Beth-definability Theorem fails for certain expansions of first order logic. (shrink)

In this paper, an extension of first order logic is introduced. In such logics atomic formulas may have infinite lengths. An Omitting Types Theorem is proved.

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.

SC, CA, QA and QEA denote the class of Pinter’s substitution algebras, Tarski’s cylindric algebras, Halmos’ quasi-polyadic and quasi-polyadic equality algebras, respectively. Let . and . We show that the class of n dimensional neat reducts of algebras in K m is not elementary. This solves a problem in [2]. Also our result generalizes results proved in [1] and [2].

We prove several interpolation theorems for many-valued infinitary logic with quantifiers by studying expansions of MV-algebras in the spirit of polyadic and cylindric algebras. We prove for various reducts of polyadic MV-algebras of infinite dimensions that if is the free algebra in the given signature,, is in the subalgebra of generated by, is in the subalgebra of generated by and, then there exists an interpolant in the subalgebra generated by and such that. We call this a varying interpolation property because (...) the integer depends on the inequality. We also address cases where this interpolation property fails, but other weaker ones hold. One such interpolation theorem says that though an interpolant may not be found as above, an interpolant can always be found if finitely many universal quantifiers are applied to making it smaller and the same number of existential quantifiers are applied to making it bigger. This number of quantifiers also varies; it depends on the inequality. Se.. (shrink)

We redefine a system of varieties definable by a schema of equations to include finite dimensions. Then we present a technique using ultraproducts enabling one to lift results proved for every finite dimension to the transfinite. Let \(\bf Ord\) denote the class of all ordinals. Let \(\langle \mathbf{K}_{\alpha}: \alpha\in \bf Ord\rangle\) be a system of varieties definable by a schema. Given any ordinal \(\alpha\), we define an operator \(\mathsf{Nr}_{\alpha}\) that acts on \(\mathbf{K}_{\beta}\) for any \(\beta>\alpha\) giving an algebra in \(\mathbf{K}_{\alpha}\), (...) as an abstaction of taking \(\alpha\)-neat reducts for cylindric algebras. We show that for any positive \(k\), and any infinite ordinal \(\alpha\) that \(\mathbf{S}\mathsf{Nr}_{\alpha}\mathbf{K}_{\alpha+k+1}\) cannot be axiomatized by a finite schema over \(\mathbf{S}\mathsf{Nr}_{\alpha}\mathbf{K}_{\alpha+k}\) given that the result is valid for all finite dimensions greater than some fixed finite ordinal. We apply our results to cylindric algebras and Halmos quasipolyadic algebras with equality. As an application to our algebraic result we obtain a strong incompleteness theorem (in the sense that validitities are not captured by finitary Hilbert style axiomatizations) for an algebraizable extension of \(L_{\omega,\omega}\). (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 < ω 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 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 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 prove that the existence of atomic models for countable atomic theories does not hold for Ln the first order logic restricted to n variables for finite n > 2. Our proof is algebraic, via polyadic algebras. We note that Lnhas been studied in recent times as a multi-modal logic with applications in computer science. 2000 MATHEMATICS SUBJECT CLASSIFICATION. 03C07, 03G15.

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.

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.