Omitting Types in Fragments and Extensions of First Order Logic

Tarek Sayed Ahmed

doi:10.18778/0138-0680.2021.13

Authors

Tarek Sayed Ahmed Cairo University, Department of Mathematics, Faculty of Science

DOI:

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

Keywords:

Algebraic logic, multimodal logic, omitting types, completions

Abstract

Fix \(2 < n < \omega\). Let \(L_n\) denote first order logic restricted to the first n variables. Using the machinery of algebraic logic, positive and negative results on omitting types are obtained for \(L_n\) and for infinitary variants and extensions of \(L_{\omega, \omega}\).

References

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

[2]H. Andréka, I. Németi, T. Sayed 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

[3] B. Biró, Non-finite-axiomatizability results in algebraic logic, Journal of Symbolic Logic, vol. 57(3) (1992), pp. 832–843, DOI: https://doi.org/10.2307/2275434
Google Scholar DOI: https://doi.org/10.2307/2275434

[4] P. Blackburn, M. d. Rijke, Y. Venema, Modal Logic, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press (2001), DOI: https://doi.org/10.1017/CBO9781107050884
Google Scholar DOI: https://doi.org/10.1017/CBO9781107050884

[5] J. Bulian, I. Hodkinson, Bare canonicity of representable cylindric and polyadic algebras, Annals of Pure and Applied Logic, vol. 164(9) (2013), pp. 884–906, DOI: https://doi.org/10.1016/j.apal.2013.04.002
Google Scholar DOI: https://doi.org/10.1016/j.apal.2013.04.002

[6] A. Daigneault, J. Monk, Representation Theory for Polyadic algebras, Fundamenta Mathematicae, 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

[7] P. Erdös, Graph Theory and Probability, Canadian Journal of Mathematics, vol. 11 (1959), pp. 34–38, DOI: https://doi.org/10.4153/CJM-1959-003-9
Google Scholar DOI: https://doi.org/10.4153/CJM-1959-003-9

[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, vol. 22 of Bolyai Society Mathematical Studies, Springer Verlag (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

[9] D. H. Fremlin, Consequences of Martin’s Axiom, Cambridge Tracts in Mathematics, Cambridge University Press (1984), DOI: https://doi.org/10.1017/CBO9780511896972
Google Scholar DOI: https://doi.org/10.1017/CBO9780511896972

[10] L. Henkin, J. D. Monk, A. Tarski, L. Henkin, J. D. Monk, A. Tarski, Cylindric Algebras. Part I, Journal of Symbolic Logic, vol. 50(1) (1985), pp. 234–237, DOI: https://doi.org/10.2307/2273803
Google Scholar DOI: https://doi.org/10.2307/2273803

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

[12] R. Hirsch, I. Hodkinson (eds.), Relation algebras by games, vol. 147 of Studies in Logic and the Foundations of Mathematics, Elsevier Science, Amsterdam (2002).
Google Scholar

[13] 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 Verlag (2013), pp. 61–90, 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

[14] R. Hirsch, I. Hodkinson, A. Kurucz, On modal logics between K × K × K and S5 × S5 × S5, Journal of Symbolic Logic, vol. 67(1) (2002), pp. 221–234, DOI: https://doi.org/10.2178/jsl/1190150040
Google Scholar DOI: https://doi.org/10.2178/jsl/1190150040

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

[16] A. Kurucz, Representable cylindric algebras and many dimensional modal logics, [in:] H. Andréka, M. Ferenczi, I. Németi (eds.), Cylindric-like Algebras and Algebraic Logic, vol. 22 of Bolyai Society Mathematical Studies, Springer Verlag (2013), pp. 185–204, DOI: https://doi.org/10.1007/978-3-642-35025-2_9
Google Scholar DOI: https://doi.org/10.1007/978-3-642-35025-2_9

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

[18] T. Sayed Ahmed, Amalgamation for reducts of polyadic algebras, Algebra Universalis, vol. 51 (2004), pp. 301–359, DOI: https://doi.org/10.1007/s00012-004-1807-y
Google Scholar DOI: https://doi.org/10.1007/s00012-004-1807-y

[19] 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 Verlag (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

[20] 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 Verlag (2013), pp. 105–134, 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

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

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

[23] T. Sayed Ahmed, Representability for cylindric and polyadic algebras, Studia Mathematicea Hungarica, vol. 56(3) (2019), pp. 335–363.
Google Scholar DOI: https://doi.org/10.1556/012.2019.56.3.1436

[24] S. Shelah, Classification Theory, vol. 92 of Studies in Logic and the Foundations of Mathematics, Elsevier (1978).
Google Scholar

[25] Y. Venema, Atom structures and Sahlqvist equations, Algebra Universalis, vol. 38 (1997), pp. 185–199, DOI: https://doi.org/10.1007/s000120050047
Google Scholar DOI: https://doi.org/10.1007/s000120050047