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

Sayed Ahmed, Tarek 

Bulletin of the Section of Logic, Tome 50 (2021) no. 4, pp. 465-511.

Résumé

Fix a finite ordinal n≥ 3 and let α be an arbitrary ordinal. Let 𝖢𝖠_n denote the class of cylindric algebras of dimension n and RA denote the class of relation algebras. Let 𝐏𝐀_α(𝖯𝖤𝖠_α) stand for the class of polyadic (equality) algebras of dimension α. We reprove that the class 𝖢𝖱𝖢𝖠_n of completely representable 𝖢𝖠_ns, and the class CRRA of completely representable 𝖱𝖠s are not elementary, a result of Hirsch and Hodkinson. We extend this result to any variety V between polyadic algebras of dimension n and diagonal free 𝖢𝖠_ns. We show that that the class of completely and strongly representable algebras in 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 CRRA is not closed under ≡_∞,ω. In contrast, we show that given α≥ω, and an atomic 𝔄∈𝖯𝖤𝖠_α, then for any n, 𝔑𝔯_n𝔄 is a completely representable 𝖯𝖤𝖠_n. We show that for any α≥ω, the class of completely representable algebras in certain reducts of 𝖯𝖠_αs, that happen to be varieties, is elementary. We show that for α≥ω, the the class of polyadic-cylindric algebras dimension α, 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 𝖯𝖠_αs for α an infinite ordinal, proving negative results for the first and positive ones for the second.

Détail

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

Bibliographie

[1] H. Andréka, M. Ferenczi, I. Németi (eds.), Cylindric-like Algebras and Algebraic Logic, Springer Berlin Heidelberg, Berlin, Heidelberg (2013) | DOI

[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

[3] A. Daigneault, J. Monk, Representation Theory for Polyadic algebras, Fundamenta Informaticae, vol. 52 (1963), pp. 151–176 | DOI

[4] 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

[5] 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

[6] M. Ferenczi, Representations of polyadic-like equality algebras, Algebra Universalis, vol. 75(1) (2016), pp. 107–125 | DOI

[7] L. Henkin, J. Monk, A. Tarski, Cylindric Algebras Parts I, II, North Holland, Amsterdam (1971).

[8] R. Hirsch, Relation algebra reducts of cylindric algebras and complete representations, Journal of Symbolic Logic, vol. 72(2) (2007), pp. 673–703 | DOI

[9] R. Hirsch, I. Hodkinson, Complete representations in algebraic logic, Journal of Symbolic Logic, vol. 62(3) (1997), pp. 816–847 | DOI

[10] R. Hirsch, I. Hodkinson, Relation algebras by games, vol. 147 of Studies in Logic and the Foundations of Mathematics, North Holland, Amsterdam (2002).

[11] 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

[12] 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

[13] 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

[14] I. Hodkinson, Atom structures of cylindric algebras and relation algebras, Annals of Pure and Applied Logic, vol. 89(2) (1997), pp. 117–148 | DOI

[15] J. S. Johnson, Nonfinitizability of classes of representable polyadic algebras, Journal of Symbolic Logic, vol. 34(3) (1969), pp. 344–352 | DOI

[16] R. D. Maddux, Nonfinite axiomatizability results for cylindric and relation algebras, Journal of Symbolic Logic, vol. 54(3) (1989), pp. 951–974 | DOI

[17] T. Sayed Ahmed, The class of neat reducts is not elementary, Logic Journal of the IGPL, vol. 9(4) (2001), pp. 593–628 | DOI

[18] T. Sayed Ahmed, The class of 2-dimensional neat reducts is not elementary, Fundamenta Mathematicae, vol. 172 (2002), pp. 61–81 | DOI

[19] T. Sayed Ahmed, A Modeltheoretic Solution to a Problem of Tarski, Mathematical Logic Quarterly, vol. 48(3) (2002), pp. 343–355343::AID-MALQ343>3.0.CO;2-4'>10.1002/1521-3870(200204)48:3343::AID-MALQ343>3.0.CO;2-4 | DOI

[20] T. Sayed Ahmed, Algebraic Logic, Where Does it Stand Today?, Bulletin of Symbolic Logic, vol. 11(4) (2005), pp. 465–516 | DOI

[21] T. Sayed Ahmed, A Note on Neat Reducts, Studia Logica: An International Journal for Symbolic Logic, vol. 85(2) (2007), pp. 139–151 | DOI

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

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

[24] 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

[25] 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

[26] 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

[27] 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

[28] 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.

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