Is $(R;+,-,\times,<,=,\exp,0,1)$ decidable assuming Schanuel's conjecture? (note, there is $=$ too)

155 Views Asked by At

A. J. Wilkie, in Schanuel’s Conjecture and the Decidability of the Real Exponential Field, says that $(R;+,-,\times,<,\exp,0,1)$ is decidable. What happens if equality is included too? That is, is $(R;+,-,\times,<,=, \exp,0,1)$ decidable or not?

There has been an earlier thread where the same question was asked but without the exponential, and the conclusion was that $(R;+,-,\times,<,=,0,1)$ is decidable. The confusion seems to come, I think, from the Wikipedia article, which says that the Tarski-Seidenberg theorem ends up into problems with equalities.

1

There are 1 best solutions below

3
On BEST ANSWER

Equality is included. In first-order logic, equality is considered a logical primitive,$^*$ on the same level as quantifiers, Boolean operations, and variables. So the answer to your question is yes.


$^*$This was not always the case: historically, equality was not always considered a logical primitive (see e.g. the "lower predicate logic" of Robinson's book Complete theories). However, it has become so, and e.g. when we speak about the theory of a structure equality is always included unless explicitly stated otherwise (and similarly, "the theory" means "the first-order theory" unless explicitly stated otherwise).


Re: the role of equality in the Tarski-Seidenberg theorem, I think there might be a misunderstanding. Briefly, TS states:

The projection of a semialgebraic set is semialgebraic.

As wikipedia mentions, the natural analogue of TS for algebraic sets fails: there is a projection of an algebraic set which is not algebraic.

So: what's the difference between semialgebraic sets and algebraic sets? To quote from the wiki page, a semialgebraic set is one which is "a finite union of sets defined by a finite number of polynomial equations and inequalities." Note the word "equations" in there: that means that "$=$" is allowed in the definition of a semialgebraic set. An algebraic set, by contrast, is one which is a finite union of sets defined by polynomial equations (no inequalities allowed). So it's not that TS fails when equality is included, but rather when inequality is excluded.