Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2025-01-03T12:52:14.186Z Has data issue: false hasContentIssue false
  • English
  • Français

The theory of all substructures of a structure: Characterisation and decision problems1

Published online by Cambridge University Press:  12 March 2014

Kenneth L. Manders
Kenneth L. Manders*
Affiliation:
Group in Logic and Methodology of Science, University of California, Berkeley, California 94720
*
Department of Philosophy and Mathematics, University of Pittsburg, Pittsburg, PA 15260
Get access Rights & Permissions [Opens in a new window]

Abstract

An infinitary characterisation of the first-order sentences true in all substructures of a structure M is used to obtain partial reduction of the decision problem for such sentences to that for Th(M). For the relational structure 〈R, ≤, + 〉 this gives a decision procedure for the ∃x∀y-part of the theory of all substructures, yet we show that the ∃x1x2∀y-part, and the entire theory, is Π11-complete. The theory of all ordered subsemigroups of 〈R, ≤, + 〉 is also shown Π11-complete. Applications in the philosophy of science are mentioned.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 44 , Issue 4 , December 1979 , pp. 583 - 598
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.)

Footnotes

1

This research is part of the author's Ph.D. thesis, Studies in applied logic, University of California, Berkeley, 1978.

References

REFERENCES

[1]Adams, E. W., Model-theoretic aspects of fundamental measurement theory, Proceedings of the Tarski Symposium, 1971, Proceedings of Symposia in Pure Mathematics, American Mathmatical Society, vol. 25 (1974), pp. 437–446.Google Scholar
[2]Berman, L., Precise bounds for Presburger arithmetic and the reals with addition, Proceedings of the 18th Annual IEEE Symposium, Foundations of Computer Science, 1977, pp. 95–99.Google Scholar
[3]Davis, M., Hilbert's 10th problem is unsolvable, American Mathematical Monthly, vol. 80 (1973), pp. 233–269.CrossRefGoogle Scholar
[4]Herbrand, J., investigations in proof theory (see [5, pp. 44–202]).Google Scholar
[5]Herbrand, J., Logical writings (Goldfarb, W., Editor), Harvard University Press, Cambridge, Massachusetts, 1971.CrossRefGoogle Scholar
[6]Krantz, D., Luce, D., Suppes, P. and Tversky, A., Foundations of measurement, vol. 1, Academic Press, New York, 1971.Google Scholar
[7]Manders, K., Necessary conditions for representability, Memorandum UCB/ERL/M77/3, Electronics Research Laboratory, University of California, Berkeley, 01 1977.Google Scholar
[8]Matijasevic, Y., Enumerable sets are Diophantine (translation), Soviet Mathematics, Doklady, vol. 11 (1970), pp. 249–259.Google Scholar
[9]McKenzie, R., Negative solution of the decision problem for sentences true in every sub-algebra of 〈N, +〉, this Journal, vol. 36 (1971), pp. 607–609.Google Scholar
[10]Nahrens, L., Measurement without Archimedean axioms, Philosophy of Science, vol. 41 (1974), pp. 379–393.Google Scholar
[11]Shoenfield, J., Mathematical logic, Addison-Wesley, Reading, Massachusetts, 1967.Google Scholar
[12]Scott, D. and Suppes, P., Foundational aspects of theories of measurement, this Journal, vol. 23 (1958), pp. 113–128.Google Scholar
[13]Tarski, A., Remarks on predicate logic with infinitely long expressions, Colloquium Mathematicum, vol. 6 (1958), pp. 171–176.CrossRefGoogle Scholar