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?