When are automorphism-invariant subsets definable?

Question

Let $\mathfrak{M}$ be an $\mathcal{L}$-structure, $A\subseteq M$, and $S\subseteq M^n$ some subset defined by an $\mathcal{L}$-formula $\phi(x_1, ..., x_n, a_1, ..., a_m)$ where $a_i\in A$. It is straightforward to see that $S$ must be preserved under any automorphism $f:M\rightarrow M$ that fixes $A$ pointwise; indeed, by definition of $f$ we have $\phi(x_1, ..., x_n, a_1, ..., a_m)\Leftrightarrow\phi(f(x_1), ..., f(x_n), f(a_1), ..., f(a_m))$, and, since $f(a_i)=a_i$ by hypothesis, we have $f(S)\subseteq S$. Thus by bijectivity $f(S)=S$.

I believe the converse of this is not true; for instance, consider $\langle\mathbb{N}, \leq\rangle$. Then $S\subseteq\mathbb{N}$ is definable if and only if it is a boolean combinations of finite subsets and intervals of $\mathbb{N}$, so for instance $2\mathbb{N}\subset\mathbb{N}$ is not definable. However, the only automorphism of $\langle\mathbb{N}, \leq\rangle$ is the identity.

More generally, for any $\mathcal{L}$-structure $\mathfrak{M}$ with an undefinable subset $S\subset M$, let $\mathcal{L}^\ast=\mathcal{L}\cup\{c_k:k\in M\}$ and consider $\mathfrak{M}$ as an $\mathcal{L}^\ast$-structure under the natural interpretation. Then the only automorphism of $\mathfrak{M}$ is the identity, but $S$ is still undefinable. Hence:

Q1: Are there criteria to determine when the converse of the statement in the first paragraph holds? To state it precisely, for what structures $\mathfrak{M}$ does the following statement hold: "If every automorphism of $\mathfrak{M}$ that fixes some subset $A\subseteq M$ pointwise also fixes some subset $S\subseteq M^n$ setwise, then $S$ is $A$-definable."

The problem in this second counterexample is of course that adding constant symbols to our language reduces the number of possible automorphisms without changing the definable subsets, so a second question is:

Q2: Is the answer to Q1 more straightforward when the language in question has no constant symbols?

Answer 1

There are only two general conditions (that I know of) under which automorphism-invariant implies definable (in first-order logic): (1) the trivial case when $\mathfrak{M}$ is finite, and (2) when $A$ is finite and $\mathfrak{M}$ is the unique countable model of an $\aleph_0$-categorical theory. In this case, the result is a consequence of the Ryll-Nardzewski theorem.

Why are such strong hypotheses necessary? Just for easy cardinality reasons!

For simplicity, let's assume our language $L$ is countable. Now suppose $A\subseteq M$ is an infinite set. Then any subset $B\subseteq A$ is invariant under automorphisms fixing $A$. And there are $2^{|A|}$ subsets of $A$, but there are only $\text{max}(|A|,\aleph_0)$ $L$-formulas with parameters from $A$. So there just aren't enough formulas to define all the invariant subsets, even of $A$.

Ok, so we have to restrict to finite sets of parameters. To make it even simpler, let's take $A = \emptyset$. Now the action of $\text{Aut}(\mathfrak{M})$ partitions $M$ into orbits, and a set $S\subseteq M$ is invariant under the action of $\text{Aut}(\mathfrak{M})$ if and only if it is a union of orbits. To put it another way, if $\mathcal{O}$ is the set of orbits, then an invariant set has the form $\bigcup_{O\in X} O$ for some set of orbits $X\subseteq \mathcal{O}$. Now again, if $\mathcal{O}$ is infinite, then there are $2^{|\mathcal{O}|}$ invariant sets, but only countably many formulas, so there must be invariant sets that aren't definable.

So we can only hope to get definability of every invariant set if the action of $\text{Aut}(\mathfrak{M})$ on $M$ has only finitely many orbits. If you want invariance to imply definability not just for subsets of $M$ but also for subsets of $M^k$ for all $k$, then you need to assume that the action of $\text{Aut}(\mathfrak{M})$ on $M^k$ has only finitely many orbits for all $k$ - and this is exactly the definition of an oligomorphic group action. By the Ryll-Nardzewski theorem, if $\mathfrak{M}$ is countably infinite and the action of $\text{Aut}(\mathfrak{M})$ is oligomorphic, then $\mathfrak{M}$ is the unique countable model of an $\aleph_0$-categorical theory.

There are other more exotic situations when every invariant subset of a model is definable: for example, the language could include a relation symbol for every subset of $M^k$ for every $k$ (note that in this case, the cardinality of the language is larger than the cardinality of $M$). As far as I know, there is no general theory of these sorts of examples.

See also the question and answers here. In particular, the note at the bottom of my answer might be of interest to you: if we're willing to work with the infinitary logic $\mathcal{L}_{\omega_1,\omega}$, then Scott's isomorphism theorem tells us that every invariant subset of a countable structure is definable by a formula of $\mathcal{L}_{\omega_1,\omega}$. But this does not apply to structures of higher cardinality in general, even if we look at infinitary logics of the form $\mathcal{L}_{\kappa,\lambda}$ for other cardinals $\kappa$ and $\lambda$.