Se compara por el lado de lo que ya se sabe

Las consignas, textuales. Ejercicio 10: «Sea $\tau$ un tipo. Si $t_1,t_2,s_1,s_2\in T^{\tau }$ y $t_1{t}_2=s_1{s}_2$, entonces $t_1=s_1$ y $t_2=s_2$». Ejercicio 11: «Sea $\tau$ un tipo. Si $f\in {ℱ}_2$ y $f(\alpha ,t),t\in T^{\tau }$, entonces $\alpha \in T^{\tau }$». Ejercicio 12: «Complete las partes no hechas en la prueba anterior», que es la del Lema 4, ocurrencias de términos en términos.

Justo antes está el Ejercicio 9: «No haga la prueba del lema anterior». El lema es el de mordisqueo, y la guía lo acepta sin prueba. Los tres ejercicios lo usan así: enunciado y sin demostrar. El lema, la lectura única y lo que se hace con ellos están en Mordisqueo y lectura única de términos.

01 · Antes de probar: qué se cancela y qué no

El 10 mira una misma palabra escrita de dos maneras como concatenación de dos términos, y dice que las piezas coinciden. Con palabras cualesquiera sería falso de mil maneras: cualquier palabra se corta donde uno quiera. Lo instructivo es que tampoco alcanza con saber que alguna pieza de cada lado es término. La palabra $\mathrm{X}1,\mathrm{X}2$ se escribe como $t_1{t}_2$ con $t_1=\mathrm{X}1$ y $t_2=,\mathrm{X}2$, y como $s_1{s}_2$ con $s_1=\mathrm{X}1,$ y $s_2=\mathrm{X}2$. Son términos $t_1$ y $s_2$, y sin embargo $t_1\ne s_1$. Los dos términos están en lados distintos, y el mordisqueo compara dos piezas del mismo lado.

El 11 da dos datos: que $f(\alpha ,t)$ es término y que $t$ lo es. De $\alpha$ no dice nada, porque es lo que hay que probar. Sin el segundo dato el enunciado es falso, y el contraejemplo es el del Ejercicio 2(h). En el tipo de los reticulados terna, el término $$\mathrm{s}(\mathrm{s}(\mathrm{X}1,\mathrm{X}2),\mathrm{X}3)$$ tiene catorce símbolos y dos comas, en las posiciones 7 y 11. Cortando en la 7, $\alpha =\mathrm{s}(\mathrm{X}1$ y $\beta =\mathrm{X}2),\mathrm{X}3$: la palabra $f(\alpha ,\beta )$ es el término de arriba, y ni $\alpha$ ni $\beta$ son términos. A $\alpha$ lo delata que tiene un «(» y ningún «)».

La versión simétrica también es verdadera: si $f(t,\beta )$ y $t$ son términos, $\beta$ es término. Sale con la misma prueba dada vuelta. Lo que decide por dónde se compara no es la forma del enunciado: es de qué pieza ya se sabe que es término.

El 12 no pide un enunciado nuevo: pide las partes del Lema 4 que la guía no probó. La guía prueba (c) y (d), y del resto dice que (a) y (b) «son fáciles y dejados al lector», que (e) «es consecuencia inmediata de (d)» y que la prueba de (f) «es similar a la de (d)». Hay que escribir esas cuatro, y de paso el caso base de (d), que sin (a) y (b) queda a medio justificar.

02 · Las herramientas, como las da la guía

La regla de corrección de la cátedra es que un resultado de una guía que se usa se enuncia y se prueba aparte, salvo que la guía diga que se usa sin prueba, como el Lema 2. Acá se usan dos definiciones, dos lemas y un teorema.

Tramos. «Diremos que $\beta$ es un tramo inicial (propio) de $\alpha$ si hay una palabra $\gamma$ tal que $\alpha =\beta \gamma$ (y $\beta \notin \{\epsilon ,\alpha \}$). En forma similar se define tramo final (propio).» Y un hecho de palabras que la guía usa sin nombrarlo: dos tramos iniciales de una misma palabra son uno tramo inicial del otro. Si $w=\beta \gamma ={\beta }^{\prime }{\gamma }^{\prime }$ y $|\beta |\le |{\beta }^{\prime }|$, los primeros $|\beta |$ símbolos de $w$ son $\beta$ y son también los primeros $|\beta |$ símbolos de ${\beta }^{\prime }$. Con tramos finales, lo mismo leyendo desde el final.

Lema 2 (Mordisqueo de términos, 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.» Lo que usan los tres ejercicios es el «en particular». El caso $s,t\in 𝒞$ es el de dos nombres de constante que se mordisquean, como «uno» y «noli», que comparten «no»; aun así, ninguno de los dos es tramo inicial ni final del otro.

Teorema 3 (Lectura Única de Términos, p. 5). «Dado $t\in T^{\tau }$ se da una y solo una de las siguientes: (1) $t\in \mathrm{Var}\cup 𝒞$; (2) Hay únicos $n\ge 1$, $f\in {ℱ}_n$, $t_1,\dots ,t_n\in T^{\tau }$ tales que $t=f(t_1,\dots ,t_n)$. Mas aún si $t\in T_{k+1}^{\tau }$ entonces cuando se da (2) los términos $t_1,\dots ,t_n$ están en $T_k^{\tau }$.»

Subtérmino (p. 7). «Sean $s,t\in T^{\tau }$. Diremos que $s$ es subtermino (propio) de $t$ si (no es igual a $t$ y) $s$ es subpalabra de $t$.» Y $\alpha$ ocurre a partir de $i$ en $\beta$ cuando $\beta =\delta \alpha \gamma$ con $|\delta |=i-1$ (p. 6).

Lema 4 (Ocurrencias de Términos en Términos, p. 7). «Sean $r,s,t,t_1,\dots ,t_n\in T^{\tau }$, con $n\ge 1$ y sea $f\in {ℱ}_n$.

• (a) Si $v\in \mathrm{Var}$, entonces $v$ no tiene subtérminos propios.
• (b) Si $c\in 𝒞$, entonces $c$ no tiene subtérminos propios.
• (c) Si $s\ne f(t_1,\dots ,t_n)$ y $s$ ocurre en $f(t_1,\dots ,t_n)$, entonces dicha ocurrencia sucede dentro de algún $t_j$, $j=1,\dots ,n$.
• (d) Si $r,s$ ocurren en $t$, entonces dichas ocurrencias son disjuntas o una ocurre dentro de otra.
• (e) Si $r$ ocurre en $t$, entonces las distintas ocurrencias de $r$ en $t$ son disjuntas.
• (f) Si $t^{\prime }$ es el resultado de reemplazar una ocurrencia de $s$ en $t$ por $r$, entonces $t^{\prime }\in T^{\tau }$.»

El Lema 2 se enuncia y no se prueba: lo dice la propia guía, en el Ejercicio 9. El Teorema 3 y los incisos (c) y (d) del Lema 4 vienen con su prueba en la guía.

03 · Ejercicio 10, la mariposa: dos tramos iniciales

La meta son dos igualdades entre términos, y la única herramienta que da una igualdad entre términos es el «en particular» del Lema 2: hace falta que uno sea tramo inicial del otro. ¿Hay dos términos así? $t_1$ y $s_1$ son tramos iniciales de la misma palabra, $t_1{t}_2=s_1{s}_2$, y el hecho de palabras dice que uno es tramo inicial del otro. Los dos son términos, así que el lema los iguala.

La segunda igualdad no necesita el lema. Dos palabras iguales tienen los mismos símbolos en las mismas posiciones; si las dos empiezan con $t_1$, lo que viene después de los primeros $|t_1|$ símbolos también coincide.

Mirando la prueba entera, nunca se usó que $t_2$ y $s_2$ sean términos. El enunciado da cuatro términos y alcanza con dos, siempre que estén del mismo lado: con $t_1,s_1\in T^{\tau }$ se compara por adelante, y con $t_2,s_2\in T^{\tau }$ se compara por atrás y se cancela al revés. Con uno de cada lado, como en $\mathrm{X}1,\mathrm{X}2$, no se compara nada. El Ejercicio 11 es exactamente la situación en que sólo se conoce el par de atrás.

04 · Ejercicio 10, el escarabajo

Prueba. Sean $t_1,t_2,s_1,s_2\in T^{\tau }$ tales que $t_1{t}_2=s_1{s}_2$, y llamemos $w$ a esa palabra.

• $t_1$ es tramo inicial de $w$, con $\gamma =t_2$, y $s_1$ también, con $\gamma =s_2$. Si $|t_1|\le |s_1|$, los primeros $|t_1|$ símbolos de $w$ son $t_1$ y son también los primeros $|t_1|$ símbolos de $s_1$: $t_1$ es tramo inicial de $s_1$. Si $|s_1|\le |t_1|$, del mismo modo $s_1$ es tramo inicial de $t_1$.
• En cualquiera de los dos casos un término es tramo inicial de otro término, y por el Lema 2 (en particular), $t_1=s_1$.
• Entonces $t_1{t}_2=t_1{s}_2$. Las dos palabras tienen los mismos símbolos en las mismas posiciones, así que borrando los primeros $|t_1|$ símbolos de cada una queda $t_2=s_2$. ∎

05 · Ejercicio 11, la mariposa: por qué por atrás

Primero, dos lecturas de la misma palabra. Llamemos $u=f(\alpha ,t)$. Para comparar hace falta otra manera de escribir $u$, una en la que las piezas sean términos, y eso lo da el Teorema 3: $u$ tiene paréntesis, así que no es variable ni nombre de constante, y entonces $u=g(s_1,\dots ,s_m)$ con $s_1,\dots ,s_m\in T^{\tau }$. Ningún nombre de función tiene paréntesis, así que $f$ y $g$ son, los dos, lo que hay antes del primer «(»: $g=f$ y $m=2$. Borrando «$f($» del principio y «$)$» del final queda

$$\alpha ,t=s_1,s_2$$

Por adelante no se puede. $\alpha$ y $s_1$ son tramos iniciales de esa palabra, así que uno es tramo inicial del otro. Para igualarlos, el Lema 2 pide que los dos sean términos, y que $\alpha$ lo sea es justamente lo que se quiere probar. Comparar por adelante es dar por sabido el resultado. Y no es una sutileza de redacción: en el Ejercicio 2(h), $\alpha =\mathrm{s}(\mathrm{X}1$ es tramo inicial propio de $s_1=\mathrm{s}(\mathrm{X}1,\mathrm{X}2)$, y no son iguales.

Por atrás, sí. $t$ y $s_2$ son tramos finales de la misma palabra, así que uno es tramo final del otro. Ahora los dos son términos: $t$ por hipótesis, $s_2$ por el Teorema 3. El lema da $t=s_2$, y cancelando $t$ y la coma que lo precede queda $\alpha =s_1$, que es término.

Abajo están las dos lecturas de una misma palabra. Elegís la coma que separa $\alpha$ de $t$, qué se sabe y por qué lado comparar, y se ve qué paso de la prueba se puede dar y cuál no.

Con la coma buena y $t$ conocido, por adelante el paso del lema queda en rojo aunque $\alpha$ sea, de hecho, $s_1$: la prueba no tiene cómo saberlo. Con la coma equivocada pasa otra cosa: $t$ deja de ser término, la hipótesis del ejercicio no se cumple, y por atrás $t$ y $s_2$ ya no son la misma palabra: uno es tramo final propio del otro.

Eso último no es una casualidad de los ejemplos. Si con una coma equivocada el pedazo de la derecha fuera término, el Ejercicio 11 diría que es $s_2$, y la coma sería la de la lectura única. Con la versión simétrica, lo mismo para el pedazo de la izquierda. Así que un corte equivocado rompe las dos piezas a la vez: nunca queda una sola sana.

06 · Ejercicio 11, el escarabajo

Prueba. Sean $f\in {ℱ}_2$ y $\alpha$ una palabra tales que $f(\alpha ,t)\in T^{\tau }$ y $t\in T^{\tau }$, y llamemos $u=f(\alpha ,t)$.

• $u$ contiene el símbolo «(». Una variable es una $\mathrm{X}$ seguida de numerales, y un nombre de constante está escrito con símbolos de ${\Sigma }_1$, que no incluye paréntesis; así que $u\notin \mathrm{Var}\cup 𝒞$.
• Por el Teorema 3 se da (2): hay $m\ge 1$, $g\in {ℱ}_m$ y $s_1,\dots ,s_m\in T^{\tau }$ tales que $u=g(s_1,\dots ,s_m)$.
• Los nombres de función tampoco tienen paréntesis, así que $f$ y $g$ son, los dos, el tramo inicial de $u$ que termina justo antes del primer «(». Luego $g=f$, y $m=a(f)=2$.
• Borrando de las dos escrituras de $u$ los primeros $|f|+1$ símbolos y el último, queda $\alpha ,t=s_1,s_2$.
• $t$ y $s_2$ son tramos finales de esa palabra, así que, leyendo desde el final, el más corto es tramo final del otro. Como $t\in T^{\tau }$ por hipótesis y $s_2\in T^{\tau }$, por el Lema 2 (en particular), $t=s_2$.
• Entonces $\alpha ,t=s_1,t$. Borrando los últimos $|t|$ símbolos de cada lado queda la igualdad $\alpha ,=s_1,$; borrando además la coma final, $\alpha =s_1$. Como $s_1\in T^{\tau }$, concluimos $\alpha \in T^{\tau }$. ∎

07 · Ejercicio 12, la mariposa: lo que la guía deja abierto

La guía prueba (c) con el mordisqueo y (d) por inducción en el nivel. Lo que deja se ordena solo:

• (a) y (b) son el caso base de todo. El caso base de (d) en la guía dice que si $r$ y $s$ ocurren en una variable, son variables, y que «nunca una variable es subpalabra propia de otra». Eso es (a) con otras palabras. Escritos (a) y (b), la base de (d) es un renglón.
• (a) es por qué la guía escribe las variables así. Que el último numeral sea el único negrita es lo que impide que $\mathrm{X}1$ ocurra en $\mathrm{X}12$ o en $\mathrm{X}21$: en las dos el $1$ es itálico. La prueba usa exactamente eso: un subtérmino de una variable tiene que empezar en su única $\mathrm{X}$ y terminar en su único negrita.
• (b) es la condición 3 de la definición de tipo: ningún nombre de constante es subpalabra propia de otro.
• (e) sale de (d) más una cuenta de longitudes. Dos ocurrencias del mismo término miden lo mismo, y una ocurrencia de largo $|r|$ dentro de otra de largo $|r|$ ocupa las mismas posiciones.
• (f) es el molde de (d). Inducción desde 0; en el paso, si lo que se reemplaza no es $t$ entero, (c) dice que la ocurrencia está adentro de algún argumento $t_j$, y ahí se usa la hipótesis inductiva.

Un ejemplo para ver qué dice cada inciso. En $t=\mathrm{s}(\mathrm{X}1,\mathrm{i}(\mathrm{X}1,\mathrm{X}2))$, de catorce símbolos, $\mathrm{X}1$ ocurre a partir de 3 y de 8, y $\mathrm{i}(\mathrm{X}1,\mathrm{X}2)$ a partir de 6, ocupando de la 6 a la 13. La ocurrencia de $\mathrm{X}1$ desde 8 sucede dentro de la de $\mathrm{i}(\mathrm{X}1,\mathrm{X}2)$ y la desde 3 es disjunta con ella: es (d). Las dos de $\mathrm{X}1$ son disjuntas entre sí: es (e). Reemplazando la que empieza en 8 por $\mathrm{i}(\mathrm{X}2,\mathrm{X}3)$ queda $$\mathrm{s}(\mathrm{X}1,\mathrm{i}(\mathrm{i}(\mathrm{X}2,\mathrm{X}3),\mathrm{X}2))$$ que es un término de veinte símbolos, de nivel 3: es (f). Con palabras que no son términos, (e) falla: en el ejemplo de la guía, «aba» ocurre en «cccccccababacccccccccc» a partir de 8 y de 10, y las dos ocurrencias comparten la «a» de la posición 10.

08 · Ejercicio 12, el escarabajo

(a) Prueba. Sean $v\in \mathrm{Var}$ y $s\in T^{\tau }$ una subpalabra de $v$. Veamos que $s=v$.

• Por el Teorema 3, $s\in \mathrm{Var}\cup 𝒞$ o $s=g(s_1,\dots ,s_m)$. Lo segundo no puede ser: $s$ tendría un «(», y $v$ no tiene.
• $s\notin 𝒞$: un nombre de constante es una palabra no vacía sobre ${\Sigma }_1$, que no contiene la $\mathrm{X}$ ni los numerales itálicos y negritas, y todos los símbolos de $v$ son de esos.
• Luego $s\in \mathrm{Var}$. Entonces $s$ empieza con $\mathrm{X}$, y la única $\mathrm{X}$ de $v$ es su primer símbolo: $s$ es tramo inicial de $v$. Y $s$ termina en un numeral negrita, y el único negrita de $v$ es su último símbolo: $s$ termina donde termina $v$. Luego $s=v$, y $v$ no tiene subtérminos propios. ∎

(b) Prueba. Sean $c\in 𝒞$ y $s\in T^{\tau }$ una subpalabra de $c$. Todos los símbolos de $s$ están en ${\Sigma }_1$, así que $s$ no es una variable, que empezaría con $\mathrm{X}$, ni de la forma $g(s_1,\dots ,s_m)$, que tendría un «(». Por el Teorema 3, $s\in 𝒞$, y es subpalabra de $c$. Por la condición 3 de la definición de tipo, ningún nombre de constante es subpalabra propia de otro; luego $s=c$. ∎

El caso base de (d). Sean $t\in T_0^{\tau }=\mathrm{Var}\cup 𝒞$ y $r,s\in T^{\tau }$ que ocurren en $t$. Los dos son subpalabras de $t$, así que por (a) o por (b), $r=s=t$. Y una palabra de largo $|t|$ sólo ocurre en $t$ a partir de 1: a partir de $i>1$ necesitaría $i-1+|t|>|t|$ símbolos. Las dos ocurrencias son la misma, así que una sucede dentro de la otra.

(e) Prueba. Sean dos ocurrencias de $r$ en $t$, a partir de $i$ y de $j$, con $i\ne j$. Por (d), tomando $s$ como $r$, son disjuntas o una sucede dentro de la otra. Supongamos que la que empieza en $i$ sucede dentro de la que empieza en $j$. Ocupa $|r|$ posiciones entre las $|r|$ posiciones $j,\dots ,j+|r|-1$, o sea todas, y entonces empieza en $j$: $i=j$, absurdo. El otro caso es igual. Luego son disjuntas. ∎

(f) Prueba. Por la Regla de Inducción desde 0, con el enunciado

${\mathrm{Enu}}_k$: para todo $t\in T_k^{\tau }$ y todos $r,s\in T^{\tau }$, si $t^{\prime }$ es el resultado de reemplazar una ocurrencia de $s$ en $t$ por $r$, entonces $t^{\prime }\in T^{\tau }$.

• ${\mathrm{Enu}}_0$ es verdadero. Sea $t\in \mathrm{Var}\cup 𝒞$ y $s$ que ocurre en $t$. Por (a) o por (b), $s=t$, y como en el caso base de (d), la ocurrencia es la de $t$ entero, a partir de 1. Reemplazarla por $r$ da $t^{\prime }=r\in T^{\tau }$.
• ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$. Supongamos ${\mathrm{Enu}}_k$ y sea $t\in T_{k+1}^{\tau }$. Si $t\in T_k^{\tau }$, vale por ${\mathrm{Enu}}_k$. Si no, por la definición de $T_{k+1}^{\tau }$, $t=f(t_1,\dots ,t_n)$ con $f\in {ℱ}_n$ y $t_1,\dots ,t_n\in T_k^{\tau }$.
  • Si $s=t$, la única ocurrencia de $s$ en $t$ es la de $t$ entero, y $t^{\prime }=r\in T^{\tau }$.
  • Si $s\ne t$, por (c) la ocurrencia reemplazada sucede dentro de algún $t_j$. Sea $t_j^{\prime }$ el resultado de reemplazarla en $t_j$ por $r$. Entonces $t^{\prime }=f(t_1,\dots ,t_{j-1},t_j^{\prime },t_{j+1},\dots ,t_n)$, y como $t_j\in T_k^{\tau }$, por ${\mathrm{Enu}}_k$ (con los mismos $r$ y $s$), $t_j^{\prime }\in T^{\tau }$.
  • Cada argumento de $t^{\prime }$ está en algún $T_{m_i}^{\tau }$. Tomando $M$ el máximo de los $m_i$, están todos en $T_M^{\tau }$, porque los $T_k^{\tau }$ crecen con $k$. Luego $t^{\prime }\in T_{M+1}^{\tau }\subseteq T^{\tau }$.

Por la Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ vale para todo $k$, y como todo término está en algún $T_k^{\tau }$, vale (f). ∎

09 · Lo que se lleva a otros ejercicios

Cancelar es comparar dos piezas del mismo lado, y las dos tienen que ser términos. Antes de escribir «uno es tramo inicial del otro», preguntá de cuál de las dos piezas ya sabés que es término: ese es el lado. El Ejercicio 11 compara por atrás porque $t$ está atrás.

Con fórmulas, el mismo razonamiento cambia en un punto. El Ejercicio 19 es el 11 con $(\alpha \wedge \beta )$ y $\beta$ fórmula, y también compara por atrás. Pero una fórmula sí puede ser tramo final propio de otra —$(x_1\equiv x_1)$ lo es de $\neg (x_1\equiv x_1)$—, así que el mordisqueo de fórmulas no da la igualdad directo y hay que mirar qué puede sobrar adelante. Está en Una fórmula puede ser el final de otra, nunca el principio. El 18, en cambio, sale igual que el 10.

(f) es lo que deja reemplazar subtérminos sin volver a probar que el resultado es término, y su molde —inducción desde 0, (c) para mandar la ocurrencia adentro de un argumento— es el de los lemas de ocurrencias de fórmulas que vienen después. Las ocurrencias y los reemplazos, con sus ejemplos, están en Ocurrencias y reemplazos.

Lo que hace perder puntos. En el 11, comparar por adelante: usa como dato que $\alpha$ es término. En el 10 y en el 11, pasar de «son tramos iniciales de la misma palabra» a «son iguales» sin decir que los dos son términos, que es lo que pide el lema. Usar el Lema 2 o el Teorema 3 sin enunciarlos. En (a), mirar sólo que un tramo inicial propio de una variable no termina en negrita, y olvidar que el subtérmino podría empezar más adelante: hacen falta los dos extremos, la única $\mathrm{X}$ y el único negrita. Y en (f), olvidar que los argumentos de $t^{\prime }$ pueden estar en niveles distintos y hay que subirlos a uno común.

Para tener a mano

1. Dos tramos iniciales de la misma palabra son uno tramo inicial del otro; si los dos son términos, por el Lema 2 son iguales. Lo mismo con tramos finales.
2. En el 10 alcanzan dos de los cuatro términos, si están del mismo lado. Con uno de cada lado no: $\mathrm{X}1,\mathrm{X}2$ se corta como $\mathrm{X}1$ y $,\mathrm{X}2$, o como $\mathrm{X}1,$ y $\mathrm{X}2$.
3. En el 11 se compara por atrás porque el término conocido es $t$. Por adelante habría que saber que $\alpha$ es término, que es lo que se pide. Sin $t\in T^{\tau }$ es falso: $\mathrm{s}(\mathrm{s}(\mathrm{X}1,\mathrm{X}2),\mathrm{X}3)$ cortado en la coma de la posición 7.
4. Un corte equivocado rompe las dos piezas: si una fuera término, el 11 o su simétrico dirían que el corte es el de la lectura única.
5. Lema 4: (a) por la única $\mathrm{X}$ y el único negrita; (b) por la condición 3 de tipo; (e) por (d) y porque dos ocurrencias del mismo término miden lo mismo; (f) por inducción desde 0, con (c) en el paso.