Una fórmula puede ser el final de otra, nunca el principio

Las consignas, textuales:

• Ejercicio 16. «Pruebe que si $\phi ,\psi \in F^{\tau }$, entonces $\phi$ no puede ser tramo inicial propio de $\psi$ (Hint: elija bien $x,y$ y $z$ y aplique la proposición anterior).»
• Ejercicio 17. «Complete las partes no hechas en la prueba anterior.» La prueba anterior es la del Teorema 7, la lectura única de fórmulas.
• Ejercicio 18. «Si ${\psi }_1,{\psi }_2,{\phi }_1,{\phi }_2\in F^{\tau }$ y ${\psi }_1{\psi }_2={\phi }_1{\phi }_2$, entonces ${\psi }_1={\phi }_1$ y ${\psi }_2={\phi }_2$.»
• Ejercicio 19. «Si $(\alpha \wedge \beta ),\beta \in F^{\tau }$, entonces $\alpha \in F^{\tau }$.»
• Ejercicio 20. «Si $\psi ,\phi ,\alpha \in F^{\tau }$ son tales que $\psi$ ocurre en $\alpha$ a partir de $i$ y $\phi$ ocurre en $\alpha$ a partir de $i+1$, entonces $|\phi |<|\psi |$.»

Los cuatro primeros tratan de lo mismo: dos fórmulas pegadas en una palabra, y de qué manera puede leerse esa palabra. Y se apoyan en el mismo resultado, la Proposición 6 de la guía. Lo que los separa es el lado desde el que se compara. Por adelante, una fórmula nunca es el principio de otra, y el 16 y el 18 salen en un par de renglones. Por atrás, una fórmula sí puede ser el final de otra, y el 19 necesita saber con exactitud qué puede sobrar adelante. El 20 es de otra familia: sale del Lema 8.

01 · Antes de probar: el principio y el final no son simétricos

Con términos daba igual el lado. Por el Lema 2 de la guía, un término no es tramo inicial propio de otro término, ni tramo final propio: está en Mordisqueo y lectura única de términos. Con fórmulas vale sólo la primera mitad. La fórmula $(\mathrm{X}1\equiv \mathrm{X}1)$ es tramo final propio de $\neg (\mathrm{X}1\equiv \mathrm{X}1)$: la primera tiene 7 símbolos, la segunda 8, y lo que sobra adelante es el $\neg$. Lo mismo pasa con cualquier fórmula y cualquier cadena de negaciones y cuantificadores con su variable puesta delante: $\forall \mathrm{X}1\neg (\mathrm{X}1\equiv \mathrm{X}1)$ también termina en $(\mathrm{X}1\equiv \mathrm{X}1)$.

Lo otro no pasa nunca. Tomemos el tipo $\tau =(\{0\},\{f\},\{r\},a)$ con $a(f)=a(r)=1$, seis fórmulas atómicas —$(\mathrm{X}1\equiv \mathrm{X}2)$, $(\mathrm{X}1\equiv 0)$, $(0\equiv 0)$, $r(\mathrm{X}1)$, $r(f(0))$ y $(f(\mathrm{X}2)\equiv \mathrm{X}1)$— y cerremos dos veces bajo $\neg$, $\forall \mathrm{X}1$, $\exists \mathrm{X}2$, $\wedge$ y $\to$, quedándonos con las de hasta 26 símbolos. Salen 3370 fórmulas distintas, y 11 356 900 pares ordenados $(\phi ,\psi )$. Buscando en cada par todas las maneras en que un final de $\phi$ coincide con un principio de $\psi$, aparecen 3712 coincidencias: 3370 son las de $\phi$ consigo misma, y las otras 342 son casos en que $\psi$ es tramo final propio de $\phi$. Ni una vez $\psi$ es tramo inicial propio de $\phi$, y ni una vez se superponen a medias. En esos 342 casos, lo que sobra adelante termina en $\neg$ 114 veces y en el numeral negrita de una variable 228: nunca en un nexo, nunca en un paréntesis.

Esa asimetría ordena el bloque. El 16 prueba la mitad que vale, y sale de elegir bien qué se mordisquea. El 18 es la cancelación: compara por adelante, así que le alcanza el 16, igual que al Ejercicio 10 le alcanzaba el Lema 2. El 19 tiene que comparar por atrás, porque la fórmula que se conoce es $\beta$, la de la derecha, y ahí el 16 no dice nada. El 17 completa la lectura única con el 16 en la mano, y el 20 sale de que las ocurrencias de subfórmulas no se cruzan.

02 · Las herramientas

Tramo inicial y tramo final, como los define la guía: $\beta$ es tramo inicial de $\alpha$ si hay una palabra $\gamma$ tal que $\alpha =\beta \gamma$, y es propio si además $\beta \notin \{\epsilon ,\alpha \}$. Tramo final, igual, con $\alpha =\gamma \beta$. Si dos palabras son tramos iniciales de una misma palabra, la más corta es tramo inicial de la otra; con los finales, lo mismo.

Proposición 6 (Mordisqueo de fórmulas). Si $\phi ,\psi \in F^{\tau }$ y $x,y,z$ son tales que $\phi =xy$, $\psi =yz$ y $y\ne \epsilon$, entonces $z=\epsilon$ y

$$x\in (\{\neg \}\cup \{Qv:Q\in \{\forall ,\exists \},v\in \mathrm{Var}\}{)}^{*}$$

En particular, ningún tramo inicial propio de una fórmula es una fórmula, y ningún tramo final propio de una fórmula atómica es una fórmula.

Dice dos cosas. La primera, $z=\epsilon$: si un final de $\phi$ coincide con un principio de $\psi$, entonces $\psi$ se termina adentro de $\phi$, o sea, es entera un tramo final de $\phi$. La segunda: lo que sobra de $\phi$ adelante, $x$, es una seguidilla de negaciones y de cuantificadores con su variable —$\neg$, $\forall \mathrm{X}1$, $\neg \exists \mathrm{X}2\neg$— o nada. Esa forma de $x$ es lo que va a decidir el 19: una palabra así, si no es vacía, termina en $\neg$ o en un numeral negrita. La guía acepta la proposición sin prueba.

Teorema 7 (Lectura única de fórmulas). Dada $\phi \in F^{\tau }$ se da una y sólo una de las siguientes:

1. $\phi =(t\equiv s)$, con $t,s\in T^{\tau }$, únicos;
2. $\phi =r(t_1,\dots ,t_n)$, con $r\in {ℛ}_n$, $t_1,\dots ,t_n\in T^{\tau }$, únicos;
3. $\phi =({\phi }_1\eta {\phi }_2)$, con $\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}$, ${\phi }_1,{\phi }_2\in F^{\tau }$, únicos;
4. $\phi =\neg {\phi }_1$, con ${\phi }_1\in F^{\tau }$, única;
5. $\phi =Qv{\phi }_1$, con $Q\in \{\forall ,\exists \}$, ${\phi }_1\in F^{\tau }$ y $v\in \mathrm{Var}$, únicos.

Más aún, si $\phi \in F_{k+1}^{\tau }$, entonces cuando se da (3) las fórmulas ${\phi }_1$ y ${\phi }_2$ están en $F_k^{\tau }$, y cuando se da (4) o (5) la fórmula ${\phi }_1$ está en $F_k^{\tau }$.

Lema 8 (Ocurrencias de fórmulas en fórmulas), la parte que se usa. Sea $\tau$ un tipo y $\phi ,{\phi }_1,{\phi }_2$ fórmulas de tipo $\tau$. (e) Si ${\phi }_1,{\phi }_2$ ocurren en $\phi$, entonces dichas ocurrencias son disjuntas o una contiene a la otra. Las partes (a) a (d) dicen dónde cae una ocurrencia según la forma de la fórmula —una atómica no tiene subfórmulas propias, y en $(\psi \eta \varphi )$, $\neg \psi$ o $Qv\psi$ una subfórmula propia cae adentro de $\psi$ o de $\varphi$—, y (f) y (g) tratan de las ocurrencias repetidas y de los reemplazos.

«Ocurre a partir de $i$» es lo de la guía: $\alpha$ ocurre a partir de $i$ en $\beta$ si $\beta =\delta \alpha \gamma$ con $|\delta |=i-1$. Una ocurrencia así ocupa las posiciones $i$ a $i+|\alpha |-1$ de $\beta$.

03 · Ejercicio 16: elegir qué se mordisquea

La mariposa. La Proposición 6 habla de un final de $\phi$ que es principio de $\psi$, y deja que sobre algo de $\phi$ adelante, $x$. El 16 quiere hablar de $\phi$ entera como principio de $\psi$. Entonces el pedazo en común, $y$, tiene que ser $\phi$ entera, y lo que sobra de $\phi$ adelante, nada. Si $\psi =\phi w$, la elección es

$$x=\epsilon ,y=\phi ,z=w.$$

Con eso $\phi =xy$ y $\psi =yz$, y la proposición devuelve $z=\epsilon$, que es exactamente $w=\epsilon$: el tramo no era propio. La única hipótesis que hay que mirar es $y\ne \epsilon$, y ninguna fórmula es la palabra vacía. Lo que la proposición dice de $x$ no hace falta: $x$ es vacía por elección.

El enunciado coincide con la primera mitad del «en particular» de la proposición. Lo que pide el ejercicio es sacarlo de ella, y esa es toda la prueba.

El escarabajo. Sean $\phi ,\psi \in F^{\tau }$ y supongamos que $\phi$ es tramo inicial propio de $\psi$: hay una palabra $w$ con $\psi =\phi w$ y $w\ne \epsilon$. Tomemos $x=\epsilon$, $y=\phi$ y $z=w$. Entonces $\phi =xy$, $\psi =yz$, e $y=\phi \ne \epsilon$ porque ninguna fórmula es vacía. Por la Proposición 6, $z=\epsilon$, o sea $w=\epsilon$, que contradice $w\ne \epsilon$. Luego $\phi$ no es tramo inicial propio de $\psi$. ∎

04 · Ejercicio 17: lo que la guía dejó sin hacer

La mariposa. Que toda fórmula tiene alguna de las cinco formas ya está: es el Lema 5, el menú para fórmulas, más la definición de $F_0^{\tau }$. La guía esboza el resto y deja tres cosas: que las formas son excluyentes, que en cada forma las piezas son únicas, y la observación sobre los niveles. Las tres salen de mirar el primer símbolo y de comparar por adelante.

El primer símbolo de cada forma:

Los nombres del tipo no pueden usar $($, $\neg$, $\forall$ ni $\exists$, así que (2), (4) y (5) quedan separadas entre sí y de las otras dos. Sólo el $($ deja dos formas abiertas, (1) y (3), y las separa el contenido: un término no tiene nexos, así que en $(t\equiv s)$ no hay ninguno, y en $({\phi }_1\eta {\phi }_2)$ está $\eta$.

Las unicidades son cinco comparaciones por adelante. En (1) hay un solo $\equiv$, porque los términos no lo contienen. En (2) el nombre es lo que está antes del primer $($, y los argumentos se cancelan de a uno como en la lectura única de términos, con el Lema 2: si un término es tramo inicial de otro, son iguales. En (3) se usa el 16, y es el único lugar donde hace falta. En (4) se cancela el $\neg$. En (5), la variable termina en su único numeral negrita.

Para los niveles hace falta el menú. Lema 5 (Menú para fórmulas): si $\phi \in F_{k+1}^{\tau }$, entonces $\phi$ es de la forma (a) $(t\equiv s)$, (b) $r(t_1,\dots ,t_n)$, (c) $({\phi }_1\eta {\phi }_2)$ con ${\phi }_1,{\phi }_2\in F_k^{\tau }$, (d) $\neg {\phi }_1$ con ${\phi }_1\in F_k^{\tau }$, o (e) $Qv{\phi }_1$ con ${\phi }_1\in F_k^{\tau }$. El menú da una descomposición con piezas de nivel $k$; la unicidad dice que es la única que hay, así que las piezas de cualquier descomposición son ésas.

El escarabajo. Sea $\phi \in F^{\tau }$. Por la definición de $F_0^{\tau }$ y el Lema 5, $\phi$ es de alguna de las formas (1) a (5).

Las formas son excluyentes. En (2) el primer símbolo de $\phi$ es el primer símbolo de un nombre de relación; en (4), $\neg$; en (5), $\forall$ o $\exists$; en (1) y (3), $($. Como ningún nombre del tipo contiene $($, $\neg$, $\forall$ ni $\exists$, estos cuatro casos de primer símbolo son disjuntos, y (2), (4) y (5) no pueden darse junto con ninguna otra forma. Si se dieran (1) y (3) a la vez, $\phi =(t\equiv s)=({\phi }_1\eta {\phi }_2)$, el símbolo $\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}$ ocurriría en $(t\equiv s)$, que no contiene nexos porque $t$ y $s$ son términos. Absurdo.

Unicidad en (1). Si $(t\equiv s)=(t^{\prime }\equiv s^{\prime })$, entonces $t\equiv s=t^{\prime }\equiv s^{\prime }$. Los términos no contienen $\equiv$, así que esa palabra tiene un solo $\equiv$; lo que está antes es $t=t^{\prime }$ y lo que está después es $s=s^{\prime }$.

Unicidad en (2). Si $r(t_1,\dots ,t_n)=r^{\prime }(s_1,\dots ,s_m)$, como los nombres de relación no tienen paréntesis, $r$ y $r^{\prime }$ son los dos el tramo anterior al primer $($: $r=r^{\prime }$ y $n=m=a(r)$. Queda $t_1,\dots ,t_n)=s_1,\dots ,s_n)$. Ahí $t_1$ y $s_1$ son tramos iniciales de la misma palabra, así que uno es tramo inicial del otro, y por el Lema 2, $t_1=s_1$. Cancelando $t_1$ y la coma que lo sigue, se repite el argumento con $t_2$ y $s_2$, y así hasta $t_n=s_n$.

Unicidad en (3). Si $({\phi }_1\eta {\phi }_2)=({\psi }_1{\eta }^{\prime }{\psi }_2)$, entonces ${\phi }_1\eta {\phi }_2={\psi }_1{\eta }^{\prime }{\psi }_2$, y ${\phi }_1$ y ${\psi }_1$ son tramos iniciales de la misma palabra: uno es tramo inicial del otro. Por el Ejercicio 16 ninguno es tramo inicial propio del otro, así que ${\phi }_1={\psi }_1$. Cancelando, $\eta {\phi }_2={\eta }^{\prime }{\psi }_2$, de donde $\eta ={\eta }^{\prime }$ y ${\phi }_2={\psi }_2$.

Unicidad en (4). Si $\neg {\phi }_1=\neg {\psi }_1$, cancelando el $\neg$, ${\phi }_1={\psi }_1$.

Unicidad en (5). Si $Qv{\phi }_1=Q^{\prime }w{\psi }_1$, el primer símbolo da $Q=Q^{\prime }$. Las variables $v$ y $w$ empiezan las dos en la posición 2, y cada una termina en su único numeral negrita, que es entonces el primer negrita a partir de la posición 2. Luego $v$ y $w$ terminan en la misma posición, $v=w$, y cancelando, ${\phi }_1={\psi }_1$.

Los niveles. Sea $\phi \in F_{k+1}^{\tau }$ con $\phi =({\phi }_1\eta {\phi }_2)$. Por el Lema 5, $\phi$ es de alguna de las formas (a) a (e) del menú; como las formas son excluyentes, es la (c): $\phi =({\psi }_1{\eta }^{\prime }{\psi }_2)$ con ${\psi }_1,{\psi }_2\in F_k^{\tau }$. Por la unicidad en (3), ${\phi }_1={\psi }_1$ y ${\phi }_2={\psi }_2$, que están en $F_k^{\tau }$. Si $\phi =\neg {\phi }_1$ o $\phi =Qv{\phi }_1$, igual, con las formas (d) y (e) del menú y la unicidad en (4) y en (5). ∎

05 · Ejercicio 18: la cancelación

La mariposa. Es el Ejercicio 10 con fórmulas en lugar de términos, y se hace igual: por adelante. ${\psi }_1$ y ${\phi }_1$ son tramos iniciales de la misma palabra, así que una es tramo inicial de la otra, y el 16 dice que no puede serlo de manera propia. Son iguales, y el resto se cancela.

Por atrás no habría salido tan barato. ${\psi }_2$ y ${\phi }_2$ son tramos finales de la misma palabra, y una fórmula sí puede ser tramo final propio de otra: con ${\psi }_2=\neg {\phi }_2$ nada en el 16 lo impide. Habría que agregar un argumento —la Proposición 6 diría que lo que sobra termina en $\neg$ o en un negrita, y ${\phi }_1$, que es fórmula, termina en $)$—, que es justo el trabajo que el 19 no se puede ahorrar.

El escarabajo. Sean ${\psi }_1,{\psi }_2,{\phi }_1,{\phi }_2\in F^{\tau }$ con ${\psi }_1{\psi }_2={\phi }_1{\phi }_2$. ${\psi }_1$ y ${\phi }_1$ son tramos iniciales de la misma palabra, así que uno de los dos es tramo inicial del otro. Por el Ejercicio 16, ninguno es tramo inicial propio del otro; luego ${\psi }_1={\phi }_1$. Las dos palabras ${\psi }_1{\psi }_2$ y ${\phi }_1{\phi }_2$ son iguales símbolo a símbolo, así que lo que sigue a los primeros $|{\psi }_1|$ símbolos coincide: ${\psi }_2={\phi }_2$. ∎

06 · Ejercicio 19: el lado que se conoce es el de atrás

La mariposa. Sin la hipótesis sobre $\beta$ el enunciado es falso: el $\wedge$ que separa $\alpha$ de $\beta$ puede no ser el principal, y es el Ejercicio 13(a). Con ella es verdadero, y la prueba empieza leyendo de afuera. $(\alpha \wedge \beta )$ es fórmula y empieza con $($, así que por el Teorema 7 es de la forma (1) o (3); contiene un $\wedge$, así que no es (1). Es $({\phi }_1\eta {\phi }_2)$ con ${\phi }_1,{\phi }_2\in F^{\tau }$, y sacando los paréntesis de afuera,

$$\alpha \wedge \beta ={\phi }_1\eta {\phi }_2.$$

Ahora hay que elegir el lado. De $\alpha$ no se sabe nada —que sea fórmula es lo que se quiere probar—, y de $\beta$ se sabe que es fórmula. Se compara por el lado de $\beta$, por atrás, como en el Ejercicio 11 con los términos. $\beta$ y ${\phi }_2$ son tramos finales de la misma palabra, así que una es tramo final de la otra. Y acá el 16 no sirve, porque una fórmula sí puede ser tramo final propio de otra. Hay dos casos, según cuál sea la más larga: ${\phi }_2=u\beta$ o $\beta =u{\phi }_2$, con $u$ lo que sobra adelante.

En los dos, la Proposición 6 dice que $u\in (\{\neg \}\cup \{Qv\}{)}^{*}$. Si $u$ no es vacía, su último símbolo es $\neg$ o el numeral negrita de una variable. Pero ese último símbolo de $u$ es, en la palabra $\alpha \wedge \beta ={\phi }_1\eta {\phi }_2$, el que está justo antes de la más corta de las dos. En el primer caso es el símbolo justo antes de $\beta$, y eso es el $\wedge$ que separa $\alpha$ de $\beta$. En el segundo, es el símbolo justo antes de ${\phi }_2$, y eso es el nexo $\eta$. Un nexo no es ni $\neg$ ni un negrita: $u=\epsilon$.

Abajo, la fórmula $(\alpha \wedge \beta )$ está dada y lo que se mueve es dónde empieza $\beta$. Cada vez se compara $\beta$ con ${\phi }_2$ por atrás y se ve qué sobra.

Las dos primeras fórmulas tienen finales que también son fórmulas: en la primera, $\forall \mathrm{X}1(\mathrm{X}1\equiv 0)$ y $(\mathrm{X}1\equiv 0)$, con $\neg$ y $\neg \forall \mathrm{X}1$ sobrando adelante. Elegido así, $\beta$ cumple la hipótesis «$\beta \in F^{\tau }$», y la Proposición 6 no protesta: $u$ es una cadena de negaciones y cuantificadores, como debe. Lo que falla es la otra hipótesis. El símbolo que precede a $\beta$ es el último de $u$, un $\neg$ o un negrita, y no un $\wedge$: con esa $\beta$, la palabra no se escribe como $(\alpha \wedge \beta )$. Con los otros $\wedge$ pasa al revés: la palabra sí se escribe como $(\alpha \wedge \beta )$, pero $u$ termina en un nexo, y por eso $\beta$ no es fórmula.

Ninguna de las dos hipótesis alcanza sola para ubicar $\beta$. Entre las 3370 fórmulas de antes, las de la forma $({\phi }_1\wedge {\phi }_2)$ son 1538. En 726 de ellas hay más de un lugar donde $\beta$ puede empezar y ser fórmula, y en 539 hay más de un $\wedge$. En las 1538 hay exactamente un comienzo que cumple las dos cosas a la vez, y es el de ${\phi }_2$.

El escarabajo. Sea $\phi =(\alpha \wedge \beta )$ y supongamos $\phi ,\beta \in F^{\tau }$. Como $\phi$ empieza con $($, por el Teorema 7 es de la forma (1) o (3). No es de la forma (1): $\wedge$ ocurre en $\phi$, y en $(t\equiv s)$ no ocurre ningún nexo. Luego hay ${\phi }_1,{\phi }_2\in F^{\tau }$ y $\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}$ con $\phi =({\phi }_1\eta {\phi }_2)$, y sacando el primer y el último símbolo, $\alpha \wedge \beta ={\phi }_1\eta {\phi }_2$.

$\beta$ y ${\phi }_2$ son tramos finales de esa palabra, así que hay una palabra $u$ con ${\phi }_2=u\beta$ o con $\beta =u{\phi }_2$.

Caso ${\phi }_2=u\beta$. Aplicamos la Proposición 6 a las fórmulas ${\phi }_2$ y $\beta$, con $x=u$, $y=\beta$, $z=\epsilon$: ${\phi }_2=u\beta$, $\beta =\beta \epsilon$ y $\beta \ne \epsilon$. Entonces $u\in (\{\neg \}\cup \{Qv:Q\in \{\forall ,\exists \},v\in \mathrm{Var}\}{)}^{*}$. Supongamos $u\ne \epsilon$. Su último símbolo es $\neg$ o el último símbolo de una variable, que es un numeral negrita. Pero de $\alpha \wedge \beta ={\phi }_1\eta u\beta$, cancelando $\beta$ al final, $\alpha \wedge ={\phi }_1\eta u$, y el último símbolo de la izquierda es $\wedge$. Absurdo. Luego $u=\epsilon$ y $\beta ={\phi }_2$.

Caso $\beta =u{\phi }_2$. Aplicamos la Proposición 6 a $\beta$ y ${\phi }_2$, con $x=u$, $y={\phi }_2$, $z=\epsilon$: $u\in (\{\neg \}\cup \{Qv:Q\in \{\forall ,\exists \},v\in \mathrm{Var}\}{)}^{*}$. Supongamos $u\ne \epsilon$. De $\alpha \wedge u{\phi }_2={\phi }_1\eta {\phi }_2$, cancelando ${\phi }_2$ al final, $\alpha \wedge u={\phi }_1\eta$. El último símbolo de la izquierda es el de $u$, $\neg$ o un numeral negrita, y el de la derecha es $\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}$. Absurdo. Luego $u=\epsilon$ y $\beta ={\phi }_2$.

En los dos casos $\beta ={\phi }_2$. Cancelando $\beta$ al final de $\alpha \wedge \beta ={\phi }_1\eta \beta$, $\alpha \wedge ={\phi }_1\eta$; comparando el último símbolo, $\eta =\wedge$, y cancelándolo, $\alpha ={\phi }_1\in F^{\tau }$. ∎

07 · Ejercicio 20: dos ocurrencias que empiezan pegadas

La mariposa. Primero, que la situación existe. En $\alpha =((\mathrm{X}1\equiv \mathrm{X}2)\wedge \neg (\mathrm{X}1\equiv 0))$, de 17 símbolos, la propia $\alpha$ ocurre a partir de 1 y $(\mathrm{X}1\equiv \mathrm{X}2)$, de 7 símbolos, a partir de 2. Más adentro, $\neg (\mathrm{X}1\equiv 0)$ ocurre a partir de 10 y $(\mathrm{X}1\equiv 0)$ a partir de 11, con 7 y 6 símbolos. En los dos pares la segunda queda adentro de la primera.

Eso es lo que hay que probar, y el Lema 8(e) lo da casi entero: dos ocurrencias de fórmulas en una fórmula son disjuntas o una contiene a la otra. Que no son disjuntas se ve en las posiciones: la de $\psi$ va de $i$ a $i+|\psi |-1$, la de $\phi$ empieza en $i+1$, y alcanza con que $\psi$ tenga al menos dos símbolos para que $i+1$ esté en las dos. La de $\phi$ no puede contener a la de $\psi$, porque empieza después. Queda que la de $\psi$ contiene a la de $\phi$, y la desigualdad sale de comparar dónde terminan.

Para «al menos dos símbolos» alcanza el Ejercicio 14: una fórmula termina en $)$ y empieza con $($, $\neg$, $\forall$, $\exists$ o el primer símbolo de un nombre de relación, que nunca es $)$. El primer y el último símbolo son distintos, así que son por lo menos dos.

El escarabajo. Sean $\psi ,\phi ,\alpha \in F^{\tau }$ con $\psi$ ocurriendo en $\alpha$ a partir de $i$ y $\phi$ a partir de $i+1$. La ocurrencia de $\psi$ ocupa las posiciones $i,\dots ,i+|\psi |-1$ de $\alpha$, y la de $\phi$ las posiciones $i+1,\dots ,i+|\phi |$.

Por el Ejercicio 14, el último símbolo de $\psi$ es $)$ y el primero no lo es, así que $|\psi |\ge 2$ y $i+1\le i+|\psi |-1$. La posición $i+1$ está en las dos ocurrencias: no son disjuntas. Por el Lema 8(e), una contiene a la otra. La de $\phi$ no contiene a la de $\psi$, porque la posición $i$ está en la de $\psi$ y no en la de $\phi$. Luego la de $\psi$ contiene a la de $\phi$, y en particular la última posición de $\phi$ no pasa de la última de $\psi$:

$$i+|\phi |\le i+|\psi |-1,$$

o sea, $|\phi |\le |\psi |-1<|\psi |$. ∎

08 · Lo que se lleva a otros ejercicios

Se compara por el lado de lo que se sabe. En el 18 se sabe todo, y se elige el lado fácil, adelante. En el 19 sólo se sabe $\beta$, y eso obliga a ir por atrás. Es la misma decisión del Ejercicio 11 con términos, con una diferencia: para términos el Lema 2 cubre los dos lados, y para fórmulas por atrás hay que usar la Proposición 6 entera y mirar qué símbolo precede a la fórmula más corta.

Lo que sobra adelante nunca termina en un nexo ni en un paréntesis. Es la forma útil de la Proposición 6: si una fórmula es tramo final propio de otra, el símbolo justo antes es $\neg$ o un numeral negrita. Cualquier situación en la que delante de una fórmula hay un nexo, un $($ o una coma se resuelve con eso.

Lo que hace perder puntos. En el 19, usar el 16 para decir que $\beta ={\phi }_2$: el 16 habla de tramos iniciales, y que ninguna fórmula sea tramo final propio de otra es falso. Hacer sólo el caso ${\phi }_2=u\beta$ y olvidar $\beta =u{\phi }_2$. Aplicar la Proposición 6 sin decir quiénes son $x$, $y$ y $z$, ni chequear $y\ne \epsilon$. En el 17, dar la unicidad en (5) sin decir por qué las dos variables terminan en el mismo lugar: lo que la sostiene es su único negrita. En el 20, citar el Lema 8(e) sin mostrar que las ocurrencias se tocan. Y si una prueba usa el 16, la regla de la cátedra pide enunciarlo y probarlo: son tres renglones.

Para tener a mano

1. Proposición 6: si $\phi =xy$, $\psi =yz$ e $y\ne \epsilon$, entonces $z=\epsilon$ y $x\in (\{\neg \}\cup \{Qv\}{)}^{*}$. Una fórmula nunca es tramo inicial propio de otra; puede ser tramo final propio, con negaciones y cuantificadores sobrando adelante.
2. Ejercicio 16: $x=\epsilon$, $y=\phi$, $z=w$, y la proposición da $w=\epsilon$.
3. Ejercicio 17: las formas se separan por el primer símbolo, y (1) de (3) porque un término no tiene nexos. Unicidades: un solo $\equiv$; Lema 2 argumento por argumento; el 16; cancelar $\neg$; la variable termina en su único negrita. Niveles: menú más unicidad.
4. Ejercicio 18: por adelante, con el 16, como el 10 con el Lema 2.
5. Ejercicio 19: forma (3) por el $\wedge$; $\alpha \wedge \beta ={\phi }_1\eta {\phi }_2$; por atrás, ${\phi }_2=u\beta$ o $\beta =u{\phi }_2$; $u$ terminaría en $\neg$ o en un negrita y lo que hay es un nexo, así que $u=\epsilon$.
6. Ejercicio 20: las ocurrencias se tocan en $i+1$, el Lema 8(e) mete la de $\phi$ adentro de la de $\psi$, y $i+|\phi |\le i+|\psi |-1$.