Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-25T21:32:42.508Z Has data issue: false hasContentIssue false
  • English
  • Français

An undecidability result for relation algebras

Published online by Cambridge University Press:  12 March 2014

Wolfgang Schönfeld
Wolfgang Schönfeld*
Affiliation:
Institut Für Informatik, Universität Stuttgart, Stuttgart, Federal Republic of Germany
Get access Rights & Permissions [Opens in a new window]

Extract

The elementary calculus of binary relations as developed by Tarski in [5] may be thought of as a certain part of the first-order predicate calculus. Though less expressive, its theory (i.e. the set of its valid sentences) was shown to be undecidable by Tarski in [6]. Translated into algebraic logic this means that the equational theory of the class of relation algebras is undecidable. Similarly it can be proved that the same holds for the (sub-) class of proper relation algebras.

The idea in Tarski's proof is to describe a pairing function by which any quantifier prefix may be contracted. In this note we apply a different method to treat the case of finite structures. We prove the

Theorem. The equational theory of the class of finite proper relation algebras is undecidable.

This result was announced in [4]. The main tool is representing the graph of primitive recursive functions via the cardinalities in finite simple models of equations.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 44 , Issue 1 , March 1979 , pp. 111 - 115
Copyright
Copyright © Association for Symbolic Logic 1979

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]Brainerd, W. S. and Landweber, L. H., Theory of computation, Wiley & Sons, New York, 1974, p. 50.Google Scholar
[2]Chin, L. H. and Tarski, A., Distributive and modular laws in the arithmetic of relation algebras, University of California Publications in Mathematics, vol. 1(1951), pp. 341–384.Google Scholar
[3]Jonsson, B. and Tarski, A., Boolean algebras with operators. II, American Journal of Mathematics, vol. 74(1952), pp. 127–162.CrossRefGoogle Scholar
[4]Schönfeld, W., Equations in finite proper relation algebras, Notices of the American Mathematical Society, vol. 24(1977), p. A–252.Google Scholar
[5]Tarski, A., On the calculus of relations, this Journal, vol. 6(1941), pp. 73–89.Google Scholar
[6]Tarski, A., Some metalogical results concerning the calculus of relations, this Journal, vol. 18(1953), pp. 188–189.Google Scholar
[7]Trakhtenbrot, B. A., Impossibility of an algorithm for the decision problem for finite classes, Doklady Akademii Nauk SSSR, vol. 70(1950), pp. 569–572.Google Scholar