An illustration of the Cherlin-Hrushovski construction
The following construction, due to Cherlin and Hrushovski, provides an example of an \(\aleph_0\)-categorical theory which is not \(G\)-finite, nor which has the small index property: take an infinite set \(A\), and expand it by equivalence relations \(E_n\) on each power \(A^n\) such that each \(E_n\) has two infinite classes and the finite imaginaries \(\{A^n/E_n\}\) are all independent. Call the resulting structure \(\mathfrak{A}\).
\(\operatorname{Aut}(\mathfrak{A})\) then has \(\left(\mathbb{Z}/2 \mathbb{Z} \right)^{\omega}\) as a quotient.
By increasing the number of equivalence classes, one can encode as a quotient of \(\operatorname{Aut}(\mathfrak{A})\) arbitrary countable products of finite symmetric groups. By introducing more predicates, one can cut down on the number of symmetries and thus encode as a quotient of \(\operatorname{Aut}(\mathfrak{A})\) arbitrary countable products of finite groups. By introducing relations which interpret functions between finite sets of imaginaries in \(\mathfrak{A}^{\operatorname{eq}}\), one can encode as a quotient of \(\operatorname{Aut}(\mathfrak{A})\) an arbitrary separable profinite group. For more detail, see Evans and Hewitt’s 1990 paper Counterexamples to a conjecture on relative categoricity.
The purpose of this post is to explicitly write down (indeed, even draw, with many colors!) what the structure \(\mathfrak{A}\) encoding \(\left(\mathbb{Z}/2 \mathbb{Z} \right)^{\omega}\) as a quotient of \(\operatorname{Aut}(\mathfrak{A})\) looks like. The existence of \(\mathfrak{A}\) is usually justified by taking a Fraïssé limit of an appropriate class of structures, which to me always seems rather black-boxy. So, I went to the trouble of writing down what \(\mathfrak{A}\) might look like. As it turns out, our calculation of \(\mathfrak{A}\) will show, rather nicely, why one should expect such an \(\mathfrak{A}\) to pop out of a Fraïssé construction in the first place.
In an appropriate category \(\mathbf{Struct}\) of multisorted first-order structures and interpretations, we can achieve \((\mathbb{Z}/2\mathbb{Z})^{\omega}\) as a quotient of some \(\operatorname{Aut}(\mathfrak{A})\) with much less work. In an abandoned chapter of my master’s thesis, I showed that given a projective diagram of groups \(G_i\) with projective limit \(G\), one can take the invariant/canonical structures of the actions \[\operatorname{Inv}\left(G_i \curvearrowright G_i\right)\] and form their colimit \(\mathfrak{B}\) in \(\mathbf{Struct}\), which has a sort for each \(G_i \curvearrowright G_i\), with definable functions linking the sorts corresponding to the transition maps in the original projective diagram. The automorphism group of \(\mathfrak{B}\) is \(G\), and it is easy to find a multisorted structure \(\mathfrak{A}\) which interprets \(\mathfrak{B}\) such that the induced continuous map \(\operatorname{Aut}(\mathfrak{A}) \to \operatorname{Aut}(\mathfrak{B})\) is surjective.
Of course, putting the equivalence relations on disjoint sorts completely bypasses the interesting part of the problem of writing down the Cherlin-Hrushovski construction in a \(1\)-sorted structure \(\mathfrak{A}\): we have to arrange the equivalence relations on \(A\), \(A^2\), \(A^3, \dots\) to be independent despite interference from the diagonal and projection maps linking the powers of \(A\).
Here’s an example that shows that this is not a vacuous problem. Given an equivalence relation \(E\) on \(A\), there is an induced equivalence relation \(E'\) on \(A \times A\), given by the kernel of the natural map \[A \times A \twoheadrightarrow A/E \times A/E, \text{ by } (a_1, a_2) \mapsto (a_1/E, a_2/E).\]
(Incidentally, this shows that a product of imaginary sorts is an imaginary sort in \(T^{\operatorname{eq}}\).)
Then it is impossible to find an automorphism of \(A\) which fixes the \(A/E\) while permuting \(A^2/E'\): if \(a\) and \(b\) are not \(E\)-equivalent, then \((a,b)\) and \((b,a)\) are not \(E'\)-equivalent, and any automorphism which interchanges the \(E\)-classes of \(a\) and \(b\) will interchange the \(E'\)-classes of \((a,b)\) and \((b,a)\).
So let’s proceed with the illustration. Let’s just try to encode \(\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}\) on \(A\) and \(A \times A\) first. Getting just \(\mathbb{Z}/2\mathbb{Z}\) is easy, since any equivalence relation with two infinite classes on \(A\) will do. So, our task is to figure out how to specify \(E_2\) on \(A \times A\). The identity map always gives us the identity group element \((0,0)\), so now we just have to achieve the generators \((0,1)\) and \((1,0)\).
We’ll let the underlying set \(A\) be an interval, say \([-1,1]\), and we’ll specify \(E_1\) on \(A\) by coloring \(A\) half green and half-purple:
and so \(A/E_1\) consists of green and purple:
Now we have to figure out how to color \(A \times A\) blue and orange:
Let’s go to a toy example and temporarily replace \(A\) with the finite set \(A = \{a,b,c,d\}\), such that \(E_1 \rightrightarrows A\) is given by coloring \(a,b\) green and \(c,d\) purple. Here’s \(A \times A\):
Since the identity permutation fixes everything, an immediate candidate for an automorphism of \(A\) which fixes green and purple but which interchanges blue and orange (whatever we specify that to be) is the permutation which interchanges \(a\) with \(b\) and \(c\) with \(d\). Here’s what it does on pairs:
Similarly, assuming the previous guess is consistent, if we want to interchange green and purple but fix blue and orange, an immediate candidate is given by interchanging \(a\) with \(c\) and \(b\) with \(d\). Here is its action:
Now, by just eyeballing this we can work out a coloring. Suppose that \((d,a)\) was orange. Then since the red arrows are supposed to permute \(E_2\)-classes, \((c,b)\) must be blue. Since the blue arrows are supposed to fix \(E_2\)-classes, \((b,c)\) must be orange and \((a,d)\) must be blue. Continuing in this way, we arrive at the following coloring of \(A \times A\):
Now let’s go back to \(A = [-1,1]\). There’s an obvious way of tranposing the previous coloring to \(A \times A = [-1,1] \times [-1,1]\), by cutting up \(A \times A\) into \(16\) pieces:
Mutatis mutandis, everything works: the following automorphism induces \((0,1)\):
While this automorphism induces \((1,0)\):
Now it’s clear what to do to extend this to an encoding of \((\mathbb{Z}/2\mathbb{Z})^n\) for any \(n\), e.g. to get \(n = 3\), color \(A^3\) as follows:
and so on, as long as the subdivisions are all happening along a single axis.
Going back to the finite model \(A = \{a,b,c,d\}\), we see that we don’t have the resolution to see \((0,0,1)\) in the \(n = 3\) case, so we have to use \(2^3\) elements instead. But then the same reasoning that we used for \(n = 2\) works.
The fact that we reasoned with automorphisms of finite models (\(A = \{a,b,c,d\}\)) and then extended the automorphisms to an infinite model (\(A = [-1, 1]\)) is an instance of the ultrahomogeneity property of a Fraïssé limit. Indeed, the Fraïssé construction proceeds by taking all possible finite models that we could perform our previous argument with and smashing them together. Another consequence of the general Fraïssé-theoretic machinery is that the resulting \(\mathfrak{A}\) is existentially closed. This rules out the possibility of obstructions like \(E_2 = E’\) as we noted above.
