In this post, we give a proof that does not interpret (without parameters) in the homogeneous poset nor in the random graph . The idea is to first show that every continuous action of  or on a set is faithful or trivial. We show this by using the fact that and  have least supports. Since and have an automorphism of order two and does not, this proves that there is no nontrivial continuous action of nor on .

Let be a group. Recall that a continuous action of on a set is an action of on with the property that for every there is a finite set such that for every , if fixes pointwise, then fixes . The set is called a support of .

Let be a structure. We say that has least supports if for every continuous action of the group on a set and for every , there is a least (under inclusion) support of .

The following result is useful for proving that a homogeneous structure has least supports.

Proposition. The structures , , the random graph, the universal homogeneous poset all have least supports.

Proof: Easily checked using the condition from Theorem 9.3 of “Automata Theory in Nominal Sets” by Bojańczyk, Klin, Lasota (see also this earlier post).

 

A structure is transitive if has one orbit on .

Lemma 1. Let be a transitive structure with least supports. Then for all , , and nonempty finite , there exists an automorphism such that and .

(Note: this is a special case of Theorem 9.3 from “Automata Theory in Nominal Sets” by Bojańczyk, Klin, Lasota, who provided a stronger conclusion than above, which is also a sufficient condition for having least supports).

Proof. Without loss of generality we may assume that . Suppose that for every , whenever then too. We show that supports . Indeed, let be a permutation which fixes pointwise. In particular, , and so by assumption. But and . Therefore, . Since both and support , it follows that the least support of is .
This contradicts the fact that there is a such that .

An action of a group on a set is faithful if
for all , if for all , then is the identity in .

Proposition 1. If is transitive and has least supports, then every continuous action of on a set is trivial or faithful.

Proof. Suppose that acts continuously and non-trivially on a set . Let be such that for each . We show that is the identity on . Let , , and suppose that .

Since the action on is non-trivial, there is an element whose least support is nonempty. By Lemma 1, there is a such that and . Replacing by , we may assume that belongs to the least support of and does not. By invariance, the least support of contains . However, , and , a contradiction. Therefore, is the identity.

Remark. The following conditions are easily seen to be equivalent for a topological group :

• Every continuous action of on a set is trivial or faithful
• For every strict open subgroup of , the normal core of is trivial.
• If is a nontrivial normal subgroup of , then the only open subgroup of containing is .

 

If a structure is 0-definable over , then, in particular, acts continuously on . Therefore, Proposition 1 gives the following.

Corollary 2. Suppose that is infinite and 0-definable over a transitive structure with least supports. Then the induced homomorphism is injective.

Theorem. The structure is not 0-interpretable over the homogeneous poset nor over the random graph .

Proof. We give a proof for ; for it is similar.

We start with the following.
Claim. has an automorphism of order two.

The argument below is due to Julius Jonušas (it follows from a theorem of Henson). Take a graph with two independent elements, and an involution denoted which swaps the two elements. We proceed in stages for , by extending the graph with its involution to a graph containing as an induced subgraph, with an involution extending the involution of . In the th stage, we satisfy all requests
of the form , where are disjoint subsets, by creating a vertex , which is connected to all vertices of and no vertices in . We define as , where for .
In the limit, we define as the union of all the constructed graphs , for , and the involution as the union of the involutions on the graphs . The resulting graph satisfies the extension property characterizing the random graph, so is isomorphic to the rado graph . Moreover, it is equipped with a nontrivial involution . Hence, has a nontrivial involution, proving the claim.

Now suppose that is 0-interpretable over . Then there is a homomorphism .
Since has no automorphism of order two, the homomorphism has nontrivial kernel, as it maps the automorphism to the identity element. This contradicts Corollary 2..

It seems that by similar arguments, one can show that does not interpret in with parameters.

Below is another proof of the fact that does not interpret in the Random graph . This argument no longer seems to work for .

Theorem. There is no nontrivial continuous action of on by automorphisms (even with infinitely many orbits).

Remark. Continuity can be dropped since has the small index property.

Proof. Recall that is a topological space with pointwise convergence topology. This is a Polish space, i.e., the topology is generated by a complete metric on — the metric in which the distance between two automorphisms of is , where is the smallest number such that , and where is a fixed enumeration of .
Recall that a set is comeagre if it contains a countable intersection of dense open sets. By Baire’s theorem, a comeagre set in a Polish space is dense.

Let denote the set of automorphisms of which have only infinite cycles.

Claim. The set is dense in .

This follows from a stronger result by Truss, which says that there is a comeagre conjugacy class of , and every automorphism in this class has infinitely many cycles of each finite length, and no infinite cycle.

We give another proof of the above claim. Let be the set of all automorphisms for which the first elements of (under a fixed enumeration of ) lie on a finite cycle.
Clearly, is open. It is enough to show that is dense in , since by Baire’s theorem, this will prove that the intersection is dense, proving the claim.

Let be any automorphism; we show that there is an automorphism in which agrees with on the first vertices of , where are arbitrary fixed numbers. This will prove denseness. Let be the finite subgraph of induced by the first vertices of and their images under . Let denote the restriction of to ; this is a partial isomorphism. By the Hrushovski-Herwig-Lascar theorem, there is a finite graph containing as an induced subgraph, and an automorphism of which extends .
Without loss of generality, we may assume that is a subgraph of , which is a supergraph of . Let be any automorphism of extending (which exists by homogeneity). Then all elements of , and of in particular , lie in a finite cycle of , and so . This proves the claim.

We now prove the theorem. Let be a continuous homomorphism; we show that is trivial.
Take any , and let be a finite support of . For every , we have that is the identity on for some . In particular, . Since induces an automorphism of it must be the case that , for all and . This shows that is contained in the kernel of the induced homomorphism from to . Since is dense in , it follows that is trivial.