Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-05T16:20:50.625Z Has data issue: false hasContentIssue false
  • English
  • Français

Decidable fragments of field theories

Published online by Cambridge University Press:  12 March 2014

Shih-Ping Tung
Shih-Ping Tung*
Affiliation:
Department of Mathematics, Chung-Yuan Christian University, Chung Li, Taiwan 320-23, Republic of China
Get access Rights & Permissions [Opens in a new window]

Abstract

We say φ is an ∀∃ sentence if and only if φ is logically equivalent to a sentence of the form ∀x∃yψ(x, y), where ψ(x, y) is a quantifier-free formula containing no variables except x and y. In this paper we show that there are algorithms to decide whether or not a given ∀∃ sentence is true in (1) an algebraic number field K, (2) a purely transcendental extension of an algebraic number field K, (3) every field with characteristic 0, (4) every algebraic number field, (5) every cyclic (abelian, radical) extension field over Q, and (6) every field.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 55 , Issue 3 , September 1990 , pp. 1007 - 1018
Copyright
Copyright © Association for Symbolic Logic 1990

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]Ax, J., The elementary theory of finite fields, Annals of Mathematics, ser. 2, vol. 88 (1968), pp. 239–271.CrossRefGoogle Scholar
[2]Davis, M., Matijasevič, Y., and Robinson, J., Hubert's tenth problem. Diophantine equations: positive aspects of a negative solution, Mathematical developments arising from Hilbert problems, Proceedings of Symposia in Pure Mathematics, vol. 28, American Mathematical Society, Providence, Rhode Island, 1976, pp. 323–378.CrossRefGoogle Scholar
[3]Chistov, A. L., Polynomial factoring algorithm for polynomials and finding components of varieties in subexponential time, Journal of Soviet Mathematics, vol. 34 (1986), pp. 1838–1882.CrossRefGoogle Scholar
[4]van den Dries, L., Some model theory and number theory for models of weak systems of arithmetic, Model theory of algebra and arithmetic (proceedings, Karpacz, 1979), Lecture Notes in Mathematics, vol. 834, Springer-Verlag, Berlin, 1980, pp. 346–362.CrossRefGoogle Scholar
[5]Enderton, H. B., A mathematical introduction to logic, Academic Press, New York, 1972.Google Scholar
[6]Hungerford, T. W., Algebra, Springer-Verlag, Berlin, 1980.CrossRefGoogle Scholar
[7]Landau, S., Factoring polynomials over algebraic number fields, SIAM Journal on Computing, vol. 14 (1985), pp. 184–195.CrossRefGoogle Scholar
[8]Lang, S., Algebra, Addison-Wesley, Reading, Massachusetts, 1965.Google Scholar
[9]Robinson, J., Definability and decision problems in arithmetic, this Journal, vol. 14 (1949), pp. 98–114.Google Scholar
[10]Robinson, J., The undecidability of algebraic rings and fields, Proceedings of the American Mathematical Society, vol. 10 (1959), pp. 950–957.CrossRefGoogle Scholar
[11]Robinson, R. M., Arithmetical definitions in the ring of integers, Proceedings of the American Mathematical Society, vol. 2 (1951), pp. 279–284.CrossRefGoogle Scholar
[12]Robinson, R. M., The undecidability of pure transcendental extensions of real fields, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 10 (1964), pp. 275–282.CrossRefGoogle Scholar
[13]Schinzel, A., Diophantine equations with parameters, Journées arithmétiques 1980 (lectures, Exeter, 1980; Armitage, J. V., editor), London Mathematical Society Lecture Note Series, vol. 56, Cambridge University Press, Cambridge, 1982, pp. 211–217.Google Scholar
[14]Schinzel, A., Selected topics on polynomials, University of Michigan Press, Ann Arbor, Michigan, 1982.CrossRefGoogle Scholar
[15]Shepherdson, J. C., A non-standard model for a free-variable fragment of number theory, Bulletin de l'Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques, vol. 12 (1964), pp. 79–86.Google Scholar
[16]Sprindzhuk, V. G., Achievements and problems in Diophantine approximation theory, Uspekhi Matematicheskikh Nauk, vol. 35 (1980), no. 4 (214), pp. 3–68; English translation, Russian Mathematical Surveys, vol. 35 (1980), no. 4, pp. 1–80.Google Scholar
[17]Tung, S. P., On weak number theories, Japanese Journal of Mathematics, vol. 11 (1985), pp. 203–232.Google Scholar
[18]Tung, S. P., Provability and decidability of arithmetical universal-existential sentences, Bulletin of the London Mathematical Society, vol. 18 (1986), pp. 241–247.CrossRefGoogle Scholar
[19]van der Waerden, B. L., Modern algebra. Vol. 1, Frederick Ungar, New York, 1949.Google Scholar