"put together" elementary substructures

Question

I’m interested in the following, broad, question: imagine I have two structures $\mathfrak M$ and $\mathfrak N$ in some language $\mathcal L$, and I know that adding a relation symbol $r_1$, interpreted as $a_1$ in the first structure and as $b_1$ in the second, I know $(\mathfrak M, a_1)$ is an elementary substructure of $(\mathfrak N, b_1)$ and suppose the same for some other relation symbol $r_2$, so $(\mathfrak M, a_2)$ is an elementary substructure of $(\mathfrak N, b_2)$.

Is there something I can say about some other structure in a richer language, that is equivalent to this fact? For example, if $r_1$ and $r_2$ were constant symbols, the two conditions stated before would be equivalent to $(\mathfrak M, a_1,a_2)$ being an elementary substructure of $(\mathfrak N, b_1, b_2)$. If I've got relation or function symbols this seems very false and much harder.

Are there results about facts similar to this one? I don’t need precisely the full language with both the relation symbols $r_1$ and $r_2$, but maybe it would be enough to have only one additional relation symbol that is at the same time containing the information of the other two relation symbols.

Maybe there is some partial result if I consider a $\Delta_0$-elementary substructure or some other weaker condition instead of full elementarity?

I know the question is vague and broad, but I am looking for "pathways" to follow and not answers.

Thanks in advance. :)

Answer 1

Let me rephrase your question in terms that would seem more natural to a model-theorist.

Fix a language $L$ and two expansions $L\subseteq L_1$ and $L\subseteq L_2$. Let $L_\cup = L_1\cup L_2$. Suppose $N$ is an $L_\cup$-structure, and $M$ is an $L_\cup$-substructure. Further, assume that in both reducts to $L_1$ and $L_2$, $M$ is an elementary substructure of $N$: $M|_{L_1}\preceq N|_{L_1}$ and $M|_{L_2}\preceq N|_{L_2}$. What can we say about the question of whether $M$ is an $L_\cup$-elementary substructure of $N$: $M\preceq N$?

This is a slight generalization of your question: You had a base language $L$ and expansions $L_1 = L\cup \{R_1\}$ and $L_2 = L\cup \{R_2\}$, i.e., each expansion just added a single new relation symbol. I think the general case of arbitrary expansions doesn't add much more complexity.

We certainly don't have $M\preceq N$ in general. Here is a very simple example: Let $L$ be the empty language, $L_1 = \{P\}$ and $L_2 = \{Q\}$, where $P$ and $Q$ are unary predicates. Let $M = \mathbb{N}$ and $N = \mathbb{N}\cup \{\infty\}$. In both structures, interpret $P$ as the set of even natural numbers and $Q$ as the set of odd natural numbers. Then $(M,P)\preceq (N,P)$, since the theory of a set with an infinite and coinfinite predicate has quantifier elimination. Similary, $(M,Q)\preceq (N,Q)$. But $(M,P,Q)$ and $(N,P,Q)$ disagree about the sentence $\exists x\, (\lnot P(x)\land \lnot Q(x))$.

It doesn't get much simpler than that: even with just unary predicates over the empty language, $M$ and $N$ can disagree about sentences with a single quantifier. So I don't think there's much to be said in the general case.

On the other hand, I can give you a positive answer under some very strong hypotheses on $M$. This actually comes from a paper (arXiv) I wrote with Chieu-Minh Tran and Erik Walsberg.

Using the same notation as above, we define an $L_\cup$-structure $M$ to be interpolative if it satisfies the following property: Whenever $X_1\subseteq M^n$ is an $L_1$-definable set and $X_2\subseteq M^n$ is an $L_2$-definable set, if $X_1\cap X_2 = \varnothing$, then there exists an $L$-definable set $Z$ such that $X_1\subseteq Z$ and $X_2\subseteq M^n\setminus Z$. That is, disjoint definable sets in the two expansions are separated by a definable set in the base language.

(Equivalently, replacing $X_2$ with its complement: whenever $X_1$ is an $L_1$-definable set and $X_2$ is an $L_2$-definable set and $X_1\subseteq X_2$, there is an $L$-definable set $Z$ with $X_1\subseteq Z\subseteq X_2$, i.e., an $L$-definable interpolant between $X_1$ and $X_2$. This justifies the name and makes the connection with the Craig interpolation theorem more clear.)

Let $T_1$ be an $L_1$-theory and $T_2$ and $L_2$-theory, such that $T_1$ and $T_2$ have the same set $T$ of $L$-consequences. Let $T_\cup = T_1\cup T_2$. We say the interpolative fusion $T_\cup^*$ exists if the class of interpolative models of $T_\cup$ is elementary.

Now if $T_\cup^*$ exists and $M$ and $N$ are models of $T_\cup^*$ (in particular, they are interpolative $L_\cup$-structures) and $M|_{L_1}\preceq N|_{L_1}$ and $M|_{L_2}\preceq N|_{L_2}$, then $M\preceq N$. See Theorem 2.7 in the linked paper.

Answer 2

Take $\mathfrak{N}$ to be the graph with vertex set $\mathbb{Q}\times \{0,1\}$ and edge relation $(a,b)E(c,d)\iff a\le c$. Let $\mathfrak{M}$ be the subgraph of $\mathfrak{N}$ consisting of vertices with negative first coordinate; it's easy to see that $\mathfrak{M}\prec\mathfrak{N}$.

Now let $U,V$ be sets of rationals such that $U_{<0}=V_{<0}$, $U\not=V$, and $(\mathfrak{M}, U_{<0})\prec (\mathfrak{N}, U)$ and $(\mathfrak{M}, V_{<0})\prec (\mathfrak{N}, V)$. For example:

$U$ = the set of dyadic rationals, $V$ = the negative dyadic rationals and the positive triadic rationals.

Since $U\not=V$ but $U_{<0}=V_{<0}$ we must have $$(\mathfrak{M},U_{<0},V_{<0})\not\prec (\mathfrak{N},U,V).$$