We show that a property known from model theory as weak elimination of imaginaries corresponds to the property of admitting least algebraically closed supports, and is a generalization of admitting least supports in many contexts. In particular, we show that an ω-categorical structure admits least supports if and only if it has no algebraicity and has weak elimination of imaginaries.
Fix an structure . Recall that for us, a
-definable set over
means a set which is defined from
by an expression which consists of nested set-builder expressions and set-unions, and where the entire expression uses parameters from
; if
is empty, then the set is 0-definable. The structure
is the multi-sorted structure whose sorts are all the 0-definable sets over
, and relations are all 0-definable relations between the sorts. Elements of
are called imaginaries in model theory.
Let be the automorphism group of
. There is a natural action of
on
. For a finite set
, by
we denote the pointwise stabilizer of
. Recall that a support of an element
is a finite set
such that
. We say that
is a least support of
if
is contained in every other support of
. Finally, we say that
admits least supports if every imaginary
has a least support.
Remark. If is ω-categorical,
is finite and
is an imaginary, then it follows from the Ryll-Nardzewski theorem that
supports
iff
is
-definable.
The structures , the random graph and the homogeneous poset all admit least supports which is easily checked using the following necessary and sufficient condition, stated as Theorem 9.3 in the paper “Automata Theory In Nominal Sets” by Bojańczyk, Klin and Lasota:
Theorem 1. A structure has least supports if and only if for any finite
and any distinct
, the following inclusion holds:
Above, denotes the subgroup of
generated by
.
Least supports can be used to prove various results, among others:
- to characterize all 0-definable sets, up to
-invariant isomorphism (see Section 10.2 of the paper),
- to show that Turing machines can be “straightened”, i.e., every 0-definable function
can be lifted to a 0-definable function
, where
are 0-definable subsets of
,
- to show that the action of
on a 0-definable set is trivial or faithful (see this post),
- to show that certain structures do not interpret in other structures (see this post).
Here is an example of ω-categorical structures which does not have least supports.
Example 1. Let be the infinite disjoint union of
-cliques (where
is fixed). The set of all maximal sub-cliques of
is definable:
, and a single clique
is supported by
, for any of its elements
. However, it is not supported by the empty set; hence there is no least support. Note that
has a somehow “canonical” support, which is
itself. This is made precise below.
Definition. We say that a 0-definable set has definable supports if there is a 0-definable mapping
mapping each element
to some support of
(in particular it follows that there is a bound
such that
has at most
elements). We say that
admits definable supports every 0-definable set
has definable supports.
Fact 1. If is ω-categorical and admits least supports, then it admits definable supports.
Proof: By uniqueness of least supports, the mapping which maps an element to its least support is
-invariant, and hence 0-definable by the Ryll-Nardzewski theorem.
The structures in Example 1 also admit definable supports, although they don’t admit least supports.
Example 2. Take to be the infinite union of infinite cliques. Then
does not admit definable supports, as the 0-definable set of all maximal subcliques of
does not have definable supports.
Example 3. Consider the rational numbers with the betweenness relation
. An orientation of
is an equivalence class of pairs
, where
and
is equivalent to
iff
(this relation can be defined using
only). The set of orientations is 0-definable over
, but does not have definable supports.
Algebraic and definable closure
Recall that the definable closure of a set , denoted
, is the set of all
-definable elements in
. An element
is algebraic over
if there is a first order formula
with parameters from
, such that
is finite and contains
. The algebraic closure of the set
, denoted
, is the set of all elements of
which are algebraic over
. Finally,
has no algebraicity if every finite set
is equal to its algebraic closure. We say that
has finite algebraicity if the algebraic closure of a finite set
is finite.
Example. In the structure in Example 1, the algebraic closure of any element is the set of elements adjacent or equal to
. The structure
does not have finite algebraicity.
Fact 2. Suppose that is
-categorical. Then
has finite algebraicity.
Proof. Note that if is algebraic over
, then
lies in a finite orbit of the action of
on
, and
induces only finitely many orbits on
altogether by
-categoricity.
Fact 3. Suppose that is
-categorical and has least supports. Then
has no algebraicity.
Proof. Let be a finite set, and suppose that
. Then
, since otherwise,
would contain
and hence would be a support of
, which is incomparable with
, contradicting the existence of least supports.
Weak elimination of imaginaries
We now show how to generalize the notion of least supports to structures with algebraicity.
Definition. We say the structure has weak elimination of imaginaries if every imaginary
, if
is the algebraic closure of
in
and
, then
is
-definable.
From now on, we assume that is
-categorical.
Definition. We say that has least algebraically closed supports if every imaginary
has a smallest (wrt. inclusion) finite support
which is algebraically closed.
Theorem 2. Let be
-categorical. Then the following conditions are equivalent.
has weak elimination of imaginaries,
has definable supports,
has least algebraically closed supports.
Proof. We show the implications 3→2→1→3.
3→2. Analogous to the proof of Fact 1.
2→1. Let be an imaginary, let
be the 0-definable set containing it, and let
be a 0-definable function mapping each
to its support
. In particular,
is
-invariant. Let
for
; this function is also
-invariant. It follows that the group
of permutations which fix
also fixes the set
; in particular, each element of
is contained in a finite orbit of
, so is algebraic over
. Hence,
, and supports
, and so
also supports
.
1→3. Take an imaginary , and suppose that
is an algebraically closed support of
. Then
is contained in
. In particular,
is the least algebraically closed support of
.
Corollary. If is ω-categorical, then
admits least supports if and only if it has no algebraicity and has weak elimination of imaginaries.
Proof. Follows from Fact 3 and the equivalence 1⇔3 of the theorem.
Corollary. If is a Fraisse limit of a free amalgamation class, then
admits least supports.
Proof. See e.g. Lemma 2.7 of the paper “Simplicity of some automorphism groups” by Dugald Macpherson and Katrin Tent.
To summarize, weak elimination of imaginaries is a generalization of least supports in the presence of algebraicity. It would be nice to have some characterizations of this property, akin to Theorem 1, allowing to easily prove that e.g. the vector space over a finite field of countable dimension or the atomless boolean algebra admit least algebraically closed supports. Finally, it would also be useful to see which of the applications of least supports survive the generalization to least algebraically closed supports. Hopefully, these questions will be addressed in future posts.