Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-29T19:19:38.479Z Has data issue: false hasContentIssue false
  • English
  • Français

Finite algebras of relations are representable on finite sets

Published online by Cambridge University Press:  12 March 2014

H. Andréka ,
I. Hodkinson  and
I. Németi
H. Andréka
Affiliation:
Mathematical Institute of Hungarian Academy of Sciences, PF. 127, 1364 Budapest, Hungary
I. Hodkinson
Affiliation:
Department of Computing, Imperial College, 180 Queen's Gate, London SW7 2BZ, UK
I. Németi
Affiliation:
Mathematical Institute of Hungarian Academy of Sciences, PF. 127, 1364 Budapest, Hungary
Get access Rights & Permissions [Opens in a new window]

Abstract

Using a combinatorial theorem of Herwig on extending partial isomorphisms of relational structures, we give a simple proof that certain classes of algebras, including Crs, polyadic Crs, and WA, have the ‘finite base property’ and have decidable universal theories, and that any finite algebra in each class is representable on a finite set.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 64 , Issue 1 , March 1999 , pp. 243 - 267
Copyright
Copyright © Association for Symbolic Logic 1999

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., van Benthem, J., and Németi, I., Modal languages and bounded fragments of predicate logic, Journal of Philosophical Logic, vol. 27 (1998), pp. 217–274.CrossRefGoogle Scholar
[2]Andréka, H., van Benthem, J., and Németi, I., Finite model property of bounded fragment of first-order logic and cylindric-relativized set algebras, Budapest, manuscript, 1995.Google Scholar
[3]Andréka, H., Goldblatt, R., and Németi, I., Relativised quantification: some canonical varieties of sequence-set algebras, this Journal, vol. 63 (1998), pp. 163–184.Google Scholar
[4]Henkin, L., Monk, J. D., and Tarski, A., Cylindric algebras, North-Holland, Amsterdam, 1971 and 1985 (Part I), 1985 (Part II).Google Scholar
[5]Henkin, L., Monk, J. D., Tarski, A., Andréka, H., and Németi, I., Cylindric set algebras. Lecture Notes in Mathematics, vol. 883, Springer-Verlag, Berlin, 1981.CrossRefGoogle Scholar
[6]Herwig, B., Extending partial isomorphisms on finite structures, Combinatorica, vol. 15 (1995), pp. 365–371.CrossRefGoogle Scholar
[7]Herwig, B., Extending partial isomorphisms for the small index property of many ω-categorical structures, Israel Journal of Mathematics, to appear.Google Scholar
[8]Herwig, B. and Lascar, D., Extending partial isomorphisms and the profinite topology on the free groups, in preparation, 1997.Google Scholar
[9]Hirsch, R., Hodkinson, I., Marx, M., Mikulás, S., and Reynolds, M., Mosaics and step-by-step, appendix to [25], to appear.Google Scholar
[10]Hrushovski, E., Extending partial isomorphisms of graphs, Combinatorica, vol. 12 (1992), pp. 411–416.CrossRefGoogle Scholar
[11]Jónsson, B., The theory of binary relations, Algebraic logic, Colloquia Mathematica Societatis János Bolyai, vol. 54, North-Holland, Amsterdam, 1991, pp. 245–292, proceedings of the 1988 Budapest conference.Google Scholar
[12]Jónsson, B. and Tarski, A., Boolean algebras with operators, I, American Journal of Mathematics, vol. 73 (1951), pp. 891–939.CrossRefGoogle Scholar
[13]Maddux, R., Some varieties containing relation algebras, Transactions of the American Mathematical Society, vol. 272 (1982), no. 2, pp. 501–526.CrossRefGoogle Scholar
[14]Marx, M. and Mikulás, S., Decidability of cylindric algebras of dimension two and first order logic with two variables, this Journal, to appear.Google Scholar
[15]Marx, M., Németi, I., and Sain, I., Conjugated Boolean algebras with operators, manuscript, in preparation.Google Scholar
[16]Mikulás, S., A note on expressing infinity in cylindric-relativized set algebras, in Proceedings of relational methods in computer science (RelMiCS), Hammamet, Tunisia, 1997.Google Scholar
[17]Monk, J. D., Remarks on the problems in the books Cylindric algebras, Part I and Part II and Cylindric set algebras, Algebraic logic, Colloquia Mathematica Societatis János Bolyai, vol. 54, North-Holland, Amsterdam, 1991, pp. 719–722.Google Scholar
[18]Monk, J. D., Lectures on cylindric set algebras, Algebraic methods in logic and in computer science (Rauszer, C., editor), Banach Center Publications, vol. 28, Institute of Mathematics, Polish Academy of Sciences, Warsaw, 1993, pp. 253–290, proceedings of the Banach semester, Fall 1991.Google Scholar
[19]Németi, I., Neither the variety of cylindric algebras nor the variety of representable cylindric algebras is generated by its finite members for dimensions greater than 2, Mathematical Institute, Budapest, preprint, 1984.Google Scholar
[20]Németi, I., Free algebras and decidability in algebraic logic, Doctoral dissertation with the Academy, Budapest, 1986.Google Scholar
[21]Németi, I., Decidability of relation algebras with weakened associativity, Proceedings of the American Mathematical Society, vol. 100 (1987), no. 2, pp. 340–344.CrossRefGoogle Scholar
[22]Németi, I., Decidable versions of first-order logic, Logic colloquium '92 (Csirmaz, L., Gabbay, D., and de Rijke, M., editors), CSLI Publications and FoLLI, 1995, pp. 177–241.Google Scholar
[23]Németi, I., Fine structure analysis of first order logic, Arrow logic and multi-modal logic (Marx, M., Pólos, L., and Masuch, M., editors), CSLI Publications, 1996, pp. 221–247.Google Scholar
[24]Simon, A., Nonrepresentable algebras of relations, Ph.D. dissertation, Budapest, 1997.Google Scholar
[25]Venema, Y. and Marx, M., A modal logic of relations, in Memorial volume for Elena Rasiowa (Orlowska, E., editor), Studia Logic Library, Kluwer, Dordrecht, to appear (Report no. IR-396, Faculteit der Wiskunde en Informatica, Vrije Universiteit Amsterdam, 1995).Google Scholar