A question I was asked recently lead me to the following question. For every closed first order formula $\theta$ in the group signature consider the set $N\_\theta$ of natural numbers $n$ such that the symmetric group $S\_n$ satisfies $\theta$. 


**Question.** Can $N\_\theta$ always be defined by a first order formula in the signature of natural numbers? 


**Update.** The original question has been answered below by Noah Schweber, but it occurred to me that I am mostly interested in the converse translation. So here is


**Converse question.** Given a first order formula that defines a set $M$ of natural numbers, is there always a first order formula in the group signature defining the set of symmetric groups $\{S\_n\mid n\in M\}$? 



Translating first order statements about symmetric groups into the language of numbers and back
If by "signature of natural numbers" you mean the usual signature of arithmetic $\{+,\times\}$ or similar, the answer is **yes**. This is because using this language we can talk in a first-order way about finite objects: in the same manner as Godel describes strings of symbols, we can explicitly write something like "For all finite groups," or so on. So really, the only issue here is that we be able to talk uniformly about the symmetric groups, but it's not hard to show that there is a primitive recursive (hence a fortiori definable) map sending $n$ to a code for a group isomorphic to $S\_n$.


Now, one might still be worried by the issue of expressing "$\models$" in the relevant way. However, this is fine: the satisfaction relation for *finite* structures is in fact uniformly definable in the language of arithmetic. This is because a sentence is satisfied by a structure if and only if appropriate Skolem functions exist, and these functions themselves are finite objects and so can be quantified over.




---


And now for the overkill answer:


Clearly for each $\theta$, the set $N\_\theta$ is computable; and every computable set is definable.




---


EDIT: The answer to the updated question is **no**. For any sentence in the language of groups, the set of indices for symmetric groups satisfying it is computable. Now pick some formula of arithmetic defining a non-computable set.


Even if we restrict attention to computable sets of natural numbers, the answer is still no. For each $\theta$, we can put a bound on the amount of time it takes to tell whether $S\_n\models\theta$; any computable set not computable within this time bound will give a counterexample. (A back-of-the-napkin calculation: each quantifier corresponds to a search through all the elements, so telling whether $S\_n$ satisfies an $m$-quantifier sentence in prenex normal form with a length-$l$ matrix probably takes something like $(n!)^k\cdot l$-many steps.)


