[FOM] Standard Language of Euclid

[Grant Olney Passmore]

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

Best wishes,
Grant
--
Grant Olney Passmore
LFCS, University of Edinburgh