Composite numbers are finite spectrum of a sentence in some language

Question

The problem is to show that the composite numbers are the finite spectrum of a sentence in some language. The hint given is to consider subgroups and cosets. (I am aware there are other solutions to this problem, e.g. here: https://math.berkeley.edu/~scanlon/m125f05/mt2sol.pdf, but I am interested in a solution using the hint, i.e. utilising groups/subgroups).

My thoughts: so it seems we want to find a first order sentence, (presumably in the language of groups?) which says that a group has a proper, nontrivial subgroup. This then implies the group has composite order. However I could not think of such a sentence. Is there such a sentence? Or is there another way to do it? Thank you for any help.

Answer 1

Hint: you can't quantify over subgroups in the first-order language of a group. You can talk about groups with a chosen subgroup, if you extend the language with a one-place predicate symbol to denote the set of elements of the subgroup. Now do you see what to do?

Answer 2

Two solutions:

1)$\;$Let the language $\mathcal{L}$ and the $\mathcal{L}$-sentence $A'$ be as I define in this answer. Then, consider the sentence $$B:=\exists z\,((\neg\exists w\,Rzw)\wedge((\exists x\,\exists y\,(Rxz\wedge Ryz\wedge Qxyz))\vee Oz)),$$ which expresses that the largest element in our universe is a composite number (or it is 1).

Then the set of composite numbers is exactly the spectrum of $A'\wedge B$ (and the set of prime number is exactly the spectrum of $A'\wedge\neg B$).

2)$\;$Let $\mathcal{L}$ be a language with equality and two binary predicates $R$ and $S$. Then the $\mathcal{L}$-sentence $C$ whose spectrum will be the set of composite numbers is one expressing that both $R$ and $S$ are equivalence relations (1-3 below), each with more than one equivalence class (4), and so that they intersect in exactly one element of the domain (5). That is, $C$ is the conjunction of the following clauses:

1. $\forall x\,Rxx$, $\forall x\,Sxx$
2. $\forall x\,\forall y\,(Rxy\Leftrightarrow Ryx)$, $\forall x\,\forall y\,(Sxy\Leftrightarrow Syx)$
3. $\forall x\,\forall y\,\forall z\,(Rxy\wedge Ryz\Rrightarrow Rxz)$, $\forall x\,\forall y\,\forall z\,(Sxy\wedge Syz\Rightarrow Sxz)$
4. $\exists x\,\exists y\,(Rxy\wedge \neg (x=y))$, $\exists x\,\exists y\,(Sxy\wedge \neg (x=y))$
5. $\forall x\,\forall y\,\exists z\,\forall t\,((Rxt\wedge Syt)\Leftrightarrow (z=t))$

Any finite structure $M$ satisfying $C$ has its domain partitioned into rows and columns by $R^{M}$ and $S^{M}$ whose interscection consists of exactly one element. That is, the elements of the domain are arranged in an $m\times n$ matrix, with $m,n\geq 2$. Conversely, for any $m,n\geq 2$, there is an $\mathcal{L}$-structure $M$ satisfying $C$. Thus $\mathrm{Spectrum}(C)$ is precisely the set of composite numbers.