how to prove that a set is not semi-algebraic

Question

I've been reading about semi-algebraic sets and I've run into several examples of sets which have been proved to not be semi-algebraic. Examples include the integers, and the curves of the sine and exponential functions. I'm really curious about how you can prove that a set is not semi-algebraic. Does anyone know how its done?

Answer 1

Here is a property of semi-algebraic sets which you can use to show that many sets are not semi-algebraic (including your examples):

Let $M \subseteq \mathbb{R}^n$ be a semialgebraic set such that the zero polynomial is the only polynomial in $\mathbb{R}[x_1,\ldots,x_n]$ that vanishes identically on $M$. Then $M$ has nonempty interior.

Take for example the integers $M=\mathbb{Z} \subseteq \mathbb{R}$. Since every nonzero univariate polynomial has only finitely many zeros, only $0$ vanishes on $M$. But $M$ has empty interior, thus $M$ is not semialgebraic.

The same argument works for the sine: if you intersect the graph with the line $y=0$, you get infinitely many intersection points.

For the graph of the exponential function (which has also empty interior), you can also convince yourself that only the zero polynomial vanishes identically on it: Roughly, this follows from the fact that the exponential function grows faster than every polynomial.