MODNET - Preprint Number 1939

Preprint Number 1939

1939. Zhi-Wei Sun
Mixed quantifier prefixes over Diophantine equations with integer variables
E-mail:

Submission date: 9 March 2021

Abstract:

In this paper we study mixed quantifiers over Diophantine equations with integer variables. For example, we prove that ∀^2∃^4 over ℤ is undecidable, that is, there is no algorithm to determine for any P(x_1,...,x_6) in ℤ[x_1,...,x_6] whether

∀ x_1 ∀ x_2 ∃ x_3 ∃ x_4∃x_5 ∃x_6(P(x_1,...,x_6)=0),

where x_1,...,x_6 are integer variables. We also have some similar undecidable results with universal quantifies bounded, for example, ∃^2 ∀^2∃^2 over ℤ with ∀ bounded is undecidable. We conjecture that ∀^2∃^2 over ℤ is undecidable.

Mathematics Subject Classification: 03D35, 11U05, 03D25, 11D99

Keywords and phrases:

Full text arXiv 2103.08302: pdf, ps.