Definable sets in an $\aleph_0$-categorical structures and automorphisms.

Question

The following links definable sets of a (first order) structure and its automorphisms:

Proposition (see D. Marker 'Model theory: an introduction' Prop 1.3.5) Let $\mathcal{M}$ be an $\mathcal{L}$-structure with domain $M$. If $X\subset M^n$ is $A$-definable, then if $\sigma$ is an automorphism of $M$ and $\sigma(a)=a$ for all $a\in A$ (that is, $A$ is fixed pointwise) then $\sigma(X)=X$ (that is, $X$ is fixed setwise).

However the converse is not true in general (see http://www.cantab.net/users/jonathankirby/InvitationToModelTheory_v0_3_1.pdf for an example).

Question: I am looking for an example of the converse failing when $\mathcal{M}$ is $\aleph_0$-categorical. That is, find an $\aleph_0$-categorical structure $\mathcal{M}$, $X\subset M^n$, and $A$ a finite subset of $M$ such that $X$ is not $A$-definable but that all automorphisms of $M$ that fix $A$ pointwise, fixes $X$ setwise.

Edit: By '$M$ is $\aleph_0$-categorical' I mean that $M$ is the unique (up to isomorphism) countable structure over a countable language with Th($M$) $\aleph_0$-categorical (the theory of $M$).

Answer 1

There is no such example. One of the features that make $\aleph_0$-categorical structures so nice is that automorphism invariance is equivalent to definability.

I'm assuming you know the Ryll-Nardzewski theorem (Theorem 4.4.1 in Marker). Suppose $M$ is an $\aleph_0$-categorical structure, $A$ is a finite subset of $M$, and $X\subseteq M^n$ is fixed setwise by all automorphisms of $M$ that fix $A$ pointwise.

Let $a$ and $b$ be $n$-tuples from $M$. Suppose $a\in X$ and $\text{tp}(a/A) = \text{tp}(b/A)$. Then since $M$ is homogeneous, there is an automorphism $\sigma$ of $M$ such that $\sigma$ fixes $A$ pointwise and $\sigma(a) = b$. Since $\sigma$ fixes $X$ setwise, $b\in X$.

Now let $S_X$ be the set of types $\{p\in S_n(A)\mid \exists a\in X\text{ satisfying }p\}$. $S_X$ is finite (since $S_n(A)$ is finite), and each type $p(x)\in S_n(A)$ is isolated by a formula $\psi_p(x)$ with parameters from $A$. Now you should try to check that $X$ is definable by $$\bigvee_{p\in S_X} \psi_p(x).$$

Answer 2

This is a comment. Maybe someone can fix this example and give a total answer. Examples might exist with uncountable languages (since the Ryll-Nardzewski theorem does not apply to these languages). Let $\mathbb{P} \subset \mathbb{N}$ be the collection of primes. Consider the structure $(\mathbb{N}; +, \times, 0,1)$ along with uncountably many unary predicates $P_\gamma$ where each $\gamma \in \mathcal{P}(\mathbb{P})$ and $$\mathbb{N} \models P_\gamma(a) \iff a \in \gamma $$ As an exercise, one can show that this structure is $\aleph_0$ categorical with the only countable model being the 'standard' model. The existence of an element which realizes a non-principal type implies the existence of $2^{\aleph_0}$ elements which realize non-principal types.

Furthermore, $(\mathbb{N},<)$ is rigid (i.e. does not have any non-trivial automorphisms) and so this structure is also rigid. However, every subset of the structure I have defined above is definable (since the map from primes to natural numbers is definable)! Therefore, one would have to rig this example above so that there exists a non-definable subset (by possibly deleting enough predicates), but I'm not sure if this is possible...