[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
necessary.
Is it decidable whether
Forall (x1,...,xn) Thereexists y p(x1,...,x_n,y)=0
implies
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