On  Complete Representations and Minimal Completions in Algebraic Logic, Both Positive and Negative Results

Tarek Sayed Ahmed

doi:10.18778/0138-0680.2021.17

Authors

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

DOI:

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

Keywords:

Algebraic logic, relation algebras, cylindric algebras, polyadic algebras, complete representations

Abstract

Fix a finite ordinal \(n\geq 3\) and let \(\alpha\) be an arbitrary ordinal. Let \(\mathsf{CA}_n\) denote the class of cylindric algebras of dimension \(n\) and \(\sf RA\) denote the class of relation algebras. Let \(\mathbf{PA}_{\alpha}(\mathsf{PEA}_{\alpha})\) stand for the class of polyadic (equality) algebras of dimension \(\alpha\). We reprove that the class \(\mathsf{CRCA}_n\) of completely representable \(\mathsf{CA}_n\)s, and the class \(\sf CRRA\) of completely representable \(\mathsf{RA}\)s are not elementary, a result of Hirsch and Hodkinson. We extend this result to any variety \(\sf V\) between polyadic algebras of dimension \(n\) and diagonal free \(\mathsf{CA}_n\)s. We show that that the class of completely and strongly representable algebras in \(\sf V\) is not elementary either, reproving a result of Bulian and Hodkinson. For relation algebras, we can and will, go further. We show the class \(\sf CRRA\) is not closed under \(\equiv_{\infty,\omega}\). In contrast, we show that given \(\alpha\geq \omega\), and an atomic \(\mathfrak{A}\in \mathsf{PEA}_{\alpha}\), then for any \(n<\omega\), \(\mathfrak{Nr}_n\mathfrak{A}\) is a completely representable \(\mathsf{PEA}_n\). We show that for any \(\alpha\geq \omega\), the class of completely representable algebras in certain reducts of \(\mathsf{PA}_{\alpha}\)s, that happen to be varieties, is elementary. We show that for \(\alpha\geq \omega\), the the class of polyadic-cylindric algebras dimension \(\alpha\), introduced by Ferenczi, the completely representable algebras (slightly altering representing 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 \(n\) and \(\mathsf{PA}_{\alpha}\)s for \(\alpha\) an infinite ordinal, proving negative results for the first and positive ones for the second.

References

H. Andréka, M. Ferenczi, I. Németi (eds.), Cylindric-like Algebras and Algebraic Logic, Springer Berlin Heidelberg, Berlin, Heidelberg (2013), DOI: https://doi.org/10.1007/978-3-642-35025-2_1
Google Scholar DOI: https://doi.org/10.1007/978-3-642-35025-2

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

A. Daigneault, J. Monk, Representation Theory for Polyadic algebras, Fundamenta Informaticae, vol. 52 (1963), pp. 151–176, DOI: https://doi.org/10.4064/fm-52-2-151-176
Google Scholar DOI: https://doi.org/10.4064/fm-52-2-151-176

M. Ferenczi, The Polyadic Generalization of the Boolean Axiomatization of Fields of Sets, Transactions of the American Mathematical Society, vol. 364(2) (2012), pp. 867–886, DOI: https://doi.org/10.2307/41407800
Google Scholar DOI: https://doi.org/10.1090/S0002-9947-2011-05332-8

M. Ferenczi, A New Representation Theory: Representing Cylindric-like Algebras by Relativized Set Algebras, [in:] H. Andréka, M. Ferenczi, I. Németi (eds.), Cylindric-like Algebras and Algebraic Logic, Springer Berlin Heidelberg, Berlin, Heidelberg (2013), pp. 135–162, DOI: https://doi.org/10.1007/978-3-642-35025-2_7
Google Scholar DOI: https://doi.org/10.1007/978-3-642-35025-2_7

M. Ferenczi, Representations of polyadic-like equality algebras, Algebra Universalis, vol. 75(1) (2016), pp. 107–125, DOI: https://doi.org/10.1007/s00012-015-0360-1
Google Scholar DOI: https://doi.org/10.1007/s00012-015-0360-1

L. Henkin, J. Monk, A. Tarski, Cylindric Algebras Parts I, II, North Holland, Amsterdam (1971).
Google Scholar

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
Google Scholar 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
Google Scholar 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, North Holland, Amsterdam (2002).
Google Scholar

R. Hirsch, I. Hodkinson, Completions and Complete Representations, [in:] H. Andréka, M. Ferenczi, I. Németi (eds.), Cylindric-like Algebras and Algebraic Logic, Springer Berlin Heidelberg, Berlin, Heidelberg (2013), pp. 61–89, DOI: https://doi.org/10.1007/978-3-642-35025-2_4
Google Scholar DOI: https://doi.org/10.1007/978-3-642-35025-2_4

R. Hirsch, I. Hodkinson, R. D. 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
Google Scholar 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, The Journal of Symbolic Logic, vol. 79(1) (2014), pp. 208–222, DOI: https://doi.org/10.1017/jsl.2013.20
Google Scholar DOI: https://doi.org/10.1017/jsl.2013.20

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

J. S. Johnson, Nonfinitizability of classes of representable polyadic algebras, Journal of Symbolic Logic, vol. 34(3) (1969), pp. 344–352, DOI: https://doi.org/10.2307/2270901
Google Scholar DOI: https://doi.org/10.2307/2270901

R. D. Maddux, Nonfinite axiomatizability results for cylindric and relation algebras, Journal of Symbolic Logic, vol. 54(3) (1989), pp. 951–974, DOI: https://doi.org/10.2307/2274756
Google Scholar DOI: https://doi.org/10.2307/2274756

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
Google Scholar DOI: https://doi.org/10.1093/jigpal/9.4.593

T. Sayed Ahmed, The class of 2-dimensional neat reducts is not elementary, Fundamenta Mathematicae, vol. 172 (2002), pp. 61–81, DOI: https://doi.org/10.4064/fm172-1-5
Google Scholar DOI: https://doi.org/10.4064/fm172-1-5

T. Sayed Ahmed, A Modeltheoretic Solution to a Problem of Tarski, Mathematical Logic Quarterly, vol. 48(3) (2002), pp. 343–355, DOI: https://doi.org/10.1002/1521-3870(200204)48:3<343::AID-MALQ343>3.0.CO;2-4
Google Scholar DOI: https://doi.org/10.1002/1521-3870(200204)48:3<343::AID-MALQ343>3.0.CO;2-4

T. Sayed Ahmed, Algebraic Logic, Where Does it Stand Today?, Bulletin of Symbolic Logic, vol. 11(4) (2005), pp. 465–516, DOI: https://doi.org/10.2178/bsl/1130335206
Google Scholar DOI: https://doi.org/10.2178/bsl/1130335206

T. Sayed Ahmed, A Note on Neat Reducts, Studia Logica: An International Journal for Symbolic Logic, vol. 85(2) (2007), pp. 139–151, DOI: https://doi.org/10.2307/40210764
Google Scholar DOI: https://doi.org/10.1007/s11225-007-9034-0

T. Sayed Ahmed, (RaCA_n) is not elementary for (ngeq 5), Bulletin of the Section of Logic, vol. 37(2) (2008), pp. 123–136.
Google Scholar

T. Sayed Ahmed, Atom-canonicity, relativized representations and omitting types for clique guarded semantics and guarded logics (2013), arXiv:1308.6165.
Google Scholar

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, Springer Berlin Heidelberg, Berlin, Heidelberg (2013), pp. 205–221, DOI: https://doi.org/10.1007/978-3-642-35025-2_10
Google Scholar 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, Springer Berlin Heidelberg, Berlin, Heidelberg (2013), pp. 105–131, DOI: https://doi.org/10.1007/978-3-642-35025-2_6
Google Scholar DOI: https://doi.org/10.1007/978-3-642-35025-2_6

T. Sayed Ahmed, The class of completely representable polyadic algebras of infinite dimensions is elementary, Algebra Universalis, vol. 72(4) (2014), pp. 371–380, DOI: https://doi.org/10.1007/s00012-014-0307-y
Google Scholar DOI: https://doi.org/10.1007/s00012-014-0307-y

T. Sayed Ahmed, On notions of representability for cylindric‐polyadic algebras, and a solution to the finitizability problem for quantifier logics with equality, Mathematical Logic Quarterly, vol. 61(6) (2015), pp. 418–477, DOI: https://doi.org/10.1002/malq.201300064
Google Scholar DOI: https://doi.org/10.1002/malq.201300064

T. Sayed Ahmed, Splitting methods in algebraic logic: Proving results on non-atom-canonicity, non-finite axiomatizability and non-first oder definability for cylindric and relation algebras (2015), arXiv:1503.02189.
Google Scholar

T. Sayed Ahmed, Atom-canonicity in algebraic logic in connection to omitting types in modal fragments of (L_{omega, omega}) (2016), arXiV:1608.03513.
Google Scholar