Homomorfismos e isomorfismos de estructuras

Hasta la Guía 10, un homomorfismo era de posets, de reticulados o de álgebras de Boole: una definición para cada clase de estructura. Con la definición general de estructura de tipo $\tau$, la Guía 10 los junta en una sola, en la sección «Un poco de semántica» (p. 11–13), y prueba los dos resultados que la hacen útil: un homomorfismo conmuta con los términos, y un isomorfismo no cambia el valor de verdad de ninguna fórmula.

01 · La definición

Notación (p. 11). Dado un modelo de tipo $\tau$, $𝐀=(A,i)$, para cada $s\in 𝒞\cup ℱ\cup ℛ$ se escribe $s^{𝐀}$ para denotar a $i(s)$.

Homomorfismo (p. 11–12). Sean $𝐀$ y $𝐁$ modelos de tipo $\tau$. Una función $F:A\to B$ es un homomorfismo de $𝐀$ en $𝐁$ si se cumplen

• (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$, $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$, $a_1,\dots ,a_n\in A$.

Se escribe $F:𝐀\to 𝐁$ es un homomorfismo para decir que $F$ es un homomorfismo de $𝐀$ en $𝐁$. Cada condición habla de una clase de nombre del tipo. (1): la constante va a la constante. (2): da lo mismo operar en $A$ y llevar el resultado, que llevar los argumentos y operar en $B$. (3): lo que está relacionado en $𝐀$ queda relacionado en $𝐁$; la vuelta no se pide. Las dos primeras son igualdades y la tercera es una implicación, y casi todo lo que sigue sale de esa diferencia.

Las definiciones viejas son casos particulares. Un poset es una estructura de un tipo con un solo nombre de relación, binario, interpretado como el orden, y para él la (3) es «$a\le b$ implica $F(a)\le F(b)$»: preservar el orden. Un reticulado terna es de tipo $(\varnothing ,\{\mathrm{s},\mathrm{i}\},\varnothing ,\{(\mathrm{s},2),(\mathrm{i},2)\})$, y la (2) es preservar supremos e ínfimos.

02 · Ejemplos: qué condición falla

Sea $\tau =(\{\mathrm{e}\},\{\mathrm{m}\},\varnothing ,\{(\mathrm{m},2)\})$. En $𝐀$ el universo es $\{0,1,2,3\}$, con ${\mathrm{e}}^{𝐀}=0$ y ${\mathrm{m}}^{𝐀}$ la suma módulo 4; en $𝐁$ el universo es $\{0,1\}$, con ${\mathrm{e}}^{𝐁}=0$ y ${\mathrm{m}}^{𝐁}$ la suma módulo 2. Medido con las tres condiciones:

• $F(x)=x$ módulo 2 es homomorfismo: $F(0)=0$, y la paridad de una suma es la suma de las paridades. Es sobre y no es inyectiva.
• $F(x)=x+1$ módulo 2 falla la (1): $F({\mathrm{e}}^{𝐀})=F(0)=1\ne 0={\mathrm{e}}^{𝐁}$.
• $F(x)=\lfloor x/2\rfloor$ cumple la (1) y falla la (2) en $(1,1)$: $F({\mathrm{m}}^{𝐀}(1,1))=F(2)=1$, pero ${\mathrm{m}}^{𝐁}(F(1),F(1))={\mathrm{m}}^{𝐁}(0,0)=0$.

Y uno con relaciones, para la (3). Con $\tau =(\varnothing ,\varnothing ,\{\mathrm{r}\},\{(\mathrm{r},1)\})$, sean $𝐀$ y $𝐁$ con universo $\{a\}$, ${\mathrm{r}}^{𝐀}=\varnothing$ y ${\mathrm{r}}^{𝐁}=\{a\}$. La identidad es homomorfismo de $𝐀$ en $𝐁$: la (3) no pide nada, porque en ${\mathrm{r}}^{𝐀}$ no hay nadie. De $𝐁$ en $𝐀$ no lo es: $a\in {\mathrm{r}}^{𝐁}$ y $a\notin {\mathrm{r}}^{𝐀}$. Una función puede ser homomorfismo en un sentido y no en el otro.

03 · Isomorfismos

Isomorfismo (p. 12). «Un isomorfismo de $𝐀$ en $𝐁$ será un homomorfismo de $𝐀$ en $𝐁$ el cual sea biyectivo y cuya inversa sea un homomorfismo de $𝐁$ en $𝐀$. Diremos que los modelos $𝐀$ y $𝐁$ son isomorfos (en símbolos: $𝐀\cong 𝐁$), cuando haya un isomorfismo $F$ de $𝐀$ en $𝐁$.»

El pedido sobre la inversa no sobra. En el último ejemplo de la sección 02, la identidad es un homomorfismo biyectivo de $𝐀$ en $𝐁$ y su inversa no es homomorfismo, así que no es isomorfismo. Lo que le falta es la vuelta de la (3): que $(F(a_1),\dots ,F(a_n))\in r^{𝐁}$ implique $(a_1,\dots ,a_n)\in r^{𝐀}$. Es lo mismo que pasa con los posets, en Un homomorfismo no refleja el orden.

Sin relaciones, biyectivo alcanza. Si $ℛ=\varnothing$, todo homomorfismo biyectivo es isomorfismo: la inversa cumple (1) y (2) despejando con $F^{-1}$, y la (3) no pide nada. Es el Ejercicio 17 de la Guía 10, resuelto en Sin relaciones, biyectivo alcanza. Por ejemplo, $x\mapsto 3x$ módulo 4 es un homomorfismo biyectivo de la estructura $𝐀$ de la sección 02 en sí misma, y por lo tanto un isomorfismo.

04 · El Lema 6: un homomorfismo conmuta con los términos

Lema 6 (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 }$, $(a_1,a_2,\dots )\in A^{𝐍}$.

Las condiciones (1) y (2) hablan de una constante y de una operación aplicada una vez. El lema las extiende a cualquier término: calcular $t$ en $𝐀$ y llevar el resultado a $B$ da lo mismo que llevar la asignación y calcular $t$ en $𝐁$. Para abreviar, si $\overrightarrow{a}=(a_1,a_2,\dots )$ se escribe $F(\overrightarrow{a})=(F(a_1),F(a_2),\dots )$. La condición (3) no interviene: un término no tiene relaciones.

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

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

• ${\mathrm{Enu}}_0$ es verdadero. Sean $F$ un homomorfismo, $t\in T_0^{\tau }=\mathrm{Var}\cup 𝒞$ y $\overrightarrow{a}\in A^{𝐍}$. Si $t=x_i$, por la cláusula (1) de la definición de $t^{𝐀}[\overrightarrow{a}]$ (p. 1), $F(t^{𝐀}[\overrightarrow{a}])=F(a_i)$, que es el $i$-ésimo elemento de $F(\overrightarrow{a})$, o sea $t^{𝐁}[F(\overrightarrow{a})]$. Si $t=c\in 𝒞$, por la cláusula (2) de esa definición y por 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$. Sean $F$ un homomorfismo, $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 }$: usando la cláusula (3) de la definición de $t^{𝐀}[\overrightarrow{a}]$, la condición (2) de homomorfismo, ${\mathrm{Enu}}_k$ para cada $t_i$ y otra vez la cláusula (3), ahora 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, vale ${\mathrm{Enu}}_k$ para todo $k$, y todo término está en algún $T_k^{\tau }$. ∎

La guía deja el caso base «al lector»; es el renglón de las variables y el de las constantes. La prueba recorre el término de las hojas a la raíz, y en cada nodo usa una sola condición: la (1) en una constante, la (2) en una operación. Si $F$ no es homomorfismo, el primer nodo donde la igualdad se rompe es un nodo donde falla una de las dos.

Abajo, las estructuras de la sección 02, un término y una asignación. Elegís $F$ y se ve, subtérmino por subtérmino, si $F(s^{𝐀}[\overrightarrow{a}])$ y $s^{𝐁}[F(\overrightarrow{a})]$ coinciden.

Con $F(x)=\lfloor x/2\rfloor$ y $x_1=x_2=1$, el nodo $\mathrm{m}(x_1,x_2)$ ya no coincide, y es justo la falla de la (2) en $(1,1)$. Con $F(x)=x+1$ módulo 2 falla la hoja $\mathrm{e}$, por la (1); y en $\mathrm{m}(x_1,\mathrm{m}(x_2,x_3))$, que no tiene $\mathrm{e}$, falla por la (2) el nodo de adentro con cualquier asignación, y la raíz coincide igual, de casualidad: una suma de tres paridades corridas en uno es la paridad corrida de la suma. Con $F(x)=x$ módulo 2, coinciden todos los nodos para cualquier término y cualquier asignación: es el lema.

05 · El Lema 7: un isomorfismo no cambia ninguna verdad

Lema 7 (p. 12). Supongamos que $F:𝐀\to 𝐁$ es un isomorfismo. Sea $\phi \in F^{\tau }$. Entonces

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

para cada $(a_1,a_2,\dots )\in A^{𝐍}$. En particular $𝐀$ y $𝐁$ satisfacen las mismas sentencias de tipo $\tau$.

Las cláusulas de $\models$ que se usan están en La relación ⊨ y la validez universal; los números entre paréntesis son los de la Guía 10, p. 4. Se usa también una igualdad entre 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}))$$

porque las dos infinituplas tienen $F(a)$ en el lugar $j$ y $F(a_i)$ en cada lugar $i\ne j$.

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

${\mathrm{Enu}}_k$: para cada $\phi \in F_k^{\tau }$ y cada $\overrightarrow{a}=(a_1,a_2,\dots )\in A^{𝐍}$, $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐁\models \phi [F(\overrightarrow{a})]$.

${\mathrm{Enu}}_0$ es verdadero. Sean $\phi \in F_0^{\tau }$ y $\overrightarrow{a}\in A^{𝐍}$.

• Caso $\phi =(t\equiv s)$. $𝐀\models \phi [\overrightarrow{a}]$ sii $t^{𝐀}[\overrightarrow{a}]=s^{𝐀}[\overrightarrow{a}]$ (cláusula 1) sii $F(t^{𝐀}[\overrightarrow{a}])=F(s^{𝐀}[\overrightarrow{a}])$ (hacia la derecha porque $F$ es función, hacia la izquierda porque es inyectiva) sii $t^{𝐁}[F(\overrightarrow{a})]=s^{𝐁}[F(\overrightarrow{a})]$ (Lema 6) sii $𝐁\models \phi [F(\overrightarrow{a})]$ (cláusula 1).
• Caso $\phi =r(t_1,\dots ,t_n)$. $𝐀\models \phi [\overrightarrow{a}]$ sii $(t_1^{𝐀}[\overrightarrow{a}],\dots ,t_n^{𝐀}[\overrightarrow{a}])\in r^{𝐀}$ (cláusula 2) sii $(F(t_1^{𝐀}[\overrightarrow{a}]),\dots ,F(t_n^{𝐀}[\overrightarrow{a}]))\in r^{𝐁}$ sii $(t_1^{𝐁}[F(\overrightarrow{a})],\dots ,t_n^{𝐁}[F(\overrightarrow{a})])\in r^{𝐁}$ (Lema 6) sii $𝐁\models \phi [F(\overrightarrow{a})]$ (cláusula 2). El segundo «sii»: hacia la derecha es la condición (3) para $F$; hacia la izquierda, la condición (3) para $F^{-1}$, que es homomorfismo, aplicada a la tupla de los $F(t_i^{𝐀}[\overrightarrow{a}])$, da $(F^{-1}(F(t_1^{𝐀}[\overrightarrow{a}])),\dots )=(t_1^{𝐀}[\overrightarrow{a}],\dots )\in r^{𝐀}$.

${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$. Supongamos que vale ${\mathrm{Enu}}_k$, y sean $\phi \in F_{k+1}^{\tau }$ y $\overrightarrow{a}\in A^{𝐍}$. Caso $\phi \in F_k^{\tau }$: vale por ${\mathrm{Enu}}_k$. Si no, $\phi$ es de alguna de las formas siguientes, con ${\phi }_1,{\phi }_2\in F_k^{\tau }$.

• Caso $\phi =\neg {\phi }_1$. $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀⊭{\phi }_1[\overrightarrow{a}]$ (cláusula 7) sii $𝐁⊭{\phi }_1[F(\overrightarrow{a})]$ (${\mathrm{Enu}}_k$, que es un «sii» y por eso vale negado) sii $𝐁\models \phi [F(\overrightarrow{a})]$ (cláusula 7).
• Caso $\phi =({\phi }_1\vee {\phi }_2)$. $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ o $𝐀\models {\phi }_2[\overrightarrow{a}]$ (cláusula 4) sii $𝐁\models {\phi }_1[F(\overrightarrow{a})]$ o $𝐁\models {\phi }_2[F(\overrightarrow{a})]$ (${\mathrm{Enu}}_k$) sii $𝐁\models \phi [F(\overrightarrow{a})]$ (cláusula 4).
• Casos $({\phi }_1\wedge {\phi }_2)$, $({\phi }_1\to {\phi }_2)$, $({\phi }_1\leftrightarrow {\phi }_2)$. Igual que el anterior, con las cláusulas 3, 5 y 6: cada una dice cuándo vale $\phi$ en términos de cuándo valen o no valen ${\phi }_1$ y ${\phi }_2$ con la misma asignación, y ${\mathrm{Enu}}_k$ dice que ${\phi }_1$ vale en $𝐀$ con $\overrightarrow{a}$ exactamente cuando vale en $𝐁$ con $F(\overrightarrow{a})$, y lo mismo ${\phi }_2$.
• Caso $\phi =\forall x_j{\phi }_1$. Si $𝐀\models \phi [\overrightarrow{a}]$, por la cláusula 8 $𝐀\models {\phi }_1[{\downarrow }_j^a(\overrightarrow{a})]$ para todo $a\in A$; por ${\mathrm{Enu}}_k$ y la igualdad de asignaciones, $𝐁\models {\phi }_1[{\downarrow }_j^{F(a)}(F(\overrightarrow{a}))]$ para todo $a\in A$; como $F$ es sobre, todo $b\in B$ es $F(a)$ para algún $a$, así que $𝐁\models {\phi }_1[{\downarrow }_j^b(F(\overrightarrow{a}))]$ para todo $b\in B$, y por la cláusula 8 $𝐁\models \phi [F(\overrightarrow{a})]$. Recíprocamente, si $𝐁\models \phi [F(\overrightarrow{a})]$, para cada $a\in A$, tomando $b=F(a)$, $𝐁\models {\phi }_1[{\downarrow }_j^{F(a)}(F(\overrightarrow{a}))]={\phi }_1[F({\downarrow }_j^a(\overrightarrow{a}))]$, y por ${\mathrm{Enu}}_k$ $𝐀\models {\phi }_1[{\downarrow }_j^a(\overrightarrow{a})]$; por la cláusula 8, $𝐀\models \phi [\overrightarrow{a}]$.
• Caso $\phi =\exists x_j{\phi }_1$. Si $𝐀\models \phi [\overrightarrow{a}]$, hay $a\in A$ con $𝐀\models {\phi }_1[{\downarrow }_j^a(\overrightarrow{a})]$ (cláusula 9); por ${\mathrm{Enu}}_k$, $𝐁\models {\phi }_1[{\downarrow }_j^{F(a)}(F(\overrightarrow{a}))]$, y $F(a)$ es testigo: $𝐁\models \phi [F(\overrightarrow{a})]$. Recíprocamente, si hay $b\in B$ con $𝐁\models {\phi }_1[{\downarrow }_j^b(F(\overrightarrow{a}))]$, como $F$ es sobre, $b=F(a)$ para algún $a\in A$; entonces $𝐁\models {\phi }_1[F({\downarrow }_j^a(\overrightarrow{a}))]$, por ${\mathrm{Enu}}_k$ $𝐀\models {\phi }_1[{\downarrow }_j^a(\overrightarrow{a})]$, y por la cláusula 9, $𝐀\models \phi [\overrightarrow{a}]$.

Por la Regla de Inducción desde 0, vale ${\mathrm{Enu}}_k$ para todo $k$, y toda fórmula está en algún $F_k^{\tau }$. Para las sentencias: si $\phi$ es una sentencia, por el Corolario 3 de la Guía 10 su valor no depende de la asignación, así que $𝐀\models \phi$ sii $𝐀\models \phi [\overrightarrow{a}]$ para una $\overrightarrow{a}$ cualquiera, sii $𝐁\models \phi [F(\overrightarrow{a})]$, sii $𝐁\models \phi$. ∎

Dónde se usó cada cosa: inyectiva en $(t\equiv s)$, hacia la izquierda; la inversa homomorfismo en $r(\dots )$, hacia la izquierda; sobre en el $\forall$ hacia la derecha y en el $\exists$ hacia la izquierda. Y el $\neg$ funciona sólo porque ${\mathrm{Enu}}_k$ es un «sii». La guía escribe los casos $r(\dots )$, $\vee$ y $\forall$ y deja el resto; en notación declaratoria es el Ejercicio 29.

06 · Sin isomorfismo: qué se conserva y qué no

Si $F$ es sólo un homomorfismo, la prueba del Lema 7 se puede repetir con «implica» en lugar de «sii», siempre que cada caso que se use sólo vaya hacia la derecha y no use lo que falta. Mirando la lista de arriba: $(t\equiv s)$ hacia la derecha usa que $F$ es función, $r(\dots )$ hacia la derecha usa la (3) de $F$, $\wedge$ y $\vee$ no usan nada, el $\exists$ hacia la derecha no usa nada, y el $\forall$ hacia la derecha usa sobre. Lo que no se puede repetir es $\neg$, $\to$ y $\leftrightarrow$: para propagar «implica» a través de una negación haría falta la implicación al revés. El resultado es el Ejercicio 37 de la Guía 11:

si $F:𝐀\to 𝐁$ es un homomorfismo sobre y en $\phi$ no ocurren $\neg$, $\to$ ni $\leftrightarrow$, entonces $𝐀\models \phi [\overrightarrow{a}]$ implica $𝐁\models \phi [F(\overrightarrow{a})]$ para cada $\overrightarrow{a}\in A^{𝐍}$.

Con asignaciones infinitas está probado en Sobre y sin negación, la verdad viaja de A a B, y en notación declaratoria, con los contraejemplos que pide la guía, en Dónde se rompe el transporte de la verdad. Los dos contraejemplos, medidos, con $\tau =(\varnothing ,\varnothing ,\{\mathrm{r}\},\{(\mathrm{r},1)\})$:

• Sin sobre. La inclusión de $(\{a\},\mathrm{r}=\{a\})$ en $(\{a,b\},\mathrm{r}=\{a\})$ es homomorfismo; $\forall x_1\mathrm{r}(x_1)$ vale en la primera y no en la segunda, porque falla en $b$, que no es imagen de nadie.
• Sobre, con $\neg$. La función que manda $a$ y $b$ a $c$, de $(\{a,b\},\mathrm{r}=\{a\})$ en $(\{c\},\mathrm{r}=\{c\})$, es homomorfismo sobre; $\neg \mathrm{r}(x_1)$ vale en la primera con $(b,b,\dots )$ y no vale en la segunda con $(c,c,\dots )$.

Para tener a mano

1. Homomorfismo: (1) constantes, (2) operaciones, igualdades; (3) relaciones, sólo de ida.
2. Isomorfismo: homomorfismo, biyectivo, y la inversa homomorfismo. Sin relaciones, lo tercero sale solo; con relaciones, no.
3. Lema 6: $F(t^{𝐀}[\overrightarrow{a}])=t^{𝐁}[F(\overrightarrow{a})]$, por inducción en el nivel de $t$; base con la (1), paso con la (2).
4. Lema 7: para un isomorfismo, $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐁\models \phi [F(\overrightarrow{a})]$, por inducción en el nivel de $\phi$, con $\overrightarrow{a}$ cuantificada adentro del ${\mathrm{Enu}}_k$; inyectiva en $\equiv$, la inversa en $r$, sobre en los cuantificadores.
5. $F({\downarrow }_j^a(\overrightarrow{a}))={\downarrow }_j^{F(a)}(F(\overrightarrow{a}))$, lugar por lugar.
6. Homomorfismo sobre: la verdad viaja de $𝐀$ a $𝐁$ en las fórmulas sin $\neg$, $\to$, $\leftrightarrow$. Sin sobre se cae el $\forall$; con $\neg$ se cae todo.