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

• Autorzy: Tarek Sayed Ahmed

Abstrakty

EN

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.

Słowa kluczowe

EN

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

• Wydawca: Wydawnictwo Uniwersytetu Łódzkiego
• Czasopismo: Bulletin of the Section of Logic
• Rocznik: 2021
• Tom: 50
• Numer: 4
• Strony: 465-511

Daty

wydano

2021

Twórcy

autor

Tarek Sayed Ahmed

• Cairo University, Department of Mathematics, Faculty of Science

• https://orcid.org/0000000260956237

Bibliografia

• 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
• 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
• 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
• 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
• 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
• 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
• L. Henkin, J. Monk, A. Tarski, Cylindric Algebras Parts I, II, North Holland, Amsterdam (1971).
• 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
• 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
• R. Hirsch, I. Hodkinson, Relation algebras by games, vol. 147 of Studies in Logic and the Foundations of Mathematics, North Holland, Amsterdam (2002).
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• T. Sayed Ahmed, (RaCA_n) is not elementary for (ngeq 5), Bulletin of the Section of Logic, vol. 37(2) (2008), pp. 123–136.
• T. Sayed Ahmed, Atom-canonicity, relativized representations and omitting types for clique guarded semantics and guarded logics (2013), arXiv:1308.6165.
• 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
• 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
• 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
• 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
• 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.
• T. Sayed Ahmed, Atom-canonicity in algebraic logic in connection to omitting types in modal fragments of (L_{omega, omega}) (2016), arXiV:1608.03513.

Identyfikatory

DOI

10.18778/0138-0680.2021.17

nonstd.3pn.id

2033851