Minh's Solution to Aiviet's Problem (arising from Tarski's metatheorem)

[Sonnet Nguyen <Sonnet.Nguyen@fuw.edu.pl>]

Dear academics,

With great pleasure I'd like to present a simple Minh's solution
to "Aiviet's problem" (the easy one of two problems I've presented in
Tarki's metatheorem topics, few days ago).  Everything is simple and
understood for non-experts, so let me repost it here.

This solution was given by young mathematician Nguyen Ngoc Minh, here is
his solution and comments to Tarski's metatheorem topics: 

------------------------------------------------------------------
On Tue, 8 Apr 1997, ngocminh nguyen wrote:

> NgocMinh has the following solution to one of your prolem.
> 
> Consider the field  Q  of rational numbers. The set 
>     A = { x in Q |  there exists y  such that  x =y^2}
> (= the set of all squares in Q) is defined using 1 quantifier.
> It is easy to see that A can not be defined by one condition
> on   x    without quantifier. (see a formal proof below).
>------------------------------------------------------------
> Comments: 
> 1. This is to say that  A  is not a quasi-algebraic set in  Q.
> If you believe in this, no proof needed!
> 2. Q  is  "formally real", but not "real closed", as required in the condition
> of Tarski's theorem. An ordered field is real closed  only if every
> positive number is a square. A moment of reflection leads to the above
> counterexample.
> 3. There is an algorithm (found in 1989) which eleminates quantifiers
> in Tarski's theorem. The computing time is super-exponential.
>------------------------------------------------------------- 
> Proof: Suppose  A = { x |  F(x)},
> where F(x) is a condition on  x. 
> By definition of (first order) conditions,   F(x) has  the
> following  forms
> p(x) > 0, p(x) >= 0, p(x) =0, p(x)/= 0, etc, where p(x) is a polynomial.
>  
> Consider things over the field R of real numbers. Let
>              B =  {  x  in  R | F(x) }.
> Then  A is the intersection of B and Q.                      
> 
> A  is a subset of B. Since  A  is dense in the set  C of positive
> real numbers, one sees that C is a subset of B. 
> A = [intersection of B and Q]  contains [the intersection of C and Q]    
> 
> The last one is the set of positive numbers in Q, which is bigger than A.
> This completes the proof.
----------------------------------------------------------------------------------