Igualdad de conjuntos de isomorfismos locales entre relaciones

Question

Sigo trabajando en las primeras páginas de Poizat Curso de teoría de modelos . Expondré de nuevo las definiciones básicas, para evitar volver a referirme a una pregunta anterior:

Poizat define un isomorfismo $s$ de una relación $R$ a una relación $R'$ como una biyección de $E$ a $E'$ (donde éstos denotan los respectivos conjuntos o universos subyacentes) que preserva la relación dada (es decir, una secuencia $\vec{a}$ satisface $R$ si la secuencia $s(\vec{a})$ también satisface $R'$ ). Tras definir la noción de isomorfismo local de $R$ a $R'$ como un isomorfismo entre restricciones finitas de $R$ a $R'$ (donde una restricción finita es una restricción de la relación a un subconjunto finito del universo original), procede a definir el conjunto $S_p(R, R')$ de $p$ -isomorfismos entre $R$ y $R'$ ( $p$ es un número entero no negativo). La definición es recursiva: $S_0(R,R')$ se define como el conjunto de todos los isomorfismos locales entre $R$ y $R'$ y, para $p\geq 0$ decimos que un isomorfismo local $s$ pertenece al conjunto $S_{p+1}(R,R')$ de acuerdo con las siguientes condiciones:

• Atrás: Por cada $a$ en el universo $E$ de $R$ existe una extensión $t$ de $s$ (es decir, $\mathrm{dom}(s)\subseteq \mathrm{dom}(t)$ y $s$ es la restricción de $t$ a $\mathrm{dom}(s)$ ), definida en $a$ que está en $S_p(R,R')$ ;

• Adelante: Por cada $b$ en el universo $E'$ de $R'$ existe una extensión $t$ de $s$ cuya imagen contiene $b$ que está en $S_p(R,R')$ .

Ahora, en la página 3, invita al lector a probar:

Si, para algunos $p$ , $S_p(R, R') = S_{p+1}(R, R')$ entonces, para todo $q > p$ , $S_p(R, R') = S_q(R, R')$ .

El caso en que $S_p(R, R')$ está vacía es trivial (se deduce directamente del hecho, demostrado por Poizat, de que, para cada $q > p$ , $S_q(R, R') \subseteq S_p(R, R')$ ), así que supongamos que no está vacío. He estado pensando en cómo demostrarlo, pero no he llegado muy lejos. He pensado en usar la inducción sobre $q$ pero no estoy seguro de cómo utilizar la hipótesis de la inducción. ¿Algún consejo?

Answer 1

La idea básica es demostrar que si $S_p(R,R^\prime) = S_q(R,R^\prime)$ entonces $S_{p+1}(R,R^\prime) = S_{q+1}(R,R^\prime)$ . Después de esto podemos utilizar el hecho de que $S_p (R,R^\prime) = S_{p+1} (R,R^\prime)$ para concluir inductivamente que $S_{q}(R,R^\prime) = S_p(R,R^\prime)$ para todos $q \geq p$ .

Para ello, supongamos $s \in S_{p+1} (R,R^\prime)$ y nos limitaremos a demostrar que satisface la condición "Volver" para estar en $S_{q+1} (R,R^\prime)$ (la condición "Forth" es, en esencia, exactamente la misma). Dado $a \in E$ ya que $s \in S_{p+1}(R,R^\prime)$ debe haber una ampliación $t$ de $s$ en $S_p(R,R^\prime)$ tal que $a \in \operatorname{dom} (t)$ . Pero ahora recuerda que $S_q(R,R^\prime) = S_p(R,R^\prime)$ Así que $t \in S_q(R,R^\prime)$ . Así, para cada $a \in E$ existe una ampliación $t$ de $s$ en $S_q(R,R^\prime)$ tal que $a \in \operatorname{dom} (t)$ .

---

Otra forma de verlo es la siguiente: la conexión entre $S_p(R,R^\prime)$ y $S_{p+1}(R,R^\prime)$ tiene absolutamente nada con el número natural $p$ sino que sólo implica el configure de isomorfismos parciales. En su lugar, podríamos definir para cada familia $S$ de isomorfismos locales el conjunto $\operatorname{EF}(S)$ (para E hrenfeucht- F raïssé ) es la colección de todos los isomorfismos locales que satisfacen las condiciones de Back y Forth con respecto a $S$ :

$s \in \operatorname{EF}(S)$ si

1. para cada $a \in E$ hay un $t \in S$ ampliando $s$ con $a \in \operatorname{dom}(t)$ y
2. para cada $b \in E^\prime$ hay un $t \in S$ ampliando $s$ con $b \in \operatorname{ran}(t)$ .

Ahora debe quedar absolutamente claro que $S = T$ implica $\operatorname{EF}(S) = \operatorname{EF}(T)$ . Además, por definición $S_{p+1}(R,R^\prime) = \operatorname{EF}(S_p(R,R^\prime))$ .

Por lo tanto, si $S_{p}(R,R^\prime) = S_{p+1}(R,R^\prime)$ tendremos, por ejemplo, que $$S_{p+1}(R,R^\prime) = \operatorname{EF}(S_{p}(R,R^\prime)) = \operatorname{EF}(S_{p+1}(R,R^\prime)) = S_{p+2}(R,R^\prime)$$ y podemos continuar de esta manera por inducción para demostrar que $S_{q}(R,R^\prime) = S_{p}(R,R^\prime)$ para todos $q \geq p$ .