Hostname: page-component-7c8c6479df-xxrs7 Total loading time: 0 Render date: 2024-03-19T09:09:36.967Z Has data issue: false hasContentIssue false

On the equational theory of representable polyadic equality algebras

Published online by Cambridge University Press:  12 March 2014

István Németi
Affiliation:
Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest PF. 127, H-1364, Hungary E-mail: nemeti@.math-inst.hu
Gábor Sági
Affiliation:
Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest PF. 127, H-1364, Hungary E-mail: sagi@math-inst.hu

Abstract

Among others we will prove that the equational theory of ω dimensional representable polyadic equality algebras (RPEAω's) is not schema axiomatizable. This result is in interesting contrast with the Daigneault-Monk representation theorem, which states that the class of representable polyadic algebras is finite schema-axiomatizable (and hence the equational theory of this class is finite schema-axiomatizable. as well). We will also show that the complexity of the equational theory of RPEAω is also extremely high in the recursion theoretic sense. Finally, comparing the present negative results with the positive results of Ildikó Sain and Viktor Gyuris [12], the following methodological conclusions will be drawn: The negative properties of polyadic (equality) algebras can be removed by switching from what we call the “polyadic algebraic paradigm” to the “cylindric algebraic paradigm”.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Andréka, H., Németi, I., and Sain, I., Algebras of Relations and Algebraic Logic, 1994, Manuscript.Google Scholar
[2]Burris, S. and Sankappanavar, H.P., A course in universal algebra, Graduate Texts in Mathematics, Springer-Verlag, New York, 1981.CrossRefGoogle Scholar
[3]Chang, C.C. and Keisler, H.J., Model Theory, North-Holland, Amsterdam, 1973.Google Scholar
[4]Craig, W., Logic in algebraic form, North-Holland, Amsterdam, 1974.Google Scholar
[5]Halmos, P., Algebraic Logic, Chelsea Publishing Company, 1962.Google Scholar
[6]Henkin, L., Monk, J.D., and Tarski, A., Cylindric Algebras Part 1, North-Holland, Amsterdam, 1971.Google Scholar
[7]Henkin, L., Monk, J.D., and Tarski, A., Cylindric Algebras Part 2, North-Holland, Amsterdam, 1985.Google Scholar
[8]Monk, J.D. and Daigneault, A., Representation theory for polyadic algebras, Funtamenta Informaticae, vol. 52 (1963), pp. 151–176.Google Scholar
[9]Németi, I., Algebraization of Quantifier Logics, an introductory overview, Studia Logica, vol. 50, no. 3/4, pp. 485–569, (A strongly updated and expanded version is available from the author. Electronic address: http://renyi.hu/pub/algebraic-logic/survey.dvi).Google Scholar
[10]Odifreddi, P., Classical Recursion Theory, North-Holland, Amsterdam, 1989.Google Scholar
[11]Sági, G., Non-computability of the consequences of the axioms of the ω dimensional polyadic algebras, Mathematical Institute, Budapest, (1995), Preprint, (submitted for publication).Google Scholar
[12]Sain, I. and Gyuris, V., Finite Schematizable Algebraic Logic, Bulletin of IGPL, vol. 5 (1997), no. 5, pp. 699–751.CrossRefGoogle Scholar
[13]Sain, I. and Thompson, R., Strictly Finite Schema Axiomatization of Quasi-polyadic Algebras, Algebraic Logic proceedings of the conference of Budapest (1988) (Amsterdam) (Andréka, H., Monk, J.D., and Németi, I., editors), vol. 54, Colloquia Mathematica Societatis János Bolyai, North-Holland, 1991, pp. 539–571.Google Scholar
[14]Tarski, A. and Givant, S., A formalization of set theory without variables, AMS Colloquium Publications 41, 1988.Google Scholar