[FOM] Standard Language of Euclid
Grant Olney Passmore
grant at math.utexas.edu
Fri Oct 2 07:49:23 EDT 2009
> A related question: is it known whether the pure first-order theory of
> fields is undecidable?
Yes, this is Theorem 4.3 in the 1949 JSL version of Julia Robinson's
dissertation (see p113 in ``Definability and Decision Problems in
Arithmetic'' (JSL 14:98-114), or p22 in her Feferman edited Collected
Works). This follows rather easily (using Tarski's interpretability
machinery for undecidable theories) from her AEA definition of Z
within the language of rings over Q (note that amazingly, no ordering
relation is needed for her definition; see p107 in the article or p16
in her Collected Works).
The continuity of her work is astounding. Consider the following two
paragraphs, immediately following ``Theorem 4.3. The general
(arithmetical) theory of abstract fields is undecidable'' in the
article referenced above:
``It should be emphasized that the general theory of abstract fields
is by no means essentially undecidable, for extensions of this theory
are known which are decidable. In fact, as it was stated by Tarski,
the arithmetical theory of real closed fields and that of
algebraically closed fields (thus in particular the arithmetic of
algebraic numbers, real algebraic numbers, real numbers, and that of
complex numbers with + and *) are decidable. Hence many further
problems are suggested which are still open.
``In particular, we can ask whether the arithmetical theory of
various algebraic extensions of the field of rational numbers are
decidable. This applies to both finite and infinite extensions.''
In 1959 (``The undecidability of algebraic rings and fields.'' Proc.
Am. Math. Soc. 10:950-57), she answered the question posed above for
finite field extensions: She showed the natural numbers to be
definable in the ring of algebraic integers of any finite field
extension of the rationals, and then showed the ring of algebraic
integers to be definable in the finite field extension itself, thus
showing the arithmetical theory of any finite field extension of Q to
be undecidable. She returned to these results in 1962 and 1965 as
well (``On the decision problem for algebraic rings.'' Studies in
Mathematical Analysis and Related Topics; essays in honor of George
Polya (Stanford: Stanford University Press 297-304), and ``The
decision problem for fields.'' Theory of Models: Proceedings of the
1963 International Symposium at Berkeley (ed. by J.W. Addison et al,
Amsterdam: North-Holland):299-311, resp.).
Grant Olney Passmore
LFCS, University of Edinburgh
More information about the FOM