Dónde se rompe el transporte de la verdad

El enunciado, textual: «Supongamos que $F:𝐀\to 𝐁$ es un homomorfismo sobre. Sea $\phi {=}_d\phi (v_1,\dots ,v_n)\in F^{\tau }$ tal que los símbolos $\neg \to \leftrightarrow$ no ocurren en $\phi$. Entonces $$𝐀\models \phi [a_1,a_2,\dots ,a_n]\text{ implica }𝐁\models \phi [F(a_1),F(a_2),\dots ,F(a_n)]$$ para cada $a_1,a_2,\dots ,a_n\in A$. Encuentre contraejemplo para cuando $F$ no es sobre y para cuando $F$ es sobre pero $\neg$ ocurre en $\phi$. (Puede usar el Ejercicio (28).)» Es el Ejercicio 37 de la Guía 11.

El Ejercicio 17 de la lista es la misma afirmación sin notación declaratoria. Lo que cambia es cómo se nombra el elemento que mueve un cuantificador: allá con asignaciones $\overrightarrow{a}\in A^{𝐍}$ y el caso $\forall x_j{\phi }_1$ pasa por $F({\downarrow }_j^a(\overrightarrow{a}))={\downarrow }_j^{F(a)}(F(\overrightarrow{a}))$; acá lo dice la declaración, y el Lema 6 de la Guía 11 separa $v=v_j$ (el elemento entra en el lugar $j$) de $v\notin \{v_1,\dots ,v_n\}$ (entra al final y la declaración crece a $n+1$).

01 · Qué dice, en criollo

Un homomorfismo lleva hechos positivos de $𝐀$ a $𝐁$: si $(a_1,\dots ,a_n)\in r^{𝐀}$, entonces $(F(a_1),\dots ,F(a_n))\in r^{𝐁}$. Hechos negativos no: que $a\notin r^{𝐀}$ no impide que $F(a)\in r^{𝐁}$. El ejercicio dice que todo lo que se arma con hechos positivos usando $\wedge$, $\vee$, $\forall$ y $\exists$ también viaja, siempre que $F$ sea sobre. Y pide mostrar que las dos condiciones hacen falta.

Por qué esos tres símbolos. $\neg$ da vuelta un hecho: si ${\phi }_1$ viaja de $𝐀$ a $𝐁$, $\neg {\phi }_1$ tendría que viajar de $𝐁$ a $𝐀$. $\to$ y $\leftrightarrow$ esconden un $\neg$: $𝐀\models ({\phi }_1\to {\phi }_2)$ puede valer porque $𝐀⊭{\phi }_1$, que es un hecho negativo. $\wedge$ y $\vee$ no dan vuelta nada. Y $\forall$ pide sobre por otra razón: en $𝐁$ recorre todo $B$, y lo que viene de $𝐀$ sólo habla de los elementos de la forma $F(a)$.

Los dos contraejemplos, con $\tau =(\varnothing ,\varnothing ,\{r\},\{(r,1)\})$: un solo nombre de relación unario, sin constantes ni funciones, así que las condiciones (1) y (2) de homomorfismo no piden nada y la (3) dice: si $a\in r^{𝐀}$, entonces $F(a)\in r^{𝐁}$.

• $F$ no sobre. $𝐀$ con universo $\{a\}$ y $r^{𝐀}=\{a\}$; $𝐁$ con universo $\{a,b\}$ y $r^{𝐁}=\{a\}$; $F(a)=a$, la inclusión. Es homomorfismo ($a\in r^{𝐀}$ y $F(a)=a\in r^{𝐁}$) y no es sobre ($b$ no es imagen de nada). Sea $\phi =\forall x_{1}r(x_1)$, que no tiene $\neg$, $\to$ ni $\leftrightarrow$, con la declaración $\phi {=}_d\phi ()$. Por el Lema 6 (9), $𝐀\models \phi []$ sii $𝐀\models r(x_1)[a]$ para todo $a\in A$, y el único elemento está en $r^{𝐀}$: $𝐀\models \phi []$. En cambio $𝐁⊭\phi []$, porque $b\notin r^{𝐁}$.
• $F$ sobre, con $\neg$. $𝐀$ con universo $\{a,b\}$ y $r^{𝐀}=\{a\}$; $𝐁$ con universo $\{c\}$ y $r^{𝐁}=\{c\}$; $F(a)=F(b)=c$. Es homomorfismo ($a\in r^{𝐀}$ y $F(a)=c\in r^{𝐁}$) y es sobre. Sea $\phi =\neg r(x_1)$, con la declaración $\phi {=}_d\phi (x_1)$. Por el Lema 6 (7) y (2), $𝐀\models \phi [b]$ porque $b\notin r^{𝐀}$; pero $𝐁\models \phi [F(b)]=\phi [c]$ pediría $c\notin r^{𝐁}$, y $c\in r^{𝐁}$: $𝐁⊭\phi [c]$.

Medidos los dos. Y uno más, que la consigna no pide pero muestra que $\to$ está en la lista por la misma razón que $\neg$: $𝐀$ con universo $\{a,b\}$ y $r^{𝐀}=\{a\}$, $𝐁$ con universo $\{c,d\}$ y $r^{𝐁}=\{c,d\}$, $F(a)=c$, $F(b)=d$. $F$ es un homomorfismo biyectivo (no isomorfismo: su inversa no cumple la condición (3)). Con $\phi =(r(x_1)\to (x_1\equiv x_2))$ y $\phi {=}_d\phi (x_1,x_2)$: $𝐀\models \phi [b,a]$ porque $b\notin r^{𝐀}$, y $𝐁⊭\phi [d,c]$ porque $d\in r^{𝐁}$ y $d\ne c$.

02 · Las herramientas

Homomorfismo (Guía 10, p. 11–12): (1) $F(c^{𝐀})=c^{𝐁}$; (2) $F(f^{𝐀}(a_1,\dots ,a_n))=f^{𝐁}(F(a_1),\dots ,F(a_n))$; (3) $(a_1,\dots ,a_n)\in r^{𝐀}$ implica $(F(a_1),\dots ,F(a_n))\in r^{𝐁}$. Sobre: para cada $b\in B$ hay $a\in A$ con $F(a)=b$.

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.

Lema 4, Convención 6 y Lema 6 de la Guía 11 (p. 9, 10 y 11), enunciados enteros en el Ejercicio 29. Lo que se usa acá, en resumen: el Lema 4 da las seis formas de $\phi {=}_d\phi (v_1,\dots ,v_n)$ —$(t\equiv s)$, $r(t_1,\dots ,t_m)$, $({\phi }_1\eta {\phi }_2)$, $\neg {\phi }_1$, $Q{v}_j{\phi }_1$ con $j\in \{1,\dots ,n\}$, y $Qv{\phi }_1$ con $v\notin \{v_1,\dots ,v_n\}$— y que si $\phi \in F_{k+1}^{\tau }$ las piezas están en $F_k^{\tau }$; la Convención 6 declara las piezas con $v_1,\dots ,v_n$, salvo en la última forma, donde ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n,v)$; y el Lema 6 calcula la verdad: (1) $(t\equiv s)$ sii $t^{𝐀}[\dots ]=s^{𝐀}[\dots ]$; (2) $r(t_1,\dots ,t_m)$ sii $(t_1^{𝐀}[\dots ],\dots ,t_m^{𝐀}[\dots ])\in r^{𝐀}$; (3) $\wedge$ sii las dos; (4) $\vee$ sii alguna; (8) $\forall v_j{\phi }_1$ sii ${\phi }_1$ vale con cualquier $a\in A$ en el lugar $j$; (9) $\forall v{\phi }_1$ sii vale con cualquier $a$ agregado al final; (10) y (11) lo mismo con «algún $a$».

Un hecho de palabras, que se prueba en una línea. Si $\phi =({\phi }_1\eta {\phi }_2)$, $\phi =\neg {\phi }_1$ o $\phi =Qv{\phi }_1$, entonces ${\phi }_1$ y ${\phi }_2$ son subpalabras de $\phi$, así que todo símbolo que ocurre en ellas ocurre en $\phi$: si $\neg$, $\to$, $\leftrightarrow$ no ocurren en $\phi$, tampoco en ${\phi }_1$ ni en ${\phi }_2$. Por la misma razón, si $\phi =({\phi }_1\eta {\phi }_2)$, el símbolo $\eta$ ocurre en $\phi$, así que $\eta \in \{\wedge ,\vee \}$; y $\phi$ no puede ser $\neg {\phi }_1$.

03 · La mariposa: una sola dirección

La misma inducción que el Ejercicio 29, con la mitad del trabajo. Regla de Inducción desde 0 en $k$ con $\phi \in F_k^{\tau }$, y la hipótesis «$\neg$, $\to$, $\leftrightarrow$ no ocurren en $\phi$» adentro del ${\mathrm{Enu}}_k$, junto con los modelos, $F$, $n$, $v_1,\dots ,v_n$ y los elementos. Si quedara afuera, el paso no la tendría para ${\phi }_1$; adentro, el hecho de palabras la pasa a las piezas.

Por qué alcanza una sola dirección. En el 29 la hipótesis inductiva era un «sii», y por eso servía negada para $\neg$, $\to$ y $\leftrightarrow$. Acá es un «implica», que negado da vuelta la flecha: de $𝐀⊭{\phi }_1$ no sale nada sobre $𝐁$. Sacar esos tres símbolos es exactamente lo que deja a la prueba sin ningún caso que necesite la vuelta.

Dónde se usa sobre. Sólo en el $\forall$. Para $𝐁\models \forall v_j{\phi }_1[F(a_1),\dots ]$ hay que revisar cada $b\in B$, y la hipótesis inductiva sólo da los $b$ de la forma $F(a)$. En el $\exists$, en cambio, alcanza un testigo: si $a$ sirve en $𝐀$, $F(a)$ sirve en $𝐁$, y no hace falta saber nada del resto de $B$. El primer contraejemplo es justo eso: un $b$ fuera de la imagen que no está en $r^{𝐁}$.

Dónde se usa homomorfismo. En las atómicas: $(t\equiv s)$ por el Ejercicio 28 (sin inyectiva: de $t^{𝐀}=s^{𝐀}$ a $F(t^{𝐀})=F(s^{𝐀})$ basta que $F$ sea función), y $r(t_1,\dots ,t_m)$ por la condición (3) y el Ejercicio 28.

Lo medido, sobre las nueve fórmulas y todas las elecciones de $a_1,a_2$. En el homomorfismo no sobre la única que no viaja es $\forall x_{1}r(x_1)$. En el sobre de $\{a,b\}$ en $\{c\}$, ninguna fórmula sin $\neg$ falla —en $𝐁$ todo es verdadero, así que nada positivo puede fallar—, y fallan $\neg r(x_1)$ (con $a_1=b$) y $\exists x_3\neg r(x_3)$ (siempre). En el biyectivo fallan las dos con $\neg$ y, además, $(r(x_1)\to (x_1\equiv x_2))$ y $((x_1\equiv x_2)\leftrightarrow r(x_1))$, las dos en la elección $a_1=b$, $a_2=a$. Ninguna fórmula sin $\neg$, $\to$ ni $\leftrightarrow$ falla en las escenas sobre.

04 · El escarabajo: la prueba escrita

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

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

Prueba de que ${\mathrm{Enu}}_0$ es verdadero. Sean $𝐀$, $𝐁$ modelos de tipo $\tau$, $F:𝐀\to 𝐁$ un homomorfismo sobre, $\phi \in F_0^{\tau }$ con $\phi {=}_d\phi (v_1,\dots ,v_n)$ y sin $\neg$, $\to$, $\leftrightarrow$, y $a_1,\dots ,a_n\in A$ tales que $𝐀\models \phi [a_1,\dots ,a_n]$. Como $\phi$ es atómica, de los casos del Lema 4 se da (1) o (2).

Caso $\phi =(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)$. Por el Lema 6 (1), $t^{𝐀}[a_1,\dots ,a_n]=s^{𝐀}[a_1,\dots ,a_n]$; aplicando $F$, $F(t^{𝐀}[a_1,\dots ,a_n])=F(s^{𝐀}[a_1,\dots ,a_n])$; por el Ejercicio 28, $t^{𝐁}[F(a_1),\dots ,F(a_n)]=s^{𝐁}[F(a_1),\dots ,F(a_n)]$; y por el Lema 6 (1) en $𝐁$, $𝐁\models \phi [F(a_1),\dots ,F(a_n)]$.

Caso $\phi =r(t_1,\dots ,t_m)$. Por la Convención 6, $t_i{=}_d{t}_i(v_1,\dots ,v_n)$ para cada $i$. Por el Lema 6 (2), $(t_1^{𝐀}[a_1,\dots ,a_n],\dots ,t_m^{𝐀}[a_1,\dots ,a_n])\in r^{𝐀}$; por la condición (3) de homomorfismo, $(F(t_1^{𝐀}[a_1,\dots ,a_n]),\dots ,F(t_m^{𝐀}[a_1,\dots ,a_n]))\in r^{𝐁}$; por el Ejercicio 28, $(t_1^{𝐁}[F(a_1),\dots ,F(a_n)],\dots ,t_m^{𝐁}[F(a_1),\dots ,F(a_n)])\in r^{𝐁}$; y por el Lema 6 (2) en $𝐁$, $𝐁\models \phi [F(a_1),\dots ,F(a_n)]$.

Prueba de que ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$. Supongamos que vale ${\mathrm{Enu}}_k$. Sean $𝐀$, $𝐁$ modelos de tipo $\tau$, $F:𝐀\to 𝐁$ un homomorfismo sobre, $\phi \in F_{k+1}^{\tau }$ con $\phi {=}_d\phi (v_1,\dots ,v_n)$ y sin $\neg$, $\to$, $\leftrightarrow$, y $a_1,\dots ,a_n\in A$ tales que $𝐀\models \phi [a_1,\dots ,a_n]$. Hay dos casos.

Caso $\phi \in F_k^{\tau }$. Como vale ${\mathrm{Enu}}_k$, $𝐁\models \phi [F(a_1),\dots ,F(a_n)]$.

Caso $\phi \in F_{k+1}^{\tau }-F_k^{\tau }$. $\phi$ no es atómica, así que por el Lema 4 se da (3), (4), (5) o (6), y las piezas están en $F_k^{\tau }$. El caso (4) no se da, porque $\neg$ no ocurre en $\phi$. En los otros, por el hecho de palabras, $\neg$, $\to$, $\leftrightarrow$ no ocurren en ${\phi }_1$ ni en ${\phi }_2$, y en el (3), $\eta \in \{\wedge ,\vee \}$. Así que ${\mathrm{Enu}}_k$ se puede aplicar a las piezas.

Caso $\phi =({\phi }_1\wedge {\phi }_2)$. Por la Convención 6, ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n)$ y ${\phi }_2{=}_d{\phi }_2(v_1,\dots ,v_n)$. Por el Lema 6 (3), $𝐀\models {\phi }_1[a_1,\dots ,a_n]$ y $𝐀\models {\phi }_2[a_1,\dots ,a_n]$. Por ${\mathrm{Enu}}_k$, aplicado a cada una, $𝐁\models {\phi }_1[F(a_1),\dots ,F(a_n)]$ y $𝐁\models {\phi }_2[F(a_1),\dots ,F(a_n)]$, y por el Lema 6 (3) en $𝐁$, $𝐁\models \phi [F(a_1),\dots ,F(a_n)]$.

Caso $\phi =({\phi }_1\vee {\phi }_2)$. Con las mismas declaraciones. Por el Lema 6 (4), $𝐀\models {\phi }_1[a_1,\dots ,a_n]$ o $𝐀\models {\phi }_2[a_1,\dots ,a_n]$. Si vale la primera, por ${\mathrm{Enu}}_k$ $𝐁\models {\phi }_1[F(a_1),\dots ,F(a_n)]$; si vale la segunda, $𝐁\models {\phi }_2[F(a_1),\dots ,F(a_n)]$. En cualquier caso, por el Lema 6 (4) en $𝐁$, $𝐁\models \phi [F(a_1),\dots ,F(a_n)]$.

Caso $\phi =\forall v_j{\phi }_1$, con $j\in \{1,\dots ,n\}$. Por la Convención 6, ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n)$. Por el Lema 6 (8), $𝐀\models {\phi }_1[a_1,\dots ,a_{j-1},a,a_{j+1},\dots ,a_n]$ para todo $a\in A$. Por ${\mathrm{Enu}}_k$, aplicado a ${\phi }_1$ con los elementos $a_1,\dots ,a_{j-1},a,a_{j+1},\dots ,a_n$, se tiene $𝐁\models {\phi }_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$, así que $𝐁\models {\phi }_1[F(a_1),\dots ,F(a_{j-1}),b,F(a_{j+1}),\dots ,F(a_n)]$. Como $b$ era arbitrario, por el Lema 6 (8) en $𝐁$, $𝐁\models \phi [F(a_1),\dots ,F(a_n)]$.

Caso $\phi =\exists v_j{\phi }_1$, con $j\in \{1,\dots ,n\}$. Por la Convención 6, ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n)$. Por el Lema 6 (10), hay $a\in A$ con $𝐀\models {\phi }_1[a_1,\dots ,a_{j-1},a,a_{j+1},\dots ,a_n]$. Por ${\mathrm{Enu}}_k$, $𝐁\models {\phi }_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$, por el Lema 6 (10) en $𝐁$, $𝐁\models \phi [F(a_1),\dots ,F(a_n)]$. No se usó que $F$ sea sobre.

Caso $\phi =\forall v{\phi }_1$, con $v\notin \{v_1,\dots ,v_n\}$. Por la Convención 6, ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n,v)$: ${\mathrm{Enu}}_k$ se aplica con $n+1$ variables. Por el Lema 6 (9), $𝐀\models {\phi }_1[a_1,\dots ,a_n,a]$ para todo $a\in A$; por ${\mathrm{Enu}}_k$, $𝐁\models {\phi }_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\in A$, y entonces $𝐁\models {\phi }_1[F(a_1),\dots ,F(a_n),b]$. Como $b$ era arbitrario, por el Lema 6 (9) en $𝐁$, $𝐁\models \phi [F(a_1),\dots ,F(a_n)]$.

Caso $\phi =\exists v{\phi }_1$, con $v\notin \{v_1,\dots ,v_n\}$. Por la Convención 6, ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n,v)$. Por el Lema 6 (11), hay $a\in A$ con $𝐀\models {\phi }_1[a_1,\dots ,a_n,a]$; por ${\mathrm{Enu}}_k$, $𝐁\models {\phi }_1[F(a_1),\dots ,F(a_n),F(a)]$, y por el Lema 6 (11) en $𝐁$, $𝐁\models \phi [F(a_1),\dots ,F(a_n)]$.

Con esto vale ${\mathrm{Enu}}_{k+1}$. Por la Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ vale para todo $k\in \mathrm{\omega }$, y como toda $\phi \in F^{\tau }$ está en algún $F_k^{\tau }$, queda probado el enunciado. ∎

Los contraejemplos, como se entregan, son los dos de la sección 01: la inclusión $\{a\}\subseteq \{a,b\}$ con $r=\{a\}$ y $\phi =\forall x_{1}r(x_1){=}_d\phi ()$, donde $𝐀\models \phi []$ y $𝐁⊭\phi []$; y $\{a,b\}\to \{c\}$ con $r^{𝐀}=\{a\}$, $r^{𝐁}=\{c\}$ y $\phi =\neg r(x_1){=}_d\phi (x_1)$, donde $𝐀\models \phi [b]$ y $𝐁⊭\phi [F(b)]$. En cada uno hay que verificar por escrito que $F$ es homomorfismo (la condición (3)) y decir si es sobre.

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

Lo que hace perder puntos. Dejar «$\neg$, $\to$, $\leftrightarrow$ no ocurren en $\phi$» fuera del ${\mathrm{Enu}}_k$, o usarla en las piezas sin decir por qué la heredan. Escribir un caso para $\neg$, o para $\to$: no se dan, y hay que decir por qué. Decir que el $\exists$ «usa sobre igual que el $\forall$». Olvidar los casos con $v\notin \{v_1,\dots ,v_n\}$. Dar contraejemplos sin verificar que $F$ es homomorfismo, o uno con $\neg$ donde $F$ no es sobre: la consigna pide sobre y con $\neg$. Y probarlo con asignaciones, que es el Ejercicio 17 y no éste.

Lo que se lleva. Es el Ejercicio 29 con la vuelta tachada: sin inyectiva y sin inversa no hay vuelta en las atómicas, y por eso hay que prohibir lo que la necesita. Las atómicas son el Ejercicio 28. La misma afirmación con asignaciones es el Ejercicio 17. Y el contraejemplo con $\to$ es un homomorfismo biyectivo que no es isomorfismo, el mismo fenómeno del Ejercicio 16: con relaciones, biyectivo no alcanza.

Para tener a mano

1. Regla de Inducción desde 0 en $k$ con $\phi \in F_k^{\tau }$; en el ${\mathrm{Enu}}_k$, adentro, también «$\neg$, $\to$, $\leftrightarrow$ no ocurren en $\phi$».
2. Las piezas heredan esa hipótesis porque son subpalabras; por eso $\eta \in \{\wedge ,\vee \}$ y el caso $\neg {\phi }_1$ no se da.
3. Atómicas: Lema 6 (1)–(2), condición (3) y Ejercicio 28. Sin inyectiva: sólo hace falta ir de $𝐀$ a $𝐁$.
4. Sobre se usa sólo en el $\forall$ (dos casos: $v_j$ y $v$ nueva). El $\exists$ toma como testigo $F(a)$.
5. Contraejemplos: $\{a\}\subseteq \{a,b\}$, $r=\{a\}$, $\forall x_{1}r(x_1)$; y $\{a,b\}\to \{c\}$, $r^{𝐀}=\{a\}$, $r^{𝐁}=\{c\}$, $\neg r(x_1)$ en $b$.