Undecidable Weak Theories of Polynomial Rings

Maxim Vsemirnov

We show that the theory Th(F_{q}[X_{1}, …, X_{n}], S_{1}, S_{X_{1}}, ⊥) is undecidable. Here F_{q} is a finite field of q elements, S_{1} and S_{X_{1}} are the natural analogues of the successor function (S_{1}(f) = f +1, S_{X_{1}}(f) = f +X_{1}) and ⊥ is a coprimeness predicate. The proof uses the truth of the analogues of the Erdös-Woods conjecture for polynomial rings over a finite field, which was obtained in [1].

[1] M. A. Vsemirnov, The Woods-Erdös conjecture for polynomial rings. Annals of Pure and Applied Logic (to appear).

Address: Steklov Institute of Mathematics at St.Petersburg, 27 Fontanka, St.Petersburg, 191011, Russia

E-mail: vsemir@pdmi.ras.ru