Lo que vale lo mismo se puede cambiar

La consigna, textual: «Sean $t,s_1,s_2\in T^{\tau }$ y sea $t^{\prime }$ el resultado de reemplazar algunas (posiblemente 0) ocurrencias de $s_1$ en $t$ por $s_2$. Acepte sin demostración que $t^{\prime }\in T^{\tau }$. Pruebe que si $𝐀=(A,i)$ es una estructura de tipo $\tau$ y $\overrightarrow{a}\in A^{𝐍}$ es una asignación tal que $s_1^{𝐀}[\overrightarrow{a}]=s_2^{𝐀}[\overrightarrow{a}]$, entonces $t^{\prime 𝐀}[\overrightarrow{a}]=t^{𝐀}[\overrightarrow{a}]$». Es el Ejercicio 6 de la Guía 10 (p. 4) con el «acepte» agregado. Está entre los ejercicios 1 a 17, así que se resuelve sin notación declaratoria: con asignaciones infinitas $\overrightarrow{a}\in A^{𝐍}$.

01 · Qué dice, con un ejemplo

El valor de un término se calcula de adentro hacia afuera, y cada pedazo aporta sólo su valor. Si dos términos valen lo mismo, al de afuera le da igual cuál de los dos tenga adentro. Es lo que se hace sin pensar al cambiar 2 + 2 por 4 en el medio de una cuenta. El ejercicio pide probarlo para cualquier término, cualquier tipo y cualquier elección de qué ocurrencias se cambian.

Con la estructura del ejemplo de la Guía 10 (p. 1): el tipo $(\{\mathrm{uno},\mathrm{doli}\},\{\mathrm{MAS},\mathrm{P}\},\{\mathrm{Her}\},a)$, el universo $𝐑$, $i(\mathrm{uno})=9$, $i(\mathrm{MAS})(x,y,z,w)=2x+4y$ y $i(\mathrm{P})(x)=5^x$. Con la asignación $\overrightarrow{a}=(1,2,3,\dots )$ el término $s_1=\mathrm{MAS}(\mathrm{X}1,\mathrm{X}1,\mathrm{X}1,\mathrm{X}1)$ vale $2·1+4·1=6$, y la variable $s_2=\mathrm{X}6$ vale $a_6=6$. En

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

$s_1$ ocurre a partir de 5 y a partir de 24, y $t^{𝐀}[\overrightarrow{a}]=2·6+4·5^6=62512$. Cambiando sólo la segunda ocurrencia queda $\mathrm{MAS}(\mathrm{MAS}(\mathrm{X}1,\mathrm{X}1,\mathrm{X}1,\mathrm{X}1),\mathrm{P}(\mathrm{X}6),\mathrm{X}3,\mathrm{uno})$, que vale $2·6+4·5^6=62512$; cambiando las dos, o ninguna, lo mismo. Con $\overrightarrow{a}=(1,1,1,\dots )$ la hipótesis falla, porque $s_1$ sigue valiendo 6 y $s_2$ vale 1, y cambiar la segunda ocurrencia da $2·6+4·5^1=32$.

Dos cosas del enunciado que conviene leer despacio. La hipótesis es sobre una sola asignación: dice que $s_1$ y $s_2$ valen lo mismo en $\overrightarrow{a}$, y nada de otras. Alcanza porque calcular $t^{𝐀}[\overrightarrow{a}]$ nunca sale de $\overrightarrow{a}$: las tres cláusulas del valor usan siempre la misma asignación. Y «algunas (posiblemente 0)» quiere decir cualquier elección de ocurrencias: todas, ninguna o un subconjunto. Esa libertad es la que hace andar la inducción.

02 · Las herramientas

El valor de un término (Guía 10, p. 1). Dados $𝐀=(A,i)$ de tipo $\tau$, $t\in T^{\tau }$ y $\overrightarrow{a}=(a_1,a_2,\dots )\in A^{𝐍}$: (1) si $t=x_i\in \mathrm{Var}$, $t^{𝐀}[\overrightarrow{a}]=a_i$; (2) si $t=c\in 𝒞$, $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}])$. Que (3) no sea ambigua lo garantiza la lectura única de términos, que la lista deja usar sin enunciar.

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\text{ y }{t}_1,\dots ,t_n\in T_k^{\tau }\}$$

con $T^{\tau }$ la unión. La Regla de Inducción desde 0: si ${\mathrm{Enu}}_0$ es verdadero y ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$ para cada $k$, entonces ${\mathrm{Enu}}_k$ vale para todo $k\in \omega$.

El tipo (Guía 8, p. 4). Los nombres de constante son palabras sobre un alfabeto ${\Sigma }_1$, los de función sobre ${\Sigma }_2$ y los de relación sobre ${\Sigma }_3$; los tres alfabetos son disjuntos de a pares y ninguno contiene $\forall$, $\exists$, $\neg$, los nexos, los paréntesis, la coma, $\equiv$, la $X$ ni los numerales itálicos o negritas. Además ninguna palabra de $𝒞$ es subpalabra propia de otra palabra de $𝒞$, y lo mismo dentro de $ℱ$ y dentro de $ℛ$.

Lema 2 (Mordisqueo de términos, Guía 9, p. 5). «Sean $s,t\in T^{\tau }$ y supongamos que hay palabras $x,y,z$, con $y\ne \epsilon$, tales que $s=xy$ y $t=yz$. Entonces $x=z=\epsilon$ o $s,t\in 𝒞$. En particular si un término es tramo inicial o final de otro término, entonces dichos términos son iguales.» La guía lo acepta sin prueba (Ejercicio 9) y así se usa acá.

El hecho de ocurrencias, que es lo que la prueba necesita saber de dónde está una ocurrencia. Son los incisos (a), (b) y (c) del Lema 4 de la Guía 9 (p. 7), que no están ni en Menú ni en lectura única, así que se enuncian y se prueban (la prueba está en el escarabajo). Sean $s,t\in T^{\tau }$ y una ocurrencia de $s$ en $t$:

• (O1) Si $t\in \mathrm{Var}\cup 𝒞$, entonces $s=t$ y la ocurrencia es $t$ entera, a partir de 1.
• (O2) Si $s=t$, la única ocurrencia de $s$ en $t$ es $t$ entera.
• (O3) Si $t=f(t_1,\dots ,t_n)$ y $s\ne t$, la ocurrencia sucede dentro de un único $t_j$.

03 · La mariposa: dónde se usa la hipótesis

De atrás para adelante. La meta es $t^{\prime 𝐀}[\overrightarrow{a}]=t^{𝐀}[\overrightarrow{a}]$, y la única manera de calcular $t^{\prime 𝐀}[\overrightarrow{a}]$ es la cláusula que corresponde a la forma de $t^{\prime }$. Así que hace falta saber qué forma tiene $t^{\prime }$, y eso depende de dónde estaban las ocurrencias reemplazadas. El hecho de ocurrencias responde: una ocurrencia de $s_1$ en $f(t_1,\dots ,t_n)$ es el término entero o vive adentro de un argumento. Nunca toma un pedazo del nombre $f$, nunca cruza una coma.

Con eso hay dos situaciones, y son los dos subcasos del paso:

• $s_1=t$. La única ocurrencia es $t$ entera. Si se reemplaza, $t^{\prime }=s_2$ y la cuenta es $t^{\prime 𝐀}[\overrightarrow{a}]=s_2^{𝐀}[\overrightarrow{a}]=s_1^{𝐀}[\overrightarrow{a}]=t^{𝐀}[\overrightarrow{a}]$. Es el único lugar de toda la prueba donde se usa la hipótesis. Lo mismo pasa en el caso base, donde (O1) obliga a que una ocurrencia sea $t$ entera.
• $s_1\ne t$. Cada ocurrencia reemplazada está adentro de un $t_j$, así que $t^{\prime }=f(t_1^{\prime },\dots ,t_n^{\prime })$, donde $t_j^{\prime }$ es el resultado de reemplazar en $t_j$ las ocurrencias elegidas que caen en $t_j$. La hipótesis inductiva da $t_j^{\prime 𝐀}[\overrightarrow{a}]=t_j^{𝐀}[\overrightarrow{a}]$, y la cláusula (3) sube la igualdad.

Qué va adentro del ${\mathrm{Enu}}_k$. Lo que cambia al bajar de $t$ a $t_j$: el término, y también cuáles ocurrencias se reemplazan, porque en $t_j$ se reemplazan sólo las que caen ahí, que pueden ser todas, algunas o ninguna. Por eso el ${\mathrm{Enu}}_k$ dice «si $t^{\prime }$ es el resultado de reemplazar algunas (posiblemente 0) ocurrencias», y no habla de un $t^{\prime }$ fijo de antemano. El «posiblemente 0» es el que deja aplicar la hipótesis inductiva a los argumentos donde no se reemplazó nada, sin un caso aparte. Con un ${\mathrm{Enu}}_k$ escrito para «una ocurrencia», los argumentos intactos quedarían sin cubrir.

La estructura y la asignación no cambian nunca: la cláusula (3) evalúa los argumentos en la misma $\overrightarrow{a}$. Acá se podrían fijar afuera de la inducción y la prueba andaría. Se escriben adentro igual, porque es el molde de los Ejercicios 5 y 6 y porque en el Ejercicio 13, que usa éste, la asignación sí cambia al pasar por un cuantificador, y ahí dejarla afuera rompe la prueba.

Con la hipótesis en pie, cualquier combinación de ocurrencias deja el valor quieto, y la lista de argumentos muestra por qué: cada argumento cambia de palabra pero no de valor. Sin la hipótesis, el argumento que tiene la ocurrencia reemplazada cambia de valor y arrastra al término entero. El último término tiene la ocurrencia en el tercer argumento de $\mathrm{MAS}$, que $i(\mathrm{MAS})$ no mira: ahí el valor no cambia aunque la hipótesis falle. La hipótesis es suficiente para cualquier término, no necesaria en cada uno.

04 · El escarabajo: la prueba escrita

Primero, tres observaciones sobre símbolos.

• (S1) Todo término empieza con $X$, con un símbolo de ${\Sigma }_1$ o con un símbolo de ${\Sigma }_2$. Por lectura única, un término es una variable, que empieza con $X$; un nombre de constante, que es una palabra no vacía sobre ${\Sigma }_1$; o $g(s_1,\dots ,s_m)$, que empieza con el nombre $g\in {\Sigma }_2^{+}$.
• (S2) Un término sólo tiene símbolos de la lista: $X$, numerales itálicos y negritas, símbolos de ${\Sigma }_1$ y de ${\Sigma }_2$, paréntesis y coma. Usaremos la Regla de Inducción desde 0, con ${\mathrm{Enu}}_k$: todo $t\in T_k^{\tau }$ tiene sólo símbolos de esa lista. ${\mathrm{Enu}}_0$ vale: una variable tiene $X$ y numerales, y una constante, símbolos de ${\Sigma }_1$. Si vale ${\mathrm{Enu}}_k$ y $t\in T_{k+1}^{\tau }$, o $t\in T_k^{\tau }$ y vale ${\mathrm{Enu}}_k$, o $t=f(t_1,\dots ,t_n)$ con los $t_j\in T_k^{\tau }$, y $t$ se arma con los símbolos de $f$, que son de ${\Sigma }_2$, paréntesis, comas y los de los $t_j$, que están en la lista por ${\mathrm{Enu}}_k$.
• (S3) Si un término $s$ ocurre en una palabra $w$ a partir de una posición que está dentro de una ocurrencia de un término $u$ en $w$, y el símbolo de $w$ que sigue a esa ocurrencia de $u$ no está en ${\Sigma }_1$ (o no hay ninguno), entonces la ocurrencia de $s$ está dentro de la de $u$. Supongamos que no. Si no hay símbolo después de $u$, la ocurrencia de $s$ no puede pasarse; si lo hay, la ocurrencia de $s$ empieza dentro de $u$ y termina después. Llamemos $x$ a lo de $u$ anterior al comienzo de $s$, $y$ a lo de $u$ desde ese comienzo hasta el final de $u$, y $z$ a lo de $s$ posterior al final de $u$. Entonces $u=xy$ y $s=yz$, con $y\ne \epsilon$ y $z\ne \epsilon$. Por el Lema 2, $x=z=\epsilon$ o $s,u\in 𝒞$; como $z\ne \epsilon$, es $s\in 𝒞$, o sea $s\in {\Sigma }_1^{+}$. Pero el primer símbolo de $z$ es el que sigue a $u$ en $w$, que no está en ${\Sigma }_1$. Absurdo.

Prueba del hecho de ocurrencias.

• (O1), $t\in \mathrm{Var}$. Los símbolos de $t$ son una $X$ y numerales, así que por (S1) $s$ empieza con $X$, y por lectura única $s$ es una variable. La única $X$ de $t$ está en la posición 1: la ocurrencia empieza en 1. El último símbolo de $s$ es un numeral negrita, y el único negrita de $t$ es su último símbolo: la ocurrencia termina en $|t|$. Luego $s=t$ y la ocurrencia es $t$ entera.
• (O1), $t\in 𝒞$. Los símbolos de $t$ son de ${\Sigma }_1$, así que $s$ no empieza con $X$ ni con un símbolo de ${\Sigma }_2$, que es disjunto de ${\Sigma }_1$; por lectura única $s\in 𝒞$. Entonces $s$ es una palabra de $𝒞$ que es subpalabra de $t\in 𝒞$, y por la condición de tipo no es subpalabra propia: $s=t$. Por (O2), la ocurrencia es $t$ entera.
• (O2). Si $t$ ocurre en $t$ a partir de $p$, la ocurrencia ocupa las posiciones $p,\dots ,p+|t|-1$, y tiene que ser $p+|t|-1\le |t|$. Luego $p=1$.
• (O3). Sea $t=f(t_1,\dots ,t_n)$, $s\ne t$, y supongamos que $s$ ocurre a partir de $p$. Las posiciones de $t$ son, en orden: las de $f$, de 1 a $|f|$; un «(»; las de $t_1$; una coma; …; las de $t_n$; un «)». Veamos dónde puede estar $p$.
  • $p=1$: entonces $s$ es tramo inicial de $t$, y los dos son términos. Por el Lema 2, $s=t$, contra lo supuesto.
  • $2\le p\le |f|$: el símbolo en $p$ es de ${\Sigma }_2$, así que por lectura única $s=g(s_1,\dots ,s_m)$ con $g\in ℱ$, y $g$ es lo que hay en $s$ antes de su primer «(». Como $f$ no tiene paréntesis, el primer «(» de $t$ a partir de $p$ es el que sigue a $f$; luego $g$ es la subpalabra de $f$ que va de $p$ a $|f|$, propia porque $p\ge 2$. Eso contradice la condición de tipo dentro de $ℱ$.
  • $p$ en el «(», en una coma o en el «)» final: ningún término empieza con esos símbolos, por (S1).
  • $p$ dentro de algún $t_j$: el símbolo que sigue a $t_j$ en $t$ es una coma o el «)» final, que no están en ${\Sigma }_1$. Por (S3), la ocurrencia está dentro de $t_j$. Es un único $t_j$ porque los argumentos ocupan tramos disjuntos.

Prueba del ejercicio. Fijemos $s_1,s_2\in T^{\tau }$. 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 $t^{\prime }$ es el resultado de reemplazar algunas (posiblemente 0) ocurrencias de $s_1$ en $t$ por $s_2$, entonces para cualquier estructura $𝐀=(A,i)$ de tipo $\tau$ y cualquier asignación $\overrightarrow{a}\in A^{𝐍}$ tal que $s_1^{𝐀}[\overrightarrow{a}]=s_2^{𝐀}[\overrightarrow{a}]$, se tiene que $t^{\prime 𝐀}[\overrightarrow{a}]=t^{𝐀}[\overrightarrow{a}]$.

• Prueba de que ${\mathrm{Enu}}_0$ es verdadero. Sean $t\in T_0^{\tau }=\mathrm{Var}\cup 𝒞$, $t^{\prime }$ como en el enunciado, $𝐀$ y $\overrightarrow{a}$ con $s_1^{𝐀}[\overrightarrow{a}]=s_2^{𝐀}[\overrightarrow{a}]$. Si no se reemplazó ninguna ocurrencia, $t^{\prime }=t$ y no hay nada que probar. Si se reemplazó alguna, por (O1) es $s_1=t$ y esa ocurrencia es $t$ entera, que por (O2) es la única. Entonces $t^{\prime }=s_2$ y $t^{\prime 𝐀}[\overrightarrow{a}]=s_2^{𝐀}[\overrightarrow{a}]=s_1^{𝐀}[\overrightarrow{a}]=t^{𝐀}[\overrightarrow{a}]$.
• Prueba de que ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$. Supongamos que vale ${\mathrm{Enu}}_k$. Sean $t\in T_{k+1}^{\tau }$, $t^{\prime }$ el resultado de reemplazar algunas (posiblemente 0) ocurrencias de $s_1$ en $t$ por $s_2$, y $𝐀$, $\overrightarrow{a}$ con $s_1^{𝐀}[\overrightarrow{a}]=s_2^{𝐀}[\overrightarrow{a}]$. Por definición de $T_{k+1}^{\tau }$ hay dos casos.
  • Caso $t\in T_k^{\tau }$. Como vale ${\mathrm{Enu}}_k$, $t^{\prime 𝐀}[\overrightarrow{a}]=t^{𝐀}[\overrightarrow{a}]$.
  • 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 }$.
    • Si $s_1=t$: por (O2) la única ocurrencia de $s_1$ en $t$ es $t$ entera. Si no se la reemplazó, $t^{\prime }=t$. Si se la reemplazó, $t^{\prime }=s_2$ y $t^{\prime 𝐀}[\overrightarrow{a}]=s_2^{𝐀}[\overrightarrow{a}]=s_1^{𝐀}[\overrightarrow{a}]=t^{𝐀}[\overrightarrow{a}]$.
    • Si $s_1\ne t$: por (O3) cada ocurrencia reemplazada sucede dentro de un único $t_j$. Para cada $j$ sea $t_j^{\prime }$ el resultado de reemplazar por $s_2$ las ocurrencias reemplazadas que suceden dentro de $t_j$ (posiblemente ninguna). Reemplazar adentro de $t_j$ sólo cambia los símbolos de $t_j$, así que $t^{\prime }=f(t_1^{\prime },\dots ,t_n^{\prime })$. Por lo aceptado en la consigna, cada $t_j^{\prime }\in T^{\tau }$; y como $t_j\in T_k^{\tau }$ y $t_j^{\prime }$ es el resultado de reemplazar algunas (posiblemente 0) ocurrencias de $s_1$ en $t_j$ por $s_2$, ${\mathrm{Enu}}_k$, aplicado con las mismas $𝐀$ y $\overrightarrow{a}$, da $t_j^{\prime 𝐀}[\overrightarrow{a}]=t_j^{𝐀}[\overrightarrow{a}]$ para $j=1,\dots ,n$. Por la cláusula (3) de la definición de valor, $$t^{\prime 𝐀}[\overrightarrow{a}]=i(f)(t_1^{\prime 𝐀}[\overrightarrow{a}],\dots ,t_n^{\prime 𝐀}[\overrightarrow{a}])=i(f)(t_1^{𝐀}[\overrightarrow{a}],\dots ,t_n^{𝐀}[\overrightarrow{a}])=t^{𝐀}[\overrightarrow{a}]$$

Por la Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ vale para todo $k\in \omega$. Dados $t$, $t^{\prime }$, $𝐀$ y $\overrightarrow{a}$ como en el ejercicio, $t\in T_k^{\tau }$ para algún $k$, y ${\mathrm{Enu}}_k$ da $t^{\prime 𝐀}[\overrightarrow{a}]=t^{𝐀}[\overrightarrow{a}]$. ∎

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

Lo que hace perder puntos. Escribir el ${\mathrm{Enu}}_k$ con un $t^{\prime }$ fijo, o para «una ocurrencia»: en el paso, lo que se reemplaza en $t_j$ es otra elección, y la hipótesis inductiva tiene que cubrirla. No nombrar la Regla de Inducción desde 0. Olvidar el subcaso $s_1=t$, que es el único donde trabaja la hipótesis: sin él la prueba nunca usa que $s_1$ y $s_2$ valen lo mismo, y eso tiene que hacer sospechar. Decir «la ocurrencia está en algún argumento» sin enunciar ni probar el hecho de ocurrencias. Y calcular $t_j^{\prime 𝐀}[\overrightarrow{a}]$ sin decir que $t_j^{\prime }$ es término: lo da el «acepte» de la consigna, que vale para cualquier término, no sólo para $t$.

Lo que se lleva. El Ejercicio 13 lo usa adentro de las fórmulas atómicas, con $t$ en el lugar de $s_1$ y $s$ en el de $s_2$, y una asignación distinta en cada piso del cuantificador. El Ejercicio 5 y el Ejercicio 6 tienen el mismo esqueleto: inducción en el nivel, la ocurrencia entera o adentro de un argumento, la cláusula (3) para subir. El hecho (O3), con «es término» en lugar de «vale lo mismo», es el Ejercicio 1. Y el Ejercicio 9 es este mismo ejercicio un piso más arriba: fórmulas equivalentes en lugar de términos que valen lo mismo.

Para tener a mano

1. ${\mathrm{Enu}}_k$: si $t\in T_k^{\tau }$ y $t^{\prime }$ es el resultado de reemplazar algunas (posiblemente 0) ocurrencias de $s_1$ en $t$ por $s_2$, para toda $𝐀$ y toda $\overrightarrow{a}$ con $s_1^{𝐀}[\overrightarrow{a}]=s_2^{𝐀}[\overrightarrow{a}]$ vale $t^{\prime 𝐀}[\overrightarrow{a}]=t^{𝐀}[\overrightarrow{a}]$.
2. Una ocurrencia de $s_1$ en $f(t_1,\dots ,t_n)$ es el término entero (y entonces $s_1=t$) o vive adentro de un único $t_j$. Se prueba con el Lema 2 de mordisqueo y las condiciones de tipo.
3. Si $s_1=t$, la hipótesis cierra: $t^{\prime }=s_2$ y $s_2^{𝐀}[\overrightarrow{a}]=s_1^{𝐀}[\overrightarrow{a}]$. Si $s_1\ne t$, $t^{\prime }=f(t_1^{\prime },\dots ,t_n^{\prime })$ y la cláusula (3) sube lo que da ${\mathrm{Enu}}_k$.
4. La asignación no cambia en ninguna cláusula del valor de un término: por eso alcanza con la hipótesis en una sola $\overrightarrow{a}$.