$A+A' \equiv B+B'$?

Question

If $A$, $A'$, $B$ and $B'$ are linearly ordered sets, and in signature $\{<,=\}$ $A \equiv B$ (elementarily equivalent) and $A'\equiv B'$, is it true that $A+A' \equiv B+B'$? and if it is true why? I'm looking for any help

Answer 1

Okay, so following the hint given by bof in the comments I'm going to use Ehrenfeucht-Fraïssé (EF for short) games to provide an answer to the question. As a quick disclaimer, since there are different notations/names given to these sort of constructions I'll just pick one of these once and for all; my choice will be to use the notation and names as given in Marker's Model Theory book. For the sake of completeness, let me properly write all the involved notation and definitions.

• We work with the $\{<, =\}$-structures $\mathscr A, \mathscr A', \mathscr B$ and $ \mathscr B'$ such that $\mathscr A \equiv \mathscr B$ and $\mathscr A' \equiv \mathscr B'$. I'll denote the universes of these structures by $A, A', B$ and $B'$, respectively.
• The universe of $\mathscr A + \mathscr A'$ is the disjoint union $A \dot{\cup} A'$ and the interpretation of $<$ in this structure is: $$a<a' \ \ \iff \ \ [(a, a' \in A \text{ and } a<a' \text{ in } A)\ \ \text{or} \ \ (a\in A \text{ and } a' \in A')].$$
• We denote $G_n(\mathscr M, \mathscr N)$ to be the EF game of length $n$ on the $\{<, =\}$-structures $\mathscr M$ and $\mathscr N$. Note that $n\geq 1$, i.e. there is no game of length $0$.
• The players of the game are player $I$ and player $II$; player $I$ wants to show that the structures are different and player $II$ wants to show that they are equal. I will use the standard convention that player $I$ is male and player $II$ is female.
• We say that player $II$ wins the game in $G_n(\mathscr M, \mathscr N)$ if the resulting set of pairs $\{(m_i, n_i) \in M \times N : i=1, \dots, n\}$ is the graph of a partial embedding; a winning strategy for player $II$ is a sequence of moves that makes player $II$ win the game.
• Since we work over the language $\{<, =\}$, $\{(m_i, n_i) \in M \times N : i=1, \dots, n\}$ is the graph of a partial embedding if $$m_i=m_j \ \ \iff \ \ n_i = n_j$$ and $$m_i < m_j \ \ \iff n_i<n_j$$ for all $i, j = 1, \dots, n$.

The result that we will make use of is the following:

Theorem (Theorem 2.4.6 in Marker's book): Let $\mathscr L$ be a finite language without function symbols and let $\mathscr M$ and $\mathscr N$ be $\mathscr L$-structures. Then $\mathscr M \equiv \mathscr N$ if and only if player $II$ has a winning strategy in $G_n(\mathscr M, \mathscr N)$ for all $n$.

---

By the above theorem, $\mathscr A \equiv \mathscr B$ implies that player $II$ has a winning strategy in $G_n(\mathscr A, \mathscr B)$ for all $n$ and similarly for $\mathscr A' \equiv \mathscr B'$; using these assumptions, we show that player $II$ has a winning strategy in $G_n(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$ for all $n$ by induction on $n$, and then $\mathscr A + \mathscr A' \equiv \mathscr B + \mathscr B'$ will follow again by the above theorem.

The idea is as follows. For each $n$, player $I$ and $II$ are playing the "public" game $G_n(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$, but player $II$ is playing simultaneously other two "private" games $G_n(\mathscr A, \mathscr B)$ and $G_n(\mathscr A', \mathscr B')$. When player $I$ makes a move in the game $G_n(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$ he has to pick an element of one of $A, A', B$ or $B'$, say $a\in A$; before player $II$ makes a move in the game $G_n(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$, she replicates the move of player $I$ in her private game $G_n(\mathscr A, \mathscr B)$ and then uses the same move that she does in $G_n(\mathscr A, \mathscr B)$ to make her move in $G_n(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$. Therefore, for each move of player $I$ in the public game, player $II$ replicates the move of player $I$ in the appropiate private game and then uses the same move that she does in this private game to make a move in the public game; note that the private game that player $II$ plays each round of the public game depends on the choice of player $I$, so if player $I$ chooses $b \in B$ then player $II$ plays in the private game $G_n(\mathscr A, \mathscr B)$, and if player $I$ chooses $a'\in A'$ then player $II$ plays in the private game $G_n(\mathscr A', \mathscr B')$.

With this idea in mind the induction is pretty straightforward. The base case is $n=1$, and here we don't have much to do. Say (without loss of generality) that player $I$ picks $a \in A$; then player $II$ replicates player $I$'s move in her private game $G_n(\mathscr A, \mathscr B)$ and by assumption player $II$ has a winning strategy in $G_1(\mathscr A, \mathscr B)$, so she wins the game $G_1(\mathscr A, \mathscr B)$. But this winning strategy also makes player $II$ win the public game, so we're done with the case $n=1$. Being pedantic, we could say that what happens here is that if $\{(a,b)\}$ is the graph of a partial embedding $\mathscr A \rightarrow \mathscr B$ then it is also the graph of a partial embedding $\mathscr A + \mathscr A' \rightarrow \mathscr B + \mathscr B'$.

Assume now as inductive hypothesis that player $II$ has a winning strategy in $G_k(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$ for some $k \geq 2$ and consider the game $G_{k+1}(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$; this means that we have a partial embedding given by the graph $$\{(a_i, b_i) \in (A\dot{\cup}A')\times(B\dot{\cup}B') : i= 1, \dots, k\}$$ and we want to extend it to a partial embedding with graph $$\{(a_i, b_i) \in (A\dot{\cup}A')\times(B\dot{\cup}B') : i= 1, \dots, k+1\}.$$ For the first $k$ rounds of the game $G_{k+1}(\mathscr A + \mathscr A', \mathscr B + \mathscr B')$ let player $II$ play as in the game $G_k(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$ and assume (again without loss of generality) that player $I$ picks $a_{k+1} \in A$ in round $k+1$. Throughout the public game $G_{k+1}(\mathscr A + \mathscr A', \mathscr B + \mathscr B')$ player $II$ has been playing two private games $G_{r_1}(\mathscr A, \mathscr B)$ and $G_{r_2}(\mathscr A', \mathscr B')$ of length $0 \leq r_1\leq k+1$ and $0 \leq r_2 \leq k+1$, respectively; here we have that $k+1 = r_1 +r_2$ and length $r_1=0$ (say) means that all rounds of the private games were carried out in $G_{r_2}(\mathscr A', \mathscr B')$. By assumption, player $II$ has a winning strategy in $G_{r_1}(\mathscr A, \mathscr B)$, so she can pick $b_{k+1} \in B$ to win $G_{r_1}(\mathscr A, \mathscr B)$; I claim that the sequence of moves of player $II$ in game $G_k(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$ followed by picking $b_{k+1}$ in round $k+1$ is a winning strategy for player $II$ in the game $G_{k+1}(\mathscr A + \mathscr A', \mathscr B + \mathscr B')$. To show this we just need to prove that $$\{(a_i, b_i) \in (A\dot{\cup}A')\times(B\dot{\cup}B') : i= 1, \dots, k\} \cup \{(a_{k+1}, b_{k+1})\}$$ is a partial embedding, and this in turn amounts to show that $$a_i=a_j \ \ \iff \ \ b_i=b_j$$ and $$a_i<a_j \ \ \iff \ \ b_i <b_j$$ for all $i, j \in \{1, 2, \dots, k+1\}$. Since $$\{(a_i, b_i) \in (A\dot{\cup}A')\times(B\dot{\cup}B') : i= 1, \dots, k\}$$ is already a partial embedding, it suffices to check these three conditions for all $i \in \{1, 2, \dots, k+1\}$:

1. $a_i = a_{k+1}$ if and only if $b_i = b_{k+1}$.
2. $a_i < a_{k+1}$ if and only if $b_i < b_{k+1}$.
3. $a_{k+1} < a_i$ if and only if $b_{k+1} < b_i$.

The first condition is trivial, so we verify the last two. Let $i \in \{1, 2, \dots, k+1\}$. Then:

2. Suppose that $a_i < a_{k+1}$. Then (by definition of the interpretation of $<$ in $\mathscr A + \mathscr A'$) we have that $a_i \in A$ and $a_i < a_{k+1}$ in $\mathscr A$, and since player $II$ wins the game $G_{r_1}(\mathscr A, \mathscr B)$, the resulting set of pairs of this game is the graph of a partial embedding, so $b_i < b_{k+1}$ in $\mathscr B$ and hence $b_i < b_{k+1}$ in $\mathscr B + \mathscr B'$. The converse is exactly analogous.
3. Suppose that $a_{k+1} < a_i$. Then (by definition of the interpretation of $<$ in $\mathscr A + \mathscr A'$) either $a_i \in A$ and $a_{k+1} < a_i$ in $\mathscr A$ or $a_i \in \mathscr A'$. The former case is as the one above, so we consider the case of $a_i \in \mathscr A'$; but this is trivial, since $a_i \in \mathscr A'$ implies $b_i \in \mathscr B'$, and since $b_{k+1} \in \mathscr B$ we have (by definition of the interpretation of $<$ in $\mathscr B + \mathscr B'$) that $b_{k+1} < b_i$ in $\mathscr B + \mathscr B'$.

This shows that $\{(a_i, b_i) \in (A\dot{\cup}A')\times(B\dot{\cup}B') : i= 1, \dots, k\} \cup \{(a_{k+1}, b_{k+1})\}$ is a partial embedding, concluding thus the inductive step; the result hence follows by induction on $n$.

Answer 2

Yes. In fact, a stronger proposition$^\dagger$ holds: if $A\preceq A'$ and $B\preceq B'$, then $A+B\preceq A'+B'$, even if you add predicates for $A$ and $B$, and even if $A$ and $B$ are only partially ordered.

To show this, notice that $M=(A+B,<,A,B)$ is bidefinable with $M_s=(A\sqcup B,<_A,<_B,A,B)$ (where $<_A,<_B$ are the restrictions of the respective orderings to $A$ and $B$). Now, it is not hard to see that $M_s\preceq N_s=(A'\sqcup B',<_{A'},<_{B'},A',B')$. This follows from the general fact that disjoint union (of arbitrary structures) preserves elementary inclusions.

Now,since $M_s\preceq N_s$, it follows (by bidefinability) that $(A+B,<,A,B)\preceq(A'+B',<,A',B')$, and hence also $(A+B,<)\preceq (A'+B',<)$.

($\dagger$ In case it is not clear why this is stronger, notice that if $A\equiv A'$ and $B\equiv B'$, then there are $A'',B''$ into which $A$, $A'$ and $B,B'$ embed elementarily.)