Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-16T07:27:41.976Z Has data issue: false hasContentIssue false
  • English
  • Français

Amalgamation in relation algebras

Published online by Cambridge University Press:  12 March 2014

Maarten Marx
Maarten Marx*
Affiliation:
Department of Computing, Imperial College, 180 Queen's Gate, SW7 2BZ London, UK, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

We investigate amalgamation properties of relational type algebras. Besides purely algebraic interest, amalgamation in a class of algebras is important because it leads to interpolation results for the logic corresponding to that class (cf. [15]). The multi-modal logic corresponding to relational type algebras became known under the name of “arrow logic” (cf. [18, 17]), and has been studied rather extensively lately (cf. [10]). Our research was inspired by the following result of Andréka et al. [1].

Let K be a class of relational type algebras such that

(i) composition is associative,

(ii) K is a class of boolean algebras with operators, and

(iii) K contains the representable relation algebras RRA.

Then the equational theory of K is undecidable.

On the other hand, there are several classes of relational type algebras (e.g., NA, WA denned below) whose equational (even universal) theories are decidable (cf. [13]). Composition is not associative in these classes. Theorem 5 indicates that also with respect to amalgamation (a very weak form of) associativity forms a borderline. We first recall the relevant definitions.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 63 , Issue 2 , June 1998 , pp. 479 - 484
Copyright
Copyright © Association for Symbolic Logic 1998

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., Kurucz, Á., Németi, I., Sain, I., and Simon, A., Decidable and undecidable modal logics with a binary modality, Journal of Logic, Language and Information, vol. 4 (1995), pp. 191–206.Google Scholar
[2] Comer, S., Classes without the amalgamation property, Pacific Journal of Mathematics, vol. 28 (1969), pp. 309–318.Google Scholar
[3] Henkin, L., Monk, J. D., and Tarski, A., Cylindric algebras, Parts I and II, North-Holland, 1971 and 1985.Google Scholar
[4] Kiss, E. W., Márki, L., Prőhle, P., and Tholen, W., Categorical algebraic properties: Compendium on amalgamation, congruence extension, epimorphisms, residual smallness and injectivity, Stadia Scientiarum Mathematicarum Hungarica, vol. 18 (1983).Google Scholar
[5] Madarász, J., Definability and epimorphisms in relation algebras, Mathematics Institute of Budapest, manuscript, 1996.Google Scholar
[6] Maddux, R., Topics in relation algebras, Ph.D. thesis, University of California, Berkeley, California, 1978.Google Scholar
[7] Maddux, R., Some varieties containing relation algebras, Transactions of the American Mathematical Society, vol. 272 (1982), pp. 501–526.10.1090/S0002-9947-1982-0662049-7Google Scholar
[8] Maksimova, L., Amalgamation and interpolation in normal modal logics, Stadia Logica, vol. L (1991), no. 3/4, pp. 457–471.Google Scholar
[9] Marx, M., Algebraic relativization and arrow logic, Ph.D. thesis, Institute for Logic, Language and Computation, University of Amsterdam, 1995, ILLC Dissertation Series 1995–3.Google Scholar
[10] Marx, M., Pólos, L., and Masuch, M. (editors), Arrow logic and multimodal logics, Studies in Logic, Language and Information, CSLI Publications, Stanford, 1996.Google Scholar
[11] McKenzie, R., The representation of relation algebras, Ph.D. thesis , University of Colorado, Boulder, 1966.Google Scholar
[12] Németi, I., Cylindric-relativised set algebras have strong amalgamation, this Journal, vol. 50 (1985), no. 3, pp. 689–700.Google Scholar
[13] Németi, I., Decidability of relation algebras with weakened associativity, Proceedings of the American Mathematical Society, vol. 100 (1987), no. 2, pp. 340–344.Google Scholar
[14] Németi, I. and Simon, A., Relation algebras from cylindric andpolyadic algebras, Logic Journal of the IGPL, vol. 5 (1997), no. 4, pp. 575–588.10.1093/jigpal/5.4.575Google Scholar
[15] Pigozzi, D., Amalgamation, congruence extension and interpolation properties in algebras, Algebra Universalis, vol. 1 (1972), pp. 269–349.Google Scholar
[16] Sain, I., Beth's and Craig's properties via epimorphisms and amalgamation in algebraic logic, Algebraic logic and universal algebra in computer science, vol. 425, 1990, pp. 209–226.Google Scholar
[17] van Benthem, J., Language in action (Categories, lambdas and dynamic logic), Studies in Logic, vol. 130, North-Holland, 1991.Google Scholar
[18] Venema, Y., Many–dimensional modal logic, Ph.D. thesis , Institute for Logic, Language and Computation, Universiteit van Amsterdam, 1992.Google Scholar