We consider equality atoms , i.e.,
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
using finite unions, finite tuples, and set-builder expressions with first-order formulas ranging over
, e.g.
is definable using the parameter
. A definable relational structure is a relational structure
where
and each relation
is a definable set. Up to isomorphism, definable structures are the same as structures which interpret in
, 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 without parameters. This corresponds to structures which interpret in
without parameters.
First a simple observation.
Lemma 1. If a structure 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 , the structure
obtained from
by adding the constant
, can be interpreted in
without parameters. In the set of equality atoms, this is easy. In terms of definable sets, we simply observe that the structure
is isomorphic to the 0-definable structure
where
is
and is the constant. This can be also expressed using a two-dimensional interpretation.
Question 1. A similar argument as above works when . For what other homogeneous (or
-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 is definable, then there is an obvious action of
on
: an automorphism
acts on elements of
, since these elements are effectively built out of
. This action induces a continuous group homomorphism
.
For equality atoms, we have the following.
Lemma 2. If is infinite then
is injective.
Observe that the kernel of is a normal subgroup of
, 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′. is a simple topological group.
A quick proof of Lemma 2′ is by invoking a theorem which classifies all normal subgroups of : the only nontrivial such subgroup is the group of all finite permutations of
; however, this group is not closed.
A similar argument applies to the case when .
Below is a direct proof of Lemma 2.
Recall that if acts on a set
, then a support of
is any set
such that every permutation
fixing
pointwise also fixes
. If
acts continuously on a set
, then every element
has a finite support. In the case when
is the pure set, then there is also the least support of
with respect to inclusion.
Proof. We show that for every nontrivial continuous action of on a set
, the kernel of the induced homomorphism
is trivial. This implies Lemma 2, since if
is infinite, then it must have an infinite orbit with respect to
(since it has only finitely many orbits), and therefore, the action is nontrivial.
Let induce the identity permutation of
; we show that
induces the identity on
. Suppose that
is such that
. Since
acts nontrivially on
, there is an element
whose orbit contains more than one element. Without loss of generality, we may assume that the least support of
contains
and does not contain
– this is because there is an automorphism
of
which maps a finite set
to any other finite set of the same cardinality, and we can replace
by
if needed. By assumption,
, but the least support of
contains
, a contradiction. Hence
must act trivially on
.
Assume that is infinite and interprets in the pure set
; below we assume that
. Let
denote the domain of
and let
be the automorphism group of
. By Lemma 2, we have:
such that
is a continuous 1-1 homomorphism with closed image;
- The group
is a closed subgroup of
;
- The action of
on
is oligomorphic, i.e., it has finitely many orbits on
, on
, on
, etc.
Let be an infinite set, and let
be a subgroup of
. Call a pair
interesting if it satisfies the conditions 1-3 above. In fact, in condition 1 we could drop the requirement that the image of
is 1-1, and in condition 3 we could only require that
has finitely many orbits on
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 always obtained by iteratively applying wreath products and cartesian products of actions, starting from the full permutation group of
and all finite permutation groups?
Question 3. Is it the case that is obtained from
by adding finitely many generators and taking the smallest closed subgroup?