Automorphism groups of definable structures

We consider equality atoms \atoms, i.e., \atoms is a countable set with the equality relation. Recall that by definable set we mean a structure which can be defined (in a possibly nested fashion) from \atoms using finite unions, finite tuples, and set-builder expressions with first-order formulas ranging over \atoms, e.g. \set{(x,y):x,y\in\atoms, x\neq y}\cup\set{x:x\in\atoms, x\neq 5} is definable using the parameter 5. A definable relational structure is a relational structure (A,R_1,\ldots,R_n) where A and each relation R_i is a definable set. Up to isomorphism, definable structures are the same as structures which interpret in \atoms, using first-order interpretations (this correspondence preserves parameters), but sometimes using definable sets makes constructions easier.

The problem described in the previous post is to determine isomorphism between two definable structures. In this post, we describe this problem in terms of automorphism groups. This post is based on discussions with Manuel Bodirsky and Antoine Mottet.


We say that a structure is 0-definable if it is definable in \atoms without parameters. This corresponds to structures which interpret in \atoms without parameters.

First a simple observation.

Lemma 1. If a structure \str M is definable, then it is isomorphic to a 0-definable structure.

Proof. Since interpretations can be composed, it is enough to show that for any fixed parameter a\in \atoms, the structure (\atoms,a) obtained from \atoms by adding the constant a, can be interpreted in \atoms without parameters. In the set of equality atoms, this is easy. In terms of definable sets, we simply observe that the structure (\atoms,a) is isomorphic to the 0-definable structure (\atoms\cup \set\emptyset,R_=,c) where R_= is \set{(a,a):a\in\atoms}\cup\set{(\emptyset,\emptyset)}
and c=\emptyset is the constant. This can be also expressed using a two-dimensional interpretation. \square

Question 1. A similar argument as above works when \atoms=(\mathbb Q,\le). For what other homogeneous (or \omega-categorical) structures does the lemma hold? For instance, does the random graph with a constant interpret in the random graph? Update: in this post we prove that the answer to the last question is negative.

If \str M is definable, then there is an obvious action of \aut\atoms on \str M: an automorphism \pi\in\aut\atoms acts on elements of \str M, since these elements are effectively built out of \atoms. This action induces a continuous group homomorphism \phi:\aut\atoms\to \aut{\str M}.

For equality atoms, we have the following.

Lemma 2. If \str M is infinite then \phi is injective.

Observe that the kernel of \phi is a normal subgroup of \aut\atoms, which is closed (since the action is continuous).
We say that a topological group is simple if its only closed normal subgroups are either the entire group or the trivial group. The following lemma immediately yields Lemma 2.

Lemma 2′. \aut\atoms is a simple topological group.

A quick proof of Lemma 2′ is by invoking a theorem which classifies all normal subgroups of \aut\atoms: the only nontrivial such subgroup is the group of all finite permutations of \atoms; however, this group is not closed.
A similar argument applies to the case when \atoms=(\mathbb Q,\le).

Below is a direct proof of Lemma 2.
Recall that if \aut\atoms acts on a set X, then a support of x\in X is any set S\subset \atoms such that every permutation \pi\in\aut\atoms fixing S pointwise also fixes x. If \aut\atoms acts continuously on a set X, then every element x\in X has a finite support. In the case when \atoms is the pure set, then there is also the least support of x with respect to inclusion.

Proof. We show that for every nontrivial continuous action of \aut\atoms on a set X, the kernel of the induced homomorphism \phi:\aut\atoms\to \textrm{Sym}(X) is trivial. This implies Lemma 2, since if \str M is infinite, then it must have an infinite orbit with respect to \aut\atoms (since it has only finitely many orbits), and therefore, the action is nontrivial.

Let \pi\in\aut\atoms induce the identity permutation of X; we show that \pi induces the identity on \atoms. Suppose that a\in\atoms is such that \pi\cdot a\neq a. Since \aut\atoms acts nontrivially on X, there is an element x\in X whose orbit contains more than one element. Without loss of generality, we may assume that the least support of x contains a and does not contain \pi(a) – this is because there is an automorphism \sigma of \atoms which maps a finite set S to any other finite set of the same cardinality, and we can replace x by \sigma\cdot x if needed. By assumption, \pi(x)=x, but the least support of \pi(x) contains \pi(a), a contradiction. Hence \pi must act trivially on \atoms.\square

Assume that \str M is infinite and interprets in the pure set \atoms; below we assume that \atoms=(\mathbb N,=). Let M denote the domain of \str M and let G\subset \textrm{Sym}(M) be the automorphism group of \str M. By Lemma 2, we have:

    \[\sym{\mathbb N}\stackrel{\phi}{\hookrightarrow} G\subset \textrm{Sym}(M),\]

such that

  1. \phi:\sym{\mathbb N}\to G is a continuous 1-1 homomorphism with closed image;
  2. The group G is a closed subgroup of \textrm{Sym}(M);
  3. The action of \sym{\mathbb N} on M is oligomorphic, i.e., it has finitely many orbits on M, on M^2, on M^3, etc.

Let M be an infinite set, and let G be a subgroup of \textrm{Sym}(M). Call a pair (\phi,G) interesting if it satisfies the conditions 1-3 above. In fact, in condition 1 we could drop the requirement that the image of \phi is 1-1, and in condition 3 we could only require that \sym{\mathbb N} has finitely many orbits on M only; one can prove that this yields an equivalent definition.

Vague question. Classify all interesting pairs, up to isomorphism.

If this question is too vague, here are some other questions concerning interesting pairs.

Question 2. Is G always obtained by iteratively applying wreath products and cartesian products of actions, starting from the full permutation group of \mathbb N and all finite permutation groups?

Question 3. Is it the case that G is obtained from \phi(\textrm{Sym}(\mathbb N))\subset \textrm{Sym}(M) by adding finitely many generators and taking the smallest closed subgroup?

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>