La coma delata un argumento

El enunciado, textual: «Pruebe que si $t\in T^{\tau }$ y $t^{\prime }$ es el resultado de reemplazar algunas ocurrencias de la palabra $,\mathrm{X}1$, en $t$ por $,\mathrm{X}2$, entonces $t^{\prime }\in T^{\tau }$.»

La palabra $,\mathrm{X}1$ tiene tres símbolos: una coma, la $\mathrm{X}$ y el numeral negrita $1$. No es un término, así que el Ejercicio 1 no se puede citar, y además acá se reemplazan varias ocurrencias a la vez. La prueba es otra inducción en el nivel, con un caso que el Ejercicio 1 no tenía.

01 · Qué pide, en criollo

Con el tipo de la guía, $\tau =(\{\mathrm{uno},\mathrm{doli}\},\{\mathrm{MAS},\mathrm{P}\},\{\mathrm{Her}\},a)$ con $a(\mathrm{MAS})=4$ y $a(\mathrm{P})=1$, sea

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

de 36 símbolos. La variable $\mathrm{X}1$ ocurre cuatro veces, a partir de 9, 14, 30 y 33, pero $,\mathrm{X}1$ sólo tres, a partir de 8, 29 y 32: la $\mathrm{X}1$ de la posición 14 viene después de un «(». Y ni $\mathrm{X}11$ ni $\mathrm{X}21$ contienen $,\mathrm{X}1$: en $\mathrm{X}11$ lo que sigue a la $\mathrm{X}$ es un $1$ itálico, que es otro símbolo.

Reemplazando las tres queda $\mathrm{MAS}(\mathrm{X}11,\mathrm{X}2,\mathrm{P}(\mathrm{X}1),\mathrm{MAS}(\mathrm{uno},\mathrm{X}21,\mathrm{X}2,\mathrm{X}2))$, que es término; y cualquiera de los ocho subconjuntos de las tres ocurrencias da un término. Lo que cambia, en cada ocurrencia elegida, es un solo símbolo: el $1$ pasa a ser $2$. La coma y la $\mathrm{X}$ quedan donde estaban.

Las tres ocurrencias no están todas en el mismo lugar. Las de 29 y 32 viven adentro del cuarto argumento, $\mathrm{MAS}(\mathrm{uno},\mathrm{X}21,\mathrm{X}1,\mathrm{X}1)$. La de 8 no vive adentro de ningún argumento: su coma es la que separa el primer argumento del segundo, y su $\mathrm{X}1$ es el segundo argumento entero. Ese es el caso nuevo. Lo que lo salva es que después de una coma de afuera empieza un término, un término que empieza con $\mathrm{X}$ es una variable, y el negrita cierra la variable: $\mathrm{X}1$ no puede ser el principio de una variable más larga. El reemplazo cambia la variable $x_1$ por la variable $x_2$, y eso deja un término.

Que lo que se pega sea $,\mathrm{X}2$ importa. Reemplazando la ocurrencia de 8 por $,\mathrm{X}$ queda $\mathrm{MAS}(\mathrm{X}11,\mathrm{X},\mathrm{P}(\mathrm{X}1),\mathrm{MAS}(\mathrm{uno},\mathrm{X}21,\mathrm{X}1,\mathrm{X}1))$, y el segundo argumento, $\mathrm{X}$ suelta, no es un término.

02 · Las herramientas

Los términos y las variables (Guía 9, p. 1). $T_0^{\tau }=\mathrm{Var}\cup 𝒞$, $$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 }\}$$ y $T^{\tau }={\bigcup }_{k\ge 0}{T}_k^{\tau }$; cada nivel contiene al anterior. La variable $x_n$ es la $\mathrm{X}$ seguida de la escritura decimal de $n$ con los numerales en itálica salvo el último, en negrita: $x_1=\mathrm{X}1$, $x_2=\mathrm{X}2$, $x_{11}=\mathrm{X}11$.

El tipo (Guía 8, p. 4). Los nombres de constante, de función y de relación son palabras no vacías sobre alfabetos ${\Sigma }_1$, ${\Sigma }_2$, ${\Sigma }_3$ disjuntos de a pares, y ninguno de esos alfabetos contiene los símbolos lógicos, los paréntesis, la coma, ≡, la $\mathrm{X}$ ni los numerales.

Ocurrencias y reemplazos (p. 6). $\alpha$ ocurre a partir de $i$ en $\beta$ si $\beta =\delta \alpha \gamma$ con $|\delta |=i-1$. Cuando las ocurrencias que se reemplazan son disjuntas entre sí, el reemplazo es simultáneo: se hacen todos de una vez sobre la palabra original.

Teorema 3 (Lectura única de términos, p. 5). Se usa sin enunciar: dado $t\in T^{\tau }$, $t\in \mathrm{Var}\cup 𝒞$, o hay únicos $n\ge 1$, $f\in {ℱ}_n$ y $t_1,\dots ,t_n\in T^{\tau }$ con $t=f(t_1,\dots ,t_n)$.

Lo demás se enuncia y se prueba. Son tres hechos chicos, y ninguno pide inducción: la lectura única ya dice de qué forma es el término.

Hecho 1. Sea $u\in T^{\tau }$. (a) Si $u$ empieza con $\mathrm{X}$, entonces $u\in \mathrm{Var}$. (b) $u$ no termina en una coma ni en $\mathrm{X}$. (c) Si $u\in \mathrm{Var}\cup 𝒞$, $u$ no tiene comas.

Prueba. Por la lectura única, $u$ es una variable, un nombre de constante o $g(s_1,\dots ,s_m)$. Una variable empieza con $\mathrm{X}$, termina en un numeral negrita y no tiene comas. Un nombre de constante tiene todos sus símbolos en ${\Sigma }_1$, que no contiene la $\mathrm{X}$ ni la coma. $g(s_1,\dots ,s_m)$ empieza con el primer símbolo de $g$, que está en ${\Sigma }_2$ y no es $\mathrm{X}$, y termina en «)». (a) sale de que sólo las variables empiezan con $\mathrm{X}$; (b), de los tres últimos símbolos posibles; (c), de los dos primeros casos. ∎

Hecho 2 (dónde puede estar $,\mathrm{X}1$). Sea $t=f(t_1,\dots ,t_n)$ con $f\in {ℱ}_n$ y $t_1,\dots ,t_n\in T^{\tau }$. Toda ocurrencia de $,\mathrm{X}1$ en $t$ cumple una de estas dos:

• (i) sucede dentro de algún $t_j$;
• (ii) su coma es la que separa $t_{j-1}$ de $t_j$, para algún $j\ge 2$, y $t_j=\mathrm{X}1$.

Prueba. La coma de la ocurrencia es un símbolo de $t$. Los símbolos de $t$ son los de $f$, que no tiene comas; el «(»; los de los argumentos; las $n-1$ comas que los separan; y el «)». Así que la coma está adentro de algún $t_j$ o es una de las que separan.

• La coma está en la posición $q$ de $t_j$. Por el Hecho 1(b), $t_j$ no termina en coma, así que $q<|t_j|$ y la $\mathrm{X}$ que sigue también está en $t_j$, en la posición $q+1$. Por el Hecho 1(b) otra vez, $t_j$ no termina en $\mathrm{X}$, así que $q+1<|t_j|$ y el $1$ también está en $t_j$. La ocurrencia sucede dentro de $t_j$: es (i).
• La coma separa $t_{j-1}$ de $t_j$. Lo que sigue a esa coma en $t$ es $t_j$, así que $[t_j{]}_1=\mathrm{X}$, y por el Hecho 1(a), $t_j$ es una variable $x_m$: la $\mathrm{X}$ seguida de numerales, con un solo negrita, que es el último. Su segundo símbolo es el $1$ de la ocurrencia, que es negrita; entonces es el último, y $t_j=\mathrm{X}1$. Es (ii). ∎

Hecho 3. Dos ocurrencias distintas de $,\mathrm{X}1$ en una palabra son disjuntas. Si una empezara en $i$ y otra en $j$ con $i<j\le i+2$, la coma de la segunda estaría en la posición $i+1$ o $i+2$ de la primera, que tienen la $\mathrm{X}$ y el $1$. ∎ Por eso el reemplazo simultáneo tiene sentido, y como $,\mathrm{X}1$ y $,\mathrm{X}2$ sólo difieren en el tercer símbolo, $t^{\prime }$ es $t$ con el $1$ de cada ocurrencia elegida cambiado por $2$: misma longitud, mismas posiciones.

03 · La mariposa: el caso que no cubre la hipótesis

Inducción en el nivel de $t$. En el paso, $t=f(t_1,\dots ,t_n)$ con argumentos de nivel más bajo, y la meta es escribir $t^{\prime }$ como $f(t_1^{\prime },\dots ,t_n^{\prime })$ con cada $t_j^{\prime }$ término. Por el Hecho 3, $t^{\prime }$ cambia algunos $1$ por $2$ y nada más, y todo $1$ de $t$ está adentro de algún argumento, porque $f$, los paréntesis y las comas no son numerales. Así que $t^{\prime }=f(t_1^{\prime },\dots ,t_n^{\prime })$, donde $t_j^{\prime }$ es $t_j$ con los cambios que caen en sus posiciones. Falta ver que cada $t_j^{\prime }$ es término, y eso depende de qué ocurrencia produjo cada cambio.

Si la ocurrencia vive adentro de $t_j$, es una ocurrencia de $,\mathrm{X}1$ en $t_j$, y la hipótesis inductiva se ocupa. Si su coma es de afuera, la ocurrencia no está adentro de ningún argumento —la coma es de $t$, la $\mathrm{X}1$ es de $t_j$— y la hipótesis inductiva no dice nada: habla de ocurrencias en $t_j$, y ésta no lo es. Ahí trabaja el Hecho 2: $t_j=\mathrm{X}1$, y el cambio la convierte en $\mathrm{X}2$, que es término de nivel 0. Es la frontera de siempre en una inducción sobre términos: la hipótesis cubre el interior de las piezas, y los lugares donde se pegan los decide la forma de afuera.

Por qué ${\mathrm{Enu}}_k$ cuantifica las ocurrencias adentro. $t$ viene con un conjunto $O$ de ocurrencias elegidas. La hipótesis se aplica a $t_j$ con otro conjunto: las de $O$ que caen adentro de $t_j$, contadas desde el principio de $t_j$. Si ${\mathrm{Enu}}_k$ hablara de un conjunto fijo, no serviría para $t_j$. Por eso dice «para todo conjunto $O$ de ocurrencias de $,\mathrm{X}1$ en $t$».

Abajo se eligen las ocurrencias a reemplazar. Para cada una se ve dónde está su coma, piso por piso, hasta el término del que es separadora.

Toda coma de un término es separadora de exactamente un subtérmino, y la ocurrencia está «adentro» en todos los pisos de arriba y «de afuera» en ese. Por eso la prueba no necesita saber de antemano a qué profundidad está cada coma: en cada piso, la que es de afuera se resuelve con el Hecho 2, y las demás se le pasan a la hipótesis inductiva.

04 · El escarabajo: la prueba como se entrega

Se escriben primero los Hechos 1, 2 y 3 con sus pruebas, como en la sección 02. Después:

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

${\mathrm{Enu}}_k$: para todo $t\in T_k^{\tau }$ y todo conjunto $O$ de ocurrencias de $,\mathrm{X}1$ en $t$, si $t^{\prime }$ es el resultado de reemplazar simultáneamente cada ocurrencia de $O$ por $,\mathrm{X}2$, entonces $t^{\prime }\in T^{\tau }$.

• ${\mathrm{Enu}}_0$ es verdadero. Si $t\in T_0^{\tau }=\mathrm{Var}\cup 𝒞$, por el Hecho 1(c) $t$ no tiene comas, así que $,\mathrm{X}1$ no ocurre en $t$, $O=\varnothing$ y $t^{\prime }=t\in T^{\tau }$.
• ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$. Supongamos que vale ${\mathrm{Enu}}_k$. Sean $t\in T_{k+1}^{\tau }$, $O$ un conjunto de ocurrencias de $,\mathrm{X}1$ en $t$ y $t^{\prime }$ el resultado del reemplazo. Por definición de $T_{k+1}^{\tau }$ hay dos casos.
  • Caso $t\in T_k^{\tau }$. Por ${\mathrm{Enu}}_k$, $t^{\prime }\in T^{\tau }$.
  • 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 }$. Por el Hecho 3, $t^{\prime }$ se obtiene de $t$ cambiando por $2$ el $1$ de cada ocurrencia de $O$. Ninguno de esos $1$ está en $f$, en los paréntesis ni en las comas que separan argumentos, así que cada uno está en las posiciones de algún $t_j$, y $$t^{\prime }=f(t_1^{\prime },\dots ,t_n^{\prime })$$ donde $t_j^{\prime }$ es $t_j$ con los cambios que caen en sus posiciones. Veamos que cada $t_j^{\prime }\in T^{\tau }$. Por el Hecho 2, cada ocurrencia de $O$ es de tipo (i) o (ii). Fijemos $j$.
    • Si $j\ge 2$ y la coma que separa $t_{j-1}$ de $t_j$ es la de una ocurrencia de $O$, por el Hecho 2(ii) $t_j=\mathrm{X}1$. Por el Hecho 1(c), $t_j$ no tiene comas, así que ninguna ocurrencia de tipo (i) cae en $t_j$, y el único cambio en $t_j$ es el de esa ocurrencia, que cambia su $1$: $t_j^{\prime }=\mathrm{X}2=x_2\in T_0^{\tau }$.
    • Si no, los cambios en $t_j$ son los de las ocurrencias de $O$ que suceden dentro de $t_j$. Cada una es una ocurrencia de $,\mathrm{X}1$ en $t_j$; sea $O_j$ el conjunto de ellas, como ocurrencias en $t_j$. Entonces $t_j^{\prime }$ es el resultado de reemplazar simultáneamente cada ocurrencia de $O_j$ en $t_j$ por $,\mathrm{X}2$, y como $t_j\in T_k^{\tau }$, por ${\mathrm{Enu}}_k$ aplicado a $t_j$ y $O_j$, $t_j^{\prime }\in T^{\tau }$. Si $O_j=\varnothing$, $t_j^{\prime }=t_j$.
    Cada $t_j^{\prime }$ está en algún $T_{m_j}^{\tau }$. Sea $M$ el máximo de los $m_j$. Como los niveles crecen, $t_1^{\prime },\dots ,t_n^{\prime }\in T_M^{\tau }$, y por definición $t^{\prime }=f(t_1^{\prime },\dots ,t_n^{\prime })\in T_{M+1}^{\tau }\subseteq T^{\tau }$.

Por la Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ vale para todo $k\in \omega$. Dado $t\in T^{\tau }$, está en algún $T_k^{\tau }$, y ${\mathrm{Enu}}_k$ da $t^{\prime }\in T^{\tau }$. ∎

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

Lo que hace perder puntos. Decir que toda ocurrencia de $,\mathrm{X}1$ en $f(t_1,\dots ,t_n)$ vive adentro de algún argumento: la de la posición 8 del ejemplo no. Es el error de copiar el molde del Ejercicio 1 sin mirar qué se reemplaza; allí la palabra era un término y no podía montarse sobre una coma. Citar el Ejercicio 1 o el Lema 4(f) de la guía: $,\mathrm{X}1$ no es un término. Usar «un término que empieza con $\mathrm{X}$ es una variable» sin justificarlo: es el hecho que la guía marca con (*) en la página 4, y acá sale de la lectura única en dos renglones. Olvidar por qué $t_j$ es $\mathrm{X}1$ entera y no el comienzo de algo más largo: lo dice el negrita. Escribir un ${\mathrm{Enu}}_k$ con las ocurrencias fijas, u olvidar el caso $t\in T_k^{\tau }$ y el máximo de los niveles.

Lo que se lleva. El mismo análisis —¿dónde está la palabra que se reemplaza, adentro de un argumento o sobre una frontera?— es el del Ejercicio 4, con $\forall \mathrm{X}1\exists$ en fórmulas, donde la palabra sólo puede ser el comienzo de $\forall x_1\exists w\psi$. Que el primer símbolo decide la forma es la idea del Ejercicio 2, ahora con términos. Y las fronteras de una inducción sobre términos, con los Ejercicios 6 y 7 de la guía, están en Inducción en la construcción.

Para tener a mano

1. $,\mathrm{X}1$ no es término: el Ejercicio 1 no se aplica. Sus ocurrencias son disjuntas, y reemplazarlas sólo cambia $1$ por $2$.
2. En $f(t_1,\dots ,t_n)$, una ocurrencia vive adentro de un $t_j$ (porque un término no termina en coma ni en $\mathrm{X}$) o su coma es de afuera y $t_j=\mathrm{X}1$ (porque un término que empieza con $\mathrm{X}$ es variable, y el negrita la cierra).
3. ${\mathrm{Enu}}_k$: para todo $t\in T_k^{\tau }$ y todo conjunto $O$ de ocurrencias de $,\mathrm{X}1$ en $t$, el reemplazo da un término. El conjunto va adentro porque en el paso cambia.
4. El caso de la coma de afuera no lo cubre la hipótesis inductiva: ahí $t_j^{\prime }=\mathrm{X}2$, de nivel 0.
5. Base: variables y constantes no tienen comas, y no hay nada que reemplazar.