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

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

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

• When you say $M$ is $\aleph_0$-categorical, do you also require it to be countable? Otherwise I don't see why $M$ needs to be homogeneous. – Levon Haykazyan Mar 2 '17 at 0:56
• @AlexKruckman: One cannot use the Ryll-Nardzewski theorem for uncountable languages. Is there a quick fix for the uncountable case? – Kyle Mar 2 '17 at 2:15
• I interpreted "$\aleph_0$-categorical structure" to mean "the unique countable model of an countably categorical theory in a countable language. My answer addresses that case. – Alex Kruckman Mar 2 '17 at 3:33
• @LevonHaykazyan: In this case $(\Bbb Q,<) + (\Bbb R,<)$ is an example, no? The $\Bbb R$ copy is not definable, but it is fixed by every automorphism of the structure. This is a dense linear order without endpoints, so $\aleph_0$-categorical. – zarathustra Mar 2 '17 at 9:48
• @AlexKruckman I do indeed mean 'the unique (up to iso) countable model of a countably categorical theory with a countable language'. However I still dont follow why $M$ has to be homogeneous? – Tom Q Mar 2 '17 at 10:30

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

• My comment actually asked if $M$ itself has to be countable, or an arbitrary model of an $\aleph_0$-categorical theory. So I shouldn't take any credit for suggesting an uncountable language. – Levon Haykazyan Mar 2 '17 at 1:59
• @LevonHaykazyan: Oops... I totally misread your comment. – Kyle Mar 2 '17 at 2:13
• @LevonHaykazyan: But in a way, you should still be given credit since my misreading of your comment led to this idea. Unless this is a bad idea. Then I take all the blame. – Kyle Mar 2 '17 at 2:20