Sometimes it is not easy to formulate a correct question. Here is a better version of [this](https://mathoverflow.net/questions/302367/translating-first-order-statements-about-symmetric-groups-into-the-language-of-n) 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?



The symmetric group theory of natural numbers
It's possible to embed within the theory of the permutation group $S\_n$ the theory of second-order arithmetic for numbers between $0$ and $n-1$. Using this we can construct propositions corresponding to any property of $n$ that can be determined by a Turing machine with resource bound that roughly corresponds to a maximum of $\sqrt {n}$ steps. With additional quantifiers we can add a finite amount of alternation to this complexity class and get a PH-like complexity class.


As Noam Elkies points out, for $n > 6$ simple transpositions are characterized by a first-order property. To be self-contained, I'll repeat his definition: $g$ is a simple transposition if $g^2 = 1$ and for any conjugate $g'$ of $g$, the order of $g g'$ is either $1$, $2$, or $3$.


Next, it is possible to encode a point in the underlying set acted on by the permutation group (that is, a point in $[n] = \{1, 2, \dots, n\}$) as pair of simple transpositions $(g\_0, g\_1)$ such that $g\_0 g\_1$ has order $3$, which represent the unique point which is transposed on both $g\_0$ and $g\_1$. The pairs $(g\_0, g\_1)$ and $(h\_0, h\_1)$ represent the same point if and only if for each $i \in \{0, 1\}$ and $j \in \{0, 1\}$ the product $g\_i h\_j$ is either the identity or order $3$. Next, given a permutation $g$ and a point $x$ encoded by $(h\_0, h\_1)$, the action of $g$ on $x$ is encoded by $(g^{-1} h\_0 g, g^{-1} h\_1 g)$. Seeing as we can quantify over all the points and compare points for equality, any two-sorted formula involving both permutations and points can be translated into an equivalent formula involving only permutations. Therefore I can freely incorporate points into my language for defining properties.


Permutations can also encode sets of points: Given a permutation $g$, define $Q (g)$ to be the set of all points not fixed by $g$. Then the sets $Q (g)$ for all $g \in S\_n$ vary over all subsets of $[n]$ other than the ones with a single point. Then if $\phi (X)$ is a formula with a variable $X$ representing a subset of $X$, we can translate the quantifier $\forall X. \phi (X)$ into $\forall g \in S\_n. \phi 
45 (Q (g)) \land \forall x \in [n]. \phi (\{x\})$, where $\phi (Q (g))$ means we replace all instances of $y \in X$ with $g (y) \neq y$, and $\phi (\{x\})$ means we replace all instances of $y \in X$ with $x = y$. The formula $\exists X. \phi (X)$ is translated similarly. Therefore we can also add subsets of $[n]$ into our language.


I define that $g\_0$ is *cyclically contained* in $g\_1$ if for every point $x$ either $g\_0 (x) = x$ or $g\_0 (x) = g\_1 (x)$. Equivalently, the cyclic decomposition of $g\_0$ is a subset of the cyclic decomposition of $g\_1$, not counting fixed points as cycles. Then a *cycle* can be defined as a permutation that is not the identity and such that every permutation cyclically contained in it is either equal to it or equal to the identity. A *maximal cycle* is a cycle without any fixed points.


For everything below, I will fix a maximal cycle $S$ and a point $O$. The lettering is intended to be suggestive of Peano arithmetic.


A permutation commutes with $S$ if and only if it is a power of $S$. I define the *addition relation* $x + y = z$ to mean that there exists a permutation $g$ which commutes with $S$ such that $g (O) = x$ and $g (y) = z$. I will denote by $x+y$ the unique point $z$ such that $x + y = z$.


I call a permutation $g$ *linear* if $g (x + y) = g (x) + g (y)$ for all $x$ and $y$. $x$ is call *invertible* if there is a linear permutation $g$ such that $g S (O) = x$. If $x$ is invertible I define the product $x \cdot y$ to be $g (y)$ for the unique such $g$. For an arbitrary $x$ I define $x \cdot y = z$ if there is a decomposition $x = x\_0 + x\_1$ or $x = x\_0 + x\_1 + x\_2$ with $x\_0, x\_1, x\_2$ all invertible and $z = x\_0 \cdot y + x\_1 \cdot y$ or $z = x\_0 \cdot y + x\_1 \cdot y + x\_2 \cdot y$, respectively.


To define the order relation we can use subsets: I define $x < y$ if there is a subset $X \subseteq [n]$ such that 


1. $S (x) \in X$.
2. If $a \in X$, then either $a = y$ or $S (a) \in X$.
3. $O \notin X$.


Using all of the definition above as tools it should be possible to define whether some tuple of subsets $X\_0, \dots, X\_{r-1}$ denote a Turing machine computation. With a naive encoding of the computation as a concatenation of the state of the Turing machine at every time step, it is necessary that the computation terminate before the spacetime resource usage is greater than a fixed multiple of $n$, where the spacetime resource usage is defined as the sum of the space usage over each time step. With this it should be possible to define "$X\_0$ encodes the binary representation of $x$" whenever $x$ less than the square root of $n$, by giving the input $x$ in unary. The binary representation of $n$ can be determined via a formula $n = x \cdot y + z$ where $y$ is a power of $2$ (definable as in Peano arithmetic) and $z < y$ and given the binary representations of $x$ and $z$. Verifying $n = x \cdot y + z$ comes down to the identity $x \cdot y + z = O$ plus the claim that $x \cdot y$ doesn't overflow. $n$ can also be split into three components to give more leeway for constant and logarithmic factors. Giving the binary representation of $n$ as input to a Turing machine allows defining all properties that checkable by a Turing machine with these resource bounds.


More sophisticated encoding schemes, making full use of the information encoded by a permutation rather than just thinking of it as a subset, should lead to a higher computational capacity. Using alternating quantifiers $\forall Y\_0 \exists Y\_1 \forall Y\_2 \dots \exists Y\_{s-1}$ and including $Y\_0, \dots, Y\_{s-1}$ as inputs to the computation, it should be possible to define all properties within a PH-like complexity class where the final verification step is restricted to computations with this spacetime resource bound or whatever resource cost the more sophisticated encoding takes.


