caa a22 4500 388039477 CHVBK 20180307125017.0 cr unu---uuuuu 161130e199803 xx s 000 0 eng 10.2307/2586585 doi S0022481200015309 pii (NATIONALLICENCE)cambridge-10.2307/2586585 Boffa M. Université de Mons-Hainaut, Institut de Mathématique et D'Informatique, Avenue Maistriau, 15, B-7000 Mons Belgium, E-mail: boffa@sunl.umh.ac.be More on an undecidability result of Bateman, Jockusch and Woods [Elektronische Daten] [M. Boffa] Let P be the set of prime numbers. Theorem 1 of [1] shows that the linear case of Schinzel's Hypothesis (H) implies that multiplication is definable in 〈ω,+,P〉 and therefore that the first-order theory of this structure is undecidable. Let m be any fixed natural number >2, let R be the set of natural numbers <m which are prime to m, and let r be any fixed element of R. The set is infinite (Dirichlet). Theorem 1 of [1] can be improved as follows: Proposition. The linear case of Schinzel's Hypothesis (H) implies that multiplication is definable in 〈ω,+,Pm,r〉 and therefore that the first-order theory of this structure is undecidable. Proof. We follow [1] with the following new ingredients. Let k be the number of elements of R, i.e. k = ϕ(m) where ϕ is Euler's totient function. Since k is even, the polynomial g(n) = n k + n satisfies g(0) = g(−1) = 0, so (by Lemma 1 of [1]) it follows from the linear case of (H) that there are natural numbers a l (l ϵ ω) such that a l+g(0), a l +g(1), , a l +g(l) are consecutive primes. Since R is finite, we may assume that all the a l 's have the same residue t in R, so that a l +g(i) ≡ t+1+i (mod m) for i ϵ R. This implies that the function t+1+i (reduced mod m) gives a permutation of R, so we can find s ϵ R such that a l +g(s) ≡ r (mod m). Consider the polynomial h(n) = g(s + mn) and let b l = a s+ml . Then b l + h(0), b l + h(1), , b l + h(l) are elements of Pm,r . They are not necessarily consecutive elements of Pm,r , but they are separated by a fixed number of elements of Pm,r . This implies that {h(n) ∣ n ϵ ω} is definable in 〈ω,+,Pm,r 〉(by adapting the proof of Theorem 1 of [1]), and the result follows. Copyright © Association for Symbolic Logic 1998 The Journal of Symbolic Logic Cambridge University Press 63/1(1998-03), 50-50 0022-4812 63:1<50 1998 63 JSL https://doi.org/10.2307/2586585 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.2307/2586585 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Boffa M. Université de Mons-Hainaut, Institut de Mathématique et D'Informatique, Avenue Maistriau, 15, B-7000 Mons Belgium, E-mail: boffa@sunl.umh.ac.be NATIONALLICENCE 773 0- The Journal of Symbolic Logic Cambridge University Press 63/1(1998-03), 50-50 0022-4812 63:1<50 1998 63 JSL CC0 http://creativecommons.org/publicdomain/zero/1.0 nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-cambridge