If $M$ has only two definable subsets, must it have a transitive automorphism group?

Question

I was told that a sufficient condition for a structure $M$ to have only the empty set and $M$ itself as parameter-free definable subsets, is for $M$ to have a transitive automorphism group. Is the converse true?

Answer 1

No, it's not - there can be obstacles to transitivity which are "invisible to first-order logic."

The simplest example is probably just a structure $M$ consisting of an equivalence relation with two classes, one of which is countably infinite and the other of which is uncountable.

• By downwards Lowenheim-Skolem, $M$ has a countable elementary substructure $M_0$; it's not hard to show that $M_0$'s automorphism group acts transitively.

• That means that $M_0$ has no nontrivial definable sets, which by elementarity means that $M$ doesn't either.

• But $M$'s automorphism group does not act transitively: no element of the countable class is automorphic to any element of the uncountable class.

Of course in some sense this is a bit unsatisfying - the reliance on cardinality leaves open the question of whether the same situation can happen with countable structures, which - per the downward Lowenheim-Skolem theorem - is arguably the right question. It turns out this still happens for countable structures, although less trivially. In my opinion, the most satisfying argument is the following:

Given linear orders $A,B$, let $AB$ be the linear order consisting of "$B$-many copies of $A$." Specifically, $AB$ has domain $A\times B$ and is ordered via $$\langle a,b\rangle\le \langle c,d\rangle\iff b<d\vee (b=d\wedge a\le c).$$

• What can you say about the definable sets in $\mathbb{Z}B$ for any linear order $B$? (A good tool for this is Ehrenfeucht-Fraisse games.)

• Can you find a linear order $B$ such that $\mathbb{Z}B$'s automorphism group does not act transitively? (HINT: think about what the transitivity of the action of $Aut(\mathbb{Z}B)$ on $\mathbb{Z}B$ would imply about the action of $Aut(B)$ on $B$.)