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

Nonfinite axiomatizability results for cylindric and relation algebras

Published online by Cambridge University Press:  12 March 2014

Roger D. Maddux
Roger D. Maddux*
Affiliation:
Department of Mathematics, Iowa State University, AMES, Iowa 50011
Get access Rights & Permissions [Opens in a new window]

Abstract

The set of equations which use only one variable and hold in all representable relation algebras cannot be derived from any finite set of equations true in all representable relation algebras. Similar results hold for cylindric algebras and for logic with finitely many variables. The main tools are a construction of nonrepresentable one-generated relation algebras, a method for obtaining cylindric algebras from relation algebras, and the use of relation algebras in defining algebraic semantics for first-order logic.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 54 , Issue 3 , September 1989 , pp. 951 - 974
Copyright
Copyright © Association for Symbolic Logic 1989

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

[Be73]Berge, C., Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.Google Scholar
[Bi87]Biró, B., Nonfinite axiomatizability results in algebraic logic, preprint, 1987.Google Scholar
[GG55]Greenwood, R. and Gleason, A., Combinatorial relations and chromatic graphs, Canadian Journal of Mathematics, vol. 7 (1955), pp. 1–7.CrossRefGoogle Scholar
[H73]Henkin, L., Internal semantics and algebraic logic, Truth, syntax, and modality (Leblanc, H., editor), North-Holland, Amsterdam, 1973, pp. 111–127.CrossRefGoogle Scholar
[HMT71]Henkin, L., Monk, J. D., and Tarski, A., Cylindric Algebras. Part I, North-Holland, Amsterdam, 1971.Google Scholar
[HMT85]Henkin, L., Monk, J. D., and Tarski, A., Cylindric Algebras. Part II, North-Holland, Amsterdam, 1985.Google Scholar
[L50]Lyndon, R. C., The representation of relational algebras, Annals of Mathematics, ser. 2, vol. 51 (1950), pp. 707–729.Google Scholar
[Ma78]Maddux, R. D., Topics in relation algebras, Doctoral dissertation, University of California, Berkeley, California, 1978.Google Scholar
[Ma82]Maddux, R. D., Some varieties containing relation algebras, Transactions of the American Mathematical Society, vol. 272 (1982), pp. 501–526.CrossRefGoogle Scholar
[Ma83]Maddux, R. D., A sequent calculus for relation algebras, Annals of Pure and Applied Logic, vol. 25 (1983), pp. 73–101.CrossRefGoogle Scholar
[Ma85]Maddux, R. D., Finite integral relation algebras, Universal algebra and lattice theory, Lecture Notes in Mathematics, vol. 1149, Springer-Verlag, Berlin, 1985, pp. 175–197.CrossRefGoogle Scholar
[Mo64]Monk, J. D., On representable relation algebras, Michigan Mathematical Journal, vol. 11 (1964), pp. 207–210.CrossRefGoogle Scholar
[Mo69]Maddux, R. D., Nonfinitizability of classes of representable cylindric algebras, this Journal, vol. 34 (1969), pp. 331–343.Google Scholar
[TG87]Tarski, A. and Givant, S. R., A formalization of set theory without variables, Colloquium Publications, vol. 41, American Mathematical Society, Providence, Rhode Island, 1987.Google Scholar