×

Complexity of equational theory of relational algebras with standard projection elements. (English) Zbl 1357.03097

Summary: The class \(\mathsf{TPA}\) of \(\underline t\)rue \(\underline p\)airing \(\underline a\)lgebras is defined to be the class of relation algebras expanded with concrete set theoretical projection functions. The main results of the present paper is that neither the equational theory of \(\mathsf{TPA}\) nor the first order theory of \(\mathsf{TPA}\) are decidable. Moreover, we show that the set of all equations valid in \(\mathsf{TPA}\) is exactly on the \(\Pi ^1_1\) level. We consider the class \(\mathsf{TPA}^-\) of the relation algebra reducts of \(\mathsf{TPA}\)’s, as well. We prove that the equational theory of \(\mathsf{TPA}^-\) is much simpler, namely, it is recursively enumerable. We also give motivation for our results and some connections to related work.

MSC:

03G27 Abstract algebraic logic
03D15 Complexity of computation (including implicit computational complexity)
03B25 Decidability of theories and sets of sentences
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Andréka, H. (1990). Complexity of the equations valid in algebras of relations. Thesis for DSc with Hungarian Academy of Sciences, Budapest · Zbl 0745.03057
[2] Andréka, H., & Németi, I. (2012). Reducing first-orde logic to \[\text{ Df }_3\] Df3, free algebras. In H. Andréka, M. Ferenczi, & I. Németi (Eds.), Cylindric-like algebras and algebraic logic (pp. 15-35). Bolyai society mathematical studies (series editor: D. Miklós). Berlin: Springer Verlag. · Zbl 1284.03272
[3] Andréka, H., Németi, I., & Sain, I. (1994). Applying algebraic logic to logic. In T. Rus, M. Nivat, C. Rattray, & G. Scollo (Eds.), Algebraic methodology and software technology (AMAST’93), Proceedings of the third international conference on algebraic methodology and software technology, The Netherlands, 21-25 June 1993. Workshops in computing (pp. 5-26), University of Twente. London: Springer-Verlag. · Zbl 1173.03049
[4] Andréka, H., Németi, I., & Sain, I. (2001). Algebraic logic. In D. M. Gabbay & F. Guenthner (Eds.), Handbook of philosophical logic (2nd edn., Vol. II, pp. 133-247). Dordrecht: Kluwer Academic Publishers. Preprint form available from the home page of the Rényi Institute. · Zbl 1003.03536
[5] Andréka, H., Németi, I., Sain, I., & Kurucz, Á. (1995). General algebraic logic including algebraic model theory: An overview. In D. M. Gabbay L. Csirmaz, M. de Rijke (Eds.), Logic colloquium’92. Proceedings, Veszprém, Hungary, 1992. Studies in logic, language and computation, (pp. 1-60). Stanford: CSLI Publications. · Zbl 0844.03034
[6] Biró, B. (1992). Non-finite-axiomatizability results in algebraic logic. Journal of Symbolic Logic, 57(3), 832-843. · Zbl 0772.03032 · doi:10.2307/2275434
[7] Blok, W. J., & Pigozzi, D. L. (1989). Algebraizable logics. Memoirs of the American Mathematical Society, 77(396), vi+78. · Zbl 0664.03042 · doi:10.1090/memo/0396
[8] Craig, W.; Henkin, L. (ed.); Addison, JW (ed.); Tarski, A. (ed.), Boolean notions extended to higher dimensions, 55-69 (1965), Amsterdam · Zbl 0166.25901
[9] Craig, W., & Vaught, R. L. (1958). Finite axiomatizability using additional predicates. Journal of Symbolic Logic, 23, 289. · Zbl 0085.24601 · doi:10.2307/2964289
[10] Ferenczi, M. (2012). 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 (pp. 135-162). Bolyai society mathematical studies (series editor: D. Miklós). Berlin: Springer Verlag. · Zbl 1278.03091
[11] Ferenczi, M. (2012). Representation theory based on relativised set algebras originating from logic. Dissertation for D. Sc. with Hungarian Academy of Sciences, Budapest. In Hungarian, ix+125 pp. · Zbl 1168.03051
[12] Formisano, A., Omodeo, E.G. (1998). An equational re-engineering of set theories. In FTP (LNCS selection) (pp. 175-190). · Zbl 0955.03016
[13] Henkin, L. (1987). L. Henkin’s remark in the discussion following R. D. Maddux’s lecture at the “Asilomar Conference”, July 6-12. · Zbl 0664.03042
[14] Henkin, L., & Monk, J. D. (1974). Cylindric Algebras and related structures. Proceedings of the Tarski Symposium on American Mathematical Society, 25, 105-121. · Zbl 0307.02041 · doi:10.1090/pspum/025/0376346
[15] Henkin, L., Monk, J. D., & Tarski, A. (1985). Cylindric algebras part II. Amsterdam: North-Holland. · Zbl 0576.03043
[16] Jónsson, B. (1982). On binary relations. In G. Hutchinson (Ed.), Proceedings of the NIH conference on universal algebra and lattice theory (pp. 2-5). Bethesda, MA: Laboratory of Computer Research and Technology, National Institute of Health. · Zbl 0812.03038
[17] Jónsson, B. (1991). The theory of binary relations. In H. Andréka, J. D. Monk, & I. Németi (Eds.), Algebraic logic. Proceedings of the conference, Budapest 1988 (pp. 245-292). Amsterdam: Colloq. Math. Soc. J. Bolyai, North-Holland. · Zbl 0760.03018
[18] Kurucz, Á. (2009). Weakly associative relation algebras with projections. Mathematical Logic Quarterly, 55, 138-153. · Zbl 1168.03051 · doi:10.1002/malq.200710074
[19] Kurucz, Á., & Németi, I. (2000). Representability of pairing relation algebras depends on your ontology. Fundamenta Informaticae, 44(4), 397-420. · Zbl 0971.03064
[20] Maddux, R.D. (1987). Finitary algebraic logic. Invited lecture at the conference “Algebras, Lattices and Logic”, Asilomar California, July 6-12. · Zbl 0770.03021
[21] Maddux, R. D. (1989). Finitary algebraic logic. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 35, 321-332. · Zbl 0661.03052 · doi:10.1002/malq.19890350405
[22] Mikulás, Sz., Sain, I., & Simon, A. (1991). The complexity of the equational theory of relational algebras with standard projection elements. Technical report, Mathematical Institute of the Hungarian Academy of Sciences, Budapest. · Zbl 0661.03052
[23] Mikulás, Sz, Sain, I., & Simon, A. (1992). Complexity of equational theory of relational algebras with projection elements. Bulletin of the Section of Logic, 21(3), 103-111. · Zbl 0770.03021
[24] Monk, J. D. (1970). On an algebra of sets of finite sequences. Journal of Symbolic Logic, 35, 19-28. · Zbl 0196.01001 · doi:10.2307/2271151
[25] Németi, I. (1986). Free algebras and decidability in algebraic logic. Dissertation for D. Sc. with Hungarian Academy of Sciences, Budapest. In Hungarian, xviii+169 pp.
[26] Németi, I. (1987). On varieties of cylindric algebras with applications to logic. Annals of Pure and Applied Logic, 36, 235-277. · Zbl 0637.03062 · doi:10.1016/0168-0072(87)90019-4
[27] Németi, I. (1991). Algebraization of quantifier logics, an introductory overview. In: W. J. Blok, D. L. Pigozzi (Eds.), Studia logica, 50, No 3/4 (a special issue devoted to Algebraic Logic) (pp. 485-570). Strongly updated and expanded [e.g. with proofs] version is electronically available as: http://circle.math-inst.hu/pub/algebraic-logic/survey.dvi, survey.ps. · Zbl 0772.03033
[28] Németi, I., & Simon, A. (2009). Weakly higher order cylindric algebras and finite axiomatization of the representables. Studia Logica, 91, 53-62. · Zbl 1173.03049 · doi:10.1007/s11225-009-9162-9
[29] Rogers, H. (1967). Theory of recursive functions and effective computability. New York: McGraw Hill. · Zbl 0183.01401
[30] Sági, G. (2000). A completeness theorem for higher order logics. Journal of Symbolic Logic, 65(2), 857-884. · Zbl 0979.03047 · doi:10.2307/2586575
[31] Sain, I. (1988). On the search for a finitizable algebraization of first order logic (shortened version a). Technical report, Mathematical Institute of the Hungarian Academy of Science, Budapest.
[32] Sain, I. (1994). On finitizing first order logic. Bulletin of the Section of Logic, 23(2), 66-79. · Zbl 0812.03038
[33] Sain, I. (1995). On the problem of finitizing first order logic and its algebraic counterpart (A Survey of results and methods). In D.M. Gabbay, L. Csirmaz, M. de Rijke (Eds.), Logic colloquium’92 (Proceedings, Veszprém, Hungary, 1992). Studies in logic, language and computation (pp. 243-292). Stanford: CSLI Publications. · Zbl 0844.03035
[34] Sain, I. (2012). Definability issues in universal logic. In H. Andréka, M. Ferenczi, & I. Németi (Eds.), Cylindric-like algebras and algebraic logic (pp. 393-419). Bolyai society mathematical studies (series editor: D. Miklós) Berlin: Springer Verlag. · Zbl 1284.03135
[35] Sain, I. (2000). On the Search for a Finitizable Algebraization of First Order Logic. Logic Journal of the IGPL, 8(4):495-589. Electronically available as: http://www3.oup.co.uk/igpl/Volume_08/Issue_04/. · Zbl 0973.03008
[36] Sain, I., & Németi, I.(1995). Fork algebras in usual and in non-well-founded settheories. (extended abstract) part i and part ii. Bulletin of the Section of Logic, 24(3 and 4):158-168 and 182-192. · Zbl 0849.03052
[37] Sayed Ahmed, T. (2005). Algebraic logic, where does it stand today? Bulletin of Symbolic Logic, 11(4), 465-516. · Zbl 1111.03053 · doi:10.2178/bsl/1130335206
[38] Sayed Ahmed, T. (2015). On notions of representability for cylindric polyadic algebras, and a solution to the finitizability problem for quantifier logics with equality. Mathematical Logic Quarterly (in press). · Zbl 1368.03069
[39] Simon, A. (1993). What the finitization problem is not. In Rauszer, C. (ed.), Algebraic methods in logic and in computer science (Proceedings of the ’91 Banach Semester, Banach Center), Vol. 28 of Banach Center Publications, pp. 95-116. Warszawa: Institute of Mathematics Polish Academy of Sciences. · Zbl 0797.03063
[40] Tarski, A., & Givant, S. (1987). A formalization of set theory without variables (Vol. 41). Providence, RI: AMS Colloquium Publications. · Zbl 0654.03036
[41] van de Vel, M. (2002). Interpreting first-order theories into a logic of records. Studia Logica, 72, 411-432. · Zbl 1015.03024 · doi:10.1023/A:1021849625062
[42] Veloso, P. A. S., & Haeberer, A. M. (1991). A Finitary Relational Algebra for Classical First-order Logic. Bulletin of the Section of Logic, 20(2), 52-62. · Zbl 0745.03057
[43] Veloso, P. A. S., & Haeberer, A. M. (1991). A new algebra of first-order logic. In Methodology and philosophy of science. Proceedings of the 9th international congress on logic, Upsala, Sweden. · Zbl 0745.03057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.