# Does finite(ish) language imply upwards-directed potential automorphism groups?

This is a follow-up to this question. Briefly, say that two structures $$\mathfrak{A},\mathfrak{B}$$ are parametrically equivalent, and write "$$\mathfrak{A}\approx\mathfrak{B}$$," iff $$(i)$$ they have the same underlying set and $$(ii)$$ each primitive function/relation in one is definable in the other (allowing parameters) - note that $$(ii)$$ is equivalent to saying that each has the same set of definable-with-parameters relations of each arity.

Given a structure $$\mathfrak{A}$$, I'm interested in the "automorphism group spectrum" $$\mathsf{AGS}(\mathfrak{A})=\{Aut(\mathfrak{B}): \mathfrak{B}\approx\mathfrak{A}\}$$. At the above-linked question, Harry West showed that $$\mathsf{AGS}(\mathfrak{A})$$ need not be upwards-directed: even if $$\mathfrak{A}\approx\mathfrak{B}$$ there need be no $$\mathfrak{C}\approx\mathfrak{A}$$ such that $$Aut(\mathfrak{A})\cup Aut(\mathfrak{B})\subseteq Aut(\mathfrak{C})$$. However, that argument crucially used an infinite language.

My question is whether we can still get failures of upwards-directedness:

Is there a structure $$\mathfrak{A}$$ in a finite language (or even a language with only finitely many non-constant symbols - call this "almost finite language") such that $$\mathsf{AGS}(\mathfrak{A})$$ is not upwards-directed?

Note that if $$\mathfrak{X}\approx\mathfrak{Y}$$ and $$\mathfrak{Y}$$ has almost finite language, then there is some $$\mathfrak{X}'\approx\mathfrak{X}$$ with almost finite language such that $$Aut(\mathfrak{X}')=Aut(\mathfrak{X})$$. So arguably restricting to the almost finite language case is a natural thing to do, in a way that looking at actually finite languages isn't (the trivial group is always in $$\mathsf{AGS}(\mathfrak{A})$$ but this requires adding infinitely many constant symbols in general).

No to the title question, yes to the question in the post.$$\DeclareMathOperator{Aut}{Aut}$$ Pick an infinite set $$X.$$ Pick infinite coinfinite sets $$Y_A,Y_B\subseteq X$$ with $$Y_B=Y_A\cup\{y\}$$ for some $$y\not\in Y_A.$$ Define $$\mathfrak A$$ and $$\mathfrak B$$ to have

• underlying set $$X$$
• a unary predicate $$U,$$ interpreted as follows
• $$U^\mathfrak A(z)$$ iff $$z\in Y_A$$
• $$U^\mathfrak B(z)$$ iff $$z\in Y_B$$

These have the same definable sets.

Suppose for contradiction that there is a structure $$\mathfrak C$$ with $$\mathfrak C\approx\mathfrak A$$ and $$\Aut(\mathfrak A)\cup\Aut(\mathfrak B)\subseteq \Aut(\mathfrak C).$$

$$\Aut(\mathfrak A)$$ is the group of symmetries fixing $$Y_A$$ setwise, and $$\Aut(\mathfrak B)$$ is the group of symmetries fixing $$Y_B$$ setwise.

$$\Aut(\mathfrak C)$$ contains every transposition $$\pi$$ swapping an element $$x\in Y_A$$ with an element $$x'\in X\setminus Y_A.$$ I will try to actually describe the symmetry this time. Recall $$y\in Y_B\setminus Y_A.$$ Conjugate $$\pi$$ by a transposition in $$\Aut(\mathfrak A)$$ to reduce to the case $$x'=y.$$ Then use a transposition in $$\Aut(\mathfrak B)$$ to swap $$x$$ and $$x'.$$ (More generally, $$\Aut(\mathfrak C)$$ contains all permutations $$\pi$$ of $$X$$ such that $$|\pi(Y_A)\setminus Y_A|$$ and $$|Y_A\setminus \pi(Y_A)|$$ are finite and of equal cardinality.)

By the assumption $$\mathfrak C\approx\mathfrak A$$ there is a sequence of parameters $$y_1,\dots,y_k\in X$$ and a relation symbol $$R$$ such that

$$z\in Y_A\iff R^{\mathfrak C}(z,y_1,\dots,y_k).$$

Let $$Y_0=\{y_1,\dots, y_k\}.$$ Pick $$x\in Y_A\setminus Y_0$$ and $$x'\in X\setminus (Y_A\cup Y_0).$$ We must have $$R^{\mathfrak C}(x,y_1,\dots,y_k)$$ and $$\neg R^{\mathfrak C}(x',y_1,\dots,y_k).$$ But there is a symmetry of $$\Aut(\mathfrak C)$$ swapping $$x$$ and $$x’$$ and fixing all elements of $$Y_0.$$ This contradicts the choice of $$\mathfrak C.$$

• Coming back to this later, I think the argument can be streamlined. It's enough to show that every transposition is in $Aut(\mathfrak{C})$, since then $Aut(\mathfrak{C})$ contains all finite permutations and so $\mathfrak{C}$ can't have any definable-with-parameters bi-infinite sets. The only case not trivially following from $Aut(\mathfrak{A})\subseteq Aut(\mathfrak{C})$ is a transposition of the form $(uv)$ with $u\in Y_A, v\not\in Y_A$, and this is handled by the assumption $Aut(\mathfrak{B})\subseteq Aut(\mathfrak{C})$ via conjugation as you observe. This is the same argument, of course. Commented Nov 28, 2021 at 22:16
• Also it's worth noting that $\mathsf{FOL}$ plays no role here: adopting the obvious analogies, every logic $\mathcal{L}$ has $\mathfrak{A}\approx_\mathcal{L}\mathfrak{B}$ but non-upwards-directed $\mathsf{AGS}_\mathcal{L}(\mathfrak{A})$. So there's really a coarse observation here about "a bi-infinite set." Commented Nov 28, 2021 at 22:18