Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-22T23:33:07.810Z Has data issue: false hasContentIssue false
  • English
  • Français

Non-finite-axiomatizability results in algebraic logic

Published online by Cambridge University Press:  12 March 2014

Balázs Biró
Balázs Biró*
Affiliation:
Mathematical Institute, Hungarian Academy of Sciences, H-1364 Budapest, Hungary
Get access Rights & Permissions [Opens in a new window]

Extract

This paper deals with relation, cylindric and polyadic equality algebras. First of all it addresses a problem of B. Jónsson. He asked whether relation set algebras can be expanded by finitely many new operations in a “reasonable” way so that the class of these expansions would possess a finite equational base. The present paper gives a negative answer to this problem: Our main theorem states that whenever Rs+ is a class that consists of expansions of relation set algebras such that each operation of Rs+ is logical in Jónsson's sense, i.e., is the algebraic counterpart of some (derived) connective of first-order logic, then the equational theory of Rs+ has no finite axiom systems. Similar results are stated for the other classes mentioned above. As a corollary to this theorem we can solve a problem of Tarski and Givant [87], Namely, we claim that the valid formulas of certain languages cannot be axiomatized by a finite set of logical axiom schemes. At the same time we give a negative solution for a version of a problem of Henkin and Monk [74] (cf. also Monk [70] and Németi [89]).

Throughout we use the terminology, notation and results of Henkin, Monk, Tarski [71] and [85]. We also use results of Maddux [89a].

Notation. RA denotes the class of relation algebras, Rs denotes the class of relation set algebras and RRA is the class of representable relation algebras, i.e. the class of subdirect products of relation set algebras. The symbols RA, Rs and RRA abbreviate also the expressions relation algebra, relation set algebra and representable relation algebra, respectively.

For any class C of similar algebras EqC is the set of identities that hold in C, while Eq1C is the set of those identities in EqC that contain at most one variable symbol. (We note that Henkin et al. [85] uses the symbol EqC in another sense.)

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 57 , Issue 3 , September 1992 , pp. 832 - 843
Copyright
Copyright © Association for Symbolic Logic 1992

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

Andréka, H. [86], Simple proof for non-finitizability in algebraic logic (manuscript), Mathematical Institute, Budapest, pp. 6.Google Scholar
Andréka, H. [89], Complexity of equations valid in algebras of relations, preprint, Second Doctoral Dissertation, Hungarian Academy of Sciences, Budapest, 1991.Google Scholar
Andréka, H., Németi, I. and Sain, I. [84], Abstract model theoretic approach to algebraic logic, Mathematical Institute, Budapest, preprint, 1984.Google Scholar
Andréka, H. and Thompson, R. J. [88], A Stone type representation theorem for algebras of relations of higher rank, Transactions of the American Mathematical Society, vol. 309, pp. 671–682.Google Scholar
Baker, K. [77], Finite equational bases for finite algebras in a congruence-distributive equational class, Advances in Mathematics, vol. 24, pp. 207–243.CrossRefGoogle Scholar
Henkin, L. and Monk, J. D. [74], Cylindric algebras and related structures, Proceedings of the Tarski symposium, Proceedings of Symposia in Pure Mathematics, vol. 25, American Mathematical Society, Providence, Rhode Island, pp. 105–121.CrossRefGoogle Scholar
Henkin, L., Monk, J. D. and Tarski, A. [71], Cylindric algebras. Part I, North-Holland, Amsterdam.CrossRefGoogle Scholar
Henkin, L., Monk, J. D. and Tarski, A. [85], Cylindric algebras. Part II, North-Holland, Amsterdam.CrossRefGoogle Scholar
Johnson, J. S. [69], Nonfinitizability of classes of representable polyadic algebras, this Journal, vol. 34, pp. 344–352.Google Scholar
Johnson, J. S. [73], Axiom systems for logic with finitely many variables, this Journal, vol. 38, pp. 576–578.Google Scholar
Jónsson, B. [84], The theory of binary relations, Lecture notes, Montreal; published version, Algebraic logic (proceedings, Budapest, 1988), Colloquia Mathematica Societatis János Bolyai, vol. 54, North-Holland, Amsterdam, 1991, pp. 245–292.Google Scholar
Maddux, R. D. [89a], Nonfinite axiomatizability results for cylindric and relation algebras, this Journal, vol. 54, pp. 951–974.Google Scholar
Maddux, R. D. [89b],Finitary algebraic logic, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 35, pp. 321–332.CrossRefGoogle Scholar
Monk, J. D. [64], On representable relation algebras, Michigan Mathematical Journal, vol. 11, pp. 207–210.Google Scholar
Monk, J. D. [70], On an algebra of sets of finite sequences, this Journal, vol. 35, pp. 19–28.Google Scholar
Monk, J. D. [71], Provability with finitely many variables, Proceedings of the American Mathematical Society, vol. 27, pp. 353–358.CrossRefGoogle Scholar
Monk, J. D. [76], Mathematical logic, Springer-Verlag, Berlin.CrossRefGoogle Scholar
Németi, I. [87], On varieties of cylindric algebras with applications to logic, Annals of Pure and Applied Logic, vol. 36, pp. 235–277.CrossRefGoogle Scholar
Németi, I. [89], Algebraizations of quantifier logics: an introductory overview, Studia Logica (special issue on algebraic logic, in press); expanded version, preprint, Mathematical Institute, Hungarian Academy of Sciences, Budapest, 1991.Google Scholar
Sain, I. [87], On the search for a finitizable algebraization of first-order logic, Preprint, Mathematical Institute, Hungarian Academy of Sciences, Budapest, 1987.Google Scholar
Sain, I. [87a], Positive results related to the Jánsson and Tarski-Givant representation problem, Preprint, Mathematical Institute, Hungarian Academy of Sciences, Budapest, 1987.Google Scholar
Simon, A. [90], A finite schema completeness result for algebraic logic, Algebraic logic (proceedings, Budapest, 1988), Colloquia Mathematica Societatis János Bolyai, vol. 54, North-Holland, Amsterdam, 1991, pp. 665–670.Google Scholar
Tarski, A. [55], Contributions to the theory of models. III, Koninklijke Nederlandse Akademie van Wetenschappen, Proceedings, Series A, vol. 58 (= Indagationes Mathematical vol. 17), pp. 56–64.Google Scholar
Tarski, A. and Givant, S. [87], A formalization of set theory without variables, Colloquium Publications, vol. 41, American Mathematical Society, Providence, Rhode Island.Google Scholar
Venema, Y. [90], Cylindric modal logic, ITLI-prepublication series ML-91-01, University of Amsterdam, Amsterdam, 1991.Google Scholar
Venema, Y. [91], Many-dimensional modal logic, Doctoral Dissertation, University of Amsterdam, ITLI (Institute for Language, Logic, and Information), 1991. vii + 178 pp.Google Scholar