Sometimes it is not easy to formulate a correct question. Here is a better version of this question (I still do not know if it is optimal, but it is better than the previous one).

We say that a set $X$ of natural numbers is *symmetric group definable* if there exists a first order formula $\theta$ in the group signature such that a symmetric group $S_n$ satisfies $\theta$ if and only if $n\in X$. Of course finite sets and sets with finite complements are symmetric group definable. It is not completely trivial to find any infinite set of natural numbers with infinite complement which is symmetric group definable. But it is not a difficult exercise to show that the set of numbers $n$ such that either $n$ or $n-1$ is prime is such a set.

**Question.** Is any of the following sets symmetric group definable?

1) the set of even numbers

2) the set of prime numbers

**A more vague question** Is there a characterization of the Boolean algebra of symmetric group definable sets?

**Update** Noam D. Elkies' answer below shows that the Boolean algebra contains many sets. Noah Schweber's answer of the previous question suggests looking at the computational complexity of $X$. Clearly, checking whether $n$ belongs to a symmetric group definable set $X$ takes time at most $(n!)^k$ where $k$ is the number of quantifiers in the corresponding formula $\theta$. So we have a couple of even better questions.

**Question 1** Is the converse true, that is every set of numbers recognizable by deterministic a Turing machine in time $\le (n!)^k$ for some $k$ symmetric group definable? Here the size of a number $n$ is $n$ that is we consider the unary representation of natural numbers.

**Question 2** Let us replace $S_n$ by, say, $SL_n(\mathbb{F}_2)$ and similarly define $SL_n(\mathbb{F}_2)$-definable sets of numbers. Will the Boolean algebra of all $SL_n(\mathbb{F}_2)$-definable sets coincide with the Boolean algebra of all deterministic polynomial time decidable sets of natural numbers?

**Question 3** Can the statements that "Primes are in P" be proved this way?

6more comments