Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-20T04:39:38.615Z Has data issue: false hasContentIssue false
  • English
  • Français

Undecidable properties of finite sets of equations

Published online by Cambridge University Press:  12 March 2014

George F. McNulty
George F. McNulty*
Affiliation:
University of South Carolina, Columbia, South Carolina 29208
Get access Rights & Permissions [Opens in a new window]

Extract

Though equations are among the simplest sentences available in a first order language, many of the most familiar notions from algebra can be expressed by sets of equations. It is the task of this paper to expose techniques and theorems that can be used to establish that many collections of finite sets of equations characterized by common algebraic or logical properties fail to be recursive. The following theorem is typical.

Theorem. In a language provided with an operation symbol of rank at least two, the collection of finite irredundant sets of equations is not recursive.

Theorems of this kind are part of a pattern of research into decision problems in equational logic. This pattern finds its origins in the works of Markov [8] and Post [20] and in Tarski's development of the theory of relation algebras; see Chin [1], Chin and Tarski [2], and Tarski [23]. The papers of Mal′cev [7] and Perkins [16] are more directly connected with the present paper, which includes generalization of much of Perkins' work as well as extensions of a theorem of D. Smith [22]. V. L. Murskii [14] contains some of the results below discovered independently. Not all known results concerning undecidable properties of finite sets of equations seem to be susceptible to the methods presented here. R. McKenzie, for example, shows in [9] that for a language with an operation symbol of rank at least two, the collection of finite sets of equations with nontrivial finite models is not recursive. D. Pigozzi has extended and elaborated the techniques of this paper in [17], [18], and [19] to obtain new results concerning undecidable properties, particularly those of algebraic character.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 41 , Issue 3 , September 1976 , pp. 589 - 604
Copyright
Copyright © Association for Symbolic Logic 1976

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.)

Footnotes

1

I would like to thank the referee for his patient reading of an earlier version of this paper and for pointing out several misstatements in that version.

References

REFERENCES

[0] Chang, C. C. and Keisler, H. J., Model theory, North-Holland, Amsterdam, 1973.Google Scholar
[1] Chin, L., Distributive and modular laws in relation algebras, Ph.D. Thesis, University of California at Berkeley, 1948.Google Scholar
[2] Chin, L., and Tarski, A., Distributive and modular laws in the arithmetic of relation algebras, University of California Publications in Mathematics, new series, vol. 1, no. 9 (1951), pp. 341–383.Google Scholar
[3] Gratzer, G., Universal algebra, Van Nostrand, Princeton, New Jersey, 1968.Google Scholar
[4] Henkin, L., Monk, J. D. and Tarski, A., Cylindric algebras. Part I, North-Holland, Amsterdam, 1971.Google Scholar
[5] Mal'cev, A. I., The metamathematics of algebraic systems, collected papers: 1936–1967, (translated and edited by Wells, B. F. III), North-Holland, Amsterdam, 1971.Google Scholar
[6] Mal'cev, A. I., Model'nye sootvetstvija, Izvestija Akademii Nauk SSSR, Serija Matematiceskaja, vol. 23 (1959), pp. 313–336; translated in Chapter XI in [3].Google Scholar
[7] Mal'cev, A. I., Toždestvennye soolnošenija na mnogoobrazijah kvazigrupp, Matematiceskii Sbornik, Novaja Serija, vol. 69 (111) (1966), pp. 3–12; translated in Chapter XXIX in [3]; American Mathematical Society Translations (2), vol. 82 (1969), pp. 225–235 (translated by K. A. Hirsch).Google Scholar
[8] Markov, A. A., On the impossibility of certain algorithms in the theory of associative systems, (Russian), Doklady Akademii Nauk SSSR, Novaja Serija, vol. 55 (1947), pp. 587–590; translated in Comptes rendus de l'Académie des Sciences de l'URSS , vol. 55 (1947), pp. 583–586.Google Scholar
[9] McKenzie, R., On spectra and the negative solution of the decision problem for identities having a finite nontrivial model, this Journal, vol. 40 (1975), pp. 186–196.Google Scholar
[10] McNulty, G., On algebras whose equational theories are essentially base-undecidable, Notices of the American Mathematical Society, vol. 17 (1970), p. 657.Google Scholar
[11] McNulty, G., Undecidable properties of finite sets of equations, Notices of the American Mathematical Society, vol. 19 (1972), p. A–328.Google Scholar
[12] McNulty, G., Undecidable properties of finite sets of equations, II, Notices of the American Mathematical Society, vol. 22 (1975), p. A–35.Google Scholar
[13] McNulty, G., The decision problem for equational bases of algebras, Annals of Mathematical Logic , to appear.Google Scholar
[14] Murskiǐ, V. L., Nondiscernible properties of finite systems of identity relations, (Russian), Doklady Akademii Nauk SSSR, vol. 196 (1971), pp. 520–522. Translated in Soviet Mathematics Doklady , vol. 12 (1971), pp. 183–186.Google Scholar
[15] Perkins, P., Decision problems for equational theories of semigroups and general algebras, Ph.D. Thesis, University of California at Berkeley, 1966.Google Scholar
[16] Perkins, P., Unsolvable problems for equational theories, Notre Dame Journal of Formal Logic, vol. 8 (1967), pp. 175–185.CrossRefGoogle Scholar
[17] Pigozzi, D., The base-undecidability of various algebraic properties of equational theories, (to appear).Google Scholar
[18] Pigozzi, D., Universal equational theories and varieties of algebras, (to appear).Google Scholar
[19] Pigozzi, D., The universality of the variety of quasigroups, (to appear).Google Scholar
[20] Post, E., Recursive unsolvability of a problem of Thue, this Journal, vol. 12 (1947), pp. 1–11.Google Scholar
[21] Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[22] Smith, D., Non-recursiveness of the set of finite sets of equations whose theories are one based, Notre Dame Journal of Formal Logic, vol. 13 (1972), pp. 135–138.CrossRefGoogle Scholar
[23] Tarski, A., An undecidable system of sentential calculus, this Journal, vol. 18 (1953), p. 189.Google Scholar
[24] Tarski, A., Equational logic, Contributions to mathematical logic (edited by Schutte, K.), North-Holland, Amsterdam, 1968, pp. 275–288.Google Scholar