Mordisqueo y lectura única de términos

Un término de tipo τ es una palabra, y una palabra no trae marcados sus cortes. $f(t_1,\dots ,t_n)$ es la concatenación de $f$, «(», $t_1$, «,», …, $t_n$ y «)», y leída de vuelta nada dice cuál de sus comas separa a $t_1$ de $t_2$. La Guía 9 prueba que, si las piezas tienen que ser términos, hay una sola manera de leerla. La pieza clave es un lema sobre cómo pueden encimarse dos términos —el mordisqueo—, y la consecuencia que la guía remarca es que sobre $T^{\tau }$ se pueden definir funciones por recursión, caso por caso, sin que el valor dependa de cómo se lea el término.

01 · Tramo inicial y tramo final

La guía los define así: $\beta$ es un tramo inicial de $\alpha$ si hay una palabra $\gamma$ tal que $\alpha =\beta \gamma$, y es propio si además $\beta \notin \{\epsilon ,\alpha \}$. En forma similar, $\beta$ es un tramo final de $\alpha$ si $\alpha =\gamma \beta$ para alguna $\gamma$, y es propio con la misma condición. En $+(\mathrm{X}1,\mathrm{X}2)$, $+($ es tramo inicial propio, $\mathrm{X}2)$ es tramo final propio, y la palabra entera es tramo inicial y final de sí misma, pero no propio.

Un hecho de palabras que se usa en todas las pruebas de abajo: dos tramos iniciales de una misma palabra están uno adentro del otro. Si $\alpha =\beta \gamma ={\beta }^{\prime }{\gamma }^{\prime }$, los dos son los primeros símbolos de $\alpha$, así que el más corto de $\beta$ y ${\beta }^{\prime }$ es tramo inicial del más largo. Lo mismo con dos tramos finales. Es una obviedad, y es la mitad de cada prueba de lectura única; la otra mitad es saber que dos términos en esa situación tienen que ser iguales.

02 · Constantes que se mordisquean

La definición de tipo exige que ningún nombre de constante sea subpalabra propia de otro nombre de constante. Eso garantiza que un nombre de constante nunca es tramo inicial ni tramo final propio de otro. Lo que sí puede pasar es que un tramo final propio de un nombre de constante $c$ sea un tramo inicial propio de otro nombre de constante $d$: que haya palabras $x,y,z$, las tres distintas de $\epsilon$, tales que $c=xy$ y $d=yz$. En ese caso se dice que $c$ y $d$ se mordisquean.

El ejemplo de la guía es $\tau =(\{\mathrm{uno},\mathrm{noli}\},\varnothing ,\varnothing ,\varnothing )$. Es un tipo, porque ninguno de los dos nombres es subpalabra del otro, y $\mathrm{uno}$ y $\mathrm{noli}$ se mordisquean: con $x=\mathrm{u}$, $y=\mathrm{no}$ y $z=\mathrm{li}$, $\mathrm{uno}=xy$ y $\mathrm{noli}=yz$. Los dos son términos de tipo τ —están en $T_0^{\tau }=\mathrm{Var}\cup \{\mathrm{uno},\mathrm{noli}\}$—, así que dos términos sí pueden encimarse: el final de uno es el principio del otro.

03 · El Lema 2: el único mordisqueo posible

El lema siguiente dice que ése es el único caso de mordisqueo de términos.

Lema 2 (Mordisqueo de términos). 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.

Leído despacio: si el final $y$ de $s$ es el principio de $t$, o el encimado es total —$x=z=\epsilon$, y entonces $s=y=t$— o los dos son nombres de constante, como $\mathrm{uno}$ y $\mathrm{noli}$. Con una variable o un término compuesto en juego, no hay mordisqueo que no sea la igualdad.

La guía lo acepta sin prueba, y su Ejercicio 9 es, textual, «No haga la prueba del lema anterior». Ésa es la consigna: el lema se usa como herramienta. La idea de por qué vale, cuando $s$ es compuesto, está en contar paréntesis: $s$ termina en «)», así que $y$ tiene alguno; un tramo final de $s$ que deja afuera algún paréntesis de $s$ tiene más «)» que «(», y ningún tramo inicial de un término tiene más «)» que «(». Entonces $y$ se lleva todos los paréntesis de $s$, y de ahí, con un poco más de trabajo, sale el resto.

El «en particular» sí conviene saber sacarlo, porque es la forma en que el lema se usa. Si $s$ es tramo inicial de $t$, hay $w$ con $t=sw$. Se aplica el lema al par $s,t$ con $x=\epsilon$, $y=s$ —que no es vacía, porque ningún término lo es— y $z=w$: $s=\epsilon s$ y $t=sw$. Entonces $w=\epsilon$, y $t=s$; o $s,t\in 𝒞$, y como $s$ es subpalabra de $t$ y ningún nombre de constante es subpalabra propia de otro, también $s=t$. Si $s$ es tramo final de $t$, $t=ws$, y el lema va al par $t,s$ con $x=w$, $y=s$, $z=\epsilon$; los dos casos terminan igual.

Dicho al revés: ningún término es tramo inicial propio ni tramo final propio de otro. Tampoco $\mathrm{uno}$ y $\mathrm{noli}$, que se mordisquean sin que ninguno sea tramo del otro.

04 · Cancelar términos

El primer uso es el Ejercicio 10:

Ejercicio 10. Sea τ 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$.

Prueba. $t_1$ y $s_1$ son tramos iniciales de la misma palabra $t_1{t}_2=s_1{s}_2$, así que uno es tramo inicial del otro. En cualquiera de los dos casos, por el «en particular» del Lema 2, $t_1=s_1$. Entonces $t_1{t}_2=t_1{s}_2$, y como las dos palabras coinciden símbolo a símbolo, lo que sigue a los primeros $\left|t_1\right|$ símbolos también coincide: $t_2=s_2$. ∎

Sin la hipótesis de que las cuatro piezas son términos no se cancela nada: la palabra $\mathrm{abc}$ es $\mathrm{ab}$ seguida de $\mathrm{c}$ y también $\mathrm{a}$ seguida de $\mathrm{bc}$. Con términos, en cambio, el corte entre $t_1$ y $t_2$ está forzado.

05 · El Teorema 3: lectura única de términos

Teorema 3 (Lectura única de términos). Dado $t\in T^{\tau }$ se da una y sólo 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)$.

Más 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 }$.

Prueba. Son excluyentes. Ni las variables ni los nombres de constante tienen paréntesis, y $f(t_1,\dots ,t_n)$ sí.

Se da alguna. $t\in T_k^{\tau }$ para algún $k$. Si $k=0$, vale (1). Si $k\ge 1$, el Lema 1 (Menú para términos) da (1) o la existencia de lo que pide (2). Falta la unicidad en (2).

Unicidad. Supongamos $t=f(t_1,\dots ,t_n)=g(s_1,\dots ,s_m)$, con $n,m\ge 1$, $f\in {ℱ}_n$, $g\in {ℱ}_m$ y todos los $t_j$, $s_j$ términos. Ningún nombre de función tiene paréntesis, así que $f$ y $g$ son, los dos, el tramo de $t$ anterior al primer «(»: $f=g$, y entonces $n=m=a(f)$. Sacando «$f($» de las dos escrituras queda

$$t_1,t_2,\dots ,t_n)=s_1,s_2,\dots ,s_n)$$

así que $t_1$ y $s_1$ son tramos iniciales de una misma palabra, uno es tramo inicial del otro, y por el Lema 2 $t_1=s_1$. Se cancela $t_1$ con la coma que lo sigue, queda $t_2,\dots ,t_n)=s_2,\dots ,s_n)$, y el mismo razonamiento da $t_2=s_2$, y así hasta $t_n=s_n$.

Más aún. Sea $t\in T_{k+1}^{\tau }$ y supongamos que se da (2). El Menú dice que $t$ está en $\mathrm{Var}\cup 𝒞$, cosa que (2) excluye, o que $t=g(s_1,\dots ,s_m)$ con $s_1,\dots ,s_m\in T_k^{\tau }$. Por la unicidad, $n=m$, $f=g$ y $t_j=s_j$, así que $t_1,\dots ,t_n\in T_k^{\tau }$. ∎

La prueba también dice cómo leer un término de afuera hacia adentro: el nombre de función es lo que está antes del primer «(», su aridad dice cuántas piezas buscar, y cada pieza es el único tramo inicial de lo que queda que es un término. Quien lee de esta forma no elige nada, y por eso decidir si una palabra es término es un procedimiento.

06 · Las piezas tienen que ser términos

La unicidad del Teorema 3 es entre descomposiciones cuyas piezas son términos. Sin eso, falla. Es el Ejercicio 2(h):

Ejercicio 2(h). Sea τ un tipo. Si $f\in {ℱ}_2$ y $\alpha ,\beta$ son palabras tales que $f(\alpha ,\beta )\in T^{\tau }$, entonces $\alpha ,\beta \in T^{\tau }$.

Es falso. En el tipo de los reticulados terna, con $f=\mathrm{s}$, tomá $\alpha =\mathrm{s}(\mathrm{X}1$ y $\beta =\mathrm{X}2),\mathrm{X}3$. Entonces $f(\alpha ,\beta )$ es la concatenación de $\mathrm{s}$, «(», $\mathrm{s}(\mathrm{X}1$, «,», $\mathrm{X}2),\mathrm{X}3$ y «)», o sea $\mathrm{s}(\mathrm{s}(\mathrm{X}1,\mathrm{X}2),\mathrm{X}3)$, que es un término de $T_2^{\tau }$. Pero $\alpha$ tiene un «(» y ningún «)», y $\beta$ empieza con $\mathrm{X}$ sin ser una variable: ninguna de las dos piezas es término. La coma que separa a $\alpha$ de $\beta$ no es la que separa los argumentos. La prueba del Teorema 3 no se aplica porque compara $t_1$ con $s_1$ usando el mordisqueo, y el mordisqueo sólo habla de términos.

Lo que sí vale es saber que una de las piezas es término. Es el Ejercicio 11:

Ejercicio 11. Sea τ un tipo. Si $f\in {ℱ}_2$ y $f(\alpha ,t),t\in T^{\tau }$, entonces $\alpha \in T^{\tau }$.

Prueba. Sea $u=f(\alpha ,t)$. Tiene paréntesis, así que no está en $\mathrm{Var}\cup 𝒞$, y por el Teorema 3 hay $g\in {ℱ}_m$ y $s_1,\dots ,s_m\in T^{\tau }$ con $u=g(s_1,\dots ,s_m)$. Como en la prueba del teorema, $f$ y $g$ son el tramo de $u$ anterior al primer «(», así que $g=f$ y $m=2$. Sacando «$f($» queda $\alpha ,t)=s_1,s_2)$. Lo que se sabe que es término es $t$, así que se compara por atrás: sacando el «)» final, $t$ y $s_2$ son tramos finales de una misma palabra, uno es tramo final del otro, y por el Lema 2 $t=s_2$. Cancelando $t$ y la coma que lo precede, $\alpha =s_1\in T^{\tau }$. ∎

Por adelante no se podía: comparar $\alpha$ con $s_1$ pide que $\alpha$ sea término, que es justo lo que había que probar. Los Ejercicios 10 y 11, con el 12, están resueltos en Se compara por el lado de lo que ya se sabe, y qué pasa con cada coma que uno prueba como separadora está en Un corte equivocado rompe las dos piezas.

07 · Definir funciones por recursión

La guía remarca por qué el Teorema 3 importa: permite definir recursivamente funciones con dominio contenido en $T^{\tau }$. Su ejemplo es una función $F:T^{\tau }\to T^{\tau }$ dada por

• $F(c)=c$, para cada $c\in 𝒞$;
• $F(v)=v$, para cada $v\in \mathrm{Var}$;
• $F(f(t_1,\dots ,t_n))=f(F(t_1),\dots ,F(t_n))$, si $f\in {ℱ}_n$, con $n\ne 2$;
• $F(f(t_1,t_2))=f(t_2,t_1)$, si $f\in {ℱ}_2$.

Las cuatro ecuaciones definen una función porque cada término cae en exactamente una de ellas, con ingredientes únicos. Eso es el Teorema 3: un término es una variable, o un nombre de constante, o un $f(t_1,\dots ,t_n)$ con $f$, $n$ y los $t_j$ determinados. Y el «más aún» asegura que la recursión termina: si $t\in T_{k+1}^{\tau }$, las llamadas a $F$ del lado derecho son sobre términos de $T_k^{\tau }$, así que $F$ queda definida primero en $T_0^{\tau }$, después en $T_1^{\tau }$, y así. La guía lo dice al revés: si la unicidad de la lectura no fuera cierta, las ecuaciones no estarían definiendo una función, porque el valor de $F$ en un término dependería de cuál descomposición se tome.

Calculada, en el tipo $\tau =(\{0,1\},\{+,\times ,\uparrow \},\varnothing ,a)$ de la guía, con $a(+)=2$, $a(\times )=3$ y $a(\uparrow )=1$, sobre el término $t=\times (+(\mathrm{X}1,\mathrm{X}2),\uparrow (+(0,\mathrm{X}3)),1)$, de $T_3^{\tau }$. Cada línea lee de afuera el primer $F(\dots )$ que queda y aplica la única ecuación que le corresponde:

1. $F(t)=\times (F(+(\mathrm{X}1,\mathrm{X}2)),F(\uparrow (+(0,\mathrm{X}3))),F(1))$$\times \in {ℱ}_3$
2. $=\times (+(\mathrm{X}2,\mathrm{X}1),F(\uparrow (+(0,\mathrm{X}3))),F(1))$$+\in {ℱ}_2$
3. $=\times (+(\mathrm{X}2,\mathrm{X}1),\uparrow (F(+(0,\mathrm{X}3))),F(1))$$\uparrow \in {ℱ}_1$
4. $=\times (+(\mathrm{X}2,\mathrm{X}1),\uparrow (+(\mathrm{X}3,0)),F(1))$$+\in {ℱ}_2$
5. $=\times (+(\mathrm{X}2,\mathrm{X}1),\uparrow (+(\mathrm{X}3,0)),1)$$1\in 𝒞$

Cinco llamadas a $F$, una por cada término que la recursión visita. Ojo con la cuarta ecuación: del lado derecho no aparece $F$. Da vuelta los dos argumentos y los deja como están, así que una binaria adentro de otra binaria no se toca: $F(+(+(\mathrm{X}1,\mathrm{X}2),\mathrm{X}3))=+(\mathrm{X}3,+(\mathrm{X}1,\mathrm{X}2))$. Con el término abierto de la guía es un solo paso:

$$F(+(+(\uparrow (\mathrm{X}4),\times (\mathrm{X}2,1,0)),\times (1,\mathrm{X}2,\mathrm{X}3)))$$ $$=+(\times (1,\mathrm{X}2,\mathrm{X}3),+(\uparrow (\mathrm{X}4),\times (\mathrm{X}2,1,0)))$$

$F$ da vuelta las binarias a las que se llega sin atravesar otra binaria.

Y sin lectura única, ¿qué se rompería? Si $+(+(\mathrm{X}1,\mathrm{X}2),\mathrm{X}3)$ se pudiera leer como $+(\alpha ,\beta )$ con $\alpha =+(\mathrm{X}1$ y $\beta =\mathrm{X}2),\mathrm{X}3$, la cuarta ecuación daría $+(\beta ,\alpha )=+(\mathrm{X}2),\mathrm{X}3,+(\mathrm{X}1)$, que no es $+(\mathrm{X}3,+(\mathrm{X}1,\mathrm{X}2))$ y ni siquiera es un término. $F$ tendría dos valores en el mismo término. El Teorema 3 es lo que descarta esa segunda lectura: $\alpha$ y $\beta$ no son términos.

Para tener a mano

1. $\beta$ es tramo inicial de $\alpha$ si $\alpha =\beta \gamma$; tramo final si $\alpha =\gamma \beta$; propio si $\beta \notin \{\epsilon ,\alpha \}$. Dos tramos iniciales de una misma palabra están uno adentro del otro, y lo mismo dos finales.
2. Dos nombres de constante pueden mordisquearse —$\mathrm{uno}$ y $\mathrm{noli}$—, pero ninguno es tramo propio del otro: lo prohíbe la definición de tipo.
3. Lema 2: si $s=xy$, $t=yz$, $y\ne \epsilon$, con $s,t$ términos, entonces $x=z=\epsilon$ o $s,t\in 𝒞$. La guía lo acepta sin prueba (Ejercicio 9). Se usa por su «en particular»: un término que es tramo inicial o final de otro es igual a él.
4. Cancelación (Ejercicio 10): $t_1{t}_2=s_1{s}_2$ con los cuatro términos da $t_1=s_1$ y $t_2=s_2$.
5. Teorema 3: todo término es de $\mathrm{Var}\cup 𝒞$ o un único $f(t_1,\dots ,t_n)$, y si $t\in T_{k+1}^{\tau }$ las piezas están en $T_k^{\tau }$. La prueba: $f$ es lo anterior al primer «(», y las piezas se igualan una por una con el Lema 2.
6. Las piezas tienen que ser términos: $f(\alpha ,\beta )\in T^{\tau }$ no da $\alpha ,\beta \in T^{\tau }$ (2(h)), pero si $t$ es término, $f(\alpha ,t)\in T^{\tau }$ da $\alpha \in T^{\tau }$ (11). Se compara por el lado de la pieza que se sabe término.
7. Por la lectura única se definen funciones sobre $T^{\tau }$ por recursión: una ecuación por forma, y la recursión baja de nivel. La $F$ de la guía da vuelta los argumentos de una binaria sin entrar en ellos.