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

$\phi:\sym{\mathbb N}\to G$ is a continuous 1-1 homomorphism with closed image;
The group $G$ is a closed subgroup of $\textrm{Sym}(M)$ ;
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?

Atompress

Automorphism groups of definable structures

Leave a Reply Cancel reply

Computation with atoms