Some new results on decidability for elementary algebra and geometry

We carry out a systematic study of decidability for theories (a) of real vector spaces, inner product spaces, and Hilbert spaces and (b) of normed spaces, Banach spaces and metric spaces, all formalized using a 2-sorted first-order language. The theories for list (a) turn out to be decidable while t...

Full description

Saved in:
Bibliographic Details
Published in:Annals of pure and applied logic 2012-12, Vol.163 (12), p.1765-1802
Main Authors: Solovay, Robert M., Arthan, R.D., Harrison, John
Format: Article
Language:English
Subjects:
Banach spaces
Decidability
Hilbert spaces
Undecidability
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We carry out a systematic study of decidability for theories (a) of real vector spaces, inner product spaces, and Hilbert spaces and (b) of normed spaces, Banach spaces and metric spaces, all formalized using a 2-sorted first-order language. The theories for list (a) turn out to be decidable while the theories for list (b) 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.
ISSN:0168-0072
DOI:10.1016/j.apal.2012.04.003