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.

$\atoms$ has weak elimination of imaginaries,
$\atoms$ has definable supports,
$\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.

Atompress

Least supports and weak elimination of imaginaries

Algebraic and definable closure

Weak elimination of imaginaries

Leave a Reply Cancel reply

Computation with atoms