Renombrar por una variable que no estaba

El enunciado, textual: «Sea $\tau$ un tipo y sea $t\in T^{\tau }$ tal que la variable $x_l$ no ocurre en $t$. Sea $t^{\prime }$ el resultado de reemplazar toda ocurrencia de $x_i$ en $t$ por $x_l$. Acepte sin demostración que $t^{\prime }\in T^{\tau }$. Entonces para cualquier estructura $𝐀$, cualquier asignación $\overrightarrow{a}\in A^{𝐍}$ y cualquier $a\in A$, se tiene que $t^{\prime 𝐀}[{\downarrow }_l^a(\overrightarrow{a})]=t^{𝐀}[{\downarrow }_i^a(\overrightarrow{a})]$.» Es el Ejercicio 4 de la Guía 10, con el agregado de que $t^{\prime }\in T^{\tau }$ se acepta.

Está entre los ejercicios 1 a 17 de la lista, así que se resuelve sin notación declaratoria: con asignaciones infinitas $\overrightarrow{a}\in A^{𝐍}$ y con ${\downarrow }_i^a$. Y como toda inducción de la lista, nombra la regla y escribe el ${\mathrm{Enu}}_k$ entero.

01 · Qué pide, con una estructura a la vista

Un término es un nombre compuesto, y su valor depende de qué le asigna $\overrightarrow{a}$ a cada variable. El ejercicio dice que si a $x_i$ se le cambia el nombre por $x_l$ en todas partes, y al mismo tiempo se le da a $x_l$ el valor que se le daba a $x_i$, el término vale lo mismo. Con una condición: que $x_l$ no estuviera ya en $t$, porque si estaba, el renombre la confunde con $x_i$.

Un ejemplo con números. Tomemos el tipo del Ejercicio 6, $\tau =(\{\mathrm{uno}\},\{\mathrm{MAS},\mathrm{P}\},\{\mathrm{Her}\},\{(\mathrm{MAS},4),(\mathrm{P},1),(\mathrm{Her},3)\})$, y la estructura $𝐀$ con universo $A=\{0,1,\dots ,6\}$, $i(\mathrm{uno})=1$, $i(\mathrm{MAS})(x,y,z,w)=x+2y+3z+4w$ módulo 7 e $i(\mathrm{P})(x)=3x$ módulo 7 (lo que sea $i(\mathrm{Her})$ no importa: no aparece en los términos). Sea $\overrightarrow{a}=(1,2,3,4,5,6,0,0,0,\dots )$ y

$$t=\mathrm{MAS}(\mathrm{X}1,\mathrm{P}(\mathrm{X}3),\mathrm{uno},\mathrm{X}1)$$

Con $i=1$ y $l=2$, $x_2=\mathrm{X}2$ no ocurre en $t$, y $t^{\prime }=\mathrm{MAS}(\mathrm{X}2,\mathrm{P}(\mathrm{X}3),\mathrm{uno},\mathrm{X}2)$. Con $a=5$:

• ${\downarrow }_1^5(\overrightarrow{a})=(5,2,3,4,\dots )$ y $t^{𝐀}[{\downarrow }_1^5(\overrightarrow{a})]=i(\mathrm{MAS})(5,i(\mathrm{P})(3),1,5)=5+2·2+3·1+4·5=32$, que módulo 7 es $4$.
• ${\downarrow }_2^5(\overrightarrow{a})=(1,5,3,4,\dots )$ y $t^{\prime 𝐀}[{\downarrow }_2^5(\overrightarrow{a})]=i(\mathrm{MAS})(5,i(\mathrm{P})(3),1,5)$, la misma cuenta: $4$.

Las dos cuentas son la misma porque en las dos el valor $5$ entra por los mismos lugares del término; sólo cambió el nombre de la variable que lo trae. En cambio, sin mover la asignación, $t^{𝐀}[\overrightarrow{a}]=5$ y $t^{\prime 𝐀}[\overrightarrow{a}]=3$: renombrar solo cambia el valor. Y si se renombra por una variable que ya estaba —$l=3$, con $t^{\prime }=\mathrm{MAS}(\mathrm{X}3,\mathrm{P}(\mathrm{X}3),\mathrm{uno},\mathrm{X}3)$—, el lado izquierdo da $t^{\prime 𝐀}[{\downarrow }_3^5(\overrightarrow{a})]=i(\mathrm{MAS})(5,i(\mathrm{P})(5),1,5)=2$, y el derecho sigue en $4$: el $\mathrm{X}3$ que estaba adentro de $\mathrm{P}$ también recibió el $5$.

02 · Las herramientas

El valor de un término (Guía 10, p. 1). Dada una estructura $𝐀=(A,i)$ de tipo $\tau$, $t\in T^{\tau }$ y $\overrightarrow{a}=(a_1,a_2,\dots )\in A^{𝐍}$, se define recursivamente:

• (1) Si $t=x_i\in \mathrm{Var}$, entonces $t^{𝐀}[\overrightarrow{a}]=a_i$.
• (2) Si $t=c\in 𝒞$, entonces $t^{𝐀}[\overrightarrow{a}]=i(c)$.
• (3) Si $t=f(t_1,\dots ,t_n)$, con $f\in {ℱ}_n$, $n\ge 1$ y $t_1,\dots ,t_n\in T^{\tau }$, entonces $t^{𝐀}[\overrightarrow{a}]=i(f)(t_1^{𝐀}[\overrightarrow{a}],\dots ,t_n^{𝐀}[\overrightarrow{a}])$.

La lectura única de términos (Teorema 3 de la Guía 9), que la lista deja usar sin enunciar, es lo que hace que la definición no sea ambigua: en (3), $f$ y los $t_j$ son únicos. Está desarrollado en El valor de un término.

La asignación modificada (Guía 10, p. 3): ${\downarrow }_i^a(\overrightarrow{a})$ es la asignación que resulta de reemplazar en $\overrightarrow{a}$ el $i$-ésimo elemento por $a$. O sea, su elemento $i$-ésimo es $a$ y su elemento $j$-ésimo, para $j\ne i$, es $a_j$.

Las variables (Guía 9, p. 1): $x_n$ es $\mathrm{X}$ seguida de los numerales de $n$, todos itálicos salvo el último, negrita. Una variable tiene una sola $\mathrm{X}$, la primera, y termina en su único negrita; por eso $x_i$ ocurre en $x_j$ sólo si $i=j$: una ocurrencia tendría que empezar en la única $\mathrm{X}$ de $x_j$ y terminar en su único negrita, y sería $x_j$ entera.

El tipo (Guía 8, p. 4): ningún nombre de constante o de función usa la $\mathrm{X}$ ni numerales itálicos o negritas. Así que una variable no ocurre en un nombre de constante, y una ocurrencia de una variable en $f(t_1,\dots ,t_n)$ no puede tocar $f$, ni los paréntesis, ni las comas.

Los niveles (Guía 9, p. 1): $T_0^{\tau }=\mathrm{Var}\cup 𝒞$ y $T_{k+1}^{\tau }=T_k^{\tau }\cup \{f(t_1,\dots ,t_n):f\in {ℱ}_n,n\ge 1,t_1,\dots ,t_n\in T_k^{\tau }\}$, con $T^{\tau }={\bigcup }_{k\ge 0}{T}_k^{\tau }$. Y la Regla de Inducción desde 0: si ${\mathrm{Enu}}_0$ es verdadero y, para cada $k$, ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$, entonces ${\mathrm{Enu}}_k$ es verdadero para todo $k\in \omega$.

03 · La mariposa: qué va en el Enu

La inducción es en el nivel de $t$, porque $t^{𝐀}[\overrightarrow{a}]$ está definido por recursión en la construcción de $t$. El ${\mathrm{Enu}}_k$ es el enunciado del ejercicio con $t\in T_k^{\tau }$ en lugar de $t\in T^{\tau }$:

${\mathrm{Enu}}_k$: Si $t\in T_k^{\tau }$ y $x_l$ no ocurre en $t$, y $t^{\prime }$ es el resultado de reemplazar toda ocurrencia de $x_i$ en $t$ por $x_l$, entonces para cualquier estructura $𝐀$ de tipo $\tau$, cualquier $\overrightarrow{a}\in A^{𝐍}$ y cualquier $a\in A$, se tiene que $t^{\prime 𝐀}[{\downarrow }_l^a(\overrightarrow{a})]=t^{𝐀}[{\downarrow }_i^a(\overrightarrow{a})]$.

Qué va adentro y por qué. La hipótesis «$x_l$ no ocurre en $t$» y la definición de $t^{\prime }$ hablan de $t$, que es lo que recorre la inducción: van adentro sí o sí. La estructura, la asignación y $a$ también van adentro, cuantificadas. En este ejercicio el paso aplica la hipótesis a cada argumento con los mismos $𝐀$, $\overrightarrow{a}$ y $a$, así que también se podrían fijar antes de empezar —«sean $𝐀$, $\overrightarrow{a}$ y $a$ fijos pero arbitrarios»— y generalizar al final. Lo que no puede pasar es que queden sueltas: un ${\mathrm{Enu}}_k$ que nombra $\overrightarrow{a}$ sin cuantificarla no es un enunciado. Adentro es el molde de la lista, y es el que sobrevive a las fórmulas: en el caso $\forall x_j{\phi }_1$ la asignación cambia, y la hipótesis se tiene que poder usar con otra (es lo que pasa en el Ejercicio 12).

La base tiene tres casos, y en uno trabaja la hipótesis. $T_0^{\tau }=\mathrm{Var}\cup 𝒞$, y entre las variables hay que separar $x_i$ de las demás:

• $t=x_i$: $t^{\prime }=x_l$, y los dos lados valen $a$: uno por ser el $l$-ésimo de ${\downarrow }_l^a(\overrightarrow{a})$, el otro por ser el $i$-ésimo de ${\downarrow }_i^a(\overrightarrow{a})$.
• $t=x_j$ con $j\ne i$: $t^{\prime }=t$. El lado derecho es el $j$-ésimo de ${\downarrow }_i^a(\overrightarrow{a})$, que es $a_j$ porque $j\ne i$. El izquierdo es el $j$-ésimo de ${\downarrow }_l^a(\overrightarrow{a})$, que es $a_j$ si $j\ne l$, y eso lo da la hipótesis: $x_l$ no ocurre en $t=x_j$. Sin ella falla: con $t=\mathrm{X}1$, $i=2$ y $l=1$, $t^{\prime }=t$ y el lado izquierdo vale $a$ mientras el derecho vale $a_1$.
• $t=c$: $t^{\prime }=c$ y los dos lados valen $i(c)$.

El paso es mirar dónde caen las ocurrencias. Si $t=f(t_1,\dots ,t_n)$, toda ocurrencia de $x_i$ en $t$ está hecha de $\mathrm{X}$ y numerales, que no aparecen en $f$, en los paréntesis ni en las comas: cae adentro de algún $t_j$. Entonces $t^{\prime }=f(t_1^{\prime },\dots ,t_n^{\prime })$, con $t_j^{\prime }$ el reemplazo hecho en $t_j$. La hipótesis también baja: si $x_l$ no ocurre en $t$, no ocurre en ningún $t_j$. Con eso ${\mathrm{Enu}}_k$ se aplica a cada argumento y la cláusula (3) cierra la cuenta.

$i=l$ es trivial, y la prueba no necesita separarlo: si $x_i=x_l$ no ocurre en $t$, no hay nada que reemplazar, $t^{\prime }=t$ y ${\downarrow }_l^a={\downarrow }_i^a$. El caso $t=x_i$ de la base no puede darse, y el resto de la prueba vale igual.

Abajo están los dos lados del ejercicio, en la estructura de la sección 01, y la tabla del paso: cada argumento de $t^{\prime }$ con la asignación de la izquierda contra el mismo argumento de $t$ con la de la derecha.

Cuando $x_l$ ya está en $t$, la tabla muestra dónde se rompe: en el argumento que contiene a $x_l$, que en $t^{\prime }$ recibe $a$ y en $t$ recibe $a_l$. Los demás argumentos coinciden, como dice la hipótesis inductiva. Y con $i$ igual a $l$ no pasa nada: $t^{\prime }=t$.

04 · El escarabajo: la prueba escrita

Prueba. Fijemos $\tau$ y $i,l\in 𝐍$. Usaremos la Regla de Inducción desde 0. Para cada $k\in \omega$ sea ${\mathrm{Enu}}_k$ el enunciado:

${\mathrm{Enu}}_k$: Si $t\in T_k^{\tau }$ y $x_l$ no ocurre en $t$, y $t^{\prime }$ es el resultado de reemplazar toda ocurrencia de $x_i$ en $t$ por $x_l$, entonces para cualquier estructura $𝐀$ de tipo $\tau$, cualquier $\overrightarrow{a}\in A^{𝐍}$ y cualquier $a\in A$, se tiene que $t^{\prime 𝐀}[{\downarrow }_l^a(\overrightarrow{a})]=t^{𝐀}[{\downarrow }_i^a(\overrightarrow{a})]$.

En lo que sigue, dados $𝐀$, $\overrightarrow{a}$ y $a$, escribimos $\overrightarrow{b}={\downarrow }_l^a(\overrightarrow{a})$ y $\overrightarrow{c}={\downarrow }_i^a(\overrightarrow{a})$. Por la definición de $\downarrow$: $b_l=a$ y $b_j=a_j$ si $j\ne l$; $c_i=a$ y $c_j=a_j$ si $j\ne i$.

Prueba de que ${\mathrm{Enu}}_0$ es verdadero. Sea $t\in T_0^{\tau }=\mathrm{Var}\cup 𝒞$ tal que $x_l$ no ocurre en $t$, sea $t^{\prime }$ el resultado de reemplazar toda ocurrencia de $x_i$ en $t$ por $x_l$, y sean $𝐀$ una estructura de tipo $\tau$, $\overrightarrow{a}\in A^{𝐍}$ y $a\in A$. Hay tres casos.

• Caso $t=x_i$. La única ocurrencia de $x_i$ en $t$ es $t$ entera, así que $t^{\prime }=x_l$. Por (1) de la definición de valor, $t^{\prime 𝐀}[\overrightarrow{b}]=b_l=a$ y $t^{𝐀}[\overrightarrow{c}]=c_i=a$.
• Caso $t=x_j$, con $j\ne i$. Una ocurrencia de $x_i$ en $x_j$ tendría que empezar en la única $\mathrm{X}$ de $x_j$, que es su primer símbolo, y terminar en su único numeral negrita, que es el último: sería $x_j$ entera, y $x_i\ne x_j$. Luego $x_i$ no ocurre en $t$ y $t^{\prime }=t=x_j$. Como $x_l$ no ocurre en $t=x_j$, $j\ne l$. Por (1), $t^{\prime 𝐀}[\overrightarrow{b}]=b_j=a_j$, porque $j\ne l$, y $t^{𝐀}[\overrightarrow{c}]=c_j=a_j$, porque $j\ne i$.
• Caso $t=c\in 𝒞$. Por la definición de tipo, $c$ no contiene el símbolo $\mathrm{X}$, así que $x_i$ no ocurre en $c$ y $t^{\prime }=c$. Por (2), $t^{\prime 𝐀}[\overrightarrow{b}]=i(c)=t^{𝐀}[\overrightarrow{c}]$.

Prueba de que si ${\mathrm{Enu}}_k$ es verdadero entonces ${\mathrm{Enu}}_{k+1}$ lo es. Supongamos que vale ${\mathrm{Enu}}_k$. Sea $t\in T_{k+1}^{\tau }$ tal que $x_l$ no ocurre en $t$, sea $t^{\prime }$ el resultado de reemplazar toda ocurrencia de $x_i$ en $t$ por $x_l$, y sean $𝐀$ una estructura de tipo $\tau$, $\overrightarrow{a}\in A^{𝐍}$ y $a\in A$. Por definición de $T_{k+1}^{\tau }$ hay dos casos.

• Caso $t\in T_k^{\tau }$. Ya que vale ${\mathrm{Enu}}_k$, $t^{\prime 𝐀}[\overrightarrow{b}]=t^{𝐀}[\overrightarrow{c}]$.
• Caso $t=f(t_1,\dots ,t_n)$, con $f\in {ℱ}_n$, $n\ge 1$ y $t_1,\dots ,t_n\in T_k^{\tau }$. La palabra $x_i$ está hecha de la $\mathrm{X}$ y numerales itálicos y negritas; por la definición de tipo ninguno de esos símbolos aparece en $f$, y tampoco son paréntesis ni comas. Luego toda ocurrencia de $x_i$ en $t$ sucede dentro de algún $t_j$, y recíprocamente toda ocurrencia de $x_i$ en un $t_j$ es una ocurrencia en $t$. Por lo tanto $$t^{\prime }=f(t_1^{\prime },\dots ,t_n^{\prime })$$ donde $t_j^{\prime }$ es el resultado de reemplazar toda ocurrencia de $x_i$ en $t_j$ por $x_l$. Cada $t_j$ es subpalabra de $t$, así que $x_l$ no ocurre en $t_j$, y por lo aceptado en el enunciado, $t_j^{\prime }\in T^{\tau }$. Como $t_j\in T_k^{\tau }$, ${\mathrm{Enu}}_k$ aplicado a $t_j$, con los mismos $𝐀$, $\overrightarrow{a}$ y $a$, da $t_j^{\prime 𝐀}[\overrightarrow{b}]=t_j^{𝐀}[\overrightarrow{c}]$ para $j=1,\dots ,n$. Entonces $$t^{\prime 𝐀}[\overrightarrow{b}]=i(f)(t_1^{\prime 𝐀}[\overrightarrow{b}],\dots ,t_n^{\prime 𝐀}[\overrightarrow{b}])=i(f)(t_1^{𝐀}[\overrightarrow{c}],\dots ,t_n^{𝐀}[\overrightarrow{c}])=t^{𝐀}[\overrightarrow{c}]$$ donde la primera y la última igualdad son (3) de la definición de valor —por la lectura única, los argumentos de $t^{\prime }$ son los $t_j^{\prime }$ y los de $t$ los $t_j$— y la del medio es ${\mathrm{Enu}}_k$.

Por la Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ vale para todo $k\in \omega$. Como todo $t\in T^{\tau }$ está en algún $T_k^{\tau }$, para cualquier $𝐀$, $\overrightarrow{a}\in A^{𝐍}$ y $a\in A$ se tiene $t^{\prime 𝐀}[{\downarrow }_l^a(\overrightarrow{a})]=t^{𝐀}[{\downarrow }_i^a(\overrightarrow{a})]$. ∎

05 · Lo que se lleva a otros ejercicios

El molde de todas las inducciones de valor sobre términos. Base con variables y constantes, paso con $f(t_1,\dots ,t_n)$, y la cláusula (3) de la definición aplicada dos veces con la hipótesis en el medio. Es el molde del Lema 1 de la Guía 10, y el de los dos ejercicios que siguen: el Ejercicio 6, donde lo que se reemplaza es $\mathrm{P}(x_1)$, y el Ejercicio 7, donde se reemplaza un término por otro que vale lo mismo. En los dos la diferencia está en dónde puede caer lo que se reemplaza: una variable cae siempre adentro de un argumento; un término con paréntesis puede ser el término entero.

Con fórmulas aparece un caso que acá no hay. En $Q{x}_j{\phi }_1$ el valor de verdad se calcula con otras asignaciones, ${\downarrow }_j^b(\overrightarrow{a})$ para cada $b\in A$, y la hipótesis inductiva se tiene que poder usar con ellas. Ahí la cuantificación de $\overrightarrow{a}$ adentro del ${\mathrm{Enu}}_k$ deja de ser una costumbre y pasa a ser necesaria.

Lo que hace perder puntos. Escribir ${\mathrm{Enu}}_k$ con $𝐀$, $\overrightarrow{a}$ o $a$ sin cuantificar, o sin nombrar la Regla de Inducción desde 0. Olvidar en la base el caso $x_j$ con $j\ne i$, o no decir que $j\ne l$ y de dónde sale. Afirmar que las ocurrencias de $x_i$ en $f(t_1,\dots ,t_n)$ caen en los argumentos sin decir por qué: la definición de tipo. No justificar que $t_j^{\prime }\in T^{\tau }$ antes de usar la cláusula (3). Olvidar el caso $t\in T_k^{\tau }$ del paso. Y confundir el enunciado con $t^{\prime 𝐀}[\overrightarrow{a}]=t^{𝐀}[\overrightarrow{a}]$, que es falso: en la sección 01, $3\ne 5$.

Para tener a mano

1. ${\mathrm{Enu}}_k$: si $t\in T_k^{\tau }$, $x_l$ no ocurre en $t$ y $t^{\prime }$ es el reemplazo, entonces para toda $𝐀$, toda $\overrightarrow{a}\in A^{𝐍}$ y todo $a\in A$, $t^{\prime 𝐀}[{\downarrow }_l^a(\overrightarrow{a})]=t^{𝐀}[{\downarrow }_i^a(\overrightarrow{a})]$.
2. Base: $x_i$ (los dos lados valen $a$), $x_j$ con $j\ne i$ (y $j\ne l$ porque $x_l$ no ocurre: los dos valen $a_j$), $c$ (los dos valen $i(c)$).
3. $x_i$ ocurre en $x_j$ sólo si $i=j$: una sola $\mathrm{X}$ al principio, un solo negrita al final.
4. Paso: las ocurrencias de una variable en $f(t_1,\dots ,t_n)$ caen en los argumentos, porque $f$, los paréntesis y las comas no tienen $\mathrm{X}$ ni numerales. $t^{\prime }=f(t_1^{\prime },\dots ,t_n^{\prime })$ y la cláusula (3) dos veces.
5. Sin la hipótesis falla: $t=\mathrm{X}1$, $i=2$, $l=1$ da $a$ contra $a_1$. Y $i=l$ es trivial.