[FOM] Is this known to be undecidable?

joeshipman@aol.com joeshipman at aol.com
Sun Dec 31 01:57:05 EST 2006

Given: a multivariable polynomial p(x1,x2,...,x_n,y) and a univariate 
polynomial q(z), in the language of fields.

Assume the axioms for fields, and the axioms for characteristic 0 if 

Is it decidable whether

Forall (x1,...,xn) Thereexists y p(x1,...,x_n,y)=0


Thereexists z q(z)=0


In other words, if I can solve all equations of type p, can I solve 
equation q?

(If it is undecidable when I generalize to allow more existentially 
quantified variables in p and q, that would also be worth knowing, but 
I am mainly interested in the specific case of only one existentially 
quantified variable, which seems quite difficult enough!)

-- JS

Check out the new AOL.  Most comprehensive set of free safety and 
security tools, free access to millions of high-quality videos from 
across the web, free AOL Mail and more.

More information about the FOM mailing list