Un isomorfismo no cambia ninguna verdad

El enunciado, textual: «Supongamos que $F : 𝐀 \to 𝐁$ es un isomorfismo. Sea $φ =_{d} φ (v_{1}, \dots, v_{n}) \in F^{τ}$ . Entonces $𝐀 ⊨ φ [a_{1}, a_{2}, \dots, a_{n}] sii 𝐁 ⊨ φ [F (a_{1}), F (a_{2}), \dots, F (a_{n})]$ para cada $a_{1}, a_{2}, \dots, a_{n} \in A$ . (Puede usar el Ejercicio (28).)» Es el Ejercicio 35 de la Guía 11, la versión en notación declaratoria del Lema 7 de la Guía 10 (p. 12–13).

Como está enunciado con $φ =_{d} φ (v_{1}, \dots, v_{n})$ , se resuelve dentro de la notación declaratoria: Lema 4, Convención 6 y Lema 6 de la Guía 11. Y el «puede usar el Ejercicio 28» quiere decir que ese resultado se enuncia y se cita sin probarlo de nuevo.

01 · Qué dice, en criollo

Un isomorfismo es un cambio de nombres: $𝐁$ es $𝐀$ con cada elemento $a$ rebautizado $F (a)$ . Lo que $𝐀$ dice de $a_{1}, \dots, a_{n}$ , $𝐁$ lo dice de los nombres nuevos, $F (a_{1}), \dots, F (a_{n})$ , y viceversa. El ejercicio es probar que ninguna fórmula puede notar el cambio.

Un caso concreto. Sea $τ = ({c}, {f}, {r}, {(f, 1), (r, 1)})$ . En $𝐀$ el universo es ${0, 1, 2, 3}$ , $c^{𝐀} = 0$ , $f^{𝐀} (x) = x + 1$ módulo 4 y $r^{𝐀}$ son los pares, ${0, 2}$ . En $𝐁$ el universo es el mismo, $c^{𝐁} = 0$ , $f^{𝐁} (y) = y - 1$ módulo 4 y $r^{𝐁} = {0, 2}$ . La función $F (x) = - x$ módulo 4 —que manda 0 a 0, 1 a 3, 2 a 2 y 3 a 1— es un isomorfismo: es biyectiva, $F (0) = 0$ , $F (x + 1) = - x - 1 = F (x) - 1$ , manda pares en pares, y su inversa (que es ella misma) cumple lo mismo de $𝐁$ en $𝐀$ . Con $φ = r (f (x_{1}))$ y la declaración $φ =_{d} φ (x_{1})$ : $𝐀 ⊨ φ [1]$ porque $f^{𝐀} (1) = 2$ es par, y $𝐁 ⊨ φ [F (1)] = φ [3]$ porque $f^{𝐁} (3) = 2$ también. Medido con las once fórmulas del widget y los 16 pares $(a_{1}, a_{2})$ , la verdad en $𝐀$ y en $𝐁$ coincide siempre.

Lo interesante es al revés: qué pasa si a $F$ le falta una de las propiedades de isomorfismo. Cada una se gasta en un caso distinto de la prueba, y sin ella ese caso —y sólo ése— se cae. Eso es lo que muestra el widget.

02 · Las herramientas

Homomorfismo e isomorfismo (Guía 10, p. 11–12). $F : A \to B$ es homomorfismo de $𝐀$ en $𝐁$ si (1) $F (c^{𝐀}) = c^{𝐁}$ para todo $c \in 𝒞$ ; (2) $F (f^{𝐀} (a_{1}, \dots, a_{n})) = f^{𝐁} (F (a_{1}), \dots, F (a_{n}))$ para $f \in ℱ_{n}$ ; (3) $(a_{1}, \dots, a_{n}) \in r^{𝐀}$ implica $(F (a_{1}), \dots, F (a_{n})) \in r^{𝐁}$ para $r \in ℛ_{n}$ . Un isomorfismo de $𝐀$ en $𝐁$ es un homomorfismo biyectivo cuya inversa $F^{- 1}$ es un homomorfismo de $𝐁$ en $𝐀$ .

El Ejercicio 28, que se puede usar: si $F : 𝐀 \to 𝐁$ es un homomorfismo y $t =_{d} t (v_{1}, \dots, v_{n})$ , entonces $F (t^{𝐀} [a_{1}, \dots, a_{n}]) = t^{𝐁} [F (a_{1}), \dots, F (a_{n})]$ para cada $a_{1}, \dots, a_{n} \in A$ . Su prueba está en Un homomorfismo conmuta con los términos.

Los niveles (Guía 9): $F_{0}^{τ}$ son las fórmulas atómicas, y $F_{k + 1}^{τ}$ es $F_{k}^{τ}$ más las fórmulas $\neg φ$ , $(φ η ψ)$ y $Q v φ$ con $φ, ψ \in F_{k}^{τ}$ , $η \in {\land, \lor, \to, \leftrightarrow}$ , $Q \in {\forall, \exists}$ y $v \in Var$ .

Lema 4 (Lectura única de fórmulas declaradas, Guía 11, p. 9):

Sea $τ$ un tipo cualquiera y $φ \in F^{τ}$ . Supongamos $φ =_{d} φ (v_{1}, \dots, v_{n})$ . Entonces se da una y sólo una de las siguientes:

$φ = (t \equiv s)$ , con $t, s \in T^{τ}$ , únicos;
$φ = r (t_{1}, \dots, t_{m})$ , con $r \in ℛ_{m}$ y $t_{1}, \dots, t_{m} \in T^{τ}$ , únicos;
$φ = (φ_{1} η φ_{2})$ , con $η \in {\land, \lor, \to, \leftrightarrow}$ , $φ_{1}, φ_{2} \in F^{τ}$ , únicas;
$φ = \neg φ_{1}$ , con $φ_{1} \in F^{τ}$ , única;
$φ = Q v_{j} φ_{1}$ , con $Q \in {\forall, \exists}$ , $j \in {1, \dots, n}$ y $φ_{1} \in F^{τ}$ , únicas;
$φ = Q v φ_{1}$ , con $Q \in {\forall, \exists}$ , $v \in Var - {v_{1}, \dots, v_{n}}$ y $φ_{1} \in F^{τ}$ , únicas.

Más aún, si $φ \in F_{k + 1}^{τ}$ , entonces cuando se da (3) las fórmulas $φ_{1}$ y $φ_{2}$ están en $F_{k}^{τ}$ , y cuando se da (4), (5) o (6) la fórmula $φ_{1}$ está en $F_{k}^{τ}$ .

Convención 6 (Guía 11, p. 10): declarado $φ =_{d} φ (v_{1}, \dots, v_{n})$ , en el caso (1) del Lema 4 se suponen hechas $t =_{d} t (v_{1}, \dots, v_{n})$ y $s =_{d} s (v_{1}, \dots, v_{n})$ ; en el (2), $t_{i} =_{d} t_{i} (v_{1}, \dots, v_{n})$ para cada $i$ ; en el (3), $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n})$ y $φ_{2} =_{d} φ_{2} (v_{1}, \dots, v_{n})$ ; en el (4) y el (5), $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n})$ ; y en el (6), $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n}, v)$ .

Lema 6 (Carácter recursivo de $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ , Guía 11, p. 11; la guía lo acepta sin prueba). Supongamos $φ =_{d} φ (v_{1}, \dots, v_{n})$ , sea $𝐀$ un modelo de tipo $τ$ y sean $a_{1}, \dots, a_{n} \in A$ . Entonces:

si $φ = (t \equiv s)$ : $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ sii $t^{𝐀} [a_{1}, \dots, a_{n}] = s^{𝐀} [a_{1}, \dots, a_{n}]$ ;
si $φ = r (t_{1}, \dots, t_{m})$ : $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ sii $(t_{1}^{𝐀} [a_{1}, \dots, a_{n}], \dots, t_{m}^{𝐀} [a_{1}, \dots, a_{n}]) \in r^{𝐀}$ ;
si $φ = (φ_{1} \land φ_{2})$ : sii $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{n}]$ y $𝐀 ⊨ φ_{2} [a_{1}, \dots, a_{n}]$ ;
si $φ = (φ_{1} \lor φ_{2})$ : sii $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{n}]$ o $𝐀 ⊨ φ_{2} [a_{1}, \dots, a_{n}]$ ;
si $φ = (φ_{1} \to φ_{2})$ : sii $𝐀 ⊨ φ_{2} [a_{1}, \dots, a_{n}]$ o $𝐀 ⊭ φ_{1} [a_{1}, \dots, a_{n}]$ ;
si $φ = (φ_{1} \leftrightarrow φ_{2})$ : sii ya sea $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{n}]$ y $𝐀 ⊨ φ_{2} [a_{1}, \dots, a_{n}]$ , o $𝐀 ⊭ φ_{1} [a_{1}, \dots, a_{n}]$ y $𝐀 ⊭ φ_{2} [a_{1}, \dots, a_{n}]$ ;
si $φ = \neg φ_{1}$ : sii $𝐀 ⊭ φ_{1} [a_{1}, \dots, a_{n}]$ ;
si $φ = \forall v_{j} φ_{1}$ : sii $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{j - 1}, a, a_{j + 1}, \dots, a_{n}]$ , para todo $a \in A$ ;
si $φ = \forall v φ_{1}$ , con $v \notin {v_{1}, \dots, v_{n}}$ : sii $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{n}, a]$ , para todo $a \in A$ ;
si $φ = \exists v_{j} φ_{1}$ : sii $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{j - 1}, a, a_{j + 1}, \dots, a_{n}]$ , para algún $a \in A$ ;
si $φ = \exists v φ_{1}$ , con $v \notin {v_{1}, \dots, v_{n}}$ : sii $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{n}, a]$ , para algún $a \in A$ .

Los casos (3)–(11) del Lema 6 usan las declaraciones de la Convención 6: sin ellas, $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{n}, a]$ no denota nada. Los lemas de esta sección son la herramienta que el encabezado manda usar; la lectura única y los lemas Menú se usan sin enunciar.

03 · La mariposa: dónde se gasta cada hipótesis

Qué inducción. El Lema 6 calcula la verdad de $φ$ a partir de la de $φ_{1}$ y $φ_{2}$ , y el «más aún» del Lema 4 dice que están un nivel más abajo. Inducción en $k$ con $φ \in F_{k}^{τ}$ , por la Regla de Inducción desde 0.

El ${Enu}_{k}$ , y por qué todo va adentro. El caso (6) es $Q v φ_{1}$ con $v$ fuera de la lista, y la Convención 6 declara $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n}, v)$ : $n + 1$ variables. Si el ${Enu}_{k}$ dijera «sean $n$ y $v_{1}, \dots, v_{n}$ fijos; para toda $φ \in F_{k}^{τ}$ con $φ =_{d} φ (v_{1}, \dots, v_{n})$ …», la hipótesis inductiva no se podría aplicar a $φ_{1}$ , que está declarada con otra lista. Lo mismo con los elementos: en el caso (5) se aplica la hipótesis a $φ_{1}$ con $a$ en el lugar de $a_{j}$ , así que «para cada $a_{1}, \dots, a_{n}$ » tiene que estar adentro. Por eso el ${Enu}_{k}$ empieza con «cualesquiera sean $n$ , las variables $v_{1}, \dots, v_{n}$ y $φ \in F_{k}^{τ}$ ».

Cada hipótesis, en su caso. La ida (de $𝐀$ a $𝐁$ ) de las atómicas sólo necesita que $F$ sea homomorfismo; la vuelta es donde se gasta el resto:

$(t \equiv s)$ : de $F (t^{𝐀} [\dots]) = F (s^{𝐀} [\dots])$ volver a $t^{𝐀} [\dots] = s^{𝐀} [\dots]$ es que $F$ sea inyectiva.
$r (t_{1}, \dots, t_{m})$ : de $(F (t_{1}^{𝐀} [\dots]), \dots) \in r^{𝐁}$ volver a $(t_{1}^{𝐀} [\dots], \dots) \in r^{𝐀}$ es la condición (3) para $F^{- 1}$ .
$\forall$ y $\exists$ : un $\forall$ en $𝐁$ recorre todo $B$ , y la hipótesis inductiva sólo habla de los $F (a)$ ; que eso sea todo $B$ es que $F$ sea sobre. En el $\forall$ se usa en la ida; en el $\exists$ , en la vuelta, para que el testigo de $𝐁$ tenga una preimagen.

Los conectivos no usan nada: son la hipótesis inductiva en las dos piezas, y como es un «sii», sirve también para las negaciones que esconden $\to$ , $\leftrightarrow$ y $\neg$ .

Lo medido, sobre los 16 pares $(a_{1}, a_{2})$ y las once fórmulas. Con la $F$ no inyectiva —el resto en 2, sobre $𝐁 = {0, 1}$ con $f (y) = y + 1$ módulo 2, $c = 0$ y $r = {0}$ , que es homomorfismo sobre y cumple la condición (3) también al revés— sólo difieren las fórmulas con $\equiv$ entre cosas distintas: $(x_{1} \equiv x_{2})$ , $(f (f (x_{1})) \equiv x_{2})$ y $(x_{1} \equiv c)$ , en 4 pares cada una, siempre con $𝐀 ⊭$ y $𝐁 ⊨$ . Con la biyectiva cuya inversa no es homomorfismo —la identidad sobre $𝐁$ con $r^{𝐁} = {0, 1, 2}$ — difieren las que miran $r$ : $r (x_{1})$ y $r (f (x_{1}))$ con $𝐀 ⊭$ y $𝐁 ⊨$ , y $\neg r (x_{1})$ y $(r (x_{1}) \to r (f (f (x_{1}))))$ al revés, en 4 pares cada una. Con la no sobre —la inclusión en $𝐁 = {0, 1, 2, 3, e}$ con $f (e) = e$ — no falla ninguna atómica ni ninguna fórmula sin cuantificadores: fallan $\forall x_{3} (r (x_{3}) \lor r (f (x_{3})))$ y $\forall x_{3} \neg (f (x_{3}) \equiv x_{3})$ con $𝐀 ⊨$ y $𝐁 ⊭$ , y $\exists x_{3} (f (x_{3}) \equiv x_{3})$ con $𝐀 ⊭$ y $𝐁 ⊨$ , en los 16 pares. El $\forall$ se rompe en la ida y el $\exists$ en la vuelta, como dice la prueba.

04 · El escarabajo: la prueba escrita

Prueba. Usaremos la Regla de Inducción desde 0. Para cada $k \in ω$ sea ${Enu}_{k}$ el enunciado:

${Enu}_{k}$ : Cualesquiera sean los modelos $𝐀$ y $𝐁$ de tipo $τ$ , el isomorfismo $F : 𝐀 \to 𝐁$ , el número $n \geq 0$ , las variables $v_{1}, \dots, v_{n}$ y la fórmula $φ \in F_{k}^{τ}$ tales que $φ =_{d} φ (v_{1}, \dots, v_{n})$ , se tiene que $𝐀 ⊨ φ [a_{1}, \dots, a_{n}] sii 𝐁 ⊨ φ [F (a_{1}), \dots, F (a_{n})]$ para cada $a_{1}, \dots, a_{n} \in A$ .

Hagamos lo que pide la Regla de Inducción desde 0.

Prueba de que ${Enu}_{0}$ es verdadero. Sean $𝐀$ , $𝐁$ modelos de tipo $τ$ , $F : 𝐀 \to 𝐁$ un isomorfismo, $φ \in F_{0}^{τ}$ con $φ =_{d} φ (v_{1}, \dots, v_{n})$ y $a_{1}, \dots, a_{n} \in A$ . Como $φ$ es atómica, de los casos del Lema 4 se da (1) o (2).

Caso $φ = (t \equiv s)$ . Por la Convención 6, $t =_{d} t (v_{1}, \dots, v_{n})$ y $s =_{d} s (v_{1}, \dots, v_{n})$ .

𝐀 ⊨ φ [a_{1}, \dots, a_{n}]

sii t^{𝐀} [a_{1}, \dots, a_{n}] = s^{𝐀} [a_{1}, \dots, a_{n}]

Lema 6 (1), en 𝐀

sii F (t^{𝐀} [a_{1}, \dots, a_{n}]) = F (s^{𝐀} [a_{1}, \dots, a_{n}])

⇒: F es función; ⇐: F es inyectiva

sii t^{𝐁} [F (a_{1}), \dots, F (a_{n})] = s^{𝐁} [F (a_{1}), \dots, F (a_{n})]

Ejercicio 28, en t y en s

sii 𝐁 ⊨ φ [F (a_{1}), \dots, F (a_{n})]

Lema 6 (1), en 𝐁

Caso $φ = r (t_{1}, \dots, t_{m})$ . Por la Convención 6, $t_{i} =_{d} t_{i} (v_{1}, \dots, v_{n})$ para $i = 1, \dots, m$ .

𝐀 ⊨ φ [a_{1}, \dots, a_{n}]

sii (t_{1}^{𝐀} [a_{1}, \dots, a_{n}], \dots, t_{m}^{𝐀} [a_{1}, \dots, a_{n}]) \in r^{𝐀}

Lema 6 (2), en 𝐀

sii (F (t_{1}^{𝐀} [a_{1}, \dots, a_{n}]), \dots, F (t_{m}^{𝐀} [a_{1}, \dots, a_{n}])) \in r^{𝐁}

ver abajo

sii (t_{1}^{𝐁} [F (a_{1}), \dots, F (a_{n})], \dots, t_{m}^{𝐁} [F (a_{1}), \dots, F (a_{n})]) \in r^{𝐁}

Ejercicio 28, en cada tᵢ

sii 𝐁 ⊨ φ [F (a_{1}), \dots, F (a_{n})]

Lema 6 (2), en 𝐁

El segundo «sii», con $e_{i} = t_{i}^{𝐀} [a_{1}, \dots, a_{n}] \in A$ . La ida es la condición (3) de homomorfismo para $F$ aplicada a $(e_{1}, \dots, e_{m}) \in r^{𝐀}$ . Para la vuelta, si $(F (e_{1}), \dots, F (e_{m})) \in r^{𝐁}$ , la condición (3) para $F^{- 1}$ , que es homomorfismo de $𝐁$ en $𝐀$ , da $(F^{- 1} (F (e_{1})), \dots, F^{- 1} (F (e_{m}))) \in r^{𝐀}$ , es decir $(e_{1}, \dots, e_{m}) \in r^{𝐀}$ .

Prueba de que ${Enu}_{k}$ implica ${Enu}_{k + 1}$ . Supongamos que vale ${Enu}_{k}$ . Sean $𝐀$ , $𝐁$ modelos de tipo $τ$ , $F : 𝐀 \to 𝐁$ un isomorfismo, $φ \in F_{k + 1}^{τ}$ con $φ =_{d} φ (v_{1}, \dots, v_{n})$ y $a_{1}, \dots, a_{n} \in A$ . Hay dos casos.

Caso $φ \in F_{k}^{τ}$ . Como vale ${Enu}_{k}$ , se cumple la conclusión de ${Enu}_{k + 1}$ .

Caso $φ \in F_{k + 1}^{τ} - F_{k}^{τ}$ . $φ$ no es atómica, porque las atómicas están en $F_{0}^{τ} \subseteq F_{k}^{τ}$ . Por el Lema 4 se da (3), (4), (5) o (6), y por su «más aún» las fórmulas $φ_{1}$ , $φ_{2}$ que aparecen están en $F_{k}^{τ}$ . Escribimos $\vec{a}$ por la lista $a_{1}, \dots, a_{n}$ sólo dentro de los corchetes, y $F (\vec{a})$ por $F (a_{1}), \dots, F (a_{n})$ .

Caso (3), $φ = (φ_{1} η φ_{2})$ . Por la Convención 6, $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n})$ y $φ_{2} =_{d} φ_{2} (v_{1}, \dots, v_{n})$ , y como $φ_{1}, φ_{2} \in F_{k}^{τ}$ , por ${Enu}_{k}$ (con los mismos $𝐀$ , $𝐁$ , $F$ , $v_{1}, \dots, v_{n}$ y $a_{1}, \dots, a_{n}$ ): $𝐀 ⊨ φ_{1} [\vec{a}]$ sii $𝐁 ⊨ φ_{1} [F (\vec{a})]$ , y $𝐀 ⊨ φ_{2} [\vec{a}]$ sii $𝐁 ⊨ φ_{2} [F (\vec{a})]$ . Llamemos (H) a estas dos equivalencias; negando los dos lados, también $𝐀 ⊭ φ_{i} [\vec{a}]$ sii $𝐁 ⊭ φ_{i} [F (\vec{a})]$ . Según $η$ :

$η = \land$ : $𝐀 ⊨ φ [\vec{a}]$ sii $𝐀 ⊨ φ_{1} [\vec{a}]$ y $𝐀 ⊨ φ_{2} [\vec{a}]$ (Lema 6 (3)) sii $𝐁 ⊨ φ_{1} [F (\vec{a})]$ y $𝐁 ⊨ φ_{2} [F (\vec{a})]$ (H) sii $𝐁 ⊨ φ [F (\vec{a})]$ (Lema 6 (3)).
$η = \lor$ : $𝐀 ⊨ φ [\vec{a}]$ sii $𝐀 ⊨ φ_{1} [\vec{a}]$ o $𝐀 ⊨ φ_{2} [\vec{a}]$ (Lema 6 (4)) sii $𝐁 ⊨ φ_{1} [F (\vec{a})]$ o $𝐁 ⊨ φ_{2} [F (\vec{a})]$ (H) sii $𝐁 ⊨ φ [F (\vec{a})]$ (Lema 6 (4)).
$η = \to$ : $𝐀 ⊨ φ [\vec{a}]$ sii $𝐀 ⊨ φ_{2} [\vec{a}]$ o $𝐀 ⊭ φ_{1} [\vec{a}]$ (Lema 6 (5)) sii $𝐁 ⊨ φ_{2} [F (\vec{a})]$ o $𝐁 ⊭ φ_{1} [F (\vec{a})]$ (H) sii $𝐁 ⊨ φ [F (\vec{a})]$ (Lema 6 (5)).
$η = \leftrightarrow$ : $𝐀 ⊨ φ [\vec{a}]$ sii ( $𝐀 ⊨ φ_{1} [\vec{a}]$ y $𝐀 ⊨ φ_{2} [\vec{a}]$ ) o ( $𝐀 ⊭ φ_{1} [\vec{a}]$ y $𝐀 ⊭ φ_{2} [\vec{a}]$ ) (Lema 6 (6)) sii ( $𝐁 ⊨ φ_{1} [F (\vec{a})]$ y $𝐁 ⊨ φ_{2} [F (\vec{a})]$ ) o ( $𝐁 ⊭ φ_{1} [F (\vec{a})]$ y $𝐁 ⊭ φ_{2} [F (\vec{a})]$ ) (H) sii $𝐁 ⊨ φ [F (\vec{a})]$ (Lema 6 (6)).

Caso (4), $φ = \neg φ_{1}$ . Por la Convención 6, $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n})$ , y $φ_{1} \in F_{k}^{τ}$ . Entonces $𝐀 ⊨ φ [\vec{a}]$ sii $𝐀 ⊭ φ_{1} [\vec{a}]$ (Lema 6 (7)) sii $𝐁 ⊭ φ_{1} [F (\vec{a})]$ ( ${Enu}_{k}$ , negando los dos lados) sii $𝐁 ⊨ φ [F (\vec{a})]$ (Lema 6 (7)).

Caso (5), $φ = \forall v_{j} φ_{1}$ , con $j \in {1, \dots, n}$ . Por la Convención 6, $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n})$ , y $φ_{1} \in F_{k}^{τ}$ . Veamos cada implicación.

(⇒) Supongamos $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ . Por el Lema 6 (8), $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{j - 1}, a, a_{j + 1}, \dots, a_{n}]$ para todo $a \in A$ . Por ${Enu}_{k}$ , aplicado a $φ_{1}$ con los elementos $a_{1}, \dots, a_{j - 1}, a, a_{j + 1}, \dots, a_{n}$ , se tiene $𝐁 ⊨ φ_{1} [F (a_{1}), \dots, F (a_{j - 1}), F (a), F (a_{j + 1}), \dots, F (a_{n})]$ para todo $a \in A$ . Sea $b \in B$ . Como $F$ es sobre, $b = F (a)$ para algún $a \in A$ , y entonces $𝐁 ⊨ φ_{1} [F (a_{1}), \dots, F (a_{j - 1}), b, F (a_{j + 1}), \dots, F (a_{n})]$ . Como $b$ era arbitrario, el Lema 6 (8) en $𝐁$ da $𝐁 ⊨ φ [F (a_{1}), \dots, F (a_{n})]$ .

(⇐) Supongamos $𝐁 ⊨ φ [F (a_{1}), \dots, F (a_{n})]$ . Por el Lema 6 (8), $𝐁 ⊨ φ_{1} [F (a_{1}), \dots, F (a_{j - 1}), b, F (a_{j + 1}), \dots, F (a_{n})]$ para todo $b \in B$ . Sea $a \in A$ ; tomando $b = F (a)$ , $𝐁 ⊨ φ_{1} [F (a_{1}), \dots, F (a_{j - 1}), F (a), F (a_{j + 1}), \dots, F (a_{n})]$ , y por ${Enu}_{k}$ , $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{j - 1}, a, a_{j + 1}, \dots, a_{n}]$ . Como $a$ era arbitrario, el Lema 6 (8) da $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ .

Caso (5), $φ = \exists v_{j} φ_{1}$ . (⇒) Si $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ , por el Lema 6 (10) hay $a \in A$ con $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{j - 1}, a, a_{j + 1}, \dots, a_{n}]$ ; por ${Enu}_{k}$ , $𝐁 ⊨ φ_{1} [F (a_{1}), \dots, F (a_{j - 1}), F (a), F (a_{j + 1}), \dots, F (a_{n})]$ , y como $F (a) \in B$ , el Lema 6 (10) en $𝐁$ da $𝐁 ⊨ φ [F (a_{1}), \dots, F (a_{n})]$ . (⇐) Si $𝐁 ⊨ φ [F (a_{1}), \dots, F (a_{n})]$ , por el Lema 6 (10) hay $b \in B$ con $𝐁 ⊨ φ_{1} [F (a_{1}), \dots, F (a_{j - 1}), b, F (a_{j + 1}), \dots, F (a_{n})]$ . Como $F$ es sobre, $b = F (a)$ para algún $a \in A$ ; por ${Enu}_{k}$ , $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{j - 1}, a, a_{j + 1}, \dots, a_{n}]$ , y el Lema 6 (10) da $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ .

Caso (6), $φ = \forall v φ_{1}$ , con $v \notin {v_{1}, \dots, v_{n}}$ . Por la Convención 6, $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n}, v)$ , y $φ_{1} \in F_{k}^{τ}$ . Acá ${Enu}_{k}$ se aplica con $n + 1$ variables, $v_{1}, \dots, v_{n}, v$ . (⇒) Si $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ , por el Lema 6 (9) $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{n}, a]$ para todo $a \in A$ ; por ${Enu}_{k}$ , $𝐁 ⊨ φ_{1} [F (a_{1}), \dots, F (a_{n}), F (a)]$ para todo $a \in A$ . Dado $b \in B$ , como $F$ es sobre, $b = F (a)$ para algún $a$ , así que $𝐁 ⊨ φ_{1} [F (a_{1}), \dots, F (a_{n}), b]$ para todo $b \in B$ , y el Lema 6 (9) da $𝐁 ⊨ φ [F (a_{1}), \dots, F (a_{n})]$ . (⇐) Si $𝐁 ⊨ φ [F (a_{1}), \dots, F (a_{n})]$ , por el Lema 6 (9) $𝐁 ⊨ φ_{1} [F (a_{1}), \dots, F (a_{n}), b]$ para todo $b \in B$ ; dado $a \in A$ , con $b = F (a)$ y ${Enu}_{k}$ , $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{n}, a]$ , y el Lema 6 (9) da $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ .

Caso (6), $φ = \exists v φ_{1}$ , con $v \notin {v_{1}, \dots, v_{n}}$ . Con $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n}, v)$ . (⇒) Si $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ , por el Lema 6 (11) hay $a \in A$ con $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{n}, a]$ ; por ${Enu}_{k}$ , $𝐁 ⊨ φ_{1} [F (a_{1}), \dots, F (a_{n}), F (a)]$ , y el Lema 6 (11) da $𝐁 ⊨ φ [F (a_{1}), \dots, F (a_{n})]$ . (⇐) Si $𝐁 ⊨ φ [F (a_{1}), \dots, F (a_{n})]$ , por el Lema 6 (11) hay $b \in B$ con $𝐁 ⊨ φ_{1} [F (a_{1}), \dots, F (a_{n}), b]$ ; como $F$ es sobre, $b = F (a)$ con $a \in A$ ; por ${Enu}_{k}$ , $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{n}, a]$ , y el Lema 6 (11) da $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ .

Con esto vale ${Enu}_{k + 1}$ . Por la Regla de Inducción desde 0, ${Enu}_{k}$ vale para todo $k \in ω$ . Si $φ \in F^{τ}$ y $φ =_{d} φ (v_{1}, \dots, v_{n})$ , entonces $φ \in F_{k}^{τ}$ para algún $k$ , y ${Enu}_{k}$ da $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ sii $𝐁 ⊨ φ [F (a_{1}), \dots, F (a_{n})]$ para cada $a_{1}, \dots, a_{n} \in A$ . ∎

05 · Lo que hace perder puntos, y lo que se lleva

Lo que hace perder puntos. Un ${Enu}_{k}$ con $n$ o los elementos fijos afuera: el caso (6) lo deja sin hipótesis inductiva aplicable. Olvidar el caso (6) entero, o tratarlo como el (5): ahí la declaración de $φ_{1}$ tiene una variable más y el Lema 6 que se usa es el (9) o el (11), con $a$ al final. Hacer la vuelta de $(t \equiv s)$ sin decir «inyectiva», o la de $r (t_{1}, \dots, t_{m})$ diciendo «porque $F$ es homomorfismo»: la condición (3) va en un solo sentido, y la vuelta es la de $F^{- 1}$ . Decir «análogo» en el $\exists$ : usa sobre en la otra dirección. Y abrir las convenciones a asignaciones $\vec{b}$ , que es la prueba de la Guía 10 y no la que pide la lista.

Lo que se lleva. Las atómicas son el Ejercicio 28. El Ejercicio 30 es esta misma prueba con menos hipótesis: un homomorfismo sobre, sin inyectiva ni inversa, a cambio de que la fórmula no tenga $\neg$ , $\to$ ni $\leftrightarrow$ ; queda sólo la ida. El molde de los cuatro casos de cuantificador es el mismo del inciso (b) del Ejercicio 27 y del Ejercicio 26. Y este resultado es el que justifica el criterio NoDefinible: un isomorfismo de $𝐀$ en $𝐀$ deja fijo todo elemento definible, porque la fórmula que lo define dice lo mismo de $a$ y de $F (a)$ (el Ejercicio 18 lo usa).

Para tener a mano

Inducción en $k$ con $φ \in F_{k}^{τ}$ , Regla de Inducción desde 0; en el ${Enu}_{k}$ , adentro: $𝐀$ , $𝐁$ , $F$ , $n$ , $v_{1}, \dots, v_{n}$ , $φ$ y $a_{1}, \dots, a_{n}$ .
Atómicas por el Lema 4 (1)–(2), la Convención 6, el Lema 6 (1)–(2) y el Ejercicio 28. La vuelta de $\equiv$ usa inyectiva; la de $r$ , que $F^{- 1}$ es homomorfismo.
Conectivos: el Lema 6 (3)–(7) y la hipótesis inductiva, que como es un «sii» también vale negada.
Cuantificadores: cuatro casos, Lema 6 (8)–(11). Sobre se usa en la ida del $\forall$ y en la vuelta del $\exists$ . En el caso $v \notin {v_{1}, \dots, v_{n}}$ , $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n}, v)$ y el elemento nuevo va al final.
Sin inyectiva falla una igualdad; sin la inversa, una relación; sin sobre, un cuantificador.