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 \atoms. Recall that for us, a S-definable set over \atoms means a set which is defined from \atoms by an expression which consists of nested set-builder expressions and set-unions, and where the entire expression uses parameters from S; if S is empty, then the set is 0-definable. The structure \atoms^{eq} is the multi-sorted structure whose sorts are all the 0-definable sets over \atoms, and relations are all 0-definable relations between the sorts. Elements of \atoms^{eq} are called imaginaries in model theory.

Let G=\aut\atoms be the automorphism group of \atoms. There is a natural action of G on \atoms^{eq}. For a finite set S\subset \atoms, by G_S we denote the pointwise stabilizer of S. Recall that a support of an element x\in \atoms^{eq} is a finite set S\subset \atoms such that G_S\cdot x =x. We say that S is a least support of x if S is contained in every other support of x. Finally, we say that \atoms admits least supports if  every imaginary x\in \atoms^{eq} has a least support.

Remark. If \atoms is ω-categorical, S\subset\atoms is finite and x is an imaginary, then it follows from the Ryll-Nardzewski theorem that S supports x iff x is S-definable.

The structures (\mathbb N,=),(\mathbb Q,\le), 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 \atoms has least supports if and only if for any finite S\subset\atoms and any distinct a,b\in\atoms-S, the following inclusion holds:

    \[G_S\cdot a\subset \langle G_{S\cup\set b}\cup G_{S\cup\set a}\rangle \cdot a.\]

Above, \langle G_{S\cup\set b}\cup G_{S\cup\set a}\rangle denotes the subgroup of G generated by  G_{S\cup\set b}\cup G_{S\cup\set a}.

Least supports can be used to prove various results, among others:

  • to characterize all 0-definable sets, up to G-invariant isomorphism (see Section 10.2 of the paper),
  • to show that Turing machines can be “straightened”, i.e., every 0-definable function f:X\to Y can be lifted to a 0-definable function \tilde f:\tilde X\to\tilde Y, where \tilde X,\tilde Y are  0-definable subsets of \atoms^*,
  • to show that the action of G 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 \atoms be the infinite disjoint union of n-cliques (where n\ge 2 is fixed). The set of all maximal sub-cliques of \atoms is definable: K=\set{\set{y:y\in \atoms, E(x,y)}:x\in\atoms}, and a single clique k=\set{y:y\in \atoms, E(x,y)} is supported by \set y, for any of its elements y. However, it is not supported by the empty set; hence there is no least support. Note that k has a somehow “canonical” support, which is k\subset \atoms itself. This is made precise below.

Definition. We say that a 0-definable set X has definable supports if there is a 0-definable mapping f mapping each element x\in X to some support of x (in particular it follows that there is a bound n such that f(x) has at most n elements). We say that \atoms admits definable supports every 0-definable set X has definable supports.

 

Fact 1. If \atoms is ω-categorical and admits least supports, then it admits definable supports.

Proof: By uniqueness of least supports,  the mapping which maps an element x\in X to its least support is G-invariant, and hence 0-definable by the Ryll-Nardzewski theorem.\square

The structures in Example 1 also admit definable supports, although they don’t admit least supports.

Example 2. Take \atoms to be the infinite union of infinite cliques. Then \atoms does not admit definable supports, as the 0-definable set of all maximal subcliques of \str A does not have definable supports.

Example 3. Consider the rational numbers \mathbb Q with the betweenness relation B(x,y,z)=(x<y<z) \lor (x>y>z). An orientation of (\mathbb Q, B) is an equivalence class of pairs (x,y), where x\neq y\in \mathbb Q and (x,y) is equivalent to (x',y') iff  x<y\iff x'<y' (this relation can be defined using B only). The set of orientations is 0-definable over (\mathbb Q,B), but does not have definable supports.

Algebraic and definable closure

Recall that the definable closure of a set S\subset \atoms, denoted \text{dcl}(S), is the set of all S-definable elements in \atoms. An element a\in \atoms is algebraic over S if there is a first order formula \phi(x) with parameters from S, such that \set{x\in\atoms: \phi(x)} is finite and contains a. The algebraic closure of the set S, denoted \text{acl}(S), is the set of all elements of \atoms which are algebraic over S. Finally, \atoms has no algebraicity if every finite set S\subset \atoms is equal to its algebraic closure. We say that \atoms has finite algebraicity if the algebraic closure of a finite set S is finite.

Example. In the structure in Example 1, the algebraic closure of any element x\in \atoms is the set of elements adjacent or equal to x. The structure (\mathbb Z,+) does not have finite algebraicity.

Fact 2. Suppose that \atoms is \omega-categorical. Then \atoms has finite algebraicity.

Proof. Note that if x is algebraic over S, then x lies in a finite orbit of the action of G_S on \atoms, and G_S induces only finitely many orbits on \atoms altogether by \omega-categoricity.\square

Fact 3. Suppose that \atoms is \omega-categorical and has least supports. Then \atoms has no algebraicity.

Proof. Let S\subset\atoms be a finite set, and suppose that x\in \text{acl}(S). Then x\in S, since otherwise, \text{acl}(S)-\set x would contain S and hence would be a support of x, which is incomparable with \set x, contradicting the existence of least supports.\square

Weak elimination of imaginaries

We now show how to generalize the notion of least supports to structures with algebraicity.

Definition. We say the structure \atoms has weak elimination of imaginaries if every imaginary x, if S is the algebraic closure of x in \atoms^{eq} and T=S\cap\atoms, then x is T-definable.

From now on, we assume that \atoms is \omega-categorical.

Definition. We say that \atoms has least algebraically closed supports if every imaginary x\in\atoms^{eq} has a smallest (wrt. inclusion) finite support S\subset \atoms which is algebraically closed.

Theorem 2. Let \atoms be \omega-categorical. Then the following conditions are equivalent.

  1. \atoms has weak elimination of imaginaries,
  2. \atoms has definable supports,
  3. \atoms 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 x be an imaginary, let X be the 0-definable set containing it, and let f  be a 0-definable function mapping each x\in X to its support S\subset \atoms. In particular, f is G-invariant. Let g(x)=\text{acl}(f(x))  for x\in X; this function is also G-invariant. It follows that the group G_x of permutations which fix x also fixes the set g(x); in particular, each element of g(x) is contained in a finite orbit of G_x, so is algebraic over x. Hence, g(x)\subset\text{acl}(x), and supports x, and so \text{acl}(x) also supports x.

1→3. Take an imaginary x, and suppose that S\subset \atoms is an algebraically closed support of x. Then \text{acl}(x)\cap \atoms is contained in \text{acl}(S)\cap \atoms=S. In particular, \text{acl}(x) is the least algebraically closed support of x.\square

Corollary. If \atoms is ω-categorical, then \atoms 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. \square

Corollary. If \atoms is a Fraisse limit of a free amalgamation class, then \atoms admits least supports.

Proof. See e.g. Lemma 2.7 of the paper  “Simplicity of some automorphism groups” by Dugald Macpherson and Katrin Tent.\square

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.

 

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>