Search Results

Abstract

Fix 2 < n < ω and let CA _n denote the class of cyindric algebras of dimension n. Roughly CA _n is the algebraic counterpart of the proof theory of first order logic restricted to the first n variables which we denote by L_n . The variety RCA _n of representable CA _n s reflects algebraically the semantics of L_n . Members of RCA _n are concrete algebras consisting of genuine n-ary relations, with set theoretic operations induced by the nature of relations, such as projections referred to as cylindrifications. Although CA _n has a finite equational axiomatization, RCA _n is not finitely axiomatizable, and it generally exhibits wild, often unpredictable and unruly behavior. This makes the theory of CA _n substantially richer than that of Boolean algebras, just as much as L_ω,ω is richer than propositional logic. We show using a so-called blow up and blur construction that several varieties (in fact infinitely many) containing and including the variety RCA _n are not atom-canonical. A variety V of Boolean algebras with operators is atom canonical, if whenever $\mathfrak{A}$ ∈ V is atomic, then its Dedekind-MacNeille completion, sometimes referred to as its minimal completion, is also in V. From our hitherto obtained algebraic results we show, employing the powerful machinery of algebraic logic, that the celebrated Henkin-Orey omitting types theorem, which is one of the classical first (historically) cornerstones of model theory of L_ω,ω , fails dramatically for L_n even if we allow certain generalized models that are only locallly classical. It is also shown that any class K such that Nr _n CA _ω ∩ CRCA _n $\underset{¯}{\subseteq }$ K $\underset{¯}{\subseteq }$ S _c Nr _n CA _{n +3}, where CRCA _n is the class of completely representable CA _n s, and S _c denotes the operation of forming dense (complete) subalgebras, is not elementary. Finally, we show that any class K such that S _d RaCA _ω $\underset{¯}{\subseteq }$ K $\underset{¯}{\subseteq }$ S _c RaCA₅ is not elementary, where S _d denotes the operation of forming dense subalgebra.

Let α be an infinite ordinal. Let RCA _α denote the variety of representable cylindric algebras of dimension α. Modifying Andréka’s methods of splitting, we show that the variety RQEA _α of representable quasi-polyadic equality algebras of dimension α is not axiomatized by a set of universal formulas containing only finitely many variables over the variety RQA _α of representable quasi-polyadic algebras of dimension α. This strengthens a seminal result due to Sain and Thompson, answers a question posed by Andréka, and lifts to the transfinite a result of hers proved for finite dimensions > 2. Using the modified method of splitting, we show that all known complexity results on universal axiomatizations of RCA _α (proved by Andréka) transfer to universal axiomatizations of RQEA _α . From such results it can be inferred that any algebraizable extension of L _ω,ω is severely incomplete if we insist on Tarskian square semantics. Ways of circumventing the strong non-negative axiomatizability results hitherto obtained in the first part of the paper, such as guarding semantics, and /or expanding the signature of RQEA _ω by substitutions indexed by transformations coming from a finitely presented subsemigroup of ( ^ω ω, ○) containing all transpositions and replacements, are surveyed, discussed, and elaborated upon.

Abstract

For β an ordinal, let PEA _β (SetPEA _β ) denote the class of polyadic equality (set) algebras of dimension β. We show that for any infinite ordinal α, if $\mathfrak{A}\in {\text{PEA}}_{\alpha }$ is atomic, then for any n < ω, the n-neat reduct of $\mathfrak{A}$ , in symbols $\Re {\mathfrak{r}}_n\mathfrak{A}\to \mathfrak{B}$ , is a completely representable PEA _n (regardless of the representability of $\mathfrak{A}$ ). That is to say, for all non-zero $a\in \Re {\mathfrak{r}}_n\mathfrak{A}$ , there is a ${\mathfrak{B}}_a\in {\text{SetPEA}}_n$ and a homomorphism $f_a:\Re {\mathfrak{r}}_n\mathfrak{A}\to \mathfrak{B}$ such that f_a (a) ≠ 0 and $f_a\left({\displaystyle \sum X}\right)={\displaystyle {\cup }_{x\in X}{f}_a\left(x\right)}$ for any $X\underset{=}{\subset }\mathfrak{A}$ for which ${\displaystyle \sum X}$ exists. We give new proofs that various classes consisting solely of completely representable algebras of relations are not elementary; we further show that the class of completely representable relation algebras is not closed under ≡_∞,ω . Various notions of representability (such as ‘satisfying the Lyndon conditions’, weak and strong) are lifted from the level of atom structures to that of atomic algebras and are further characterized via special neat embeddings. As a sample, we show that the class of atomic CA _n s satisfying the Lyndon conditions coincides with the class of atomic algebras in ElS _c Nr _n CA _ω , where El denotes ‘elementary closure’ and S _c is the operation of forming complete subalgebras.

Abstract

We prove completeness, interpolation, decidability and an omitting types theorem for certain multi-dimensional modal logics where the states are not abstract entities but have an inner structure. The states will be sequences. Our approach is algebraic addressing varieties generated by complex algebras of Kripke semantics for such logics. The algebras dealt with are common cylindrification free reducts of cylindric and polyadic algebras. For finite dimensions, we show that such varieties are finitely axiomatizable, have the super amalgamation property, and that the subclasses consisting of only completely representable algebras are elementary, and are also finitely axiomatizable in first order logic. Also their modal logics have an N P complete satisfiability problem. Analogous results are obtained for infinite dimensions by replacing finite axiomatizability by finite schema axiomatizability.