Contar paréntesis no alcanza

Los enunciados, textuales:

• Ejercicio 13: «V o F o I, justificar. (a) Si $\alpha ,\beta$ son palabras tales que $(\alpha \wedge \beta )\in F^{\tau }$, entonces $\alpha ,\beta \in F^{\tau }$»
• Ejercicio 14: «Sea $\phi \in F^{\tau }$. (a) $[\phi {]}_{|\phi |}=)$ (b) $[\phi {]}_1\in \{[r{]}_1:r\in \mathrm{ℛ}\}$ o $[\phi {]}_1$ es alguno de los siguientes símbolos $\forall \exists \neg ($ (c) Si ${\phi }^{\prime }=$ resultado de remover en $\phi$ cada ocurrencia del símbolo $\neg$ entonces ${\phi }^{\prime }\in F^{\tau }$ (d) Si ${\phi }^{\prime }=$ resultado de reemplazar algunas ocurrencias de la variable $x_1$ en $\phi$ por $x_2$, entonces ${\phi }^{\prime }\in F^{\tau }$ (e) Si ${\phi }^{\prime }=$ resultado de reemplazar algunas ocurrencias de la palabra $\forall x_1\exists x_2$ en $\phi$ por $\exists x_1\forall x_2$, entonces ${\phi }^{\prime }\in F^{\tau }$»
• Ejercicio 15: «Pruebe que las siguientes palabras no son fórmulas de tipo $(\{0,1\},\{+\},\{r\},\{(+,2),(r,2)\})$. (a) $\neg (((x_1\equiv x_2)\wedge r(+(0,x_{12}),x_2)),\forall x_3(x_3\equiv 0))$ (b) $((r(x_1,(0\equiv 1))\wedge \forall x_1\exists x_{2}r(x_1,x_2))\wedge ((0\equiv x_3)\to r(x_3,x_7)))$ (c) $\exists x_3(r(x_3,x_4)\to \neg (x_4\equiv 0)\forall x_4)$»

Son los primeros ejercicios sobre fórmulas, y las herramientas son las del bloque de términos: inducción, ahora sobre los $F_k^{\tau }$ y sus cinco formas, e invariantes para descartar palabras. Como en la guía, $x_1$ abrevia la variable que como palabra es $\mathrm{X}1$, y $x_{12}$ es $\mathrm{X}12$: tres símbolos, el último negrita.

01 · Antes de probar: qué es verdadero y qué no

El 13(a) es falso, y por la misma razón que el Ejercicio 2(h): el $\wedge$ que separa $\alpha$ de $\beta$ no tiene por qué ser el principal. La palabra $(((x_1\equiv x_2)\wedge (x_1\equiv x_1))\wedge (x_2\equiv x_2))$ es una fórmula de nivel 2 con dos $\wedge$, en las posiciones 10 y 19. Cortada por el de la 19, las dos mitades son fórmulas. Cortada por el de la 10, $\alpha$ es $((x_1\equiv x_2)$, con dos «(» y un «)», y no es fórmula. La versión verdadera pide que uno de los dos ya sea fórmula: es el Ejercicio 19.

Las cinco del 14 son verdaderas. Cuatro salen por inducción en el nivel, con el mismo molde; la (b) sale del menú, sin inducción. La (d) y la (e) son las delicadas: antes de inducir hay que saber dónde puede estar una ocurrencia de $x_1$ o de $\forall x_1\exists x_2$, porque un reemplazo que cae a caballo entre dos piezas podría romper la fórmula.

Ninguna de las tres del 15 es fórmula, y contar paréntesis no delata a ninguna: la (a) tiene 6 «(» y 6 «)», la (b) 8 y 8, la (c) 3 y 3. Tampoco las delatan el primer símbolo (son $\neg$, «(» y $\exists$, los tres permitidos) ni el último (las tres terminan en «)»). A la (a) y a la (b) las delata lo que sigue a una coma; a la (c), sólo leerla de afuera hacia adentro.

02 · Las herramientas

La definición, en la página 9 de la guía. $F_0^{\tau }$ son las fórmulas atómicas, $(t\equiv s)$ y $r(t_1,\dots ,t_n)$ con $r\in {\mathrm{ℛ}}_n$, $n\ge 1$ y $t,s,t_1,\dots ,t_n\in T^{\tau }$, y

$$F_{k+1}^{\tau }=F_k^{\tau }\cup \{\neg \phi :\phi \in F_k^{\tau }\}\cup \{(\phi \eta \psi ):\phi ,\psi \in F_k^{\tau }\}\cup \{Qv\phi :\phi \in F_k^{\tau },v\in \mathrm{Var}\}$$

con $\eta$ uno de los nexos $\wedge$, $\vee$, $\to$, $\leftrightarrow$ y $Q$ uno de los cuantificadores $\forall$, $\exists$. Los niveles crecen, $F_k^{\tau }\subseteq F_{k+1}^{\tau }$, y $F^{\tau }$ es su unión.

El menú para fórmulas (Lema 5, p. 10): si $\phi \in F_{k+1}^{\tau }$, entonces $\phi$ es atómica, o es $({\phi }_1\eta {\phi }_2)$, $\neg {\phi }_1$ o $Qv{\phi }_1$ con ${\phi }_1,{\phi }_2\in F_k^{\tau }$. Es lo que hace andar cada paso inductivo.

La Regla de Inducción desde 0, con el enunciado ${\mathrm{Enu}}_k$: «toda $\phi \in F_k^{\tau }$ cumple P». Se prueba ${\mathrm{Enu}}_0$ mirando las atómicas, y ${\mathrm{Enu}}_k\Rightarrow {\mathrm{Enu}}_{k+1}$ mirando las cinco formas; el molde, con su porqué, está en Inducción en la construcción.

La lectura única (Teorema 7, p. 12): cada fórmula tiene una sola de las cinco formas, con piezas únicas. Es lo que permite leer una palabra de afuera hacia adentro y concluir algo de cada pieza; está en Fórmulas de tipo τ y su lectura única.

Los invariantes, que el bloque mismo prueba: igual cantidad de «(» que de «)» (sección 03), termina en «)» (el 14(a)), empieza con «(», $\neg$, $\forall$, $\exists$ o el primer símbolo de un nombre de relación (el 14(b)), y después de una coma empieza un término (sección 06). Cómo se elige entre ellos y cuándo hay que leer de afuera está en Probar que una palabra no es término ni fórmula.

03 · El Ejercicio 13: el corte por el ∧ equivocado

La mariposa. El 2(h) armaba $\mathrm{s}(\mathrm{s}(x_1,x_2),x_3)$ y lo cortaba por la coma de adentro. Acá se hace lo mismo con un $\wedge$: hace falta una fórmula con dos $\wedge$ a distinta profundidad, y cortarla por el de adentro. La más chica de esa forma es $((A\wedge B)\wedge C)$ con tres atómicas. El corte por el primer $\wedge$ deja $\alpha =(A$, que abre un paréntesis que nunca cierra. Cualquier atómica sirve; con igualdades entre variables, el contraejemplo vale en todo tipo.

El escarabajo. Falso. Sea

$$\phi =(((x_1\equiv x_2)\wedge (x_1\equiv x_1))\wedge (x_2\equiv x_2))$$

Las variables son términos de cualquier tipo, así que $(x_1\equiv x_2)$, $(x_1\equiv x_1)$ y $(x_2\equiv x_2)$ están en $F_0^{\tau }$; entonces $((x_1\equiv x_2)\wedge (x_1\equiv x_1))\in F_1^{\tau }$ y $\phi \in F_2^{\tau }$. Tomando

$$\alpha =((x_1\equiv x_2)\text{ y }\beta =(x_1\equiv x_1))\wedge (x_2\equiv x_2)$$

la palabra $(\alpha \wedge \beta )$ —concatenar «(», $\alpha$, $\wedge$, $\beta$ y «)»— es exactamente $\phi$, así que $(\alpha \wedge \beta )\in F^{\tau }$. Pero $\alpha$ tiene dos «(» y un «)», y toda fórmula tiene tantos «(» como «)». Luego $\alpha \notin F^{\tau }$.

Ese conteo es un resultado, y la cátedra pide que un resultado de una guía que se usa se enuncie y se pruebe. Va por inducción, con ${\mathrm{Enu}}_k$: toda $\phi \in F_k^{\tau }$ tiene tantos «(» como «)». En las atómicas, $(t\equiv s)$ y $r(t_1,\dots ,t_n)$ agregan un «(» y un «)» a los de sus términos, que están balanceados por el Ejercicio 3 (que a su vez se enuncia y se prueba igual, sobre $T_k^{\tau }$). En el paso, $({\phi }_1\eta {\phi }_2)$ agrega un par a los de ${\phi }_1$ y ${\phi }_2$, y $\neg {\phi }_1$ y $Qv{\phi }_1$ no agregan ninguno: una variable no tiene paréntesis.

04 · El Ejercicio 14, de (a) a (c): un solo molde

La mariposa. Las tres se prueban con el mismo esqueleto. En el paso, $\phi \in F_{k+1}^{\tau }$ está en $F_k^{\tau }$, y vale la hipótesis, o es $({\phi }_1\eta {\phi }_2)$, $\neg {\phi }_1$ o $Qv{\phi }_1$ con subfórmulas en $F_k^{\tau }$. Son tres casos, siempre los mismos; lo que cambia de un ítem a otro es la propiedad, y qué hay que mirar en las atómicas.

(a), el escarabajo. ${\mathrm{Enu}}_k$: toda $\phi \in F_k^{\tau }$ termina en «)». Base: $(t\equiv s)$ termina en «)», y $r(t_1,\dots ,t_n)$ también, porque $n\ge 1$ y la atómica relacional siempre lleva sus paréntesis. Paso: $({\phi }_1\eta {\phi }_2)$ termina en «)»; $\neg {\phi }_1$ y $Qv{\phi }_1$ terminan con el último símbolo de ${\phi }_1$, que es «)» por ${\mathrm{Enu}}_k$.

(b), el escarabajo, sin inducción. Si $\phi \in F^{\tau }$, está en algún $F_k^{\tau }$. Si $k=0$, es $(t\equiv s)$ o $r(t_1,\dots ,t_n)$, y empieza con «(» o con $[r{]}_1$. Si $k\ge 1$, por el menú es atómica o $({\phi }_1\eta {\phi }_2)$, $\neg {\phi }_1$ o $Qv{\phi }_1$, que empiezan con «(», $\neg$, $\forall$ o $\exists$. El primer símbolo de cada forma está a la vista, y no hace falta saber nada de las piezas: por eso alcanza el menú.

(c), el escarabajo. ${\mathrm{Enu}}_k$: si $\phi \in F_k^{\tau }$, el resultado ${\phi }^{\prime }$ de borrar todos los $\neg$ de $\phi$ está en $F^{\tau }$. Base: en una atómica no ocurre $\neg$, porque los términos no lo contienen ($\neg$ no puede estar en los nombres del tipo), así que ${\phi }^{\prime }=\phi$. Paso: para $\neg {\phi }_1$, ${\phi }^{\prime }={\phi }_1^{\prime }$, que está en $F^{\tau }$ por hipótesis. Para $Qv{\phi }_1$, ${\phi }^{\prime }=Qv{\phi }_1^{\prime }$: si ${\phi }_1^{\prime }\in F_m^{\tau }$, entonces ${\phi }^{\prime }\in F_{m+1}^{\tau }$. Para $({\phi }_1\eta {\phi }_2)$, los $\neg$ son los de ${\phi }_1$ y los de ${\phi }_2$, y ${\phi }^{\prime }=({\phi }_1^{\prime }\eta {\phi }_2^{\prime })$. La hipótesis da ${\phi }_1^{\prime }\in F_{m_1}^{\tau }$ y ${\phi }_2^{\prime }\in F_{m_2}^{\tau }$, en niveles que pueden ser distintos; tomando $M=\max (m_1,m_2)$, los dos están en $F_M^{\tau }$ y ${\phi }^{\prime }\in F_{M+1}^{\tau }$.

05 · El Ejercicio 14, (d) y (e): dónde puede estar una ocurrencia

La mariposa de (d). Reemplazar adentro de una palabra es peligroso si lo reemplazado puede quedar a caballo entre dos piezas. Así que primero, dónde puede ocurrir la palabra $x_1=\mathrm{X}1$:

• No contiene «(», «)», «,», $\equiv$, nexos, $\neg$ ni cuantificadores, así que no puede cruzar el borde entre dos piezas que esos símbolos separan.
• Dentro de un término, una ocurrencia de $\mathrm{X}1$ es una ocurrencia del término $x_1$. No hay ocurrencias espurias: $\mathrm{X}1$ no ocurre en $\mathrm{X}12$ ni en $\mathrm{X}21$, porque el $1$ de $\mathrm{X}12$ es itálico y el de $\mathrm{X}21$ no viene pegado a la $\mathrm{X}$. Reemplazar una ocurrencia de un subtérmino por un término da un término (Lema 4(f), p. 7), y como $x_1$ y $x_2$ tienen el mismo largo, reemplazar una no corre las posiciones de las demás: se pueden reemplazar de a una.
• En $Qv{\phi }_1$, una ocurrencia que empieza en la posición 2 es $v$ misma: dos variables que empiezan en el mismo lugar coinciden, porque cada una termina en su único negrita. Y no puede empezar más adentro de $v$, porque la $\mathrm{X}$ de una variable es su primer símbolo.

Lo otro delicado es el enunciado de la inducción. «Algunas ocurrencias» quiere decir cualquier conjunto de ellas, y la hipótesis se va a aplicar a cada subfórmula con las ocurrencias elegidas que caen adentro, que son otro conjunto. Si ${\mathrm{Enu}}_k$ hablara de reemplazarlas todas, la hipótesis no serviría.

El escarabajo de (d). ${\mathrm{Enu}}_k$: si $\phi \in F_k^{\tau }$ y ${\phi }^{\prime }$ resulta de reemplazar cualquier conjunto de ocurrencias de $x_1$ en $\phi$ por $x_2$, entonces ${\phi }^{\prime }\in F^{\tau }$.

• Base. En $(t\equiv s)$ las ocurrencias están en $t$ o en $s$, y ${\phi }^{\prime }=(t^{\prime }\equiv s^{\prime })$ con $t^{\prime },s^{\prime }\in T^{\tau }$ por el Lema 4(f). En $r(t_1,\dots ,t_n)$, igual con cada argumento.
• Paso. En $({\phi }_1\eta {\phi }_2)$ y en $\neg {\phi }_1$ las ocurrencias están dentro de las subfórmulas, y ${\phi }^{\prime }$ es $({\phi }_1^{\prime }\eta {\phi }_2^{\prime })$ o $\neg {\phi }_1^{\prime }$: alcanza con la hipótesis y, en el primero, con el máximo de los niveles, como en (c). En $Qv{\phi }_1$, ${\phi }^{\prime }=Q{v}^{\prime }{\phi }_1^{\prime }$, donde $v^{\prime }$ es $x_2$ si $v=x_1$ y esa ocurrencia se eligió, y $v^{\prime }=v$ si no. En los dos casos $v^{\prime }\in \mathrm{Var}$ y ${\phi }_1^{\prime }\in F^{\tau }$, así que ${\phi }^{\prime }\in F^{\tau }$.

El significado puede cambiar: en $\forall x_1(x_1\equiv x_2)$, reemplazar sólo la $x_1$ del cuantificador da $\forall x_2(x_1\equiv x_2)$. Sigue siendo una fórmula, que es lo único que se pide.

La mariposa de (e). La palabra $\forall x_1\exists x_2$ tiene seis símbolos y un solo $\forall$, el primero, así que dos ocurrencias suyas no se pueden solapar: reemplazar un conjunto de ellas no es ambiguo. Las atómicas no tienen $\forall$. En $({\phi }_1\eta {\phi }_2)$ y en $\neg {\phi }_1$, la palabra no tiene paréntesis, nexos ni $\neg$, así que cada ocurrencia está dentro de una subfórmula. Lo nuevo aparece en $Qv{\phi }_1$: una ocurrencia que empieza en la posición 1 abarca el cuantificador de afuera y el de la subfórmula. Ese caso obliga a bajar dos niveles.

El escarabajo de (e). ${\mathrm{Enu}}_k$: si $\phi \in F_k^{\tau }$ y ${\phi }^{\prime }$ resulta de reemplazar cualquier conjunto de ocurrencias de $\forall x_1\exists x_2$ en $\phi$ por $\exists x_1\forall x_2$, entonces ${\phi }^{\prime }\in F^{\tau }$.

• Base. En las atómicas no ocurre $\forall$: ${\phi }^{\prime }=\phi$.
• Paso, $({\phi }_1\eta {\phi }_2)$ y $\neg {\phi }_1$. Cada ocurrencia está dentro de una subfórmula; vale la hipótesis, con el máximo de los niveles.
• Paso, $\phi =Qv{\phi }_1$ con ${\phi }_1\in F_k^{\tau }$. Ninguna ocurrencia empieza dentro de $v$, que no tiene $\forall$. Si ninguna elegida empieza en la posición 1, todas están en ${\phi }_1$ y ${\phi }^{\prime }=Qv{\phi }_1^{\prime }$ con ${\phi }_1^{\prime }\in F^{\tau }$ por hipótesis. Si se eligió la que empieza en la posición 1, entonces $Q=\forall$, y como $v$ y $x_1$ son variables que empiezan en la posición 2, $v=x_1$. Así ${\phi }_1$ empieza con $\exists x_2$; no es atómica, así que $k\ge 1$ y, por el menú, ${\phi }_1=\exists w\psi$ con $\psi \in F_{k-1}^{\tau }$, y como antes $w=x_2$. Entonces $\phi =\forall x_1\exists x_2\psi$, las demás ocurrencias elegidas están en $\psi$, y ${\phi }^{\prime }=\exists x_1\forall x_2{\psi }^{\prime }$. Como $\psi \in F_{k-1}^{\tau }\subseteq F_k^{\tau }$, la hipótesis da ${\psi }^{\prime }\in F^{\tau }$, y entonces ${\phi }^{\prime }\in F^{\tau }$.

06 · El Ejercicio 15: qué la delata

La mariposa. Para descartar una palabra se busca un invariante que viole, del más barato al más caro: contar paréntesis, mirar el primer y el último símbolo, mirar qué sigue a cada coma. Si ninguno la delata, se la lee de afuera hacia adentro suponiendo que es fórmula, hasta llegar a un absurdo. Abajo están las tres palabras del 15 y esas cinco pruebas; arranca en la (a) con el conteo.

Las cinco pruebas, sobre las tres palabras: contar paréntesis, el primer símbolo y el último no delatan a ninguna. Las comas delatan a la (a) en la posición 28 y a la (b) en la 8, y no a la (c), cuya única coma, en la 9, va seguida de una $\mathrm{X}$. Leer de afuera las delata a las tres, como tiene que ser: es la definición misma, aplicada hasta el final.

El invariante de las comas. Se usa, así que se enuncia y se prueba:

Si una coma ocurre en un término o en una fórmula, no es su último símbolo, y el símbolo que la sigue es el primero de un término: una $\mathrm{X}$, un símbolo de ${\mathrm{\Sigma }}_1$ o uno de ${\mathrm{\Sigma }}_2$. En el tipo del Ejercicio 15, uno de $0$, $1$, $+$ o $\mathrm{X}$.

Prueba, para términos, por inducción en el nivel. En $T_0^{\tau }$ no hay comas: ni las variables ni los nombres de constante las contienen. En $f(t_1,\dots ,t_n)$, una coma es una de las separadoras, y la sigue el primer símbolo de $t_{j+1}$, que por el menú es una $\mathrm{X}$, uno de ${\mathrm{\Sigma }}_1$ o uno de ${\mathrm{\Sigma }}_2$; o es interior de algún $t_j$. No es el último símbolo de $t_j$, porque un término termina en un negrita, en un símbolo de ${\mathrm{\Sigma }}_1$ o en «)», así que el símbolo que la sigue también está en $t_j$, y vale la hipótesis.

Para fórmulas, por inducción en el nivel. En $(t\equiv s)$ y en $r(t_1,\dots ,t_n)$, cada coma separa dos argumentos de $r$, y la sigue el primer símbolo de un término, o es interior de un término sin ser su último símbolo, y vale lo de los términos. En $({\phi }_1\eta {\phi }_2)$, $\neg {\phi }_1$ y $Qv{\phi }_1$, lo que se agrega no tiene comas, así que cada coma es interior de una subfórmula; no es su último símbolo, porque toda fórmula termina en «)» (el 14(a)), y vale la hipótesis.

(a), el escarabajo. En la palabra, la coma de la posición 27 —la que sigue a $r(+(0,x_{12}),x_2))$— está seguida por $\forall$, en la posición 28. Como $\forall \notin \{0,1,+,\mathrm{X}\}$, la palabra viola el invariante de las comas y no es una fórmula. Las otras dos comas, en las posiciones 17 y 22, van seguidas de una $\mathrm{X}$: el invariante no se fija en las comas que cumplen, alcanza con una que no.

Leída de afuera también cae, y se ve qué hace ahí esa coma: después del $\neg$ viene una palabra que empieza con «(» y termina en «)», así que tendría que ser $(t\equiv s)$ o $({\phi }_1\eta {\phi }_2)$. Pero en el nivel de afuera no hay ningún $\equiv$ ni nexo: entre $((x_1\equiv x_2)\wedge r(+(0,x_{12}),x_2))$ y $\forall x_3(x_3\equiv 0)$ está la coma, en el lugar donde tendría que estar el nexo.

(b), el escarabajo. La palabra contiene «,(», en $r(x_1,(0\equiv 1))$: la coma de la posición 7 va seguida del «(» de la 8. Como «(» no es el primer símbolo de ningún término, la palabra viola el invariante de las comas. Dicho de otro modo: $(0\equiv 1)$ es una fórmula, no un término, y no puede ser argumento de $r$.

(c), el escarabajo. Ningún invariante de los de arriba la delata, así que se la lee de afuera. Supongamos que $\gamma =\exists x_3(r(x_3,x_4)\to \neg (x_4\equiv 0)\forall x_4)\in F^{\tau }$.

• Empieza con $\exists$, así que por la lectura única $\gamma =\exists v{\gamma }_1$ con $v\in \mathrm{Var}$ y ${\gamma }_1\in F^{\tau }$. La variable $v$ empieza en la posición 2 y 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 «(», así que es $(t\equiv s)$ o $({\phi }_1\eta {\phi }_2)$. No es $(t\equiv s)$: $t$ empezaría con $r$, y ningún término empieza con el símbolo de un nombre de relación.
• Luego ${\gamma }_1=({\phi }_1\eta {\phi }_2)$, y $\eta$ es un nexo de ${\gamma }_1$. El único es la $\to$ de la posición 13 ($\neg$ y $\forall$ no son nexos), así que ${\phi }_1=r(x_3,x_4)$ y ${\phi }_2=\neg (x_4\equiv 0)\forall x_4$, de la posición 14 a la 23.
• Pero ${\phi }_2$ termina en el negrita de $x_4$, y toda fórmula termina en «)» (el 14(a)). Absurdo.

El $\forall x_4$ está fuera de lugar —un cuantificador va adelante de su fórmula, no atrás—, pero ningún conteo ni ninguna coma lo nota: la palabra tiene sus paréntesis en orden, empieza bien y termina bien. Sólo la lectura llega a la pieza donde eso importa.

07 · Lo que se lleva a otros ejercicios

Un corte por un símbolo cualquiera no es una lectura. Que $(\alpha \wedge \beta )$ sea fórmula dice que hay un $\wedge$ que la parte en dos fórmulas, no que lo haga el que elegiste. Es la misma trampa del 2(h) con comas, y se arregla igual: sabiendo que una de las mitades es fórmula, la otra también. Para términos es el Ejercicio 11; para fórmulas, el 19.

Antes de inducir sobre un reemplazo, se ubican las ocurrencias. En (d) y (e) la inducción es corta; lo que la hace correcta es haber visto antes que ninguna ocurrencia cruza el borde de una pieza, salvo la que empieza en el cuantificador de afuera en (e), que obliga a mirar dos niveles. El enunciado inductivo habla de cualquier conjunto de ocurrencias, para que la hipótesis se pueda aplicar a la parte que cae en cada subfórmula. Lo mismo hace falta en el Ejercicio 20.

Los invariantes de las fórmulas son los de los términos más dos. El de los paréntesis y el de las comas valen igual que para términos, y sus pruebas para fórmulas se apoyan en las de términos; el 14(a) y el 14(b) son propios de las fórmulas. El 14(a) se usa dos veces en este mismo bloque: en la prueba del invariante de las comas y en el absurdo de 15(c).

Lo que hace perder puntos. Responder «verdadero» en el 13(a) suponiendo que el $\wedge$ dado es el principal. Contar paréntesis en el 15 y, como dan iguales, dar la palabra por buena: el balance es necesario, no suficiente. Usar el invariante de las comas, o el balance de paréntesis de las fórmulas, sin enunciarlo y probarlo. En (c) del 14, aplicar la hipótesis a ${\phi }_1^{\prime }$ y ${\phi }_2^{\prime }$ sin juntar sus niveles. En (d), enunciar la inducción para «todas las ocurrencias». En (e), olvidar la ocurrencia que empieza en la posición 1. Y en 15(c), cortar por la $\to$ sin haber descartado antes la forma $(t\equiv s)$.

Para tener a mano

1. 13(a) es falso: en $(((x_1\equiv x_2)\wedge (x_1\equiv x_1))\wedge (x_2\equiv x_2))$, cortar por el primer $\wedge$ deja $\alpha =((x_1\equiv x_2)$, con dos «(» y un «)». Lo verdadero es el 19: si $(\alpha \wedge \beta )$ y $\beta$ son fórmulas, $\alpha$ también.
2. El molde del 14: base en las atómicas; en el paso, $({\phi }_1\eta {\phi }_2)$, $\neg {\phi }_1$ y $Qv{\phi }_1$ con piezas en $F_k^{\tau }$. Si la hipótesis da $F^{\tau }$, se junta con el máximo de los niveles.
3. 14(b) sale del menú: el primer símbolo de cada forma está a la vista.
4. 14(d) y (e): primero dónde puede ocurrir la palabra; después la inducción, para cualquier conjunto de ocurrencias. En (e), la ocurrencia que empieza en la posición 1 fuerza $\phi =\forall x_1\exists x_2\psi$.
5. 15: contar da 6 y 6, 8 y 8, 3 y 3, y no delata a ninguna. La coma seguida de $\forall$ delata a la (a), la seguida de «(» a la (b), y a la (c) la delata leerla de afuera: ${\phi }_2=\neg (x_4\equiv 0)\forall x_4$ termina en un negrita.