Annals of Pure and Applied Logic 163 (12):1765-1802 (2012)

Robert Solovay
University of California, Berkeley
We carry out a systematic study of decidability for theories of real vector spaces, inner product spaces, and Hilbert spaces and of normed spaces, Banach spaces and metric spaces, all formalized using a 2-sorted first-order language. The theories for list turn out to be decidable while the theories for list are not even arithmetical: the theory of 2-dimensional Banach spaces, for example, has the same many-one degree as the set of truths of second-order arithmetic.We find that the purely universal and purely existential fragments of the theory of normed spaces are decidable, as is the ∀∃ fragment of the theory of metric spaces. These results are sharp of their type: reductions of Hilbertʼs 10th problem show that the ∃∀ fragments for metric and normed spaces and the ∀∃ fragment for normed spaces are all undecidable
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2012.04.003
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,316
Through your library

References found in this work BETA

Undecidable Theories.Alfred Tarski - 1953 - Amsterdam: North-Holland Pub. Co..
Subsystems of Second-Order Arithmetic.Stephen G. Simpson - 2004 - Studia Logica 77 (1):129-129.
Model Theory.Wilfrid Hodges - 2008 - Stanford Encyclopedia of Philosophy.

View all 20 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

The Completeness of Elementary Algebra and Geometry.Alfred Tarski - 1967 - Paris: Centre National De La Recherche Scientifique, Institut Blaise Pascal.
Medieval Arabic Algebra as an Artificial Language.Jeffrey A. Oaks - 2007 - Journal of Indian Philosophy 35 (5-6):543-575.
Newton and Hamilton: In Defense of Truth in Algebra.Janet Folina - 2012 - Southern Journal of Philosophy 50 (3):504-527.
Why Solovay Real Produces Cohen Real.Janusz Pawlikowski - 1986 - Journal of Symbolic Logic 51 (4):957-968.
Standards of Equality and Hume's View of Geometry.Emil Badici - 2011 - Pacific Philosophical Quarterly 92 (4):448-467.


Added to PP index

Total views
17 ( #639,009 of 2,519,274 )

Recent downloads (6 months)
1 ( #407,861 of 2,519,274 )

How can I increase my downloads?


My notes