Say that two structures $\mathfrak{A},\mathfrak{B}$ are parametrically equivalent ("$\approx$") iff they have the same underlying set and each primitive relation/function of one is definable (by a single first-order formula, with parameters) in the other. The automorphism group spectrum of a structure $\mathfrak{A}$ is the set of automorphism groups of its parametric equivalents: $$\mathsf{AGS}(\mathfrak{A})=\{Aut(\mathfrak{B}): \mathfrak{B}\approx\mathfrak{A}\}.$$
In general this may be quite large. For example, the following three structures are parametrically equivalent but have quite different automorphism groups:
-
$\mathfrak{A}=(\mathbb{Q};+,<,1)$ has no nontrivial automorphisms. (Indeed every structure is parametrically equivalent to a rigid one – just add constants naming every element.)
-
$\mathfrak{B}=(\mathbb{Q};+,<)$ has some automorphisms: they're exactly the maps $x\mapsto ax$ for $a$ a positive rational.
-
The "torsor-and-betweenness version" of $\mathfrak{B}$, namely $$\mathfrak{C}=(\mathbb{Q}; (x,y,z)\mapsto x-y+z, \{(x,y,z): \vert y-x\vert+\vert z-y\vert=\vert z-x\vert\}),$$ has even more automorphisms: its automorphism group is generated by $Aut(\mathfrak{B})$, multiplication by $-1$, and addition by any fixed rational number.
There's quite a lot (to put it mildly!) known about the relationship between a structure and its automorphism group. I'm curious about the relationship between a structure and its automorphism group spectrum, which is obviously a vastly looser construction. However, at present I know very little about this even in relatively tame situations. I think the following seemingly-trivial question is a good starting point:
Is $\mathsf{AGS}(\mathfrak{A})$ always upwards-directed? That is, if $\mathfrak{A}\approx\mathfrak{B}$, must there be a $\mathfrak{C}$ with $\mathfrak{C}\approx\mathfrak{A}$ and $Aut(\mathfrak{A})\cup Aut(\mathfrak{B})\subseteq Aut(\mathfrak{C})$?
(Of course downwards-directedness is trivial, since we can just combine the structures involved in the obvious way. In fact $\mathsf{AGS}(\mathfrak{A})$ is always a lower semilattice.)
Note that the structures involved do not have to have finite languages, so we have a fair amount of control here.
EDIT: I think it may be helpful to include a bit more "flavor:" namely, $\mathsf{AGS}(\mathfrak{A})$ never (except in trivial situations) has a greatest element.
Suppose we have a relational structure $\mathfrak{A}$ with domain $A$ and primitive relations $R_i$ of arity $n_i$ ($i\in I$) and elements $a,b\in\mathfrak{A}$. Consider the new structure $\hat{\mathfrak{A}}$ defined as follows. The domain of $\hat{\mathfrak{A}}$ is $A$, and the language of $\hat{\mathfrak{A}}$ has a $2n_i$-ary relation $S_i$ for each $n_i$-ary relation $R_i$. We set $S_i^\hat{\mathfrak{A}}$ to be the set of tuples $(x_1,…,x_{2n_i})\in A^{2n_i}$ such that
-
for each $1\le k\le n_i$, either $x_{2k-1}=x_{2k}$ or $\{x_{2k-1},x_{2k}\}\subseteq\{a,b\}$, and
-
in $\mathfrak{A}$ we have $R_i([x_1,x_2],[x_3,x_4],…,[x_{2n_i-1}, x_{2n_i}])$,
where the bracket operation is defined as follows:
$$[u_1,u_2]=\begin{cases}
u_1 & \mbox{ if }u_1=u_2\not\in\{a,b\},\\
a & \mbox{ if }\{u_1,u_2\}\in\{\{a\},\{b\}\},\\
b & \mbox{ if }\{u_1,u_2\}=\{a,b\},\\
\mbox{[doesn'tmatter]} & \mbox{otherwise}.\\
\end{cases}$$
We have $\mathfrak{A}\approx\hat{\mathfrak{A}}$ (just name one of $a$ or $b$), but now the permutation swapping $a$ and $b$ and leaving everything else fixed is in $Aut(\hat{\mathfrak{A}})$. Teasing this out, the only way $\mathsf{AGS}(\mathfrak{A})$ can have a top element is if $\mathfrak{A}$ is parametrically equivalent to a structure where every permutation is an automorphism.
Admittedly things might get more interesting if we weaken the notion of maximality (e.g. ask whether there is $H\in\mathsf{AGS}(\mathfrak{A})$ such that for all $\mathfrak{B}\approx\mathfrak{A}$ there are $\pi_1,…,\pi_j$ such that the group generated by $H\cup\{\pi_1,…,\pi_j\}$ contains $Aut(\mathfrak{B})$) or constrain the language (e.g. forbid relations of arity $>n$ for some "small" $n$) but at least for literal maximality there is no interesting behavior possible.
Best Answer
No, it’s not always upwards-directed.
The underlying set will be $\mathbb Q.$ Define relations $<_n$ by $$a<_n b \iff n<a<b<n+2.$$
Take $\mathfrak A$ to have relations $<_n$ for $n$ even, and take $\mathfrak B$ to have relations $<_n$ for $n$ odd. These models have the same definable sets. $\operatorname{Aut}(\mathfrak A)$ is the group of order-preserving bijections fixing the even integers. $\operatorname{Aut}(\mathfrak B)$ is the group of order-preserving bijections fixing the odd integers.
By a shuffle that does not translate well to text (though I can try if you like!), the map $\tau:x\mapsto x+1$ is a composition of bijections in $\operatorname{Aut}(\mathfrak A)\cup \operatorname{Aut}(\mathfrak B).$ Consider a unary relation $U(x)$ that is definable by a formula $\phi(x,y)$ in $\mathfrak A$ with a tuple $y$ as a parameter. For sufficiently large integers $N,$ the parameter $y$ and all operations and relations used by $\phi$ are invariant under bijections that fix $[-N,N].$ If $U$ is invariant under $\tau^{4N},$ then it must also be invariant under bijections that fix $[3N,5N].$ This can’t happen unless $U$ is either $\emptyset$ or $\mathbb Q.$
In particular $U$ cannot be the interval $(0,2)=\{x:x<_0 2\}.$ So no $\mathfrak C\approx \mathfrak A$ can be $\tau$-invariant.