Least supports and non-interpretability

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

Let G\subset \textrm{Sym}(A) be a group. Recall that a continuous action of G on a set X is an action of G on X with the property that for every x\in X there is a finite set S\subset A such that for every \pi\in G, \pi if fixes S pointwise, then \pi fixes x. The set S is called a support of x.

Let \atoms be a structure. We say that \atoms has least supports if for every continuous action of the group \aut\atoms\subset \textrm{Sym}(\atoms) on a set X and for every x\in X, there is a least (under inclusion) support of x.

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

Proposition. The structures (\mathbb N,=), (\mathbb Q,\le), 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 \atoms is transitive if \aut\atoms has one orbit on \atoms.

Lemma 1. Let \atoms be a transitive structure with least supports. Then for all a,b\in \atoms, a\neq b, and nonempty finite S\subset \atoms, there exists an automorphism \pi\in\aut\atoms such that a\in \pi(S) and b\not \in\pi(S).

(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 a\in S. Suppose that for every \pi, whenever a\in\pi(S) then b\in\pi(S) too. We show that S-\set{b} supports b. Indeed, let \pi be a permutation which fixes S-\set{b} pointwise. In particular, a\in\pi(S), and so b\in \pi(S) by assumption. But \pi(S)=\pi(S-\set b)\cup \set {\pi(b)}=S-\set b\cup\set{\pi(b)} and b\notin S-\set b. Therefore, b=\pi(b). Since both S-\set{b} and \set b support b, it follows that the least support of b is \emptyset.
This contradicts the fact that there is a \pi\in\aut\atoms such that \pi(b)=a\neq b. \square

An action of a group G on a set X is faithful if
for all \pi\in G, if \pi(x)=x for all x\in X, then \pi is the identity in G.

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

Proof. Suppose that \aut\atoms acts continuously and non-trivially on a set X. Let \rho\in\aut\atoms be such that \rho(x)=x for each x\in X. We show that \rho is the identity on \atoms. Let a\in \atoms, b=\rho(a), and suppose that b\neq a.

Since the action on X is non-trivial, there is an element x\in X whose least support S is nonempty. By Lemma 1, there is a \pi\in\aut\atoms such that a\in\pi(S) and b\notin\pi(S). Replacing x by \pi(x), we may assume that a belongs to the least support S of x and b does not. By invariance, the least support of \rho(x) contains \rho(a). However, \rho(x)=x, and \rho(a)=b\not\in S, a contradiction. Therefore, \pi is the identity.\square

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

  • Every continuous action of G on a set X is trivial or faithful
  • For every strict open subgroup H of G, the normal core \bigcap_{g\in G}gHg^{-1} of H is trivial.
  • If N is a nontrivial normal subgroup of G, then the only open subgroup of G containing N is G.


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

Corollary 2. Suppose that \str A is infinite and 0-definable over a transitive structure \atoms with least supports. Then the induced homomorphism \aut\atoms\to\aut{\str A} is injective.\square

Theorem. The structure (\str Q,\le) is not 0-interpretable over the homogeneous poset P nor over the random graph R.

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

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

The argument below is due to Julius Jonušas (it follows from a theorem of Henson). Take a graph G_0 with two independent elements, and an involution denoted - which swaps the two elements. We proceed in stages for n=0,1,2,\ldots, by extending the graph G_n with its involution - to a graph G_{n+1} containing G_n as an induced subgraph, with an involution - extending the involution of G_n. In the nth stage, we satisfy all requests
of the form (A,B), where A,B\subset V(G_n) are disjoint subsets, by creating a vertex (n,A,B), which is connected to all vertices of A and no vertices in B. We define -(n,A,B) as (n,-A,-B), where -X=\set{-x:x\in X} for X=A,B.
In the limit, we define G as the union of all the constructed graphs G_n, for n=0,1,2,\ldots, and the involution - as the union of the involutions on the graphs G_n. The resulting graph G satisfies the extension property characterizing the random graph, so G is isomorphic to the rado graph R. Moreover, it is equipped with a nontrivial involution -. Hence, R has a nontrivial involution, proving the claim.

Now suppose that (\str Q,\le) is 0-interpretable over P. Then there is a homomorphism \phi:\aut P\to \aut{\str Q}.
Since \aut{\str Q} has no automorphism of order two, the homomorphism \phi has nontrivial kernel, as it maps the automorphism \alpha to the identity element. This contradicts Corollary 2.\square.

It seems that by similar arguments, one can show that (\str Q,\le) does not interpret in P with parameters.

Below is another proof of the fact that (\str Q,\le) does not interpret in the Random graph R. This argument no longer seems to work for P.

Theorem. There is no nontrivial continuous action of \aut{R} on \str Q by automorphisms (even with infinitely many orbits).

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

Proof. Recall that \aut R is a topological space with pointwise convergence topology. This is a Polish space, i.e., the topology is generated by a complete metric on \aut R — the metric in which the distance between two automorphisms \alpha,\beta of R is 2^{-n}, where n is the smallest number such that \alpha(r_n)\neq\beta(r_n), and where r_1,r_2,\ldots is a fixed enumeration of R.
Recall that a set X 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 M denote the set of automorphisms of R which have only infinite cycles.

Claim. The set M is dense in \aut R.

This follows from a stronger result by Truss, which says that there is a comeagre conjugacy class of \aut R, 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 U_n\subset \aut R be the set of all automorphisms for which the first n elements of R (under a fixed enumeration of R) lie on a finite cycle.
Clearly, U_n is open. It is enough to show that U_n is dense in \aut R, since by Baire’s theorem, this will prove that the intersection \bigcap_n U_n is dense, proving the claim.

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

We now prove the theorem. Let \phi:\aut R\to\aut{\str Q} be a continuous homomorphism; we show that \phi is trivial.
Take any q\in \str Q, and let S\subset R be a finite support of q. For every \pi\in M, we have that \pi^n is the identity on S for some n. In particular, \pi^n(q)=q. Since \pi induces an automorphism of (\str Q,\le), it must be the case that \pi(q)=q, for all \pi\in M and q\in \str Q. This shows that M is contained in the kernel of the induced homomorphism from \aut R to \aut{\str Q}. Since M is dense in \aut R, it follows that \phi is trivial.

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>