Complete Representations  and Neat Embeddings

Tarek Sayed Ahmed

doi:10.18778/0138-0680.2022.17

Authors

Tarek Sayed Ahmed Cairo University, Department of Mathematics, Faculty of Science, Giza, Egypt Author https://orcid.org/0000-0002-6095-6237

DOI:

https://doi.org/10.18778/0138-0680.2022.17

Keywords:

algebraic logic, cylindric algebras, relation algebras, atom-canonicity, combinatorial game theory

Abstract

Let \(2<n<\omega\). Then \({\sf CA}_n\) denotes the class of cylindric algebras of dimension \(n\), \({\sf RCA}_n\) denotes the class of representable \(\sf CA_n\)s, \({\sf CRCA}_n\) denotes the class of completely representable \({\sf CA}_n\)s, and \({\sf Nr}_n{\sf CA}_{\omega}(\subseteq {\sf CA}_n\)) denotes the class of \(n\)-neat reducts of \({\sf CA}_{\omega}\)s. The elementary closure of the class \({\sf CRCA}_n\)s (\(\mathbf{K_n}\)) and the non-elementary class \({\sf At}({\sf Nr}_n{\sf CA}_{\omega})\) are characterized using two-player zero-sum games, where \({\sf At}\) is the operator of forming atom structures. 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 \(2<n<m\), any \(l\geq n+3\) any any class \(\mathbf{K}\) (such that \({\sf At}({\sf Nr}_n{\sf CA}_{m})\cap {\sf CRCA}_n\subseteq \mathbf{K}\subseteq {\sf At}\mathbf{S_c}{\sf Nr}_n{\sf CA}_{l}\), \(\mathbf{K}\) is not not first order definable either.

References

H. Andréka, M. Ferenczi, I. Németi (eds.), Cylindric-like Algebras and Algebraic Logic, vol. 22 of Bolyai Society Mathematical Studies, Springer, Berlin, Heidelberg (2012), DOI: https://doi.org/10.1007/978-3-642-35025-2 DOI: https://doi.org/10.1007/978-3-642-35025-2

H. Andréka, I. Németi, T. Sayed Ahmed, Omitting types for finite variable fragments and complete representations, Journal of Symbolic Logic, vol. 73(1) (2008), pp. 65–89, DOI: https://doi.org/10.2178/jsl/1208358743 DOI: https://doi.org/10.2178/jsl/1208358743

L. Henkin, J. Monk, A. Tarski, Cylindric Algebras Part II, no. 115 in Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam (1985), DOI: https://doi.org/10.1016/S0049-237X(08)70001-6 DOI: https://doi.org/10.1016/S0049-237X(08)70001-6

R. Hirsch, Relation algebra reducts of cylindric algebras and complete representations, Journal of Symbolic Logic, vol. 72(2) (2007), pp. 673–703, DOI: https://doi.org/10.2178/jsl/1185803629 DOI: https://doi.org/10.2178/jsl/1185803629

R. Hirsch, I. Hodkinson, Complete representations in algebraic logic, Journal of Symbolic Logic, vol. 62(3) (1997), pp. 816–847, DOI: https://doi.org/10.2307/2275574 DOI: https://doi.org/10.2307/2275574

R. Hirsch, I. Hodkinson, Relation algebras by games, vol. 147 of Studies in Logic and the Foundations of Mathematics, Elsevier, Amsterdam (2002), DOI: https://doi.org/10.1016/S0049-237X(02)80054-4 DOI: https://doi.org/10.1016/S0049-237X(02)80054-4

R. Hirsch, I. Hodkinson, Completions and complete representations, [in:] H. Andréka, M. Ferenczi, I. Németi (eds.), Cylindric-like Algebras and Algebraic Logic, vol. 22 of Bolyai Society Mathematical Studies, Springer, Berlin, Heidelberg (2012), pp. 61–90, DOI: https://doi.org/10.1007/978-3-642-35025-2_4 DOI: https://doi.org/10.1007/978-3-642-35025-2_4

R. Hirsch, I. Hodkinson, R. Maddux, Relation algebra reducts of cylindric algebras and an application to proof theory, Journal of Symbolic Logic, vol. 67(1) (2002), pp. 197–213, DOI: https://doi.org/10.2178/jsl/1190150037 DOI: https://doi.org/10.2178/jsl/1190150037

R. Hirsch, T. Sayed Ahmed, The neat embedding problem for algebras other than cylindric algebras and for infinite dimensions, Journal of Symbolic Logic, vol. 79(1) (2014), pp. 208–222, DOI: https://doi.org/10.1017/jsl.2013.20 DOI: https://doi.org/10.1017/jsl.2013.20

I. Hodkinson, Atom structures of relation and cylindric algebras, Annals of Pure and Applied Logic, vol. 89(2–3) (1997), pp. 117–148, DOI: https://doi.org/10.1016/S0168-0072(97)00015-8 DOI: https://doi.org/10.1016/S0168-0072(97)00015-8

T. Sayed Ahmed, The class of neat reducts is not elementary, Logic Journal of the IGPL, vol. 9(4) (2001), pp. 593–628, DOI: https://doi.org/10.1093/jigpal/9.4.593 DOI: https://doi.org/10.1093/jigpal/9.4.593

T. Sayed Ahmed, Neat embedding is not sufficient for complete representations, Bulletin of the Section of Logic, vol. 36(1) (2007), pp. 29–36.

T. Sayed Ahmed, Completions, complete representations and omitting types, [in:] H. Andréka, M. Ferenczi, I. Németi (eds.), Cylindric-like Algebras and Algebraic Logic, vol. 22 of Bolyai Society Mathematical Studies, Springer, Berlin, Heidelberg (2012), pp. 186–205, DOI: https://doi.org/10.1007/978-3-642-35025-2_10 DOI: https://doi.org/10.1007/978-3-642-35025-2_10

T. Sayed Ahmed, Neat reducts and neat embeddings in cylindric algebras, [in:] H. Andréka, M. Ferenczi, I. Németi (eds.), Cylindric-like Algebras and Algebraic Logic, vol. 22 of Bolyai Society Mathematical Studies, Springer, Berlin, Heidelberg (2012), pp. 105–134, DOI: https://doi.org/10.1007/978-3-642-35025-2_6 DOI: https://doi.org/10.1007/978-3-642-35025-2_6

T. Sayed Ahmed, Various notions of represetability for cylindric and polyadic algebras, Studia Scientiarum Mathematicarum Hungarica, vol. 56(3) (2019), pp. 335–363, DOI: https://doi.org/10.1556/012.2019.56.3.1436 DOI: https://doi.org/10.1556/012.2019.56.3.1436

T. Sayed Ahmed, Blow up and Blow constructions in Algebraic Logic, [in:] J. Madarász, G. Székely (eds.), Hajnal Andréka and István Németi on Unity of Science. From Computing to Relativity Theory Through Algebraic Logic, vol. 19 of Outstanding Contributions to Logic, Springer, Cham (2021), pp. 347–359, DOI: https://doi.org/10.1007/978-3-030-64187-0_14 DOI: https://doi.org/10.1007/978-3-030-64187-0_14

T. Sayed Ahmed, I. Németi, On neat reducts of algebras of logic, Studia Logica, vol. 68(2) (2001), pp. 229–262, DOI: https://doi.org/10.1023/A:1012447223176 DOI: https://doi.org/10.1023/A:1012447223176