El menú ya dice el primer símbolo

El enunciado, textual: «Pruebe que si $\phi \in F^{\tau }$ entonces $[\phi {]}_1\in \{[r{]}_1:r\in ℛ\}$ o $[\phi {]}_1$ es alguno de los siguientes símbolos $\forall$ $\exists$ $\neg$ $($.» Es el Ejercicio 14(b) de la Guía 9 (p. 11). $[\alpha {]}_i$ es el $i$-ésimo símbolo de la palabra $\alpha$, así que $[\phi {]}_1$ es el primero.

01 · Qué pide, en criollo

Que una fórmula sólo puede empezar de cinco maneras: con un paréntesis, una negación, un cuantificador o el primer símbolo de un nombre de relación. Nunca con una variable, un nombre de constante o de función, una coma o un nexo.

Los once ejemplos de la página 10 de la guía lo cumplen. Con $\tau =(\{\mathrm{uno},\mathrm{doli}\},\{\mathrm{MAS},\mathrm{P}\},\{\mathrm{Her}\},a)$ empiezan con ¬, ∃, ∃, ¬ y «(»; por ejemplo

$$\neg \exists \mathrm{X}9\forall \mathrm{X}7(\mathrm{Her}(\mathrm{X}9,\mathrm{doli},\mathrm{X}7)\to (\mathrm{P}(\mathrm{doli})\equiv \mathrm{X}7))$$

empieza con ¬. Con $\tau =(\{0,1\},\{\mathrm{s},\mathrm{i}\},\{\le \},a)$ empiezan con ≤, ≤, ¬, ∀, «(» y ∀: $\le (\mathrm{X}1,\mathrm{X}2)$ es atómica, y su primer símbolo es el del nombre de relación $\le$, que tiene un solo símbolo. En el primer tipo, una atómica como $\mathrm{Her}(\mathrm{uno},\mathrm{X}4,\mathrm{doli})$ empieza con la H de $\mathrm{Her}$.

Lo que hay que notar en la fórmula de arriba: empieza con ¬, lo que viene después del ¬ empieza con ∃, y lo que viene después de $\exists \mathrm{X}9$ con ∀. El primer símbolo es el de la última construcción, y lo de adentro no importa. Y una fórmula no empieza nunca con un término: $\mathrm{X}1\equiv \mathrm{X}2$ no es fórmula, porque la igualdad va siempre entre paréntesis.

02 · Las herramientas

Las fórmulas (Guía 9, p. 9). Las atómicas de tipo $\tau$ son las palabras $(t\equiv s)$, con $t,s\in T^{\tau }$, y $r(t_1,\dots ,t_n)$, con $r\in {ℛ}_n$, $n\ge 1$ y $t_1,\dots ,t_n\in T^{\tau }$. $F_0^{\tau }$ son las atómicas, y $F_{k+1}^{\tau }$ es $F_k^{\tau }$ más las palabras $\neg \phi$, $(\phi \eta \psi )$ con $\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}$ y $Qv\phi$ con $Q\in \{\forall ,\exists \}$ y $v\in \mathrm{Var}$, para $\phi ,\psi \in F_k^{\tau }$. $F^{\tau }={\bigcup }_{k\ge 0}{F}_k^{\tau }$, y cada nivel contiene al anterior.

Lema 5 (Menú para fórmulas, p. 10). Se usa sin enunciar; queda acá para tenerlo a mano. Sea $k\ge 0$. Si $\phi \in F_{k+1}^{\tau }$, entonces se da alguna de las siguientes:

• (a) $\phi =(t\equiv s)$, con $t,s\in T^{\tau }$
• (b) $\phi =r(t_1,\dots ,t_n)$, con $r\in {ℛ}_n$, $n\ge 1$, $t_1,\dots ,t_n\in T^{\tau }$
• (c) $\phi =({\phi }_1\eta {\phi }_2)$, con $\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}$, ${\phi }_1,{\phi }_2\in F_k^{\tau }$
• (d) $\phi =\neg {\phi }_1$, con ${\phi }_1\in F_k^{\tau }$
• (e) $\phi =Qv{\phi }_1$, con $Q\in \{\forall ,\exists \}$, $v\in \mathrm{Var}$ y ${\phi }_1\in F_k^{\tau }$.

El tipo (Guía 8, p. 4). Los nombres de relación son palabras no vacías de un alfabeto ${\Sigma }_3$: $ℛ\subseteq {\Sigma }_3^{+}$. Por eso $[r{]}_1$ existe, y la palabra $r(t_1,\dots ,t_n)$, que es la concatenación de $r$, «(», los argumentos y las comas, y «)», empieza con el primer símbolo de $r$.

03 · La mariposa: por qué alcanza el menú

La pregunta es por el primer símbolo, que es una propiedad de afuera: depende de cómo está armada la fórmula en su último paso, no de lo que tiene adentro. El menú dice exactamente eso, el último paso: toda fórmula de un nivel $k+1$ tiene una de cinco formas. Y cada forma muestra su primer símbolo a la vista: «(» en (a) y en (c), $[r{]}_1$ en (b), ¬ en (d), $Q$ en (e). Las piezas $t$, $s$, ${\phi }_1$, ${\phi }_2$ no aparecen en la cuenta.

Hay un solo detalle técnico. El menú habla de $\phi \in F_{k+1}^{\tau }$, y el dato es $\phi \in F^{\tau }$. Se pasa en un renglón: $\phi$ está en algún $F_k^{\tau }$, y como $F_k^{\tau }\subseteq F_{k+1}^{\tau }$, está en $F_{k+1}^{\tau }$. Así las atómicas, que están en $F_0^{\tau }$, también entran: están en $F_1^{\tau }$, y el menú les da la forma (a) o la (b).

¿Dónde quedó la inducción? Adentro del menú. La definición de $F_{k+1}^{\tau }$ dice «lo de antes, más las palabras nuevas», y «lo de antes» puede venir de $F_k^{\tau }$, y eso de $F_{k-1}^{\tau }$, y así hasta abajo. El Lema 5 se prueba con la Regla de Inducción desde 0 justamente para aplanar esa cadena: una vez probado, toda fórmula tiene una forma de las cinco sin importar en qué nivel nació. Usar el menú es usar esa inducción ya hecha.

El último símbolo, en cambio, no sale así. Es el Ejercicio 14(a): $[\phi {]}_{|\phi |}=)$. En $\neg {\phi }_1$ y en $Qv{\phi }_1$ la construcción no agrega nada al final, y el último símbolo es el de ${\phi }_1$: para saber cuál es hay que mirar adentro, y eso pide la hipótesis inductiva. El criterio de bolsillo: si la propiedad mira afuera, alcanza el menú; si mira adentro de las piezas, inducción.

Abajo se arma una fórmula paso a paso. En cada paso cambia, o no, el primer símbolo, y se ve que lo decide la construcción de afuera: la pieza de adentro puede empezar con cualquier cosa.

Con $(\psi \to \phi )$ la fórmula de adentro queda a la derecha, y el primer símbolo es «(» aunque $\phi$ empiece con ¬ o con ∀. Con ¬ y con un cuantificador la fórmula de adentro queda pegada atrás, intacta: por eso el primer símbolo cambia y el último no.

04 · El escarabajo, sin inducción

Prueba. Sea $\phi \in F^{\tau }$. Como $F^{\tau }={\bigcup }_{k\ge 0}{F}_k^{\tau }$, hay un $k$ con $\phi \in F_k^{\tau }$, y como $F_k^{\tau }\subseteq F_{k+1}^{\tau }$, $\phi \in F_{k+1}^{\tau }$. Por el Lema 5 (Menú para fórmulas) se da alguna de las siguientes:

• (a) $\phi =(t\equiv s)$ con $t,s\in T^{\tau }$. Entonces $[\phi {]}_1=($.
• (b) $\phi =r(t_1,\dots ,t_n)$ con $r\in {ℛ}_n$. Como $r$ es una palabra no vacía y $\phi$ empieza con $r$, $[\phi {]}_1=[r{]}_1\in \{[r{]}_1:r\in ℛ\}$.
• (c) $\phi =({\phi }_1\eta {\phi }_2)$. Entonces $[\phi {]}_1=($.
• (d) $\phi =\neg {\phi }_1$. Entonces $[\phi {]}_1=\neg$.
• (e) $\phi =Qv{\phi }_1$ con $Q\in \{\forall ,\exists \}$. Entonces $[\phi {]}_1=Q$, que es ∀ o ∃.

En todos los casos $[\phi {]}_1\in \{[r{]}_1:r\in ℛ\}$ o $[\phi {]}_1$ es uno de ∀, ∃, ¬, «(». ∎

05 · Con inducción también vale

La inducción en el nivel es el camino de siempre para una propiedad de todas las fórmulas, y acá también da una prueba correcta. Escrita entera:

Prueba. Usaremos la Regla de Inducción desde 0. Para cada $k\in \omega$ sea ${\mathrm{Enu}}_k$ el enunciado:

${\mathrm{Enu}}_k$: para toda $\phi \in F_k^{\tau }$, $[\phi {]}_1\in \{[r{]}_1:r\in ℛ\}$ o $[\phi {]}_1\in \{\forall ,\exists ,\neg ,(\}$.

• ${\mathrm{Enu}}_0$ es verdadero. Si $\phi \in F_0^{\tau }$, $\phi$ es atómica: $\phi =(t\equiv s)$, y $[\phi {]}_1=($; o $\phi =r(t_1,\dots ,t_n)$ con $r\in {ℛ}_n$, y como $r\ne \epsilon$, $[\phi {]}_1=[r{]}_1$.
• ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$. Supongamos que vale ${\mathrm{Enu}}_k$ y sea $\phi \in F_{k+1}^{\tau }$. Por definición de $F_{k+1}^{\tau }$ hay cuatro casos.
  • Caso $\phi \in F_k^{\tau }$. Vale la conclusión por ${\mathrm{Enu}}_k$.
  • Caso $\phi =\neg {\phi }_1$ con ${\phi }_1\in F_k^{\tau }$. $[\phi {]}_1=\neg$.
  • Caso $\phi =({\phi }_1\eta {\phi }_2)$ con $\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}$ y ${\phi }_1,{\phi }_2\in F_k^{\tau }$. $[\phi {]}_1=($.
  • Caso $\phi =Qv{\phi }_1$ con $Q\in \{\forall ,\exists \}$, $v\in \mathrm{Var}$ y ${\phi }_1\in F_k^{\tau }$. $[\phi {]}_1=Q$.

Por la Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ vale para todo $k\in \omega$, y como toda fórmula está en algún $F_k^{\tau }$, vale el enunciado. ∎

Mirá dónde se usó la hipótesis inductiva: sólo en el caso $\phi \in F_k^{\tau }$, el que no construye nada. En los tres casos nuevos, que ${\phi }_1$ y ${\phi }_2$ estén en $F_k^{\tau }$ no se usa nunca. Ese caso único es exactamente el que el menú ya resolvió una vez y para siempre. Las dos pruebas son correctas y valen lo mismo; la del menú es más corta, y la de inducción tiene que escribir el ${\mathrm{Enu}}_k$ con su «para toda $\phi \in F_k^{\tau }$». La pregunta que decide en un parcial: ¿uso la hipótesis inductiva en algún caso que construye algo? Si la respuesta es no, alcanza el menú.

06 · Lo que hace perder puntos, y lo que se lleva

Lo que hace perder puntos. Aplicar el menú a $\phi \in F^{\tau }$ sin decir cómo se llega a $\phi \in F_{k+1}^{\tau }$, que es lo que el lema pide. Escribir $[\phi {]}_1=r$: $r$ es una palabra, posiblemente de varios símbolos como $\mathrm{Her}$, y el primer símbolo de $\phi$ es $[r{]}_1$. Olvidar que hay dos formas que empiezan con «(», la igualdad y la de los nexos. En la versión con inducción, escribir «${\mathrm{Enu}}_k$: $[\phi {]}_1\in \dots$» sin decir para qué $\phi$, u olvidar el caso $\phi \in F_k^{\tau }$ del paso.

Lo que se lleva. El primer símbolo decide la forma, y eso es lo que hace funcionar la lectura única de fórmulas: está en El primer símbolo ya dice qué forma tiene. El Ejercicio 4 lo usa: una fórmula que empieza con ∀ es $\forall v\psi$. Con términos pasa lo mismo, y en el Ejercicio 3 es la llave: un término que empieza con $\mathrm{X}$ es una variable. Cuándo alcanza el menú y cuándo hace falta inducción, con los Ejercicios 4, 5 y 14(a) de la guía, está en Inducción en la construcción.

Para tener a mano

1. $\phi \in F^{\tau }$ ⇒ $\phi \in F_k^{\tau }$ para algún $k$ ⇒ $\phi \in F_{k+1}^{\tau }$, y ahí se aplica el menú.
2. Las cinco formas y su primer símbolo: $(t\equiv s)$ y $({\phi }_1\eta {\phi }_2)$ con «(», $r(t_1,\dots ,t_n)$ con $[r{]}_1$, $\neg {\phi }_1$ con ¬, $Qv{\phi }_1$ con $Q$.
3. $[r{]}_1$ existe porque los nombres son palabras no vacías.
4. Con inducción, la hipótesis sólo se usa en el caso $\phi \in F_k^{\tau }$, que es el que el menú ya resolvió. Si una inducción no usa la hipótesis en ningún caso que construye, alcanza el menú.
5. El último símbolo no sale del menú: ¬ y $Qv$ no agregan nada atrás. Eso es el 14(a), y pide inducción.