Let $\mathfrak A \subset \mathfrak B$ be two $\mathcal L$-structures over the language $\mathcal L$. $\mathfrak A$ is an elemetary substructure of $\mathfrak B$ if for all $\mathcal L$-formulas and all assignments $\alpha: \mathcal V \to A$ we have $\mathfrak A \vDash \varphi[\alpha] \iff \mathfrak B \vDash \varphi[\alpha]$, where $\mathcal V$ is the set of variables of $\mathcal L$, $A\subset B$ are the constants sets of the two structures $\mathfrak A$ and $\mathfrak B$.
My question is about the symmetric group $\mathfrak S_k$ of premutations $\sigma: K \to K$, where $K= \{1,…,k\} \subset \mathbb N$.
My idea is that any nontrivial subgroup $\mathfrak S'_r \subset \mathfrak S_k$ (which is a substructure) is not elementary, where $r<k$. Because the formula $\varphi(x_1,\cdots,x_r) \equiv \forall v (v = x_1 \lor \cdots \lor v = x_r)$ which is valid in $\mathfrak A$ under any assignement $\alpha: \mathcal V \to A$ is not valid in $\mathfrak B$.
It seems that no substructure can be an elementary substructure because of the that formula. What is wrong ?
Best Answer
Yes, this is correct. In fact it has nothing to do with symmetric groups per se: no finite structure ever has (proper) elementary substructures, or proper elementary extensions for that matter by exactly the same argument!
There are a couple points worth making, however:
Of course the argument above fails badly for infinite structures, and in fact the situation for infinite structures is highly nontrivial. By compactness (in the form of the upward Lowenheim-Skolem theorem) every infinite structure whatsoever has lots of proper elementary extensions. The situation for elementary substructures is a bit more complicated. Say that a $\Sigma$-structure $\mathcal{A}$ is big relative to its language iff $\vert\mathcal{A}\vert>\aleph_0+\vert\Sigma\vert$. The downward Lowennheim-Skolem theorem (which contra the upward version is unrelated to compactness) says that every structure which is big relative to its language has proper elementary submodels. Finally, if $\mathcal{A}$ is not big relative to its language then $\mathcal{A}$ may or may not have proper elementary substructures (compare e.g. $(\mathbb{N};<)$ and $(\mathbb{Q};<)$).
Equality plays a crucial role in your argument. If we look at equality-free first-order logic we see a very different picture. Specifically, every logic $\mathcal{L}$ (there are many logics out there besides first-order logic!) has a corresponding notion of elementary substructurehood $\preccurlyeq_\mathcal{L}$, namely $\mathcal{M}\preccurlyeq_\mathcal{L}\mathcal{N}$ iff $\mathcal{M}$ is a substructure of $\mathcal{N}$ and $\mathcal{M}$ and $\mathcal{N}$ agree about the truth value of all $\mathcal{L}$-sentences with parameters from $\mathcal{M}$. Equality-free first-order logic - which I'll call "$\mathsf{FOL_{w/o=}}$" although that's not standard - consists of all formulas and sentences in first-order logic that don't involve "$=$." There turn out to be a number of differences between $\mathsf{FOL}$ and $\mathsf{FOL_{w/o=}}$, including as regards their elementary substructurehood notions. For example, if $X\subsetneq Y$ are finite sets (thought of as structures in the empty language) then of course $X\not\preccurlyeq Y$ but we can show $X\preccurlyeq_{\mathsf{FOL_{w/o=}}}Y$. This answer of mine may be useful here, the connection being that if $\mathcal{A}$ is a substructure of $\mathcal{B}$ and $\mathcal{A}$ is quasi-isomorphic (using the terminology of that answer) to $\mathcal{B}$ then $\mathcal{A}\preccurlyeq_{\mathsf{FOL_{w/o=}}}\mathcal{B}$.