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 $n$ th 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.
$\square$

Atompress

Least supports and non-interpretability

Leave a Reply Cancel reply

Computation with atoms