Sobre y sin negación, la verdad viaja de A a B

El enunciado, textual: «Supongamos $F:𝐀\to 𝐁$ es un homomorfismo suryectivo. Sea $\phi \in F^{\tau }$ tal que los símbolos $\to$ $\leftrightarrow$ $\neg$ no ocurren en $\phi$. Pruebe que entonces

$$𝐀\models \phi [(a_1,a_2,\dots )]\text{ implica }𝐁\models \phi [(F(a_1),F(a_2),\dots )]$$

para cada $(a_1,a_2,\dots )\in A^{𝐍}$.»

Es el Ejercicio 37 de la Guía 11 escrito sin notación declaratoria: con asignaciones infinitas y ${\downarrow }_i^a$, como piden los ejercicios 1 a 17 de la lista. La versión declaratoria, con los dos contraejemplos que pide la guía, es el Ejercicio 30.

01 · Qué pide, en criollo

Una fórmula que sólo usa $\equiv$, nombres de relación, $\wedge$, $\vee$, $\forall$ y $\exists$ —ninguna negación, ninguna implicación, ninguna doble implicación— y que es verdadera en $𝐀$ para una asignación, sigue siendo verdadera en $𝐁$ para la asignación que resulta de aplicarle $F$ a cada elemento. Se le pide a $F$ que sea homomorfismo y que sea sobre. Y la conclusión va en un solo sentido: dice «implica», no «si y sólo si».

Un ejemplo. Sea $\tau =(\varnothing ,\{\mathrm{g}\},\{\mathrm{r}\},\{(\mathrm{g},1),(\mathrm{r},1)\})$. En $𝐀$ el universo es $A=\{1,2,3\}$, con ${\mathrm{g}}^{𝐀}$ dada por $1\mapsto 2$, $2\mapsto 3$, $3\mapsto 3$, y ${\mathrm{r}}^{𝐀}=\{1,2\}$. En $𝐁$ el universo es $B=\{p,q\}$, con ${\mathrm{g}}^{𝐁}(p)={\mathrm{g}}^{𝐁}(q)=q$ y ${\mathrm{r}}^{𝐁}=\{p,q\}$. La función $F$ con $F(1)=p$ y $F(2)=F(3)=q$ es un homomorfismo sobre (no es inyectiva). La fórmula

$$\forall x_1(\mathrm{r}(x_1)\vee (x_1\equiv x_2))$$

es verdadera en $𝐀$ para $\overrightarrow{a}=(1,3,3,\dots )$: el $1$ y el $2$ están en ${\mathrm{r}}^{𝐀}$, y el $3$ es el valor de $x_2$. En $𝐁$, para $(F(1),F(3),F(3),\dots )=(p,q,q,\dots )$, también: $p$ y $q$ están en ${\mathrm{r}}^{𝐁}$. En cambio $\neg \mathrm{r}(x_1)$ es verdadera en $𝐀$ para $(3,1,1,\dots )$, porque $3\notin {\mathrm{r}}^{𝐀}$, y falsa en $𝐁$ para $(q,p,p,\dots )$, porque $q\in {\mathrm{r}}^{𝐁}$. La negación no viaja.

Para abreviar, como en la Guía 10 (p. 12–13): si $\overrightarrow{a}=(a_1,a_2,\dots )\in A^{𝐍}$, se escribe $F(\overrightarrow{a})$ para $(F(a_1),F(a_2),\dots )\in B^{𝐍}$.

02 · Las herramientas

Homomorfismo (Guía 10, p. 11–12). $F:A\to B$ es un 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 cada $f\in {ℱ}_n$ y $a_1,\dots ,a_n\in A$; (3) $(a_1,\dots ,a_n)\in r^{𝐀}$ implica $(F(a_1),\dots ,F(a_n))\in r^{𝐁}$, para todo $r\in {ℛ}_n$ y $a_1,\dots ,a_n\in A$. Las tres, con ejemplos, en Homomorfismos e isomorfismos de estructuras.

El valor de un término (Guía 10, p. 1). Para $\overrightarrow{a}=(a_1,a_2,\dots )\in A^{𝐍}$: (i) si $t=x_i$, $t^{𝐀}[\overrightarrow{a}]=a_i$; (ii) si $t=c\in 𝒞$, $t^{𝐀}[\overrightarrow{a}]=c^{𝐀}$; (iii) si $t=f(t_1,\dots ,t_n)$, $t^{𝐀}[\overrightarrow{a}]=f^{𝐀}(t_1^{𝐀}[\overrightarrow{a}],\dots ,t_n^{𝐀}[\overrightarrow{a}])$. En la guía son las cláusulas (1), (2) y (3); acá van con números romanos para no confundirlas con las condiciones de homomorfismo.

La relación ⊨ (Guía 10, p. 4). ${\downarrow }_i^a(\overrightarrow{a})$ es la asignación que resulta de reemplazar en $\overrightarrow{a}$ el $i$-ésimo elemento por $a$. Las cláusulas que se usan son seis:

• (1) $𝐀\models (t\equiv s)[\overrightarrow{a}]$ sii $t^{𝐀}[\overrightarrow{a}]=s^{𝐀}[\overrightarrow{a}]$;
• (2) $𝐀\models r(t_1,\dots ,t_m)[\overrightarrow{a}]$ sii $(t_1^{𝐀}[\overrightarrow{a}],\dots ,t_m^{𝐀}[\overrightarrow{a}])\in r^{𝐀}$;
• (3) $𝐀\models ({\phi }_1\wedge {\phi }_2)[\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ y $𝐀\models {\phi }_2[\overrightarrow{a}]$;
• (4) $𝐀\models ({\phi }_1\vee {\phi }_2)[\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ o $𝐀\models {\phi }_2[\overrightarrow{a}]$;
• (8) $𝐀\models \forall x_i{\phi }_1[\overrightarrow{a}]$ sii para cada $a\in A$, $𝐀\models {\phi }_1[{\downarrow }_i^a(\overrightarrow{a})]$;
• (9) $𝐀\models \exists x_i{\phi }_1[\overrightarrow{a}]$ sii hay un $a\in A$ tal que $𝐀\models {\phi }_1[{\downarrow }_i^a(\overrightarrow{a})]$.

Los niveles (Guía 9). $F_0^{\tau }$ son las fórmulas atómicas, $(t\equiv s)$ y $r(t_1,\dots ,t_n)$, y $F_{k+1}^{\tau }$ es $F_k^{\tau }$ más las fórmulas $\neg {\phi }_1$, $({\phi }_1\wedge {\phi }_2)$, $({\phi }_1\vee {\phi }_2)$, $({\phi }_1\to {\phi }_2)$, $({\phi }_1\leftrightarrow {\phi }_2)$, $\forall v{\phi }_1$ y $\exists v{\phi }_1$, con ${\phi }_1,{\phi }_2\in F_k^{\tau }$ y $v\in \mathrm{Var}$. Toda fórmula está en algún $F_k^{\tau }$. Que cada fórmula se descomponga de una sola manera es la lectura única de fórmulas, que la lista deja usar sin enunciar.

Hay dos cosas más que se usan y no están en esa lista: el Lema 6 de la Guía 10 y una igualdad entre asignaciones. Las dos se enuncian y se prueban en la sección siguiente.

03 · El Lema 6 y la igualdad de asignaciones

Lema 6 (Guía 10, p. 12). Sea $F:𝐀\to 𝐁$ un homomorfismo. Entonces $F(t^{𝐀}[(a_1,a_2,\dots )])=t^{𝐁}[(F(a_1),F(a_2),\dots )]$ para cada $t\in T^{\tau }$ y cada $(a_1,a_2,\dots )\in A^{𝐍}$.

Dice que da lo mismo calcular el término en $𝐀$ y llevar el resultado a $B$, que llevar la asignación a $B$ y calcular ahí. Es lo que convierte las atómicas en las condiciones de homomorfismo.

Prueba. Sea $F:𝐀\to 𝐁$ un homomorfismo. Usaremos la Regla de Inducción desde 0. Para cada $k\in \omega$ sea ${\mathrm{Enu}}_k$ el enunciado:

${\mathrm{Enu}}_k$: para cada $t\in T_k^{\tau }$ y cada $\overrightarrow{a}=(a_1,a_2,\dots )\in A^{𝐍}$, se tiene $F(t^{𝐀}[\overrightarrow{a}])=t^{𝐁}[F(\overrightarrow{a})]$.

• ${\mathrm{Enu}}_0$ es verdadero. Sean $t\in T_0^{\tau }=\mathrm{Var}\cup 𝒞$ y $\overrightarrow{a}\in A^{𝐍}$. Si $t=x_i$, por (i) $t^{𝐀}[\overrightarrow{a}]=a_i$, y $F(a_i)$ es el $i$-ésimo elemento de $F(\overrightarrow{a})$, que por (i) es $t^{𝐁}[F(\overrightarrow{a})]$. Si $t=c\in 𝒞$, por (ii) y la condición (1) de homomorfismo, $F(t^{𝐀}[\overrightarrow{a}])=F(c^{𝐀})=c^{𝐁}=t^{𝐁}[F(\overrightarrow{a})]$.
• ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$. Supongamos que vale ${\mathrm{Enu}}_k$, y sean $t\in T_{k+1}^{\tau }$ y $\overrightarrow{a}\in A^{𝐍}$. Caso $t\in T_k^{\tau }$: vale por ${\mathrm{Enu}}_k$. Caso $t=f(t_1,\dots ,t_n)$ con $n\ge 1$, $f\in {ℱ}_n$ y $t_1,\dots ,t_n\in T_k^{\tau }$: por (iii), por la condición (2) de homomorfismo, por ${\mathrm{Enu}}_k$ aplicado a cada $t_i$, y por (iii) en $𝐁$, $$F(t^{𝐀}[\overrightarrow{a}])=F(f^{𝐀}(t_1^{𝐀}[\overrightarrow{a}],\dots ,t_n^{𝐀}[\overrightarrow{a}]))=f^{𝐁}(F(t_1^{𝐀}[\overrightarrow{a}]),\dots ,F(t_n^{𝐀}[\overrightarrow{a}]))=f^{𝐁}(t_1^{𝐁}[F(\overrightarrow{a})],\dots ,t_n^{𝐁}[F(\overrightarrow{a})])=t^{𝐁}[F(\overrightarrow{a})].$$

Por la Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ vale para todo $k$, y como todo término está en algún $T_k^{\tau }$, vale el lema. ∎

La igualdad de asignaciones. Para $\overrightarrow{a}\in A^{𝐍}$, $a\in A$ y $j\in 𝐍$,

$$F({\downarrow }_j^a(\overrightarrow{a}))={\downarrow }_j^{F(a)}(F(\overrightarrow{a}))$$

Prueba. Las dos son infinituplas de elementos de $B$; se comparan lugar por lugar. En el lugar $j$, la de la izquierda tiene $F$ aplicada al $j$-ésimo de ${\downarrow }_j^a(\overrightarrow{a})$, que es $F(a)$, y la de la derecha tiene $F(a)$. En un lugar $i\ne j$, la de la izquierda tiene $F(a_i)$, porque ${\downarrow }_j^a$ no toca el lugar $i$, y la de la derecha tiene el $i$-ésimo de $F(\overrightarrow{a})$, que es $F(a_i)$. ∎

04 · La mariposa: qué caso pide qué

La inducción. La fórmula se arma por niveles, así que se induce en el nivel: Regla de Inducción desde 0, con un ${\mathrm{Enu}}_k$ que habla de las fórmulas de $F_k^{\tau }$. Hay dos cosas que tienen que estar adentro del ${\mathrm{Enu}}_k$.

• La asignación, cuantificada. En el caso $\exists x_j{\phi }_1$, lo que se sabe de $𝐀$ es que ${\phi }_1$ vale en ${\downarrow }_j^a(\overrightarrow{a})$, otra asignación. Para usar la hipótesis inductiva ahí, ${\mathrm{Enu}}_k$ tiene que hablar de todas las asignaciones. Si se fija $\overrightarrow{a}$ antes de empezar la inducción, ${\mathrm{Enu}}_k$ sólo dice algo de esa $\overrightarrow{a}$, y el caso $\exists$ queda sin hipótesis.
• La restricción sobre los símbolos. «$\neg$, $\to$ y $\leftrightarrow$ no ocurren en $\phi$» va en ${\mathrm{Enu}}_k$, y se hereda: si $\phi =({\phi }_1\wedge {\phi }_2)$, todo símbolo de ${\phi }_1$ es un símbolo de $\phi$, así que en ${\phi }_1$ tampoco ocurren.

Los casos.

• $(t\equiv s)$. De $t^{𝐀}[\overrightarrow{a}]=s^{𝐀}[\overrightarrow{a}]$ sale $F(t^{𝐀}[\overrightarrow{a}])=F(s^{𝐀}[\overrightarrow{a}])$ porque $F$ es una función: a cosas iguales, imágenes iguales. El Lema 6 reescribe los dos lados como valores en $𝐁$. La vuelta no sale: si $F$ no es inyectiva, dos valores distintos en $A$ pueden tener la misma imagen.
• $r(t_1,\dots ,t_n)$. La condición (3) lleva la tupla de valores de $r^{𝐀}$ a $r^{𝐁}$, y el Lema 6 dice que la tupla llevada es la de los valores en $𝐁$.
• $\wedge$ y $\vee$. Directos: la hipótesis inductiva para cada pieza verdadera.
• $\exists x_j{\phi }_1$. Hay un testigo $a$ en $A$, y $F(a)$ es testigo en $B$. Con la igualdad de asignaciones, la hipótesis inductiva aplicada a ${\downarrow }_j^a(\overrightarrow{a})$ habla exactamente de ${\downarrow }_j^{F(a)}(F(\overrightarrow{a}))$. No hace falta que $F$ sea sobre.
• $\forall x_j{\phi }_1$. Hay que ver que ${\phi }_1$ vale en ${\downarrow }_j^b(F(\overrightarrow{a}))$ para todo $b\in B$. La hipótesis inductiva sólo da los $b$ de la forma $F(a)$. Que sean todos es exactamente que $F$ sea sobre. Es el único caso que usa la sobreyectividad.

Por qué $\neg$ y $\to$ rompen. Si $\phi =\neg {\phi }_1$ y $𝐀\models \phi [\overrightarrow{a}]$, lo que se sabe es $𝐀⊭{\phi }_1[\overrightarrow{a}]$. La hipótesis inductiva dice «si ${\phi }_1$ vale en $𝐀$, vale en $𝐁$», y de una fórmula que no vale en $𝐀$ no dice nada. Haría falta «si ${\phi }_1$ no vale en $𝐀$, no vale en $𝐁$», que es la implicación al revés: «si vale en $𝐁$, vale en $𝐀$». En el ejemplo de la sección 01, $\mathrm{r}(x_1)$ no vale en $𝐀$ para $(3,1,\dots )$ y vale en $𝐁$ para $(q,p,\dots )$, porque la condición (3) mete a $F(3)=q$ en ${\mathrm{r}}^{𝐁}$ aunque $3\notin {\mathrm{r}}^{𝐀}$. Con $\to$ pasa lo mismo, porque $({\phi }_1\to {\phi }_2)$ puede valer en $𝐀$ por ser ${\phi }_1$ falsa: $(\mathrm{r}(x_1)\to (x_1\equiv x_2))$ vale en $𝐀$ para $(3,1,\dots )$ y no vale en $𝐁$ para $(q,p,\dots )$, donde $\mathrm{r}(q)$ es verdadera y $q\ne p$. Y $\leftrightarrow$ tiene las dos cosas adentro.

Abajo, las mismas estructuras. Elegís una fórmula y los valores de $x_1$ y $x_2$ en $A$, y se ve el recorrido de la prueba: qué se sabe de $𝐀$ en cada subfórmula y si llega a $𝐁$. Después le agregás a $B$ un elemento que no es imagen de nadie.

Las tres primeras fórmulas no tienen $\neg$ ni $\to$, y con $F$ sobre todo llega. Con la segunda, la del $\exists$, sigue llegando con $F$ no sobre: el testigo en $B$ es $F$ del testigo en $A$, y eso no necesita que $s$ sea imagen de algo. Con la primera y la tercera, en cambio, el $\forall$ falla en $s$, que no es $F(a)$ para ningún $a$. Las de $\neg$ y $\to$ se rompen en el nodo marcado, con $F$ sobre y todo. Y la última tiene $\neg$ y $\to$ y aun así, con $F$ sobre, llega: el ejercicio no dice que esas fórmulas no viajen, dice que la prueba no las cubre.

05 · El escarabajo: la prueba escrita

Prueba. Sean $𝐀$ y $𝐁$ estructuras de tipo $\tau$ y $F:𝐀\to 𝐁$ un homomorfismo sobre. Para $\overrightarrow{a}=(a_1,a_2,\dots )\in A^{𝐍}$ denotamos $F(\overrightarrow{a})=(F(a_1),F(a_2),\dots )$. Usaremos el Lema 6 de la Guía 10 y la igualdad $F({\downarrow }_j^a(\overrightarrow{a}))={\downarrow }_j^{F(a)}(F(\overrightarrow{a}))$, probados arriba. Usaremos la Regla de Inducción desde 0. Para cada $k\in \omega$ sea ${\mathrm{Enu}}_k$ el enunciado:

${\mathrm{Enu}}_k$: para toda $\phi \in F_k^{\tau }$ en la que no ocurren $\neg$, $\to$ ni $\leftrightarrow$, y para toda $\overrightarrow{a}=(a_1,a_2,\dots )\in A^{𝐍}$, si $𝐀\models \phi [\overrightarrow{a}]$ entonces $𝐁\models \phi [F(\overrightarrow{a})]$.

Prueba de que ${\mathrm{Enu}}_0$ es verdadero. Sean $\phi \in F_0^{\tau }$ y $\overrightarrow{a}\in A^{𝐍}$ tales que $𝐀\models \phi [\overrightarrow{a}]$. Como $\phi$ es atómica, hay dos casos.

• Caso $\phi =(t\equiv s)$, con $t,s\in T^{\tau }$. Por la cláusula (1), $t^{𝐀}[\overrightarrow{a}]=s^{𝐀}[\overrightarrow{a}]$. Como $F$ es una función, $F(t^{𝐀}[\overrightarrow{a}])=F(s^{𝐀}[\overrightarrow{a}])$, y por el Lema 6, $t^{𝐁}[F(\overrightarrow{a})]=s^{𝐁}[F(\overrightarrow{a})]$. Por la cláusula (1), $𝐁\models \phi [F(\overrightarrow{a})]$.
• Caso $\phi =r(t_1,\dots ,t_n)$, con $n\ge 1$, $r\in {ℛ}_n$ y $t_1,\dots ,t_n\in T^{\tau }$. Por la cláusula (2), $(t_1^{𝐀}[\overrightarrow{a}],\dots ,t_n^{𝐀}[\overrightarrow{a}])\in r^{𝐀}$. Por la condición (3) de homomorfismo, $(F(t_1^{𝐀}[\overrightarrow{a}]),\dots ,F(t_n^{𝐀}[\overrightarrow{a}]))\in r^{𝐁}$, y por el Lema 6 esa tupla es $(t_1^{𝐁}[F(\overrightarrow{a})],\dots ,t_n^{𝐁}[F(\overrightarrow{a})])$. Por la cláusula (2), $𝐁\models \phi [F(\overrightarrow{a})]$.

Prueba de que si ${\mathrm{Enu}}_k$ es verdadero entonces ${\mathrm{Enu}}_{k+1}$ lo es. Supongamos que vale ${\mathrm{Enu}}_k$. Sean $\phi \in F_{k+1}^{\tau }$ en la que no ocurren $\neg$, $\to$ ni $\leftrightarrow$, y $\overrightarrow{a}\in A^{𝐍}$ tales que $𝐀\models \phi [\overrightarrow{a}]$.

• Caso $\phi \in F_k^{\tau }$. Ya que ${\mathrm{Enu}}_k$ es verdadero, $𝐁\models \phi [F(\overrightarrow{a})]$.
• Si $\phi \notin F_k^{\tau }$, por la definición de $F_{k+1}^{\tau }$, $\phi$ es de la forma $\neg {\phi }_1$, $({\phi }_1\wedge {\phi }_2)$, $({\phi }_1\vee {\phi }_2)$, $({\phi }_1\to {\phi }_2)$, $({\phi }_1\leftrightarrow {\phi }_2)$, $\forall x_j{\phi }_1$ o $\exists x_j{\phi }_1$, con ${\phi }_1,{\phi }_2\in F_k^{\tau }$ y $j\in 𝐍$. Como en $\phi$ no ocurren $\neg$, $\to$ ni $\leftrightarrow$, no es de las formas $\neg {\phi }_1$, $({\phi }_1\to {\phi }_2)$ ni $({\phi }_1\leftrightarrow {\phi }_2)$. Y como ${\phi }_1$ y ${\phi }_2$ son subpalabras de $\phi$, en ellas tampoco ocurren $\neg$, $\to$ ni $\leftrightarrow$. Quedan cuatro casos.
• Caso $\phi =({\phi }_1\wedge {\phi }_2)$. Por la cláusula (3), $𝐀\models {\phi }_1[\overrightarrow{a}]$ y $𝐀\models {\phi }_2[\overrightarrow{a}]$. Por ${\mathrm{Enu}}_k$, aplicado a ${\phi }_1$ y a ${\phi }_2$ con la asignación $\overrightarrow{a}$, $𝐁\models {\phi }_1[F(\overrightarrow{a})]$ y $𝐁\models {\phi }_2[F(\overrightarrow{a})]$. Por la cláusula (3), $𝐁\models \phi [F(\overrightarrow{a})]$.
• Caso $\phi =({\phi }_1\vee {\phi }_2)$. Por la cláusula (4), $𝐀\models {\phi }_1[\overrightarrow{a}]$ o $𝐀\models {\phi }_2[\overrightarrow{a}]$. Si $𝐀\models {\phi }_1[\overrightarrow{a}]$, por ${\mathrm{Enu}}_k$ $𝐁\models {\phi }_1[F(\overrightarrow{a})]$; si $𝐀\models {\phi }_2[\overrightarrow{a}]$, por ${\mathrm{Enu}}_k$ $𝐁\models {\phi }_2[F(\overrightarrow{a})]$. En cualquier caso, por la cláusula (4), $𝐁\models \phi [F(\overrightarrow{a})]$.
• Caso $\phi =\exists x_j{\phi }_1$. Por la cláusula (9), hay un $a\in A$ tal que $𝐀\models {\phi }_1[{\downarrow }_j^a(\overrightarrow{a})]$. Por ${\mathrm{Enu}}_k$, aplicado a ${\phi }_1$ con la asignación ${\downarrow }_j^a(\overrightarrow{a})$, $𝐁\models {\phi }_1[F({\downarrow }_j^a(\overrightarrow{a}))]$, es decir, $𝐁\models {\phi }_1[{\downarrow }_j^{F(a)}(F(\overrightarrow{a}))]$. Como $F(a)\in B$, por la cláusula (9), $𝐁\models \exists x_j{\phi }_1[F(\overrightarrow{a})]$.
• Caso $\phi =\forall x_j{\phi }_1$. Por la cláusula (8), $𝐀\models {\phi }_1[{\downarrow }_j^a(\overrightarrow{a})]$ para todo $a\in A$. Por ${\mathrm{Enu}}_k$, aplicado a ${\phi }_1$ con cada asignación ${\downarrow }_j^a(\overrightarrow{a})$, y por la igualdad de asignaciones, $𝐁\models {\phi }_1[{\downarrow }_j^{F(a)}(F(\overrightarrow{a}))]$ para todo $a\in A$. Sea $b\in B$. Como $F$ es sobre, hay $a\in A$ con $F(a)=b$, y entonces $𝐁\models {\phi }_1[{\downarrow }_j^b(F(\overrightarrow{a}))]$. Como $b$ era cualquiera, por la cláusula (8), $𝐁\models \forall x_j{\phi }_1[F(\overrightarrow{a})]$.

Por la Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ es verdadero para todo $k\in \omega$. Como $F^{\tau }={\bigcup }_{k\ge 0}{F}_k^{\tau }$, toda $\phi \in F^{\tau }$ está en algún $F_k^{\tau }$, y por ${\mathrm{Enu}}_k$, si en $\phi$ no ocurren $\neg$, $\to$ ni $\leftrightarrow$, entonces $𝐀\models \phi [(a_1,a_2,\dots )]$ implica $𝐁\models \phi [(F(a_1),F(a_2),\dots )]$ para cada $(a_1,a_2,\dots )\in A^{𝐍}$. ∎

06 · Sin sobre, o con negación: los contraejemplos

Con $\tau =(\varnothing ,\varnothing ,\{\mathrm{r}\},\{(\mathrm{r},1)\})$, medidos los tres:

En la primera fila $F$ es homomorfismo porque $a\in {\mathrm{r}}^{𝐁}$, y no es sobre: $b$ no es imagen de nadie, y es justo el elemento donde falla el $\forall$. En la misma estructura, $\exists x_1\mathrm{r}(x_1)$ vale en $𝐀$ y vale en $𝐁$: el $\exists$ no necesitaba sobre. En la segunda, $F$ es sobre y homomorfismo, porque ${\mathrm{r}}^{𝐁}$ es todo $B$; la negación de $\mathrm{r}(x_1)$ vale en $b$ y su imagen $c$ está en ${\mathrm{r}}^{𝐁}$. En la tercera, $F$ es biyectiva y homomorfismo, porque ${\mathrm{r}}^{𝐀}$ es vacía, y en la misma estructura también se rompen $\neg \mathrm{r}(x_1)$ en $(a,\dots )$ y $(\mathrm{r}(x_1)\leftrightarrow \mathrm{r}(x_2))$ en $(a,b,\dots )$. Es la estructura del contraejemplo del Ejercicio 16 con un elemento más: un homomorfismo biyectivo que no es isomorfismo. Para un isomorfismo la verdad viaja en los dos sentidos y en todas las fórmulas, que es el Lema 7 de la Guía 10 y el Ejercicio 29.

07 · Lo que se lleva a otros ejercicios

El Lema 6 en notación declaratoria es el Ejercicio 28, y este mismo ejercicio en notación declaratoria es el Ejercicio 30. Los casos son los mismos; cambia cómo se escribe la asignación. La relación $\models$ con todas sus cláusulas está en La relación ⊨ y la validez universal.

El molde de los cuantificadores —cambiar la asignación con ${\downarrow }_j^a$ y por eso cuantificarla dentro del ${\mathrm{Enu}}_k$— es el de los ejercicios 12 a 15 de la lista, y el del Lema 7.

Lo que hace perder puntos. Fijar $\overrightarrow{a}$ antes de la inducción, con lo que el caso $\exists$ no puede usar la hipótesis inductiva. Olvidar decir que en ${\phi }_1$ y ${\phi }_2$ tampoco ocurren $\neg$, $\to$ ni $\leftrightarrow$, sin lo cual no se les puede aplicar ${\mathrm{Enu}}_k$. Usar el Lema 6 sin enunciarlo y probarlo: la lista sólo deja usar sin enunciar los lemas Menú y la lectura única. Pasar de $𝐁\models {\phi }_1[F({\downarrow }_j^a(\overrightarrow{a}))]$ a $𝐁\models {\phi }_1[{\downarrow }_j^{F(a)}(F(\overrightarrow{a}))]$ sin justificar la igualdad. En el caso $\forall$, concluir sin decir que todo $b\in B$ es de la forma $F(a)$. Y escribir «sii» donde va «implica».

Para tener a mano

1. ${\mathrm{Enu}}_k$: para toda $\phi \in F_k^{\tau }$ sin $\neg$, $\to$, $\leftrightarrow$ y toda $\overrightarrow{a}\in A^{𝐍}$, $𝐀\models \phi [\overrightarrow{a}]$ implica $𝐁\models \phi [F(\overrightarrow{a})]$. La asignación, adentro.
2. Atómicas: $(t\equiv s)$ porque $F$ es función, $r(\dots )$ por la condición (3); las dos con el Lema 6, que se enuncia y se prueba.
3. $\wedge$ y $\vee$ directos. $\exists$: el testigo $a$ da el testigo $F(a)$. $\forall$: todo $b$ es $F(a)$, y es el único caso que usa sobre.
4. $F({\downarrow }_j^a(\overrightarrow{a}))={\downarrow }_j^{F(a)}(F(\overrightarrow{a}))$, lugar por lugar.
5. $\neg$ y $\to$ rompen porque la hipótesis inductiva sólo lleva verdades de $𝐀$ a $𝐁$; para una falsedad haría falta la vuelta, que tiene un isomorfismo y no un homomorfismo.