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.