Para probar que no es término, contá o leé de afuera

Los enunciados, textuales, de la página 3 de la Guía 9:

• Ejercicio 3. Si $t\in T^{\tau }$, entonces ${|t|}_{(}={|t|}_{)}$.
• Ejercicio 4. Probar que si $t\in T^{\tau }-(\mathrm{Var}\cup \mathrm{𝒞})$ entonces $|t|\ge 4$.
• Ejercicio 5. Si $t\in T^{\tau }$ es tal que en $t$ ocurre el símbolo $)$, entonces $t=f(t_1,\dots ,t_n)$ con $f\in {\mathrm{ℱ}}_n$, $n\ge 1$ y $t_1,\dots ,t_n\in T^{\tau }$.
• Ejercicio 6. Si $t\in T^{\tau }$ y $i\in \{1,\dots ,|t|-1\}$ es tal que ${[t]}_i=)$ entonces ${[t]}_{i+1}=,$ o ${[t]}_{i+1}=)$.
• Ejercicio 7. Probar que en un término nunca puede ocurrir la palabra $(,$

Y el de la página 4: «Ejercicio 8. Sea $\tau =(\{\mathrm{cero},1\},\{\mathrm{suma},\mathrm{glp}\},\mathrm{\varnothing },a)$, con $a(\mathrm{suma})=2$, $a(\mathrm{glp})=1$. Probar que las siguientes palabras no son términos de tipo $\tau$:

• (a) $\mathrm{glp}((\mathrm{X}133)$
• (b) $\mathrm{suma}(\mathrm{g},\mathrm{cero})$
• (c) $\mathrm{glp}(0)$
• (d) $\mathrm{suma}(\mathrm{X}1232,\mathrm{X}2,1)$
• (e) $\mathrm{suma}(\mathrm{suma}(\mathrm{suma}(\mathrm{suma}(\mathrm{suma}(\mathrm{X}1234,1),1),1),1),\mathrm{glp}(\mathrm{cero})))$»

Son dos trabajos distintos. Del 3 al 7 se prueba que todo término cumple algo; en el 8 se usa eso para probar que cinco palabras no son términos. Lo que los une es que un término de tipo $\tau$ es una palabra, armada por niveles, y que sólo hay dos maneras de decir algo de todas: inducción en el nivel, o mirar cómo es por afuera.

01 · Antes de probar: qué se sabe de un término

La definición, de la página 1 de la guía: $T_0^{\tau }=\mathrm{Var}\cup \mathrm{𝒞}$, y

$$T_{k+1}^{\tau }=T_k^{\tau }\cup \{f(t_1,\dots ,t_n):f\in {\mathrm{ℱ}}_n,n\ge 1\text{ y }{t}_1,\dots ,t_n\in T_k^{\tau }\}.$$

Un término es un elemento de $T^{\tau }={\bigcup }_{k\ge 0}{T}_k^{\tau }$, y cada uno está en algún $T_k^{\tau }$. La palabra $f(t_1,\dots ,t_n)$ es la concatenación de $f$, «$($», $t_1$, «$,$», …, «$,$», $t_n$ y «$)$», así que tiene longitud $|f|+|t_1|+\cdots +|t_n|+(n-1)+2$, con $n-1$ comas. Las variables son palabras concretas: $\mathrm{X}$ seguida de numerales itálicos, el último negrita.

Lo que dice el tipo. En $\tau =(\mathrm{𝒞},\mathrm{ℱ},\mathrm{ℛ},a)$ los nombres de constante son palabras de un alfabeto ${\mathrm{\Sigma }}_1$ y los de función de otro, ${\mathrm{\Sigma }}_2$, disjuntos, y ninguno de los dos tiene la $\mathrm{X}$, los numerales itálicos o negritas, los paréntesis ni la coma. Casi todo lo que sigue sale de esa frase: ni las variables ni los nombres tienen paréntesis ni comas. Los únicos paréntesis y las únicas comas de un término son los que pone $f(\dots )$.

La notación. ${|\alpha |}_{\sigma }$ es la cantidad de veces que aparece el símbolo $\sigma$ en la palabra $\alpha$, y ${[\alpha ]}_i$ es su $i$-ésimo símbolo, contando desde 1.

Qué es verdadero y qué no alcanza. Los enunciados del 3 al 7 son todos verdaderos. Lo que no vale es la vuelta, y eso decide cómo se hace el 8: los tres hechos que prueban el 3, el 6 y el 7 —tantos «$($» como «$)$»; después de un «$)$», una coma o un «$)$»; nunca «$(,$»— son cosas que todo término cumple, pero no alcanzan para ser término. Medido sobre las cinco palabras del 8: (b), (c) y (d) cumplen los tres, y no son términos. Sólo (a) y (e) caen por uno de ellos, el conteo: (a) tiene 2 paréntesis que abren y 1 que cierra; (e), 6 y 7. Para las otras tres hay que leer la palabra.

02 · Las herramientas: el menú y el molde

El Lema 1 (Menú para términos), como lo da la guía en la página 3: «Supongamos $t\in T_{k+1}^{\tau }$, con $k\ge 0$. Entonces se da alguna de las siguientes: (a) $t\in \mathrm{Var}\cup \mathrm{𝒞}$; (b) $t=f(t_1,\dots ,t_n)$, con $f\in {\mathrm{ℱ}}_n$, $n\ge 1$ y $t_1,\dots ,t_n\in T_k^{\tau }$.» Dice cómo es un término por afuera, y lo dice sin mirar adentro de los $t_j$.

La Regla de Inducción desde 0. Si para cada $k\in \mathrm{\omega }$ hay un enunciado ${\mathrm{Enu}}_k$, y se prueba ${\mathrm{Enu}}_0$ y que ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$, entonces vale ${\mathrm{Enu}}_k$ para todo $k$. Para probar que todo término cumple una propiedad $P$, el molde es siempre el mismo:

• ${\mathrm{Enu}}_k$: para todo $t\in T_k^{\tau }$, $P(t)$. Si $P$ tiene otros parámetros, van cuantificados adentro.
• ${\mathrm{Enu}}_0$: $t\in \mathrm{Var}\cup \mathrm{𝒞}$. Como ahí no hay paréntesis ni comas, casi siempre es inmediato o vacuo.
• ${\mathrm{Enu}}_k\Rightarrow {\mathrm{Enu}}_{k+1}$: si $t\in T_{k+1}^{\tau }$, o $t\in T_k^{\tau }$ y vale por hipótesis, o $t=f(t_1,\dots ,t_n)$ con los $t_j\in T_k^{\tau }$, y entonces se mira cada pieza —$f$, «$($», los $t_j$, las comas, «$)$»— y cada frontera entre dos piezas.
• Cierre: todo $t\in T^{\tau }$ está en algún $T_k^{\tau }$.

La pregunta antes de cada ejercicio es si hace falta. Una propiedad que habla sólo de la forma de afuera —qué símbolo va primero, si el término es compuesto, cuánto mide como mínimo— sale del menú sin inducción. Una que habla de lo que pasa en cualquier posición de la palabra tiene que bajar hasta los $t_j$, y para eso necesita la hipótesis inductiva.

03 · Ejercicio 3: tantos paréntesis que abren como que cierran

La mariposa. La propiedad habla de toda la palabra, así que va con el molde. En la base no hay nada que contar: cero y cero. En el paso, $f(t_1,\dots ,t_n)$ agrega exactamente un «$($» y un «$)$» por fuera de los $t_j$ —el nombre y las comas no aportan ninguno—, y adentro de cada $t_j$ la hipótesis dice que están parejos. Es una suma.

El escarabajo. Prueba. Por la Regla de Inducción desde 0. Para cada $k\in \mathrm{\omega }$ sea

$${\mathrm{Enu}}_k:\text{para todo }t\in T_k^{\tau },{|t|}_{(}={|t|}_{)}.$$

${\mathrm{Enu}}_0$. Si $t\in T_0^{\tau }=\mathrm{Var}\cup \mathrm{𝒞}$: una variable sólo tiene la $\mathrm{X}$ y numerales, y un nombre de constante sólo símbolos de ${\mathrm{\Sigma }}_1$, que no tiene paréntesis. En los dos casos ${|t|}_{(}=0={|t|}_{)}$.

${\mathrm{Enu}}_k\Rightarrow {\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, $t=f(t_1,\dots ,t_n)$ con $f\in {\mathrm{ℱ}}_n$, $n\ge 1$ y $t_1,\dots ,t_n\in T_k^{\tau }$. La palabra $t$ es la concatenación de $f$, «$($», $t_1$, «$,$», …, «$,$», $t_n$, «$)$». El nombre $f$ y las comas no tienen paréntesis, así que

$${|t|}_{(}=1+{\sum }_{j=1}^n{|t_j|}_{(}=1+{\sum }_{j=1}^n{|t_j|}_{)}={|t|}_{)},$$

donde la igualdad del medio es ${\mathrm{Enu}}_k$ aplicado a cada $t_j$. Luego vale ${\mathrm{Enu}}_k$ para todo $k$, y como todo $t\in T^{\tau }$ está en algún $T_k^{\tau }$, vale para todo término. ∎

04 · Ejercicio 4: un término compuesto mide al menos cuatro

La mariposa. Un término que no está en $\mathrm{Var}\cup \mathrm{𝒞}$ tiene que ser $f(t_1,\dots ,t_n)$: eso lo dice el menú, sin inducción. Y una palabra de esa forma tiene, como mínimo, un símbolo de nombre, los dos paréntesis y un argumento que no es vacío. Lo único que hay que asegurar aparte es eso último: que ningún término es la palabra vacía.

El escarabajo. Prueba. Primero, todo término tiene longitud al menos 1: las variables tienen longitud al menos 2, los nombres de constante son palabras no vacías de ${\mathrm{\Sigma }}_1$, y un $f(t_1,\dots ,t_n)$ tiene por lo menos sus dos paréntesis.

Sea $t\in T^{\tau }-(\mathrm{Var}\cup \mathrm{𝒞})$. Entonces $t\in T_k^{\tau }$ para algún $k$, y $k\ge 1$ porque $T_0^{\tau }=\mathrm{Var}\cup \mathrm{𝒞}$. Por el Lema 1 aplicado a $t\in T_{(k-1)+1}^{\tau }$, y como $t\notin \mathrm{Var}\cup \mathrm{𝒞}$, es $t=f(t_1,\dots ,t_n)$ con $f\in {\mathrm{ℱ}}_n$, $n\ge 1$ y $t_j\in T_{k-1}^{\tau }$. Entonces

$$|t|=|f|+|t_1|+\cdots +|t_n|+(n-1)+2\ge 1+1+0+2=4,$$

usando $|f|\ge 1$, porque $f$ es una palabra no vacía de ${\mathrm{\Sigma }}_2$; $|t_1|\ge 1$, por lo de recién; los demás $|t_j|\ge 0$, y $n-1\ge 0$. ∎

La cota es justa. En el tipo $(\{0,1\},\{\mathrm{\uparrow }\},\mathrm{\varnothing },\{(\mathrm{\uparrow },1)\})$, el término $\mathrm{\uparrow }(0)$ está en $T_1^{\tau }$ y tiene longitud 4: un símbolo de nombre, dos paréntesis y un símbolo de constante. No se puede pedir 5.

05 · Ejercicio 5: si aparece un «)», el término es compuesto

La mariposa. Otra vez una propiedad de la forma de afuera, y otra vez sin inducción. El menú deja dos posibilidades, y una de ellas no tiene paréntesis. El trabajo es el mismo del 4: separar el caso $k=0$, donde el menú no se aplica porque pide $T_{k+1}^{\tau }$.

El escarabajo. Prueba. Sea $t\in T^{\tau }$ tal que en $t$ ocurre «$)$», y sea $k$ tal que $t\in T_k^{\tau }$. Si $k=0$, $t\in \mathrm{Var}\cup \mathrm{𝒞}$, y ni las variables ni los nombres de constante tienen paréntesis: contradice que «$)$» ocurre en $t$. Luego $k\ge 1$, y por el Lema 1 aplicado a $t\in T_{(k-1)+1}^{\tau }$, o $t\in \mathrm{Var}\cup \mathrm{𝒞}$ —imposible por lo mismo— o $t=f(t_1,\dots ,t_n)$ con $f\in {\mathrm{ℱ}}_n$, $n\ge 1$ y $t_j\in T_{k-1}^{\tau }\subseteq T^{\tau }$. ∎

06 · Ejercicio 6: el índice va adentro del enunciado

La mariposa. Ésta sí pide inducción: habla de lo que viene después de cualquier «$)$», y un «$)$» puede estar enterrado en un $t_j$. La pregunta del paso es de dónde sale el «$)$» de la posición $i$: no de $f$, no de una coma, y no del «$)$» final, porque $i<|t|$. Sale de algún $t_j$. Y ahí hay dos casos: o hay otro símbolo de $t_j$ después —y la hipótesis se encarga—, o es el último símbolo de $t_j$, y lo que sigue es una frontera: la coma que lo separa de $t_{j+1}$, o el «$)$» del final.

El detalle que decide si la prueba se puede escribir es dónde va el índice. Medido en $t=\mathrm{suma}(\mathrm{glp}(\mathrm{glp}(\mathrm{X}1)),1)$, de longitud 20 y en $T_3^{\tau }$ con el tipo del Ejercicio 8: los «$)$» están en las posiciones 16, 17 y 20. Para el de la posición 16 hay que mirar $t_1=\mathrm{glp}(\mathrm{glp}(\mathrm{X}1))$, que empieza en la posición 6 de $t$, y en $t_1$ ese mismo «$)$» está en la posición 11. Si ${\mathrm{Enu}}_k$ dijera «para este $i$», la hipótesis pediría la posición 16 de $t_1$, que mide 12, y lo que hace falta es la 11. Por eso el enunciado es «para todo $t\in T_k^{\tau }$ y todo $i$»: la hipótesis tiene que valer en la posición que le toque al $t_j$. El «$)$» de la posición 17 es el otro caso: es el último de $t_1$, el 12, y lo sigue la coma.

El escarabajo. Prueba. Por la Regla de Inducción desde 0, con

$${\mathrm{Enu}}_k:\text{para todo }t\in T_k^{\tau }\text{ y todo }i\in \{1,\dots ,|t|-1\}\text{, si }{[t]}_i=)\text{ entonces }{[t]}_{i+1}\text{ es «,» o «)».}$$

${\mathrm{Enu}}_0$. En $\mathrm{Var}\cup \mathrm{𝒞}$ no ocurre «$)$»: vale vacuamente.

${\mathrm{Enu}}_k\Rightarrow {\mathrm{Enu}}_{k+1}$. Supongamos ${\mathrm{Enu}}_k$. Sea $t\in T_{k+1}^{\tau }$ e $i<|t|$ con ${[t]}_i=)$. Si $t\in T_k^{\tau }$, vale por ${\mathrm{Enu}}_k$. Si no, $t=f(t_1,\dots ,t_n)$ con $t_j\in T_k^{\tau }$. Ese «$)$» no es de $f$, que no tiene paréntesis, ni una coma, ni el «$)$» final, que está en la posición $|t|$. Entonces es un símbolo de algún $t_j$, en una posición $p$ de $t_j$ con ${[t_j]}_p=)$.

• Si $p<|t_j|$, el símbolo siguiente también es de $t_j$, y por ${\mathrm{Enu}}_k$ aplicado a $t_j$ y a la posición $p$, ${[t]}_{i+1}={[t_j]}_{p+1}$ es «$,$» o «$)$».
• Si $p=|t_j|$, lo que sigue en $t$ es la coma que separa $t_j$ de $t_{j+1}$, si $j<n$, o el «$)$» final, si $j=n$.

En todos los casos ${[t]}_{i+1}$ es «$,$» o «$)$». Luego vale ${\mathrm{Enu}}_k$ para todo $k$, y con eso para todo $t\in T^{\tau }$. ∎

07 · Ejercicio 7: la palabra «(,» no ocurre

La mariposa. El mismo molde que el 6, y la misma pregunta: de dónde sale el «$($» de una supuesta ocurrencia de «$(,$». Adentro de un $t_j$ lo resuelve la hipótesis. Lo que no resuelve son las dos fronteras: el «$($» que pone $f$, seguido del primer símbolo de $t_1$, y un «$($» que fuera el último símbolo de un $t_j$, seguido de la coma que pone $f$. Para cerrarlas hacen falta dos hechos sobre los bordes de un término, y ésos salen del menú sin inducción:

• (P) Primer símbolo. Todo término empieza con $\mathrm{X}$, si es variable; con un símbolo de ${\mathrm{\Sigma }}_1$, si es constante, o con uno de ${\mathrm{\Sigma }}_2$, si es $f(\dots )$. Nunca con una coma ni con un paréntesis.
• (U) Último símbolo. Todo término termina en un numeral negrita, si es variable; en un símbolo de ${\mathrm{\Sigma }}_1$, si es constante, o en «$)$», si es $f(\dots )$. Nunca en «$($».

Las dos se ven igual que el 5: si $t\in T_0^{\tau }$ es variable o constante, y si $t\in T_{k+1}^{\tau }$ el menú da las mismas dos formas. Es el caso que el molde avisa: la propiedad falla, si falla, justo donde se pegan las piezas.

El escarabajo. Prueba. Por la Regla de Inducción desde 0, con

$${\mathrm{Enu}}_k:\text{para todo }t\in T_k^{\tau }\text{, la palabra «(,» no ocurre en }t.$$

${\mathrm{Enu}}_0$. En $\mathrm{Var}\cup \mathrm{𝒞}$ no hay «$($».

${\mathrm{Enu}}_k\Rightarrow {\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, $t=f(t_1,\dots ,t_n)$ con $t_j\in T_k^{\tau }$. Supongamos que «$(,$» ocurre en $t$ a partir de $i$. Como $f$ no tiene paréntesis, el «$($» de la posición $i$ es el que sigue a $f$ o es un símbolo de algún $t_j$.

• Si es el que sigue a $f$, la coma de la posición $i+1$ es el primer símbolo de $t_1$: absurdo por (P).
• Si es un símbolo de $t_j$ que no es el último, la coma también es de $t_j$, y «$(,$» ocurre en $t_j$: absurdo por ${\mathrm{Enu}}_k$.
• Si es el último símbolo de $t_j$: absurdo por (U).

Luego «$(,$» no ocurre en $t$, vale ${\mathrm{Enu}}_k$ para todo $k$, y con eso para todo término. ∎

El mismo molde, tres veces. El 3, el 6 y el 7 tienen la misma base —en $\mathrm{Var}\cup \mathrm{𝒞}$ no hay paréntesis— y el mismo paso: el caso $t\in T_k^{\tau }$ es la hipótesis, y en $f(t_1,\dots ,t_n)$ se mira cada pieza. Lo que cambia es cuánto trabajo dan las fronteras: ninguno en el 3, que sólo suma; dos casos en el 6; dos casos y dos hechos auxiliares en el 7. El 4 y el 5, en cambio, no tienen nada que buscar adentro de los $t_j$, y por eso alcanza con el menú.

08 · Ejercicio 8: contar, o leer de afuera

Primero, que $\tau$ es un tipo. Los nombres de constante usan ${\mathrm{\Sigma }}_1=\{\mathrm{c},\mathrm{e},\mathrm{r},\mathrm{o},1\}$ y los de función ${\mathrm{\Sigma }}_2=\{\mathrm{s},\mathrm{u},\mathrm{m},\mathrm{a},\mathrm{g},\mathrm{l},\mathrm{p}\}$: son disjuntos, no tienen ningún símbolo prohibido, y ningún nombre es subpalabra propia de otro del mismo conjunto.

La mariposa. Para probar que una palabra no es término, mirarla y decir que está mal escrita no es una prueba. Hay dos estrategias, y conviene probar primero la barata:

• Un invariante. Una propiedad que cumplen todos los términos y la palabra no. Los del 3, el 6 y el 7 son exactamente eso. La que la guía usa para (a) es la del 3.
• Leer de afuera hasta el absurdo. Suponer que la palabra es término y desarmarla con el menú, hasta que una pieza no pueda serlo.

Medido en la sección 01: (a) y (e) caen contando paréntesis, y (b), (c) y (d) pasan los tres invariantes. Para esas tres hay que leer. Y para leer hacen falta dos herramientas, las dos sacadas del menú:

• (∗) Si un término empieza con $\mathrm{X}$, es una variable. Un término es variable, constante —empieza con un símbolo de ${\mathrm{\Sigma }}_1$— o $f(\dots )$ —empieza con uno de ${\mathrm{\Sigma }}_2$—, y la $\mathrm{X}$ no está en ${\mathrm{\Sigma }}_1\cup {\mathrm{\Sigma }}_2$. La guía dice que es «fácil probar por inducción»; con el menú, ni siquiera hace falta.
• La lectura de afuera. Si una palabra $\alpha$ con paréntesis es término, no está en $\mathrm{Var}\cup \mathrm{𝒞}$, así que por el menú es $f(t_1,\dots ,t_n)$ con los $t_j$ términos. Como los nombres no tienen paréntesis, $f$ es exactamente el tramo de $\alpha$ anterior al primer «$($», y eso fija $n=a(f)$. Lo que queda entre ese «$($» y el «$)$» del final es $t_1,\dots ,t_n$: los argumentos separados por $n-1$ de sus comas, y no se sabe cuáles.

Eso último es lo que hay que cuidar: entre los argumentos puede haber más comas que las separadoras, porque un argumento puede tener comas adentro. La prueba no puede elegir la coma que le conviene. Tiene que decir «la separadora es alguna de éstas» y llegar al absurdo con cada una.

Abajo están las cinco palabras. Arranca en (d) contando, que es donde contar no decide nada: pasá a leerla de afuera y elegí vos la coma.

El escarabajo, ítem por ítem.

(a) La palabra $\mathrm{glp}((\mathrm{X}133)$ tiene dos «$($» y un «$)$». Por el Ejercicio 3, todo término tiene tantos de uno como del otro. Luego no es término. ∎

Es la prueba de la guía, en la página 4, y es la que hay que dar: leyéndola de afuera también se llega —$\mathrm{glp}$ tiene aridad 1, el argumento sería $(\mathrm{X}133$, y por (P) ningún término empieza con «$($»—, pero eso pide (P), que hay que probar, y el conteo ya está probado.

(b) Supongamos que $\mathrm{suma}(\mathrm{g},\mathrm{cero})\in T^{\tau }$. Por la lectura de afuera, $f=\mathrm{suma}$, $n=2$, y $\mathrm{suma}(\mathrm{g},\mathrm{cero})=\mathrm{suma}(t_1,t_2)$ con $t_1,t_2\in T^{\tau }$. Sacando «$\mathrm{suma}($» y el «$)$» final, $\mathrm{g},\mathrm{cero}=t_1,t_2$. La palabra de la izquierda tiene una sola coma, y la separadora del lado derecho es una de ellas, así que $t_1$ y $t_2$ no tienen comas: $t_1=\mathrm{g}$. Pero $\mathrm{g}\notin \mathrm{Var}\cup \mathrm{𝒞}$ y $|\mathrm{g}|=1<4$, así que por el Ejercicio 4, $\mathrm{g}\notin T^{\tau }$. Absurdo. ∎

El argumento corto que tienta es «la letra $\mathrm{g}$ no está en el alfabeto del tipo», y es falso: $\mathrm{g}\in {\mathrm{\Sigma }}_2$, es la primera letra de $\mathrm{glp}$. Lo que falla no es el símbolo: es que la palabra $\mathrm{g}$ no es un término.

(c) Supongamos que $\mathrm{glp}(0)\in T^{\tau }$. Por la lectura de afuera, $f=\mathrm{glp}$, $n=1$ y $t_1=0$. El símbolo $0$ no es un nombre de constante, porque $\mathrm{𝒞}=\{\mathrm{cero},1\}$; no es una variable, porque no empieza con $\mathrm{X}$, y tiene longitud $1<4$. Por el Ejercicio 4, $0\notin T^{\tau }$. Absurdo. ∎

(d) Supongamos que es término. Por la lectura de afuera, $f=\mathrm{suma}$, $n=2$, y

$$\mathrm{X}1232,\mathrm{X}2,1=t_1,t_2$$

con $t_1,t_2\in T^{\tau }$. La palabra de la izquierda tiene dos comas, y la separadora es una de ellas.

• Si es la primera, $t_2=\mathrm{X}2,1$. Empieza con $\mathrm{X}$, así que por (∗) es una variable; pero las variables no tienen comas. Absurdo.
• Si es la segunda, $t_1=\mathrm{X}1232,\mathrm{X}2$. Empieza con $\mathrm{X}$ y tiene una coma: el mismo absurdo.

En los dos casos se llega a un absurdo, así que la palabra no es término. ∎

La versión de la guía. La página 4 resuelve el mismo ítem en otro orden: en vez de repartir por la coma, corta primero $t_1$. De $\mathrm{X}1232,\mathrm{X}2,1=t_1,t_2$ saca que $t_1$ empieza con $\mathrm{X}$ —porque $t_1$ no puede ser $\epsilon$, y ése es el «justifique» que deja: todo término mide al menos 1—, por (∗) $t_1$ es una variable, y como una variable termina en su único negrita, $t_1=\mathrm{X}1232$. Queda $\mathrm{X}2,1=t_2$, y aplicando (∗) otra vez, $\mathrm{X}2,1$ tendría que ser una variable. Absurdo. Las dos usan (∗); la de la guía lo usa para ubicar la coma, y la de arriba prueba todas.

(e) Contando: hay cinco «$\mathrm{suma}($» y un «$\mathrm{glp}($», o sea 6 paréntesis que abren. Los que cierran son uno después de cada uno de los cuatro «$,1$», uno después de «$\mathrm{cero}$» y dos más al final: 7. Como $6\ne 7$, por el Ejercicio 3 no es término. ∎

Leerla de afuera también termina, y se ve en la simulación de arriba: la palabra de adentro tiene cinco comas. Con cada una de las cuatro primeras, $t_1$ tiene 4 paréntesis que abren y 0, 1, 2 o 3 que cierran; con la quinta, $t_1$ sí es término, y el que falla es $t_2=\mathrm{glp}(\mathrm{cero}))$, con 1 que abre y 2 que cierran. Las cinco ramas terminan contando paréntesis, y ésa es la razón para contar desde el principio.

09 · Lo que se lleva a otros ejercicios

Antes de una inducción, preguntá si la propiedad mira adentro. Si sólo habla de la forma de afuera, el menú alcanza y la inducción es ruido; si habla de cualquier posición, hace falta, y los parámetros van cuantificados adentro de ${\mathrm{Enu}}_k$. Es el mismo criterio con fórmulas, en el Ejercicio 14.

El conteo de paréntesis tiene más usos que el 8. El 2(h) lo necesita para ver que $\mathrm{s}(\mathrm{X}1$ no es término: tiene un «$($» y ningún «$)$». Está en Antes de decidir, preguntá qué clase de objeto es.

Elegir la coma es el problema de la lectura única. En el 8 la palabra no es término y toda coma lleva al absurdo. Cuando la palabra sí es término, hay exactamente una coma buena, y saber cuál es lo que resuelven el Ejercicio 11 y el ensayo Un corte equivocado rompe las dos piezas.

Lo que hace perder puntos. Escribir ${\mathrm{Enu}}_k$ con el índice afuera, en el 6. Olvidar las fronteras en el 7, sobre todo el «$($» que es último símbolo de un $t_j$. Probar el 4 sin asegurar que $|t_1|\ge 1$. En el 8, decir que $\mathrm{g}$ no está en el alfabeto, cortar por la coma que conviene sin descartar las otras, o confundir $0$ con su negrita. Y citar el 3 o el 4 sin haberlos probado: la regla de la cátedra es que un resultado de una guía que se usa se enuncia y se prueba.

Para tener a mano

1. El molde: ${\mathrm{Enu}}_k$ es «para todo $t\in T_k^{\tau }$ (y todo parámetro), $P(t)$»; base en $\mathrm{Var}\cup \mathrm{𝒞}$, sin paréntesis ni comas; paso con $t\in T_k^{\tau }$ o $t=f(t_1,\dots ,t_n)$, revisando cada pieza y cada frontera.
2. 3, 6 y 7 van con el molde. 4 y 5 salen del menú, con el caso $k=0$ aparte.
3. Ningún término es vacío; uno compuesto mide al menos 4, y $\mathrm{\uparrow }(0)$ muestra que la cota es justa.
4. (P) y (U): un término empieza con $\mathrm{X}$ o con un símbolo de nombre, y termina en un negrita, un símbolo de constante o «$)$». Y (∗): si empieza con $\mathrm{X}$, es una variable.
5. Para probar que no es término: primero contar ((a): 2 y 1; (e): 6 y 7). Si el conteo pasa, leer de afuera: $f$ es lo que está antes del primer «$($», $n=a(f)$, y el absurdo tiene que salir con cada coma que podría ser la separadora.