Skolem functions of arithmetical sentences. (Q1427862): Difference between revisions

This paper is a continuation of the author's previous paper [Inf. Comput. 120, 149--154 (1995; Zbl 0846.11065)]. Let \(\psi(x,y)\) be an arithmetical formula. Suppose that for any \(x\) in the set of natural numbers \({\mathbb N}\) there exists a \(y\in {\mathbb N}\) such that \(\psi(x,y)\). Then for any \(a\in {\mathbb N}\) let \(f(a)\) be the least \(b\) such that \(\psi(a,b)\) is true in \({\mathbb N}\). The function \(f\) is called as Skolem function for the sentence \(\forall x\exists y\psi(x,y)\). In the paper under review the author proves that for every arithmetical sentence \(\forall x\exists y\forall z \psi(x,y,z)\) true in \({\mathbb N}\) there is a polynomial \(g(x)\) over \({\mathbb Z}\) (the set of integers) such that the corresponding Skolem function \(f(x)<g(x)\) for any \(x\in {\mathbb N}\). The same result holds with \({\mathbb Z}\) instead \({\mathbb N}\) with appropriate changes. An interesting application of these results is the following: If the Generalized Riemann Hypothesis holds, then for every \(d\) there is a polynomial-time algorithm for the following problem: given a quantifier-free arithmetical formula \(\varphi (x,y)\) of degree at most \(d\), does \(\forall x\exists y\varphi(x,y)\) hold in \({\mathbb Z}\)?