A Non-Recursively Enumerable Subset of <em>N </em>Which Has {a Short} Description in Terms of Arithmetic

Let F(x, n) denote the formula ∃ab∀i≤n∃swpq∀jν∃eg {(s + w)2 + 3w + s = 2i ∧ &lt;[j = w ∧ ν = q] ν [j = 3i ∧ ν = p + q] ∨ [j = s ∧ (ν = p ∨ (i = n ∧ ν = q + x))] ν [j = 3i + 1 ∧ ν = pq] → a = ν + e + ejb ∧ ν + g = jb&gt;} from J. P. Jones’ article published in 1978. From the results of this article, it follows that the set {n ∈ N : ¬F(n, n)} is non-recursively enumerable and co-recursively enumerable. We prove that the set W = {n ∈ N : ∃p, q ∈ N ((2n = (p + q)(p + q + 1) + 2q) ∧ ∀(x0, . . . , xp) ∈ Np+1 ∃(y0, . . . , yp) ∈ {0, . . . , q}p+1 ((∀j, k ∈ {0, . . . , p} (xj + 1 = xk ⇒ yj + 1 = yk)) ∧ (∀i, j, k ∈ {0, . . . , p} (xi · xj = xk ⇒ yi · yj = yk))))} is not recursively enumerable. We prove that the set N \W is recursively enumerable. Let β : N3 → N denote Gödel’s β function. For x1, x2, x3 ∈ N, β(x1, x2, x3) equals the remainder after integer division of x1 by 1 + (x3 + 1) · x2. We prove that the set W consists of all n ∈ N such that ∀u, v ∈ N ∃a, b, p, q ∈ N ((2n = (p + q)(p + q + 1) + 2q) ∧ ∀i, j, k ∈ {0, . . . , p} ((β(a, b, i) ⩽ q) ∧ (β(u, v, j) + 1 = β(u, v, k) ⇒ β(a, b, j) + 1 = β(a, b, k)) ∧ (β(u, v, i) · β(u, v, j) = β(u, v, k) ⇒ β(a, b, i) · β(a, b, j) = β(a, b, k)))) The above formula can be easily translated into a formula in Peano arithmetic.