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

  • 2
    $\begingroup$ 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. $\endgroup$ – Levon Haykazyan Mar 2 '17 at 0:56
  • $\begingroup$ @AlexKruckman: One cannot use the Ryll-Nardzewski theorem for uncountable languages. Is there a quick fix for the uncountable case? $\endgroup$ – Kyle Mar 2 '17 at 2:15
  • $\begingroup$ 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. $\endgroup$ – Alex Kruckman Mar 2 '17 at 3:33
  • 1
    $\begingroup$ @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. $\endgroup$ – zarathustra Mar 2 '17 at 9:48
  • $\begingroup$ @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? $\endgroup$ – 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...

  • $\begingroup$ 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. $\endgroup$ – Levon Haykazyan Mar 2 '17 at 1:59
  • $\begingroup$ @LevonHaykazyan: Oops... I totally misread your comment. $\endgroup$ – Kyle Mar 2 '17 at 2:13
  • 1
    $\begingroup$ @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. $\endgroup$ – Kyle Mar 2 '17 at 2:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.