Probar que una palabra no es término ni fórmula

«Está mal escrita» no es una prueba. Que una palabra no sea un término quiere decir que no está en ningún $T_k^{\tau }$, y esos conjuntos se arman de adentro hacia afuera, sin fin: no hay una lista donde buscarla y no encontrarla. La guía da dos maneras de probarlo, en la p. 4, a propósito del Ejercicio 8. La primera es encontrar una propiedad que tienen todos los términos y la palabra no. La segunda es suponer que es un término y leerla de afuera hacia adentro hasta que algo no cierre. Las dos sirven igual para fórmulas, y casi siempre se terminan usando juntas.

01 · Qué hay que probar

Un término de tipo $\tau$ es una palabra: una sucesión finita de símbolos. $T_0^{\tau }=\mathrm{Var}\cup 𝒞$, y $T_{k+1}^{\tau }$ agrega a $T_k^{\tau }$ todas las palabras $f(t_1,\dots ,t_n)$ con $f\in {ℱ}_n$ y $t_1,\dots ,t_n\in T_k^{\tau }$. $T^{\tau }$ es la unión de todos los niveles. Entonces $\alpha \notin T^{\tau }$ quiere decir que $\alpha \notin T_k^{\tau }$ para todo $k\ge 0$, y es una afirmación sobre infinitos conjuntos a la vez. Mirar los primeros niveles no prueba nada: la palabra podría aparecer más arriba. Hay dos maneras de cubrir todos los $k$ de una vez.

Un invariante. Una propiedad $P$ de palabras que cumplen todos los términos. Se prueba una sola vez, en general por inducción en el nivel: vale en $T_0^{\tau }$, y si vale en $T_k^{\tau }$ vale en $T_{k+1}^{\tau }$. Después alcanza con mirar que $\alpha$ no cumple $P$.

El absurdo. Suponer $\alpha \in T^{\tau }$. Entonces $\alpha \in T_k^{\tau }$ para algún $k$, y el Lema 1 de la guía —el menú— dice qué forma tiene: si $k\ge 1$, $\alpha \in \mathrm{Var}\cup 𝒞$ o $\alpha =f(t_1,\dots ,t_n)$ con los $t_j$ en $T_{k-1}^{\tau }$. Leyendo así, pieza por pieza, se llega a una pieza que no puede ser lo que la forma exige.

02 · Primera estrategia: un invariante

La guía lo dice así: «encontrar una propiedad que posean todos los términos la cual no cumpla dicha palabra». Éstas son las que da la guía o salen de ella. Para todo término $t$, escribiendo ${[t]}_i$ para el símbolo de la posición $i$ y ${|t|}_{\sigma }$ para la cantidad de veces que aparece el símbolo $\sigma$:

1. Paréntesis${|t|}_{(}={|t|}_{)}$. Es el Ejercicio 3, por inducción: las variables y las constantes no tienen paréntesis, y $f(t_1,\dots ,t_n)$ agrega un par a los de sus argumentos.
2. Primer símbolo${[t]}_1$ es $\mathrm{X}$, el primer símbolo de un nombre de constante o el primer símbolo de un nombre de función. Sale del menú sin inducción. En particular, ningún término empieza con «(», «)» ni «,».
3. Último símboloUn numeral negrita, el último símbolo de un nombre de constante, o «)». También sin inducción. Ningún término termina en «(» ni en «,».
4. Empieza con X(∗) Si un término empieza con $\mathrm{X}$, es una variable. Es el primer símbolo leído al revés: $\mathrm{X}$ no aparece en ningún nombre del tipo.
5. Después de «)»Si ${[t]}_i=)$ con $i<|t|$, entonces ${[t]}_{i+1}$ es «,» o «)». Ejercicio 6, por inducción con la posición cuantificada adentro.
6. «(,» no ocurreEjercicio 7, por inducción, usando el primer y el último símbolo.
7. Después de una comaUna coma nunca es el último símbolo, y lo que la sigue es el primer símbolo de un término. Por inducción, como el 7: una coma de $f(t_1,\dots ,t_n)$ separa dos argumentos o está adentro de uno.
8. LargoSi $t\notin \mathrm{Var}\cup 𝒞$, $|t|\ge 4$. Ejercicio 4, sin inducción: $|f(t_1,\dots ,t_n)|$ es $|f|+|t_1|+\cdots +|t_n|+(n-1)+2$, que es al menos $1+1+0+2$.

Para fórmulas hay cuatro con la misma forma. ${|\phi |}_{(}={|\phi |}_{)}$, por inducción: las atómicas tienen un par más los de sus términos, $({\phi }_1\eta {\phi }_2)$ agrega uno, $\neg {\phi }_1$ y $Qv{\phi }_1$ ninguno. El primer símbolo es el de un nombre de relación, $\forall$, $\exists$, $\neg$ o «(» (Ejercicio 14(b)). El último es siempre «)» (Ejercicio 14(a)): las atómicas terminan así, y $\neg$ y $Qv$ se agregan adelante. Y después de una coma empieza un término, porque en una fórmula las comas sólo viven adentro de las atómicas.

Usar uno es una línea. $\mathrm{glp}((\mathrm{X}133)$, el 8(a), tiene dos «(» y un «)»: por el Ejercicio 3 no es un término. El 8(e) tiene seis «(», uno por cada $\mathrm{suma}$ y el de $\mathrm{glp}$, y siete «)». En el Ejercicio 15, sobre el tipo $(\{0,1\},\{\mathrm{+}\},\{r\},\{(\mathrm{+},2),(r,2)\})$, el (a) tiene una coma seguida de $\forall$ y el (b) una coma seguida de «(»: ninguno de los dos símbolos empieza un término, y ninguna de las dos es fórmula. El (b) dicho de otro modo: $(0\equiv 1)$ es una fórmula, no un término, y no puede ser argumento de $r$.

Lo que la línea no muestra es que el invariante es un resultado. La cátedra corrige con una regla: si se usa un resultado de una guía, hay que enunciarlo y probarlo. «Por el Ejercicio 3» va acompañado de la inducción del Ejercicio 3, aunque sean cuatro renglones; las que salen sin inducción, como el primer símbolo, se justifican con el menú en una frase.

03 · Segunda estrategia: leerla de afuera

El tipo del Ejercicio 8 es $\tau =(\{\mathrm{cero},1\},\{\mathrm{suma},\mathrm{glp}\},\varnothing ,a)$, con $a(\mathrm{suma})=2$ y $a(\mathrm{glp})=1$. El (d) es $\mathrm{suma}(\mathrm{X}1232,\mathrm{X}2,1)$, y la guía lo resuelve suponiendo que es un término. Desarmado:

1. Paso 1 · un nivelEstá en algún $T_k^{\tau }$, y $k\ge 1$: no está en $T_0^{\tau }=\mathrm{Var}\cup \{\mathrm{cero},1\}$.
2. Paso 2 · el menúPor el Lema 1, es $f(t_1,\dots ,t_n)$ con $f\in {ℱ}_n$, $n\ge 1$ y $t_1,\dots ,t_n\in T_{k-1}^{\tau }$.
3. Paso 3 · el nombreLos nombres no tienen paréntesis, así que $f$ es exactamente el tramo anterior al primer «(»: $f=\mathrm{suma}$, y eso fija $n=a(\mathrm{suma})=2$. La otra opción, $\mathrm{glp}(t_1)$, empieza distinto.
4. Paso 4 · las piezasSacando «$\mathrm{suma}$(» y el «)» final queda $\mathrm{X}1232,\mathrm{X}2,1=t_1,t_2$. La coma que separa $t_1$ de $t_2$ es una de las dos que hay a la izquierda; cuál, todavía no se sabe.
5. Paso 5 · (∗)$t_1$ no es vacío —todo término tiene al menos un símbolo—, así que empieza con $\mathrm{X}$, y por (∗) es una variable. Una variable termina en su único negrita: $t_1=\mathrm{X}1232$. Entonces $t_2=\mathrm{X}2,1$, que empieza con $\mathrm{X}$, tendría que ser una variable, y tiene una coma. Absurdo.

La elección de la coma separadora se puede hacer también por casos: si es la primera, $t_2=\mathrm{X}2,1$; si es la segunda, $t_1=\mathrm{X}1232,\mathrm{X}2$. Las dos piezas empiezan con $\mathrm{X}$ y tienen una coma, y (∗) las descarta igual. Es la misma idea: el paso 3 fija la aridad, la aridad dice cuántas comas separan, y las separadoras se eligen entre las que hay.

El 8(b) es más corto. Si $\mathrm{suma}(\mathrm{g},\mathrm{cero})$ fuera un término, $f=\mathrm{suma}$, $n=2$, y hay una sola coma, que tiene que ser la separadora: $t_1=\mathrm{g}$. Pero $\mathrm{g}$ no es una variable ni un nombre de constante, y tiene largo 1 < 4, así que por el Ejercicio 4 no es un término. El 8(c) es igual: en $\mathrm{glp}(0)$, $t_1=0$, el numeral normal, que no es una constante —$𝒞=\{\mathrm{cero},1\}$—, ni una variable, y tiene largo 1.

Con fórmulas, el primer símbolo decide la forma, como en la tabla del Teorema 7: con $\neg$ es $\neg {\phi }_1$, con $\forall$ o $\exists$ es $Qv{\phi }_1$, con «(» es $(t\equiv s)$ o $({\phi }_1\eta {\phi }_2)$, y si no, una atómica $r(t_1,\dots ,t_n)$. El 15(c) es $\exists x_3(r(x_3,x_4)\to \neg (x_4\equiv 0)\forall x_4)$. Si fuera fórmula, como empieza con $\exists$ sería $\exists v{\gamma }_1$; la variable termina en el primer negrita, así que $v=x_3$ y ${\gamma }_1=(r(x_3,x_4)\to \neg (x_4\equiv 0)\forall x_4)$. ${\gamma }_1$ empieza con «(», y no es $(t\equiv s)$: $t$ empezaría con $r$, y ningún término empieza con un símbolo de un nombre de relación. Es $({\phi }_1\eta {\phi }_2)$, y como $\to$ es el único nexo binario, ${\phi }_2=\neg (x_4\equiv 0)\forall x_4$. Pero ${\phi }_2$ termina en el negrita de $x_4$, y toda fórmula termina en «)». Absurdo.

Fijate cómo terminan las cuatro lecturas: con un invariante. En el 8(b) y el 8(c) es el largo, en el 15(c) el último símbolo, en el 8(d) el (∗). La palabra entera los cumple a todos; una pieza no. Leer de afuera no reemplaza al invariante: lo lleva hasta la pieza donde falla.

04 · Cuándo conviene cada una

Primero el invariante, porque cuando funciona es una línea. De las ocho palabras de los Ejercicios 8 y 15, cuatro caen con uno de la lista: el 8(a) y el 8(e) contando paréntesis, el 15(a) y el 15(b) por la coma. Las otras cuatro —8(b), 8(c), 8(d) y 15(c)— cumplen todos, enteras, y piden la lectura.

Se ve venir mirando dónde está el error. Si está en una juntura —una coma seguida de algo que no empieza un término, un «)» seguido de una letra, un paréntesis de más—, algún invariante lo ve, porque los invariantes miran símbolos sueltos, pares de símbolos vecinos o conteos. Si la palabra está bien armada y lo que falla es qué hay adentro —un argumento que no es término, como $\mathrm{g}$ o $0$, o una cantidad de argumentos que no es la aridad—, hay que leerla: los invariantes de la lista no saben qué es un nombre de constante ni cuántos argumentos lleva $\mathrm{suma}$.

La guía dice que con esta estrategia «se pueden hacer todos los incisos restantes». Es cierto, pero para el 8(d) el invariante habría que inventarlo. Por ejemplo, contar comas: cada «(» de un término abre un $f(\dots )$ y viene pegado a su nombre, y ese $f(\dots )$ aporta $a(f)-1$ comas. En el 8(d) el único «(» sigue a $\mathrm{suma}$, así que un término tendría una coma, y la palabra tiene dos. Es correcto, y probarlo es otra inducción; leer de afuera cuesta menos.

La lectura, en cambio, nunca se queda sin respuesta. Mirar el primer símbolo, elegir la forma, cortar y seguir con las piezas es un procedimiento que siempre termina, porque las piezas son más cortas: así se ve que decidir si una palabra es fórmula es efectivamente computable, que es lo que desarrolla El primer símbolo ya dice qué forma tiene. El precio es el largo de la prueba, y que cada corte hay que justificarlo.

05 · Contar paréntesis no alcanza

Es el primer invariante que uno prueba, y el más débil. Tener tantos «(» como «)» es necesario para ser término o fórmula, no suficiente: el conteo no mira dónde están ni qué hay entre ellos. El 15(a)

$$\neg (((x_1\equiv x_2)\wedge r(\mathrm{+}(0,x_{12}),x_2)),\forall x_3(x_3\equiv 0))$$

tiene seis y seis, y además bien anidados: cada «(» tiene su pareja, y la de la posición 2 cierra al final. Lo que falla es la coma de la posición 27, que pega dos fórmulas como si fueran argumentos. El 15(b) tiene ocho y ocho, el 15(c) tres y tres, y el 8(b), el 8(c) y el 8(d), uno y uno. De las ocho palabras, el conteo delata dos.

La guía tiene otro ejemplo, en la p. 10: $(\mathrm{X}1\le \mathrm{X}2)$ no es una fórmula del tipo de los reticulados con $\mathrm{\le }$ como relación, y la guía avisa que eso «no es trivial de la definición de fórmula y requiere de una demostración». Un «(» y un «)», empieza con «(», termina en «)», no tiene comas: ningún invariante de la lista la toca. La lectura la resuelve en un renglón: si fuera fórmula, por empezar con «(» sería $(t\equiv s)$ o $({\phi }_1\eta {\phi }_2)$, y no tiene ni $\equiv$ ni nexo. La forma correcta es $\mathrm{\le }(\mathrm{X}1,\mathrm{X}2)$.

Lo mismo pasa con $(\mathrm{X}1\equiv \mathrm{X}2)\wedge (\mathrm{X}2\equiv \mathrm{X}1)$, a la que le faltan los paréntesis de afuera: dos y dos, empieza y termina bien. Leída, si fuera $({\phi }_1\eta {\phi }_2)$ sin los paréntesis de afuera quedaría $\mathrm{X}1\equiv \mathrm{X}2)\wedge (\mathrm{X}2\equiv \mathrm{X}1={\phi }_1\eta {\phi }_2$, y ${\phi }_1$ empezaría con $\mathrm{X}$, que no es primer símbolo de ninguna fórmula; si fuera $(t\equiv s)$, $t$ empezaría con $\mathrm{X}$ y por (∗) sería $\mathrm{X}1$, y $s$ sería una variable con un «)». De nuevo, el que cierra es un invariante sobre una pieza.

Para tener a mano

1. $\alpha \notin T^{\tau }$ es «$\alpha \notin T_k^{\tau }$ para todo $k$»: no se prueba mirando, se prueba con un invariante o por el absurdo.
2. Invariante: una propiedad que todo término (o fórmula) cumple, probada una vez por inducción o con el menú, y que la palabra viola. La cátedra pide enunciarlo y probarlo.
3. Los de términos: paréntesis (Ej. 3), primer y último símbolo, (∗) empieza con $\mathrm{X}$ ⇒ variable, después de «)» viene «,» o «)» (Ej. 6), «(,» no ocurre (Ej. 7), después de una coma empieza un término, largo $\ge 4$ si no es variable ni constante (Ej. 4).
4. Los de fórmulas: paréntesis, primer símbolo (Ej. 14(b)), termina en «)» (Ej. 14(a)), después de una coma empieza un término.
5. Leer de afuera: el nombre es el tramo antes del primer «(», fija la aridad, y las comas separadoras se eligen entre las que hay. En fórmulas, el primer símbolo decide la forma.
6. La lectura casi siempre termina en un invariante aplicado a una pieza: el largo de $\mathrm{g}$, el «)» final de ${\phi }_2$, el (∗).
7. Error en una juntura: invariante. Error en lo que hay adentro, o en la aridad: lectura.
8. Contar paréntesis no alcanza: 15(a) tiene seis y seis, y $(\mathrm{X}1\le \mathrm{X}2)$ uno y uno.