4
$\begingroup$

We know that the complex field has quantifier elimination. This is usually in reference to the signature $(+,·,-,0,1)$. My question is, does it also have quantifier elimination with reference to the signature $(+,·)$?

$\endgroup$
5
$\begingroup$

Yes, it does. To prove this, it suffices to check that every atomic quantifier-free formula in the signature $(+,\cdot,-,0,1)$ is equivalent to one in the signature $(+,\cdot)$. Such an atomic quantifier-free formula is just a statement that two terms are equal, so by subtracting the terms we see that it is equivalent to the statement $$p(x_1,\dots,x_n)=0.$$ for some polynomial $p$ with coefficients with $\mathbb{Z}$, where $x_1,\dots,x_n$ are the free variables.

Putting all the terms with positive coefficients on one side and all the terms with negative coefficients on the other side, we can rewrite this in the form $$q(x_1,\dots,x_n)=r(x_1,\dots,x_n)$$ where $q$ and $r$ now have coefficients in $\mathbb{N}$. As long as $q$ and $r$ are not $0$ and have no constant terms, this means we can write them using only addition and multiplication. If $q$ is $0$, we can rewrite our equation as $r=r+r$, and similarly if $r$ is $0$. If both $q$ and $r$ are $0$, our equation is equivalent to $\top$.

The only remaining issue is if $q$ or $r$ has a constant term. To fix this, we can consider the equation $$x_1q(x_1,\dots,x_n)=x_1r(x_1,\dots,x_n)$$ which has no constant terms and is equivalent to our original equation as long as $x_1+x_1\neq x_1$ (i.e., $x_1\neq 0$). So by taking Boolean combinations, it suffices to also be able to express the formula $$q(0,x_2,\dots,x_n)=r(0,x_2,\dots,x_n).$$ But this formula has one fewer variable than we started with, so we can handle it by induction on the number of variables. (In the base case where there are no variables, every formula is equivalent to $\top$ or $\bot$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.