Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-25T03:43:40.600Z Has data issue: false hasContentIssue false
  • English
  • Français

Decision problems concerning properties of finite sets of equations

Published online by Cambridge University Press:  12 March 2014

Cornelia Kalfa
Cornelia Kalfa*
Affiliation:
Department of Mathematics, Aristotle University, Thessaloniki, Greece
Get access Rights & Permissions [Opens in a new window]

Extract

In this paper a general method of proving the undecidability of a property P, for finite sets Σ of equations of a countable algebraic language, is presented. The method is subsequently applied to establish the undecidability of the following properties, in almost all nontrivial such languages:

  1. 1. The first-order theory generated by the infinite models of Σ is complete.

  2. 2. The first-order theory generated by the infinite models of Σ is model-complete.

  3. 3. Σ has the joint-embedding property.

  4. 4. The first-order theory generated by the models of Σ with more than one element has the joint-embedding property.

  5. 5. The first-order theory generated by the infinite models of Σ has the joint-embedding property.

A countable algebraic language ℒ is a first-order language with equality, with countably many nonlogical symbols but without relation symbols, ℒ is trivial if it has at most one operation symbol, and this is of rank one. Otherwise, ℒ is nontrivial. An ℒ-equation is a sentence of the form , where φ and ψ are ℒ-terms. The set of ℒ-equations is denoted by Eqℒ. A set of sentences is said to have the joint-embedding property if any two models of it are embeddable in a third model of it.

If P is a property of sets of ℒ-equations, the decision problem of P for finite sets of ℒ-equations is the problem of the existence or not of an algorithm for deciding whether, given a finite Σ ⊂ Eqℒ, Σ has P or not.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 51 , Issue 1 , March 1986 , pp. 79 - 87
Copyright
Copyright © Association for Symbolic Logic 1986

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

REFERENCE

[1]Burris, S., Models in equational theories of unary algebras, Algebra Universalis, vol. 1 (1972), pp. 386–392.CrossRefGoogle Scholar
[2]Chang, C. C. and Keisler, H. J., Model theory, North-Holland, Amsterdam, 1973.Google Scholar
[3]Kalfa, C., Undecidable properties of finite sets of equations, Notices of the American Mathematical Society, vol. 26 (1979), p. A-425 (abstract 79T-A169).Google Scholar
[4]Kalfa, C., Decision problems concerning sets of equations, Ph.D. thesis, Bedford College, University of London, London, 1980.Google Scholar
[5]Kalfa, C., Some undecidability results in strong algebraic languages, this Journal, vol. 49 (1984), pp. 951–954.Google Scholar
[6]Kalfa, C., Decidable properties of finite sets of equations in trivial languages, this Journal, vol. 49 (1984), pp. 1333–1338.Google Scholar
[7]Mal'cev, A. I., Identical relations in varieties of quasi-groups, The metamathematics of algebraic systems: Collected papers 1936–1967 (Wells, B. F. III, translator and editor), North-Holland, Amsterdam, 1971, pp. 384–395.Google Scholar
[8]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
[9]McNulty, G. F., Undecidable properties of finite sets of equations, this Journal, vol. 41 (1976), pp. 589–604.Google Scholar
[10]McNulty, G. F., The decision problem for equational bases of algebras, Annals of Mathematical Logic, vol. 11 (1976), pp. 193–256.CrossRefGoogle Scholar
[11]Murskiǐ, V. L., Nondiscernible properties of finite systems of identity relations, Doklady Akadémii Nauk SSSR, vol. 196 (1971), pp. 520–522; English translation in Soviet Mathematics—Doklady, vol. 12 (1971), pp. 183–186.Google Scholar
[12]Perkins, P., Unsolvable problems for equational theories, Notre Dame Journal of Formal Logic, vol. 8 (1967), pp. 175–185.Google Scholar
[13]Pigozzi, D., Base-undecidable properties of universal varieties, Algebra Universalis, vol. 6 (1976), pp. 193–223.Google Scholar
[14]Tarski, A., Equational logic and equational theories of algebras, Contributions to mathematical logic (Proceedings of the logic colloquium, Hannover, 1966; Schmidt, H. A., Schütte, K. and Thiele, H. J., editors), North-Holland, Amsterdam, 1968, pp. 275–288.Google Scholar