Least supports and weak elimination of imaginaries

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.

1. has weak elimination of imaginaries,
2. has definable supports,
3. 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.