El cero absorbe todo el término

El enunciado, textual: «Sea $\tau =(\{\mathrm{cero}\},\{{\mathrm{fu}}^2\},\varnothing ,a)$. Sea $𝐀$ una estructura de tipo $\tau$ tal que ${\mathrm{fu}}^{𝐀}(x,{\mathrm{cero}}^{𝐀})={\mathrm{fu}}^{𝐀}({\mathrm{cero}}^{𝐀},x)={\mathrm{cero}}^{𝐀}$ para cada $x\in A$. Sea $t{=}_{d}t(v_1,\dots ,v_n)\in T^{\tau }$, con $n\ge 1$ y supongamos que $v_1$ ocurre en $t$. Pruebe que cualesquiera sean $a_2,\dots ,a_n\in A$, se tiene que $t^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n]={\mathrm{cero}}^{𝐀}$.» Es el Ejercicio 32 de la Guía 11.

Está enunciado con ${=}_d$: se resuelve dentro de la notación declaratoria, con los lemas y convenciones de la sección «Manejo técnico de la notación declaratoria» de la Guía 11.

01 · Qué dice, antes de probar

${\mathrm{cero}}^{𝐀}$ se come a cualquier cosa con la que ${\mathrm{fu}}^{𝐀}$ lo junte, de los dos lados, como el 0 en un producto. Los términos de $\tau$ se arman con variables, $\mathrm{cero}$ y $\mathrm{fu}$. El enunciado dice que si $v_1$ aparece en $t$ y se le da a $v_1$ el valor ${\mathrm{cero}}^{𝐀}$, el término entero vale ${\mathrm{cero}}^{𝐀}$, valgan lo que valgan las otras variables.

Un ejemplo. Sea $𝐀$ con universo $\{0,1,2,3,4,5\}$, ${\mathrm{cero}}^{𝐀}=0$ y ${\mathrm{fu}}^{𝐀}(x,y)$ el producto módulo 6, y declaremos $t=\mathrm{fu}(\mathrm{fu}(v_2,v_3),\mathrm{fu}(v_1,v_2))$ como $t{=}_{d}t(v_1,v_2,v_3)$. En $[0,2,5]$, el argumento $\mathrm{fu}(v_2,v_3)$ vale $10\mathrm{mod}6=4$, que no es cero; el otro, $\mathrm{fu}(v_1,v_2)$, vale $0$ porque tiene a $v_1$; y $t^{𝐀}[0,2,5]={\mathrm{fu}}^{𝐀}(4,0)=0$. Un argumento sin $v_1$ puede valer cualquier cosa, y no importa: el que tiene a $v_1$ vale cero y se lo come.

Las dos hipótesis hacen falta. Sin «$v_1$ ocurre en $t$», el término $\mathrm{fu}(v_2,v_3)$ vale 4 en $[0,2,5]$. Y con una sola mitad de la absorción tampoco alcanza: con universo $\{0,1,2\}$, ${\mathrm{cero}}^{𝐀}=0$ y ${\mathrm{fu}}^{𝐀}(x,y)=x$, vale ${\mathrm{fu}}^{𝐀}({\mathrm{cero}}^{𝐀},x)={\mathrm{cero}}^{𝐀}$ pero no ${\mathrm{fu}}^{𝐀}(x,{\mathrm{cero}}^{𝐀})={\mathrm{cero}}^{𝐀}$, y $t=\mathrm{fu}(v_2,v_1)$ da $t^{𝐀}[0,2]=2$.

Medido sobre los 404 términos de nivel a lo sumo 2 en $v_1,v_2,v_3$ y $\mathrm{cero}$, declarados con $(v_1,v_2,v_3)$: en el producto módulo 6, los 257 que tienen a $v_1$ valen 0 en los 36 pares $(a_2,a_3)$, y de los 147 que no la tienen, 38 dejan de valer 0 en algún par. Con la proyección, 104 de los 257 que tienen a $v_1$ fallan en algún par.

02 · Las herramientas

Los lemas y las convenciones de la sección «Manejo técnico de la notación declaratoria» son lo que el encabezado de la lista manda usar en los ejercicios 21 a 30: se enuncian y se citan. Lo que haga falta de otra parte —acá, un hecho de ocurrencias— se enuncia y se prueba.

La Regla de Inducción desde 0. Si para cada $k\in \omega$ hay un enunciado ${\mathrm{Enu}}_k$, y se prueba que ${\mathrm{Enu}}_0$ es verdadero y que ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$ para cada $k$, entonces ${\mathrm{Enu}}_k$ es verdadero para todo $k$. Se usa con $T_k^{\tau }$: $T_0^{\tau }=\mathrm{Var}\cup 𝒞$, los $T_k^{\tau }$ crecen con $k$, y todo término está en alguno.

Lema 1 de la Guía 11, p. 8 (lectura única de términos declarados). Si $t\in T^{\tau }$ y $t{=}_{d}t(v_1,\dots ,v_n)$, se da una y sólo una de: (1) $t=c$ para algún $c\in 𝒞$; (2) $t=v_j$ para algún $j\in \{1,\dots ,n\}$; (3) $t=f(t_1,\dots ,t_m)$ con $f\in {ℱ}_m$, $m\ge 1$ y $t_1,\dots ,t_m\in T^{\tau }$ únicos. Más aún, si $t\in T_{k+1}^{\tau }$, en el caso (3) los $t_1,\dots ,t_m$ están en $T_k^{\tau }$.

Convención Notacional 5 de la Guía 11, p. 8. Si $t{=}_{d}t(v_1,\dots ,v_n)$ y se da el caso (3) del Lema 1, se supone hecha también la declaración $t_j{=}_d{t}_j(v_1,\dots ,v_n)$ para cada $j$: la misma lista de variables.

Lema 3 de la Guía 11, p. 9. Si $t{=}_{d}t(v_1,\dots ,v_n)$, $𝐀$ es un modelo de tipo $\tau$ y $a_1,\dots ,a_n\in A$: (1) si $t=c$, $t^{𝐀}[a_1,\dots ,a_n]=c^{𝐀}$; (2) si $t=v_j$, $t^{𝐀}[a_1,\dots ,a_n]=a_j$; (3) si $t=f(t_1,\dots ,t_m)$, entonces

$$t^{𝐀}[a_1,\dots ,a_n]=f^{𝐀}(t_1^{𝐀}[a_1,\dots ,a_n],\dots ,t_m^{𝐀}[a_1,\dots ,a_n])$$

Lo que hay que saber de ocurrencias, y no es de la Guía 11. Tres hechos: $v_1$ no ocurre en $\mathrm{cero}$; si $v_1$ ocurre en $v_j$, entonces $j=1$; y si $v_1$ ocurre en $\mathrm{fu}(t_1,t_2)$, entonces ocurre en $t_1$ o en $t_2$. Salen de dos cosas de la Guía 9: los símbolos de una variable son la $X$ y numerales itálicos y negritas, y ningún nombre del tipo usa esos símbolos; y en una variable la $X$ es el primer símbolo y el único negrita es el último. Se enuncian y se prueban en el escarabajo.

03 · La mariposa: la hipótesis «v₁ ocurre» viaja adentro

Es una propiedad de todos los términos en los que ocurre $v_1$, así que va por la Regla de Inducción desde 0 en el nivel. La pregunta es qué escribir en ${\mathrm{Enu}}_k$.

«$v_1$ ocurre en $t$» va en la hipótesis de ${\mathrm{Enu}}_k$. Si se lo deja afuera —«fijemos $t$ con $v_1$ adentro; ${\mathrm{Enu}}_k$: si $t\in T_k^{\tau }$…»— no hay inducción: ${\mathrm{Enu}}_k$ habla de un solo término y no se puede aplicar a sus argumentos. Y si se lo saca del todo —«todo $t\in T_k^{\tau }$ cumple $t^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n]={\mathrm{cero}}^{𝐀}$»— el enunciado es falso: ya ${\mathrm{Enu}}_0$ falla con $t=v_2$. La forma correcta es una implicación adentro de ${\mathrm{Enu}}_k$, cuantificada sobre todos los $t$ de $T_k^{\tau }$: si $v_1$ ocurre en $t$, entonces $t$ vale cero.

El caso base deja un solo término. En $T_0^{\tau }$ están $\mathrm{cero}$ y las variables. $v_1$ no ocurre en $\mathrm{cero}$, ni en $v_j$ con $j\ne 1$: la hipótesis descarta todo salvo $t=v_1$, y ahí el Lema 3 (2) da el valor de la primera variable, que es ${\mathrm{cero}}^{𝐀}$.

En el paso, la hipótesis inductiva se usa sobre un solo argumento. $t=\mathrm{fu}(t_1,t_2)$, y $v_1$ ocurre en $t_1$ o en $t_2$, pero no necesariamente en los dos. Si ocurre en $t_1$, ${\mathrm{Enu}}_k$ da $t_1^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n]={\mathrm{cero}}^{𝐀}$; de $t_2$ no se sabe nada, y no hace falta, porque ${\mathrm{fu}}^{𝐀}({\mathrm{cero}}^{𝐀},x)={\mathrm{cero}}^{𝐀}$ para cualquier $x$. Si no ocurre en $t_1$, ocurre en $t_2$, y trabaja la otra mitad: ${\mathrm{fu}}^{𝐀}(x,{\mathrm{cero}}^{𝐀})={\mathrm{cero}}^{𝐀}$. Cada mitad de la absorción sirve a un lado.

$n$ y $a_2,\dots ,a_n$ pasan iguales. La Convención 5 declara $t_1$ y $t_2$ con la misma lista $(v_1,\dots ,v_n)$, así que ${\mathrm{Enu}}_k$ se aplica a los argumentos con los mismos elementos. En fórmulas no es así: un cuantificador alarga la lista, y entonces $n$ tiene que quedar cuantificado adentro de ${\mathrm{Enu}}_k$, como en el Ejercicio 26.

Abajo, el término desarmado en sus subtérminos, con $v_1$ valiendo cero. Los que tienen a $v_1$ tienen que dar cero; los otros dan lo que den.

Con el producto, cada fila con $v_1$ vale 0, aunque al lado haya un argumento sin $v_1$ que vale cualquier cosa. Con la proyección, el primer subtérmino que falla es uno de la forma $\mathrm{fu}(s,u)$ con $v_1$ sólo en $u$: es exactamente el caso del paso que usa ${\mathrm{fu}}^{𝐀}(x,{\mathrm{cero}}^{𝐀})={\mathrm{cero}}^{𝐀}$, la mitad que la proyección no cumple.

04 · El escarabajo: la prueba escrita

Hecho (ocurrencias). Sean $v_1,\dots ,v_n$ variables distintas y $t_1,t_2\in T^{\tau }$. (a) $v_1$ no ocurre en $\mathrm{cero}$. (b) Si $v_1$ ocurre en $v_j$, entonces $j=1$. (c) Si $v_1$ ocurre en $\mathrm{fu}(t_1,t_2)$, entonces $v_1$ ocurre en $t_1$ o en $t_2$.

Prueba. Los símbolos de $v_1$ son una $X$ y numerales itálicos o negritas, y por la definición de tipo ningún símbolo de un nombre de constante o de función es $X$ ni un numeral itálico o negrita.

• (a) Todos los símbolos de $\mathrm{cero}$ son de un nombre de constante, y ninguno es símbolo de $v_1$. Luego $v_1$ no es subpalabra de $\mathrm{cero}$.
• (b) Supongamos que $v_1$ ocurre en $v_j$. La $X$ de $v_1$ cae en una $X$ de $v_j$, y la única está en la posición 1: la ocurrencia empieza donde empieza $v_j$. El último símbolo de $v_1$ es negrita y cae en un negrita de $v_j$, y el único es el último: la ocurrencia termina donde termina $v_j$. Luego $v_1=v_j$, y como las variables de la declaración son distintas, $j=1$.
• (c) $\mathrm{fu}(t_1,t_2)$ es la palabra que tiene los símbolos de $\mathrm{fu}$, después «(», después $t_1$, después la coma, después $t_2$ y al final «)». Una ocurrencia de $v_1$ ocupa posiciones consecutivas, y en ninguna puede haber un símbolo de $\mathrm{fu}$, un paréntesis o una coma, porque no son símbolos de $v_1$. Entonces no toca la coma que separa a $t_1$ de $t_2$ ni los paréntesis de afuera, y un tramo de posiciones consecutivas que no toca esa coma queda entero antes o entero después de ella: dentro de $t_1$ o dentro de $t_2$. ∎

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

${\mathrm{Enu}}_k$: Sea $𝐀$ una estructura de tipo $\tau$ tal que ${\mathrm{fu}}^{𝐀}(x,{\mathrm{cero}}^{𝐀})={\mathrm{fu}}^{𝐀}({\mathrm{cero}}^{𝐀},x)={\mathrm{cero}}^{𝐀}$ para cada $x\in A$. Cualesquiera sean $n\ge 1$ y las variables distintas $v_1,\dots ,v_n$: si $t\in T_k^{\tau }$, $t{=}_{d}t(v_1,\dots ,v_n)$ con $n\ge 1$, y $v_1$ ocurre en $t$, entonces para cualesquiera $a_2,\dots ,a_n\in A$ se tiene que $t^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n]={\mathrm{cero}}^{𝐀}$.

• ${\mathrm{Enu}}_0$ es verdadero. Sean $𝐀$ como en el enunciado, $t\in T_0^{\tau }$ con $t{=}_{d}t(v_1,\dots ,v_n)$, $n\ge 1$, tal que $v_1$ ocurre en $t$, y $a_2,\dots ,a_n\in A$. Como $T_0^{\tau }=\mathrm{Var}\cup 𝒞$, $t$ no tiene paréntesis, y por el Lema 1 de la Guía 11, $t=c$ con $c\in 𝒞=\left\{\mathrm{cero}\right\}$ o $t=v_j$ con $j\in \{1,\dots ,n\}$. Si $t=\mathrm{cero}$, $v_1$ no ocurriría en $t$, por (a). Si $t=v_j$, por (b) $j=1$. Luego $t=v_1$, y por el Lema 3 (2) de la Guía 11, $t^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n]={\mathrm{cero}}^{𝐀}$.
• ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$. Supongamos ${\mathrm{Enu}}_k$. Sean $𝐀$ como en el enunciado, $t\in T_{k+1}^{\tau }$ con $t{=}_{d}t(v_1,\dots ,v_n)$, $n\ge 1$, tal que $v_1$ ocurre en $t$, y $a_2,\dots ,a_n\in A$.
  • Caso $t\in T_k^{\tau }$. Vale por ${\mathrm{Enu}}_k$.
  • Caso $t\in T_{k+1}^{\tau }-T_k^{\tau }$. Por el Lema 1 de la Guía 11, $t$ no es $\mathrm{cero}$ ni una variable, que están en $T_0^{\tau }\subseteq T_k^{\tau }$. Luego $t=f(t_1,\dots ,t_m)$ con $f\in {ℱ}_m$, y como el único nombre de función es $\mathrm{fu}$, de aridad 2, $t=\mathrm{fu}(t_1,t_2)$, con $t_1,t_2\in T_k^{\tau }$ por la segunda parte del Lema 1. Por la Convención Notacional 5, $t_1{=}_d{t}_1(v_1,\dots ,v_n)$ y $t_2{=}_d{t}_2(v_1,\dots ,v_n)$. Por el Lema 3 (3) de la Guía 11, $$t^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n]={\mathrm{fu}}^{𝐀}(t_1^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n],t_2^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n])$$ Como $v_1$ ocurre en $t=\mathrm{fu}(t_1,t_2)$, por (c) ocurre en $t_1$ o en $t_2$.
    • Si $v_1$ ocurre en $t_1$: como $t_1\in T_k^{\tau }$ y $t_1{=}_d{t}_1(v_1,\dots ,v_n)$, por ${\mathrm{Enu}}_k$, $t_1^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n]={\mathrm{cero}}^{𝐀}$. Llamando $x=t_2^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n]$, queda $t^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n]={\mathrm{fu}}^{𝐀}({\mathrm{cero}}^{𝐀},x)={\mathrm{cero}}^{𝐀}$, por la hipótesis sobre ${\mathrm{fu}}^{𝐀}$.
    • Si $v_1$ no ocurre en $t_1$, entonces ocurre en $t_2$, y por ${\mathrm{Enu}}_k$ aplicado a $t_2$, $t_2^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n]={\mathrm{cero}}^{𝐀}$. Llamando $x=t_1^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n]$, queda $t^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n]={\mathrm{fu}}^{𝐀}(x,{\mathrm{cero}}^{𝐀})={\mathrm{cero}}^{𝐀}$, por la hipótesis sobre ${\mathrm{fu}}^{𝐀}$.

Por la Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ vale para todo $k\in \omega$. Sea ahora $t{=}_{d}t(v_1,\dots ,v_n)\in T^{\tau }$ con $n\ge 1$ y $v_1$ ocurriendo en $t$, y sea $k$ tal que $t\in T_k^{\tau }$: por ${\mathrm{Enu}}_k$, $t^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n]={\mathrm{cero}}^{𝐀}$ para cualesquiera $a_2,\dots ,a_n\in A$. ∎

05 · Lo que se lleva a otros ejercicios

Una hipótesis sobre $t$ va adentro de ${\mathrm{Enu}}_k$, como antecedente. Es la misma jugada que «$x_l$ no ocurre en $t$» en el Ejercicio 5: lo que la consigna supone de $t$ es parte de lo que se prueba para cada nivel. Lo que cambia acá es que la hipótesis no pasa a todos los argumentos: pasa a uno, y el otro se resuelve sin la hipótesis inductiva.

El hecho de ocurrencias es el de siempre. Una ocurrencia de algo que no tiene paréntesis ni comas en $f(t_1,\dots ,t_m)$ cae adentro de un argumento: es lo mismo que el Ejercicio 1 enuncia para términos cualesquiera, donde además puede ser el término entero. Para una variable alcanza con mirar los símbolos.

Lo que hace perder puntos. Escribir ${\mathrm{Enu}}_k$ sin «$v_1$ ocurre en $t$», que lo vuelve falso, o con esa hipótesis afuera del enunciado. En el caso base, olvidar descartar $\mathrm{cero}$ y las $v_j$ con $j\ne 1$, o descartarlas sin decir por qué. En el paso, aplicar ${\mathrm{Enu}}_k$ a los dos argumentos, cuando uno puede no tener a $v_1$. Usar «$v_1$ ocurre en $t_1$ o en $t_2$» sin justificarlo. Usar sólo una mitad de la absorción: hacen falta las dos, una por lado. Y olvidar el caso $t\in T_k^{\tau }$.

Para tener a mano

1. ${\mathrm{Enu}}_k$: si $t\in T_k^{\tau }$, $t{=}_{d}t(v_1,\dots ,v_n)$, $n\ge 1$ y $v_1$ ocurre en $t$, entonces $t^{𝐀}[{\mathrm{cero}}^{𝐀},a_2,\dots ,a_n]={\mathrm{cero}}^{𝐀}$ para todos $a_2,\dots ,a_n$. La hipótesis va adentro.
2. Caso base: $\mathrm{cero}$ no tiene a $v_1$; $v_j$ la tiene sólo si $j=1$. Queda $t=v_1$, y el Lema 3 (2).
3. Paso: $t=\mathrm{fu}(t_1,t_2)$; $v_1$ ocurre en $t_1$ o en $t_2$ (los símbolos de $\mathrm{fu}$, los paréntesis y la coma no son de $v_1$); ${\mathrm{Enu}}_k$ en ese argumento, y la mitad de la absorción que corresponde se come al otro.
4. Sin «$v_1$ ocurre», $\mathrm{fu}(v_2,v_3)$ vale 4 en $[0,2,5]$ con el producto módulo 6. Con una sola mitad, $\mathrm{fu}(v_2,v_1)$ vale 2 en $[0,2]$ con ${\mathrm{fu}}^{𝐀}(x,y)=x$.