Un homomorfismo conmuta con los términos

El enunciado, textual: «Sea $F : 𝐀 \to 𝐁$ un homomorfismo. Supongamos $t =_{d} t (v_{1}, \dots, v_{n})$ . Entonces $F (t^{𝐀} [a_{1}, a_{2}, \dots, a_{n}]) = t^{𝐁} [F (a_{1}), F (a_{2}), \dots, F (a_{n})]$ para cada $a_{1}, a_{2}, \dots, a_{n} \in A$ .» Es el Ejercicio 34 de la Guía 11, y la guía lo presenta como la versión en notación declaratoria del Lema 6 de la Guía 10, que allá se prueba con asignaciones infinitas.

El encabezado de la lista decide cómo se resuelve: un ejercicio enunciado en notación declaratoria se hace dentro de ella, con los lemas y convenciones de la sección «Manejo técnico de la notación declaratoria» de la Guía 11. Copiar la prueba de la Guía 10 no es resolver éste.

01 · Qué dice, en criollo

Dos caminos para llegar a un elemento de $B$ . Uno: calcular el término en $𝐀$ con los elementos $a_{1}, \dots, a_{n}$ y mandar el resultado a $B$ con $F$ . Otro: mandar primero cada $a_{i}$ a $B$ y calcular el término allá. El ejercicio dice que los dos caminos llegan al mismo lugar, para todo término, siempre que $F$ sea homomorfismo.

Un caso concreto. Sea $τ = ({cero}, {+}, \emptyset, {(+, 2)})$ , sea $𝐀$ el modelo con universo ${0, 1, 2, 3, 4, 5}$ , ${cero}^{𝐀} = 0$ y $+^{𝐀}$ la suma módulo 6, y sea $𝐁$ el modelo con universo ${0, 1, 2}$ , ${cero}^{𝐁} = 0$ y $+^{𝐁}$ la suma módulo 3. La función $F (x) =$ resto de dividir $x$ por 3 es un homomorfismo: $F (0) = 0$ , y como 3 divide a 6, el resto en 3 de una suma módulo 6 es la suma módulo 3 de los restos. Tomemos $t = + (+ (x_{1}, x_{2}), cero)$ con la declaración $t =_{d} t (x_{1}, x_{2})$ , y $a_{1} = 4$ , $a_{2} = 5$ :

por arriba: $t^{𝐀} [4, 5] = (4 + 5) + 0$ módulo 6 $= 3$ , y $F (3) = 0$ ;
por abajo: $F (4) = 1$ , $F (5) = 2$ , y $t^{𝐁} [1, 2] = (1 + 2) + 0$ módulo 3 $= 0$ .

Los dos dan 0. Medido con los cuatro términos del widget de abajo y los 36 pares $(a_{1}, a_{2})$ , no falla ninguno. Con una $F$ que no es homomorfismo, como $F (x) = ⌊ x / 2 ⌋$ , el término $+ (x_{1}, x_{2})$ ya falla en 9 de los 36 pares.

Qué quiere decir la notación. La declaración $t =_{d} t (v_{1}, \dots, v_{n})$ dice que $v_{1}, \dots, v_{n}$ son variables distintas y que toda variable que ocurre en $t$ está entre ellas. Y $t^{𝐀} [a_{1}, \dots, a_{n}]$ es, por la Convención 2 de la Guía 11 (p. 2), el valor $t^{𝐀} [\vec{b}]$ para cualquier asignación $\vec{b}$ que le dé a cada $v_{i}$ el valor $a_{i}$ . La prueba de la Guía 10 abre esa convención y trabaja con $\vec{b}$ ; la de acá no la abre nunca.

02 · Las herramientas

Homomorfismo (Guía 10, p. 11–12). Sean $𝐀$ y $𝐁$ modelos de tipo $τ$ . Una función $F : A \to B$ es un homomorfismo de $𝐀$ en $𝐁$ si:

$F (c^{𝐀}) = c^{𝐁}$ , para todo $c \in 𝒞$ ;
$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$ ;
$(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$ .

Un término no tiene nombres de relación, así que la prueba usa (1) y (2) y nunca (3).

Los niveles (Guía 9): $T_{0}^{τ} = Var \cup 𝒞$ , y $T_{k + 1}^{τ}$ es $T_{k}^{τ}$ más las palabras $f (t_{1}, \dots, t_{n})$ con $f \in ℱ_{n}$ , $n \geq 1$ y $t_{1}, \dots, t_{n} \in T_{k}^{τ}$ . Todo término está en algún $T_{k}^{τ}$ .

Lema 1 (Lectura única de términos declarados, Guía 11, p. 8):

Sea $τ$ un tipo cualquiera y supongamos $t \in T^{τ}$ . Si $t =_{d} t (v_{1}, \dots, v_{n})$ , entonces se da una y sólo una de las siguientes:

$t = c$ , para algún $c \in 𝒞$ ;
$t = v_{j}$ , para algún $j \in {1, \dots, n}$ ;
$t = f (t_{1}, \dots, t_{m})$ , con $f \in ℱ_{m}$ , $m \geq 1$ y $t_{1}, \dots, t_{m} \in T^{τ}$ únicos.

Más aún, si $t \in T_{k + 1}^{τ}$ , entonces cuando se da (3) los términos $t_{1}, \dots, t_{m}$ están en $T_{k}^{τ}$ .

Convención 5 (Guía 11, p. 8): cuando se declaró $t =_{d} t (v_{1}, \dots, v_{n})$ y se da el caso (3) del Lema 1, se supone tácitamente que también se hicieron las declaraciones $t_{1} =_{d} t_{1} (v_{1}, \dots, v_{n})$ , …, $t_{m} =_{d} t_{m} (v_{1}, \dots, v_{n})$ . Se puede porque las variables de cada $t_{i}$ son variables de $t$ .

Lema 3 (Carácter recursivo de la notación $t^{𝐀} [a_{1}, \dots, a_{n}]$ , Guía 11, p. 9):

Sea $τ$ un tipo cualquiera y $t \in T^{τ}$ . Supongamos $t =_{d} t (v_{1}, \dots, v_{n})$ . Sea $𝐀$ un modelo de tipo $τ$ y sean $a_{1}, \dots, a_{n} \in A$ . Se tiene que:

si $t = c$ , entonces $t^{𝐀} [a_{1}, \dots, a_{n}] = c^{𝐀}$ ;
si $t = v_{j}$ , entonces $t^{𝐀} [a_{1}, \dots, a_{n}] = a_{j}$ ;
si $t = f (t_{1}, \dots, t_{m})$ , con $f \in ℱ_{m}$ , $m \geq 1$ y $t_{1}, \dots, t_{m} \in T^{τ}$ , entonces $t^{𝐀} [a_{1}, \dots, a_{n}] = f^{𝐀} (t_{1}^{𝐀} [a_{1}, \dots, a_{n}], \dots, t_{m}^{𝐀} [a_{1}, \dots, a_{n}]) .$

El Lema 3 (3) sólo tiene sentido gracias a la Convención 5: $t_{1}^{𝐀} [a_{1}, \dots, a_{n}]$ es la notación de la Convención 2 para la declaración $t_{1} =_{d} t_{1} (v_{1}, \dots, v_{n})$ , y sin esa declaración no denota nada. Estos lemas son la herramienta que el encabezado manda usar; no se reprueban. La lectura única y los lemas Menú se usan sin enunciar.

03 · La mariposa: el Lema 3, a los dos lados

Qué inducción. El Lema 3 calcula $t^{𝐀} [a_{1}, \dots, a_{n}]$ a partir de los valores de $t_{1}, \dots, t_{m}$ , y el «más aún» del Lema 1 dice que esos $t_{i}$ están un nivel más abajo. Eso pide inducción en el nivel $k$ con $t \in T_{k}^{τ}$ : la Regla de Inducción desde 0.

Qué hace cada caso. Si $t$ es una constante $c$ , el Lema 3 (1) lleva el lado izquierdo a $F (c^{𝐀})$ y el derecho a $c^{𝐁}$ : es exactamente la condición (1). Si $t$ es una variable $v_{j}$ , el Lema 3 (2) da $F (a_{j})$ a la izquierda y, a la derecha, el $j$ -ésimo de la lista $F (a_{1}), \dots, F (a_{n})$ , que es $F (a_{j})$ : no hay nada que usar. Si $t = f (t_{1}, \dots, t_{m})$ , se abre el Lema 3 (3) en $𝐀$ , se pasa $F$ adentro de $f^{𝐀}$ con la condición (2), se usa la hipótesis inductiva en cada $t_{i}$ y se cierra con el Lema 3 (3) en $𝐁$ . Ese es el caso que importa, y son cuatro igualdades.

El ${Enu}_{k}$ . Todo lo que no es $k$ va cuantificado adentro: los modelos, el homomorfismo, la cantidad $n$ de variables declaradas, las variables, el término y los elementos. En términos ninguna de esas cosas cambia entre $t$ y sus $t_{i}$ : la Convención 5 los declara con las mismas $v_{1}, \dots, v_{n}$ , y el Lema 3 los evalúa en los mismos $a_{1}, \dots, a_{n}$ . Pero en fórmulas sí cambian —el caso $\forall v φ_{1}$ declara $φ_{1}$ con $n + 1$ variables, en el Ejercicio 29—, y escribir el ${Enu}_{k}$ así desde el principio es lo que hace que el mismo molde sirva para los dos.

Lo que no hay que hacer. Escribir «sea $\vec{b}$ una asignación con $b (v_{i}) = a_{i}$ ; por la Convención 2…» y seguir con $F (\vec{b})$ . Es la prueba del Lema 6 de la Guía 10, correcta, pero es salir de la notación declaratoria, que es justo lo que el encabezado de la lista prohíbe para este ejercicio.

Lo que muestra la tabla es la inducción misma. Un renglón de variable no falla nunca, con ninguna $F$ : es el Lema 3 (2). Un renglón de constante falla exactamente cuando falla la condición (1): con $F (x) =$ resto de $x + 1$ en 3, $F (0) = 1 \neq 0$ , y el término entero falla en los 36 pares. Y un renglón $f (t_{1}, \dots, t_{m})$ cuyos argumentos coinciden sólo puede fallar si falla la condición (2) en esos argumentos: con $⌊ x / 2 ⌋$ , $F (1 + 1) = 1$ y $F (1) + F (1) = 0$ . Si todos los renglones de abajo coinciden y $F$ es homomorfismo, el de arriba también: eso es el paso inductivo.

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 homomorfismo $F : 𝐀 \to 𝐁$ , el número $n \geq 0$ , las variables $v_{1}, \dots, v_{n}$ y el término $t \in T_{k}^{τ}$ tales que $t =_{d} t (v_{1}, \dots, v_{n})$ , se tiene que $F (t^{𝐀} [a_{1}, \dots, a_{n}]) = t^{𝐁} [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 homomorfismo, $t \in T_{0}^{τ}$ con $t =_{d} t (v_{1}, \dots, v_{n})$ y $a_{1}, \dots, a_{n} \in A$ . Como $T_{0}^{τ} = Var \cup 𝒞$ , $t$ es una constante o una variable, y si es una variable, por la declaración es alguna de las $v_{j}$ . Es decir, de los tres casos del Lema 1 se da (1) o (2).

Caso $t = c$ , con $c \in 𝒞$ .

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

Lema 3 (1), en 𝐀

= c^{𝐁}

condición (1) de homomorfismo

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

Lema 3 (1), en 𝐁

Caso $t = v_{j}$ , con $j \in {1, \dots, n}$ .

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

Lema 3 (2), en 𝐀

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

Lema 3 (2), en 𝐁: el j-ésimo es F(aⱼ)

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

Caso $t \in T_{k}^{τ}$ . Como vale ${Enu}_{k}$ , se cumple $F (t^{𝐀} [a_{1}, \dots, a_{n}]) = t^{𝐁} [F (a_{1}), \dots, F (a_{n})]$ .

Caso $t \in T_{k + 1}^{τ} - T_{k}^{τ}$ . $t$ no es una constante ni una variable, porque ésas están en $T_{0}^{τ} \subseteq T_{k}^{τ}$ . Por el Lema 1, $t = f (t_{1}, \dots, t_{m})$ con $f \in ℱ_{m}$ , $m \geq 1$ , y como $t \in T_{k + 1}^{τ}$ , $t_{1}, \dots, t_{m} \in T_{k}^{τ}$ . Por la Convención 5, $t_{1} =_{d} t_{1} (v_{1}, \dots, v_{n})$ , …, $t_{m} =_{d} t_{m} (v_{1}, \dots, v_{n})$ . Entonces

F (t^{𝐀} [a_{1}, \dots, a_{n}]) = F (f^{𝐀} (t_{1}^{𝐀} [a_{1}, \dots, a_{n}], \dots, t_{m}^{𝐀} [a_{1}, \dots, a_{n}]))

Lema 3 (3), en 𝐀

= f^{𝐁} (F (t_{1}^{𝐀} [a_{1}, \dots, a_{n}]), \dots, F (t_{m}^{𝐀} [a_{1}, \dots, a_{n}]))

condición (2) de homomorfismo

= f^{𝐁} (t_{1}^{𝐁} [F (a_{1}), \dots, F (a_{n})], \dots, t_{m}^{𝐁} [F (a_{1}), \dots, F (a_{n})])

Enuₖ, en cada tᵢ

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

Lema 3 (3), en 𝐁

En el paso 2, la condición (2) se aplica a los elementos $t_{1}^{𝐀} [a_{1}, \dots, a_{n}], \dots, t_{m}^{𝐀} [a_{1}, \dots, a_{n}]$ de $A$ . En el paso 3, ${Enu}_{k}$ se aplica a cada $t_{i}$ , que está en $T_{k}^{τ}$ y tiene la declaración $t_{i} =_{d} t_{i} (v_{1}, \dots, v_{n})$ , con los mismos $𝐀$ , $𝐁$ , $F$ y $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 $t \in T^{τ}$ y $t =_{d} t (v_{1}, \dots, v_{n})$ , entonces $t \in T_{k}^{τ}$ para algún $k$ , y ${Enu}_{k}$ da $F (t^{𝐀} [a_{1}, \dots, a_{n}]) = t^{𝐁} [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. Abrir la Convención 2 y probarlo con una asignación $\vec{b}$ : es la prueba de la Guía 10, no la que pide la lista. Usar el Lema 3 (3) sin decir que los $t_{i}$ quedan declarados con $v_{1}, \dots, v_{n}$ por la Convención 5. Aplicar ${Enu}_{k}$ a los $t_{i}$ sin haber dicho que están en $T_{k}^{τ}$ . Olvidar el caso $t \in T_{k}^{τ}$ del paso. Escribir el caso base sólo con variables: si $τ$ tiene constantes, ése es el caso que usa la condición (1). Y dejar el ${Enu}_{k}$ sin los cuantificadores de adentro, o sin nombrar la regla de inducción.

Lo que se lleva. Este ejercicio es la mitad de abajo de otros dos: el Ejercicio 29 (un isomorfismo no cambia ninguna verdad) y el Ejercicio 30 (un homomorfismo sobre transporta las fórmulas sin ¬, → ni ↔) lo usan en las fórmulas atómicas, y los dos dicen «puede usar el Ejercicio 28». El mismo esqueleto —Lema 1, Convención 5, Lema 3 a cada lado— resuelve el inciso (a) del Ejercicio 27, donde en lugar de $F$ hay dos estructuras que coinciden en lo que el término usa, y los Ejercicios 21 a 25, que son inducciones en términos de reticulados. La versión con asignaciones, la del Lema 6 de la Guía 10, se usa en el Ejercicio 17.

Para tener a mano

Inducción en $k$ con $t \in T_{k}^{τ}$ , Regla de Inducción desde 0, y en el ${Enu}_{k}$ adentro: $𝐀$ , $𝐁$ , $F$ , $n$ , $v_{1}, \dots, v_{n}$ , $t$ y $a_{1}, \dots, a_{n}$ .
Caso base por el Lema 1: $t = c$ usa la condición (1); $t = v_{j}$ no usa nada.
Paso: $t = f (t_{1}, \dots, t_{m})$ con $t_{i} \in T_{k}^{τ}$ (Lema 1) y $t_{i} =_{d} t_{i} (v_{1}, \dots, v_{n})$ (Convención 5); Lema 3 (3) en $𝐀$ , condición (2), ${Enu}_{k}$ , Lema 3 (3) en $𝐁$ .
La condición (3) de homomorfismo no se usa: un término no tiene relaciones.
Nunca se abre la Convención 2: la asignación $\vec{b}$ no aparece en la prueba.