Abstract
We address the general problem of determining the validity of
boolean combinations of equalities and inequalities between
real-valued expressions. In particular, we consider methods of
establishing such assertions using only restricted forms of
distributivity. At the same time, we explore ways in which "local"
decision or heuristic procedures for fragments of the theory of the
reals can be amalgamated into global ones.
Let Tadd[Q] be the first-order theory of the real numbers in the
language of ordered groups, with negation, a constant 1, and
function symbols for multiplication by rational constants. Let Tmult[Q] be the analogous theory for the multiplicative
structure, and let T[Q] be the union of the two. We show that although T[Q] is undecidable, the universal
fragment of T[Q] is decidable. We also show that terms of T[Q]can fruitfully be put in a normal form. We prove analogous results for
theories in which Q is replaced, more generally, by suitable
subfields F of the reals. Finally, we consider practical
methods of establishing quantifier-free validities that
approximate our (impractical) decidability results.
|