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

Question

Si $A$ , $A'$ , $B$ y $B'$ son conjuntos ordenados linealmente, y en firma $\{<,=\}$ $A \equiv B$ (elementalmente equivalente) y $A'\equiv B'$ ¿es cierto que $A+A' \equiv B+B'$ ? y si es verdad ¿por qué? Busco cualquier ayuda

Answer 1

Bien, siguiendo la pista dada por bof en los comentarios voy a utilizar los juegos de Ehrenfeucht-Fraïssé (EF para abreviar) para dar respuesta a la pregunta. Como aclaración rápida, ya que hay diferentes notaciones/nombres dados a este tipo de construcciones voy a elegir uno de ellos de una vez por todas; mi elección será utilizar la notación y los nombres que se dan en Marker's Teoría de modelos libro. En aras de la exhaustividad, permítanme escribir adecuadamente todas las notaciones y definiciones implicadas.

• Trabajamos con el $\{<, =\}$ -estructuras $\mathscr A, \mathscr A', \mathscr B$ y $ \mathscr B'$ tal que $\mathscr A \equiv \mathscr B$ y $\mathscr A' \equiv \mathscr B'$ . Denotaré los universos de estas estructuras por $A, A', B$ y $B'$ respectivamente.
• El universo de $\mathscr A + \mathscr A'$ es la unión disjunta $A \dot{\cup} A'$ y la interpretación de $<$ en esta estructura es: $$a<a' \ \ \iff \ \ [(a, a' \in A \text{ and } a<a' \text{ in } A)\ \ \text{or} \ \ (a\in A \text{ and } a' \in A')].$$
• Denotamos $G_n(\mathscr M, \mathscr N)$ ser el EF juego de longitud $n$ en el $\{<, =\}$ - estructuras $\mathscr M$ et $\mathscr N$ . Tenga en cuenta que $n\geq 1$ es decir, no hay ningún juego de longitud $0$ .
• Los protagonistas del juego son los jugadores $I$ y jugador $II$ jugador $I$ quiere demostrar que las estructuras son diferentes y el jugador $II$ quiere demostrar que son iguales. Utilizaré la convención estándar de que el jugador $I$ es masculino y el jugador $II$ es mujer.
• Decimos que el jugador $II$ gana el partido en $G_n(\mathscr M, \mathscr N)$ si el conjunto de pares resultante $\{(m_i, n_i) \in M \times N : i=1, \dots, n\}$ es el gráfico de una incrustación parcial; a estrategia ganadora para el jugador $II$ es una secuencia de movimientos que hace que el jugador $II$ ganar el partido.
• Dado que trabajamos sobre la lengua $\{<, =\}$ , $\{(m_i, n_i) \in M \times N : i=1, \dots, n\}$ es el gráfico de una incrustación parcial si $$m_i=m_j \ \ \iff \ \ n_i = n_j$$ y $$m_i < m_j \ \ \iff n_i<n_j$$ para todos $i, j = 1, \dots, n$ .

El resultado que utilizaremos es el siguiente:

Teorema (Teorema 2.4.6 del libro de Marker): Sea $\mathscr L$ sea un lenguaje finito sin símbolos de función y sea $\mathscr M$ y $\mathscr N$ sea $\mathscr L$ -estructuras. Entonces $\mathscr M \equiv \mathscr N$ si y sólo si el jugador $II$ tiene una estrategia ganadora en $G_n(\mathscr M, \mathscr N)$ para todos $n$ .

---

Por el teorema anterior, $\mathscr A \equiv \mathscr B$ implica que el jugador $II$ tiene una estrategia ganadora en $G_n(\mathscr A, \mathscr B)$ para todos $n$ y análogamente para $\mathscr A' \equiv \mathscr B'$ utilizando estos supuestos, demostramos que el jugador $II$ tiene una estrategia ganadora en $G_n(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$ para todos $n$ por inducción en $n$ y luego $\mathscr A + \mathscr A' \equiv \mathscr B + \mathscr B'$ se seguirá de nuevo por el teorema anterior.

La idea es la siguiente. Para cada $n$ , jugador $I$ y $II$ están jugando el juego "público $G_n(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$ pero jugador $II$ está jugando simultáneamente otros dos partidos "privados $G_n(\mathscr A, \mathscr B)$ y $G_n(\mathscr A', \mathscr B')$ . Cuando el jugador $I$ hace un movimiento en el juego $G_n(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$ tiene que elegir un elemento de uno de $A, A', B$ o $B'$ , digamos $a\in A$ antes que el jugador $II$ hace un movimiento en el juego $G_n(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$ replica la jugada del jugador $I$ en su juego privado $G_n(\mathscr A, \mathscr B)$ y luego utiliza el mismo movimiento que hace en $G_n(\mathscr A, \mathscr B)$ para que se mude $G_n(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$ . Por lo tanto, para cada movimiento del jugador $I$ en el juego público, el jugador $II$ replica el movimiento del jugador $I$ en el juego privado apropiado y luego utiliza la misma jugada que hace en este juego privado para hacer una jugada en el juego público; nótese que el juego privado que el jugador $II$ juega cada ronda del juego público depende de la elección del jugador $I$ por lo que si el jugador $I$ elige $b \in B$ entonces jugador $II$ juega en el juego privado $G_n(\mathscr A, \mathscr B)$ y si el jugador $I$ elige $a'\in A'$ entonces jugador $II$ juega en el juego privado $G_n(\mathscr A', \mathscr B')$ .

Con esta idea en mente, la inducción es bastante sencilla. El caso base es $n=1$ y aquí no tenemos mucho que hacer. Digamos (sin pérdida de generalidad) que el jugador $I$ elige $a \in A$ entonces jugador $II$ replica al jugador $I$ en su juego privado $G_n(\mathscr A, \mathscr B)$ y por suposición jugador $II$ tiene una estrategia ganadora en $G_1(\mathscr A, \mathscr B)$ así que ella gana el juego. $G_1(\mathscr A, \mathscr B)$ . Pero esta estrategia ganadora también hace que el jugador $II$ ganar el juego público, así que hemos terminado con el caso $n=1$ . Siendo pedantes, podríamos decir que lo que ocurre aquí es que si $\{(a,b)\}$ es el gráfico de una incrustación parcial $\mathscr A \rightarrow \mathscr B$ entonces también es el gráfico de una incrustación parcial $\mathscr A + \mathscr A' \rightarrow \mathscr B + \mathscr B'$ .

Supongamos ahora como hipótesis inductiva que el jugador $II$ tiene una estrategia ganadora en $G_k(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$ para algunos $k \geq 2$ y considerar el juego $G_{k+1}(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$ esto significa que tenemos una incrustación parcial dada por el gráfico $$\{(a_i, b_i) \in (A\dot{\cup}A')\times(B\dot{\cup}B') : i= 1, \dots, k\}$$ y queremos extenderlo a una incrustación parcial con grafo $$\{(a_i, b_i) \in (A\dot{\cup}A')\times(B\dot{\cup}B') : i= 1, \dots, k+1\}.$$ Por primera $k$ rondas del juego $G_{k+1}(\mathscr A + \mathscr A', \mathscr B + \mathscr B')$ dejar jugador $II$ jugar como en el juego $G_k(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$ y supongamos (de nuevo sin pérdida de generalidad) que el jugador $I$ elige $a_{k+1} \in A$ en redondo $k+1$ . A lo largo del juego público $G_{k+1}(\mathscr A + \mathscr A', \mathscr B + \mathscr B')$ jugador $II$ ha estado jugando dos partidos privados $G_{r_1}(\mathscr A, \mathscr B)$ et $G_{r_2}(\mathscr A', \mathscr B')$ de longitud $0 \leq r_1\leq k+1$ y $0 \leq r_2 \leq k+1$ respectivamente; aquí tenemos que $k+1 = r_1 +r_2$ y longitud $r_1=0$ (digamos) significa que todas las rondas de los juegos privados se llevaron a cabo en $G_{r_2}(\mathscr A', \mathscr B')$ . Por supuesto, el jugador $II$ tiene una estrategia ganadora en $G_{r_1}(\mathscr A, \mathscr B)$ para que pueda elegir $b_{k+1} \in B$ para ganar $G_{r_1}(\mathscr A, \mathscr B)$ Afirmo que la secuencia de movimientos del jugador $II$ en juego $G_k(\mathscr A + \mathscr A', \mathscr B+ \mathscr B')$ seguido de recoger $b_{k+1}$ en redondo $k+1$ es una estrategia ganadora para el jugador $II$ en el juego $G_{k+1}(\mathscr A + \mathscr A', \mathscr B + \mathscr B')$ . Para demostrarlo, basta con demostrar que $$\{(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})\}$$ es una incrustación parcial, y esto a su vez equivale a demostrar que $$a_i=a_j \ \ \iff \ \ b_i=b_j$$ y $$a_i<a_j \ \ \iff \ \ b_i <b_j$$ para todos $i, j \in \{1, 2, \dots, k+1\}$ . Desde $$\{(a_i, b_i) \in (A\dot{\cup}A')\times(B\dot{\cup}B') : i= 1, \dots, k\}$$ ya es una incrustación parcial, basta con comprobar estas tres condiciones para todos los $i \in \{1, 2, \dots, k+1\}$ :

1. $a_i = a_{k+1}$ sólo si $b_i = b_{k+1}$ .
2. $a_i < a_{k+1}$ sólo si $b_i < b_{k+1}$ .
3. $a_{k+1} < a_i$ sólo si $b_{k+1} < b_i$ .

La primera condición es trivial, así que verificamos las dos últimas. Sea $i \in \{1, 2, \dots, k+1\}$ . Entonces:

2. Supongamos que $a_i < a_{k+1}$ . Entonces (por definición de la interpretación de $<$ en $\mathscr A + \mathscr A'$ ) tenemos que $a_i \in A$ y $a_i < a_{k+1}$ en $\mathscr A$ y puesto que el jugador $II$ gana el partido $G_{r_1}(\mathscr A, \mathscr B)$ el conjunto resultante de pares de este juego es el grafo de una incrustación parcial, por lo que $b_i < b_{k+1}$ en $\mathscr B$ y por lo tanto $b_i < b_{k+1}$ en $\mathscr B + \mathscr B'$ . La inversa es exactamente análoga.
3. Supongamos que $a_{k+1} < a_i$ . Entonces (por definición de la interpretación de $<$ en $\mathscr A + \mathscr A'$ ) o bien $a_i \in A$ y $a_{k+1} < a_i$ en $\mathscr A$ o $a_i \in \mathscr A'$ . El primer caso es como el anterior, por lo que consideramos el caso de $a_i \in \mathscr A'$ pero esto es trivial, ya que $a_i \in \mathscr A'$ implica $b_i \in \mathscr B'$ y puesto que $b_{k+1} \in \mathscr B$ tenemos (por definición de la interpretación de $<$ en $\mathscr B + \mathscr B'$ ) que $b_{k+1} < b_i$ en $\mathscr B + \mathscr B'$ .

Esto demuestra que $\{(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})\}$ es una incrustación parcial, concluyendo así el paso inductivo; el resultado se sigue por inducción en $n$ .

Answer 2

Sí. De hecho, una proposición más fuerte $^\dagger$ se cumple: si $A\preceq A'$ y $B\preceq B'$ entonces $A+B\preceq A'+B'$ aunque se añadan predicados para $A$ y $B$ e incluso si $A$ y $B$ sólo están parcialmente ordenados.

Para demostrarlo, observe que $M=(A+B,<,A,B)$ es bidefinible con $M_s=(A\sqcup B,<_A,<_B,A,B)$ (donde $<_A,<_B$ son las restricciones de los respectivos ordenamientos a $A$ y $B$ ). Ahora bien, no es difícil ver que $M_s\preceq N_s=(A'\sqcup B',<_{A'},<_{B'},A',B')$ . Esto se deduce del hecho general de que la unión disjunta (de estructuras arbitrarias) preserva las inclusiones elementales.

Ahora bien, como $M_s\preceq N_s$ se deduce (por bidefinibilidad) que $(A+B,<,A,B)\preceq(A'+B',<,A',B')$ y, por tanto, también $(A+B,<)\preceq (A'+B',<)$ .

( $\dagger$ En caso de que no esté claro por qué esto es más fuerte, observe que si $A\equiv A'$ y $B\equiv B'$ entonces hay $A'',B''$ en el que $A$ , $A'$ y $B,B'$ incrustar elementalmente).