5
$\begingroup$

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\}$?

$\endgroup$

1 Answer 1

8
$\begingroup$

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.)

$\endgroup$
11
  • $\begingroup$ It is not clear to me. Where do you use the fact that we are translating first order theory into a first order theory? Is it true that every computable set of natural numbers first order definable? $\endgroup$
    – user6976
    Jun 8, 2018 at 19:18
  • $\begingroup$ @MarkSapir Yes, every computable set of natural numbers is first-order definable. In fact, every computable set of natural numbers is $\Delta^0_1$ - that is, definable by both an existential formula and a universal formula. $\endgroup$ Jun 8, 2018 at 19:20
  • $\begingroup$ @MarkSapir And I'm using very little here. The same argument works for second-order sentences, and third-order, and ... Basically, the only requirement is that satisfaction of a sentence in a finite structure be witnessed by a finite object in an appropriately simple way. $\endgroup$ Jun 8, 2018 at 19:21
  • $\begingroup$ A good point to start is the result, proved in most expositions of Godel's theorem, that every primitive recursive function is representable in PA. This is a stronger condition than mere definability: a function $f(x_1,...,x_n)$ is representable in PA iff there is some formula $\varphi(x_1,...,x_n,y)$ such that $(i)$ PA proves $\forall x_1...x_n\exists !y\varphi(x_1,...,x_n,y)$ and $(ii)$ for every tuple of natural numbers $k_1,..., k_n$, PA proves $\varphi(\underline{k_1},...,\underline{k_n}, \underline{l})$ where $l=f(k_1,...,k_n)$ and "$\underline{a}$" is the numeral corresponding to $a$. $\endgroup$ Jun 8, 2018 at 19:24
  • $\begingroup$ In fact, every computable function is representable in PA. (Note that representability isn't just a property of a function in a model, but a function in a model and a theory; this is in contrast to definability, which just takes into account the ambient model.) $\endgroup$ Jun 8, 2018 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.