There exists a non-recursively enumerable set {n∈N: φ(n)} such that the formula φ(n) is short and can be easily translated into a first-order formula which uses only + and \cdot

We prove that the set W={n∈N: ∃p,q∈N ((2n=(p+q)(p+q+1)+2q) ∧ ∀(x_0,...,x_p)∈N^{p+1} ∃(y_0,...,y_p)∈{0,...,q}^{p+1} ((∀i,j,k∈{0,...,p} (x_j+1=x_k ⇒ y_j+1=y_k)) ∧ (∀i,j,k∈{0,...,p} (x_i \cdot x_j=x_k ⇒ y_i \cdot y_j=y_k))))} is co-recursively enumerable and not recursively enumerable. Let β:N^3→N denote Gödel's β function. For x_1,x_2,x_3∈N, β(x_1,x_2,x_3) equals the remainder after integer division of x_1 by 1+(x_3+1) \cdot x_2. 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) \cdot β(u,v,j)=β(u,v,k) ⇒ β(a,b,i) \cdot β(a,b,j)=β(a,b,k)))). We express the above formula in Peano arithmetic.