Notions of representability for cylindric algebras: some algebras are more representable than others
Open Access
- 21 July 2022
- journal article
- research article
- Published by Springer Nature in Periodica Mathematica Hungarica
- Vol. 86 (2) , 343-377
Abstract
The theory of cylindric algebras was introduced by Tarski in the fifties of the twentieth century, and its intensive study was further pursued by pioneers such as Henkin and Monk and, by the Hungarian mathematicians Andréka, Németi and Sain, and many of their students; to name only a few: Madarász, Marx, Kurucz, Simon, Mikulás, and Sági and many others outside Hungary including the author of this paper. Here we introduce and investigate new notions of representability for cylindric algebras and investigate various connections between such notions. Let $$2<n\le l<m\le \omega $$ . Let $$\textsf {CA}_n$$ denote the variety of cylindric algebras of dimension n and let $$\textsf {RCA}_n$$ denote the variety of representable $$\textsf {CA}_n$$ s. We say that an atomic algebra $${{\mathfrak {A}}}\in \textsf {CA}_n$$ has the complex neat embedding property up to l and m if $${{\mathfrak {A}}}\in \textsf {RCA}_n\cap \textsf {Nr}_n\textsf {CA}_l$$ and $${{{\mathfrak {C}}}{{\mathfrak {m}}}}\textsf {At}{{\mathfrak {A}}}\in \mathbf {S}\textsf {Nr}_n\textsf {CA}_m$$ . Fixing the prarameters l at the value n, this is a measure of how much the algebra is representable. The yardstick is how far can its Dedekind–MacNeille completion be dilated, that is to say, counting the number of more extra dimensions its Dedekind–MacNeille completion neatly embeds into. If $${{\mathfrak {A}}}, {{\mathfrak {B}}}\in \textsf {RCA}_n$$ are atomic, $${{{\mathfrak {C}}}{{\mathfrak {m}}}}\textsf {At}{{\mathfrak {B}}}\in S\textsf {Nr}_n\textsf {CA}_l$$ and $${{{\mathfrak {C}}}{{\mathfrak {m}}}}\textsf {At}{{\mathfrak {A}}}\in S\textsf {Nr}_n\textsf {CA}_m$$ , then we say that $${{\mathfrak {A}}}$$ is more representable than $${{\mathfrak {B}}}$$ . When $$m=\omega $$ , we say that $${{\mathfrak {A}}}$$ is strongly representable; this is the maximum degree of representability; the algebra in question cannot be ‘more representable’ than that. In this case the atom structure of $${{\mathfrak {A}}}$$ , namely $$\textsf {At}{{\mathfrak {A}}}$$ , is strongly representable in the sense of Hirsch and Hodkinson. This notion gives an infinite potential spectrum of ‘degrees’ of representability. In this connection, we exhibit various atomic algebras in $$\textsf {RCA}_n\cap \textsf {Nr}_n\textsf {CA}_l$$ that do no not have the complex neat embedding property for infinitely many values of l and m. It is known that the class of Kripke frames $$\textsf {Str}(\textsf {RCA}_n)=\{{{\mathfrak {F}}}: {{{\mathfrak {C}}}{{\mathfrak {m}}}}{{\mathfrak {F}}}\in \textsf {RCA}_n\}$$ is not elementary. From this it follows that there is some $$n<m<\omega $$ such that $$\textsf {Str}(\mathbf {S}\textsf {Nr}_n\textsf {CA}_m)=\{{{\mathfrak {F}}}: {{{\mathfrak {C}}}{{\mathfrak {m}}}}{{\mathfrak {F}}}\in \mathbf {S}\textsf {Nr}_n\textsf {CA}_m\}$$ is not elementary. Replacing $$\mathbf {S}$$ by $$\mathbf {S}_c$$ (forming complete subalgebras), $$\mathbf {S}_d$$ (forming dense subalgebras) and $$\mathbf {I}$$ (forming isomorphic copies), respectively, we show that for any $$\mathbf {O}\in \{\mathbf {S}_c, \mathbf {S}_d, \mathbf {I}\}$$ , the class of frames $$\textsf {Str}(\mathbf {O}\textsf {Nr}_n\textsf {CA}_{n+3})=\{{{\mathfrak {F}}}: {{{\mathfrak {C}}}{{\mathfrak {m}}}}{{\mathfrak {F}}}\in \mathbf {O}\textsf {Nr}_n\textsf {CA}_{n+3}\}$$ is not elementary. Metalogical applications are given to n-variable fragments of first-order logic endowed with so-called clique guarded semantics. The last semantics capture the new notions of representations introduced and studied in this paper.
Keywords
All Related Versions
Funding Information
- Cairo University
This publication has 12 references indexed in Scilit:
- The class of completely representable polyadic algebras of infinite dimensions is elementaryAlgebra universalis, 2014
- THE NEAT EMBEDDING PROBLEM FOR ALGEBRAS OTHER THAN CYLINDRIC ALGEBRAS AND FOR INFINITE DIMENSIONSThe Journal of Symbolic Logic, 2014
- Neat Reducts and Neat Embeddings in Cylindric Algebras2013
- Completions and Complete Representations2013
- Omitting types for finite variable fragments and complete representations of algebrasThe Journal of Symbolic Logic, 2008
- The class of neat reducts is not elementaryLogic Journal of the IGPL, 2001
- Atom structures of cylindric algebras and relation algebrasAnnals of Pure and Applied Logic, 1997
- Complete representations in algebraic logicThe Journal of Symbolic Logic, 1997
- Non-finite-axiomatizability results in algebraic logicThe Journal of Symbolic Logic, 1992
- Nonfinite axiomatizability results for cylindric and relation algebrasThe Journal of Symbolic Logic, 1989