Given a semi-algebraic set $A$, show that $\operatorname{dist} (\cdot, A)$ is semi-algebraic

Question

We recall that a (real) semi-algebraic set is a subset $S$ of $\mathbb R^n$ defined by a finite sequence of polynomial equations (of the form $P(x_{1},...,x_{n})=0$ and inequalities (of the form $Q(x_{1},...,x_{n})>0$), or any finite union of such sets. A function $\mathbb R^n \to \mathbb R$ is called semi-algebraic if its graph is semi-algebraic.

Let $A \subset \mathbb R^n$, $A \neq \emptyset$, be a semialgebraic set. Then the function \begin{eqnarray*}\mathbb R^n &\to& \mathbb R,\;\\x &\mapsto& \operatorname{dist}(x, A) = \inf\left\{\|x − y\| \;; y \in A\right\}\end{eqnarray*} is semi-algebraic.

This is what I write for the moment: The graph of the function $\operatorname{dist}(\cdot,A)$ is $$\left\{(x,t)\in \mathbb{R}^{n+1}|\;t\ge 0\;\text{and}\;\forall y \in A,\;t^2\le \|x-y\|^2\;\text{and}\;\forall \epsilon\in\mathbb{R},\;\epsilon>0\Rightarrow \exists y\in A,\;t^2+\epsilon>\|x-y\|^2\right\}\;.$$ In the above formula, $A$ is a semi-algebraic set, $\|x-y\|^2$ is a polynomial function. I want to use the Tarski Seideimberg theorem which states: If $A$ is a semi-algebraic subset of $\mathbb{R}^{n+m}=\mathbb{R}^{n}\oplus \mathbb{R}^{m}$, then the projection $A'$ of $A$ in $\mathbb{R}^{m}$ is also semi-algebraic.

Answer 1

I know an answer that use the concepts of Model Theory.

If you consider the language of ordered field $L=\{+,\cdot, 0, 1, <\}$ you can observe that it is possible axiomatize the property of real closed fields (RCF) in this language; so an $L$-structure $A$ is a real closed field if and only if

$A\models RCF$

where $RCF$ is the Theory generated by the set of $L$-axioms of the real closed fields.

You can prove that this theory has the property of Quantifier Elimination, so for every $L$-formula $\psi$ there exists a $L$-formula $\mu$ without quantifier such that $\psi$ and $\mu$ are equivalent modulo $RCF$, so

$RCF \models \forall x(\psi \leftrightarrow \mu)$

The atomic formulas in the language $L$ are all of the type

$\psi(x_1,...,x_n): $ $ (p(x_1,...x_n)=0)$ or

$\mu(x_1,...,x_n): $ $ (p(x_1,...x_n)<0)$

for some $p(x_1,...,x_n)\in \mathbb{Z}[x_1,...,x_n]$

What is the relation with your problem?

A definible set $A$ of a $L$-Model $R$ of $RCF$ is a subset of $R^n$ such that there exists some $L$-formula $\psi(\vec{x},\vec{y})$ and $\vec{c}\in R^m$ such that

$A=\{\vec{x}\in R^n: R\models \psi(\vec{x},\vec{c})\}$

Than every semi-Algebraic set of $R$ it can be view as a definable set of $R$ with respect a disjoint normal formula $\psi(\vec{x},\vec{y})$ because a semi-Algebraic set is a boolean combination of sets that are locus of solution of polinomial equations of the type

$(p(x_1,...x_n)=0)$ or

$(p(x_1,...x_n)<0)$

for some $p\in R[x_1,...,x_n]$

By the qualifier elimination you have also that definable sets of $R$ are all semi-Algebraic set.

You can use this fondamental result because you can prove that the graph of the function is only a definible set.

$A$ is an Algebraic set so is a definible set and than there exists $\phi(\vec{x},\vec{y})$ and $\vec{c}\in R^m$ such that

$A=\{\vec{x}\in R^n: R\models \phi(\vec{x},\vec{c})\}$

But now you can see the graph of function $\Gamma$ as

$\Gamma=\{(\vec{x},y)\in R^{n+1}: R\models (y>0\land$

$ \forall \vec{z}(\phi(\vec{z}, \vec{c})\land y^2<\sum_{k=1}^n(x_k-z_k)^2)$

$\land \forall \epsilon (\epsilon>0)$

$\exists \vec{z} (\phi(\vec{z}, \vec{c})\land$

$ [ (y+\epsilon)^2>\sum_{k=1}^n(x_k-z_k)^2]\}$

and so it is definible and then it is a semi-Algebraic set.

Answer 2

Is there a more simple answer? this is what i whote for the moment: The graph of the function $dist(\cdot,A)$ is $$\left\{(x,t)\in \mathbb{R}^{n+1}|\;t\ge 0\;\text{and}\;\forall y \in A,\;t^2\le \|x-y\|^2\;\text{and}\;\forall \epsilon\in\mathbb{R},\;\epsilon>0\Rightarrow \exists y\in A,\;t^2+\epsilon>\|x-y\|^2\right\}\;.$$ In the above formula, $A$ is a semi-algebraic set, $\|x-y\|^2$ is a polynomial function. I want to use the Tarski Seideimberg theorem how states: If $A$ is a semi-algebraic subset of $\mathbb{R}^{n+m}=\mathbb{R}^{n}\oplus \mathbb{R}^{m}$, then the projection $A'$ of $A$ in $\mathbb{R}^{m}$ is also semi-algebraic.??