Los cuantificadores se dan vuelta sin romper la fórmula

El enunciado, textual: «Pruebe que si $\phi \in F^{\tau }$ y ${\phi }^{\prime }$ es el resultado de reemplazar cada ocurrencia de la palabra $\forall \mathrm{X}1\exists$ en $\phi$ por $\exists \mathrm{X}1\forall$ entonces ${\phi }^{\prime }\in F^{\tau }$». Es pariente del Ejercicio 14(e) de la Guía 9, que reemplaza algunas ocurrencias de $\forall x_1\exists x_2$ por $\exists x_1\forall x_2$. Acá la palabra es más corta —termina en el $\exists$, sin su variable— y se reemplazan todas.

Es un ejercicio de sintaxis: no hay estructuras ni valores de verdad. Que $\forall x\exists y\psi$ y $\exists x\forall y\psi$ no digan lo mismo no importa; lo único que se pregunta es si la palabra que queda sigue siendo una fórmula.

01 · Qué pide, con una fórmula a la vista

Con el tipo $\tau =(\{0\},\{\mathrm{f}\},\{\mathrm{r}\},\{(\mathrm{f},1),(\mathrm{r},2)\})$, la fórmula

$$\phi =(\forall \mathrm{X}1\exists \mathrm{X}2\mathrm{r}(\mathrm{X}1,\mathrm{X}2)\wedge \neg \forall \mathrm{X}1\exists \mathrm{X}1\forall \mathrm{X}1\exists \mathrm{X}2(\mathrm{f}(\mathrm{X}1)\equiv \mathrm{X}2))$$

tiene cuarenta símbolos y es de nivel 6. La palabra $\forall \mathrm{X}1\exists$ ocurre en ella tres veces, a partir de las posiciones 2, 18 y 24. Reemplazando las tres a la vez queda

$${\phi }^{\prime }=(\exists \mathrm{X}1\forall \mathrm{X}2\mathrm{r}(\mathrm{X}1,\mathrm{X}2)\wedge \neg \exists \mathrm{X}1\forall \mathrm{X}1\exists \mathrm{X}1\forall \mathrm{X}2(\mathrm{f}(\mathrm{X}1)\equiv \mathrm{X}2))$$

que también es una fórmula, y también de nivel 6. Cada ocurrencia de $\phi$ era el principio de una fórmula de la forma $\forall x_1\exists w\psi$: la de la posición 2 empieza $\forall \mathrm{X}1\exists \mathrm{X}2\mathrm{r}(\mathrm{X}1,\mathrm{X}2)$, la de la 18 empieza $\forall \mathrm{X}1\exists \mathrm{X}1\forall \mathrm{X}1\exists \mathrm{X}2(\mathrm{f}(\mathrm{X}1)\equiv \mathrm{X}2)$ y la de la 24 empieza $\forall \mathrm{X}1\exists \mathrm{X}2(\mathrm{f}(\mathrm{X}1)\equiv \mathrm{X}2)$. Dar vuelta el par de cuantificadores del principio de una fórmula así deja otra fórmula, $\exists x_1\forall w\psi$. Eso es todo el ejercicio, y la prueba es convertir esta observación en una inducción.

Un detalle que conviene ver una vez: en ${\phi }^{\prime }$ la palabra $\forall \mathrm{X}1\exists$ vuelve a aparecer, a partir de la posición 21. El $\forall$ que la empieza lo puso el primer reemplazo de la mitad y el $\exists$ que la termina, el segundo. No es un problema: «cada ocurrencia de $\forall \mathrm{X}1\exists$ en $\phi$» habla de las ocurrencias de $\phi$, las tres, y se reemplazan las tres a la vez. Lo que aparece después no se toca.

02 · Las herramientas

Las fórmulas por niveles (Guía 9, p. 9). $F_0^{\tau }$ son las fórmulas atómicas, $(t\equiv s)$ y $r(t_1,\dots ,t_n)$ con $t,s,t_1,\dots ,t_n\in T^{\tau }$ y $r\in {ℛ}_n$, 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 },\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}\}\cup \{Qv\phi :\phi \in F_k^{\tau },Q\in \{\forall ,\exists \},v\in \mathrm{Var}\}$$

con $F^{\tau }={\bigcup }_{k\ge 0}{F}_k^{\tau }$. Dos hechos salen de la definición sin prueba: $F_k^{\tau }\subseteq F_{k+1}^{\tau }$, así que una fórmula de un nivel está en todos los siguientes; y si $\phi \in F_m^{\tau }$, entonces $\neg \phi$ y $Qv\phi$ están en $F_{m+1}^{\tau }$.

Las variables (Guía 9, p. 1): $x_n$ es la palabra $\mathrm{X}$ seguida de la escritura decimal de $n$, con todos los numerales en itálica salvo el último, que va en negrita. $x_1$ es $\mathrm{X}1$, de dos símbolos, y $x_{12}$ es $\mathrm{X}12$. Una variable termina en su único numeral negrita.

El tipo (Guía 8, p. 4): los nombres de constante, de función y de relación no usan ninguno de los símbolos $\forall$, $\exists$, $\neg$, los nexos, los paréntesis, la coma, $\equiv$, la $\mathrm{X}$ ni los numerales itálicos o negritas.

El reemplazo simultáneo (Guía 9, p. 6): cuando las ocurrencias de una palabra $\alpha$ en $\beta$ son disjuntas entre sí, se puede hablar del resultado de reemplazar simultáneamente cada ocurrencia de $\alpha$ en $\beta$ por $\gamma$. «Cada ocurrencia» del enunciado es esto, y por eso hay que ver que las ocurrencias de $\forall \mathrm{X}1\exists$ no se pisan.

La lectura única de fórmulas (Teorema 7, p. 12), que la lista deja usar sin enunciar: toda $\phi \in F^{\tau }$ es de una y sólo una de las formas $(t\equiv s)$, $r(t_1,\dots ,t_n)$, $({\phi }_1\eta {\phi }_2)$, $\neg {\phi }_1$, $Qv{\phi }_1$, con piezas únicas; y si $\phi \in F_{k+1}^{\tau }$, las piezas ${\phi }_1$, ${\phi }_2$ están en $F_k^{\tau }$. Lo que se usa de ella es el cuadro de primeros símbolos: las dos primeras formas empiezan con $($ o con un símbolo de un nombre de relación, la tercera con $($, la cuarta con $\neg$ y la quinta con $Q$.

La Regla de Inducción desde 0: si para cada $k\in \omega$ hay un enunciado ${\mathrm{Enu}}_k$, ${\mathrm{Enu}}_0$ es verdadero, y para cada $k$, si ${\mathrm{Enu}}_k$ es verdadero entonces ${\mathrm{Enu}}_{k+1}$ lo es, entonces ${\mathrm{Enu}}_k$ es verdadero para todo $k\in \omega$. El molde, con los ejemplos de la Guía 9, está en Inducción en la construcción.

03 · La mariposa: dónde puede caer la palabra

La palabra tiene cuatro símbolos, y ninguno pega. $\forall \mathrm{X}1\exists$ es $\forall$, $\mathrm{X}$, $1$, $\exists$. No tiene paréntesis, ni nexos, ni $\neg$, ni $\equiv$, ni comas: ninguno de los símbolos con los que se arma $({\phi }_1\eta {\phi }_2)$ o $\neg {\phi }_1$ a partir de sus piezas. Entonces una ocurrencia en $({\phi }_1\eta {\phi }_2)$ no puede tocar el paréntesis de afuera ni el $\eta$, y cae entera adentro de ${\phi }_1$ o adentro de ${\phi }_2$; una ocurrencia en $\neg {\phi }_1$ cae adentro de ${\phi }_1$. En esos casos el reemplazo se hace pieza por pieza: ${\phi }^{\prime }=({\phi }_1^{\prime }\eta {\phi }_2^{\prime })$ y ${\phi }^{\prime }=\neg {\phi }_1^{\prime }$, y la hipótesis inductiva se aplica a las piezas.

En una atómica no hay ninguna. Una atómica está hecha de términos, de un nombre de relación, de paréntesis, comas y quizás $\equiv$. Los términos están hechos de variables, nombres de constante y de función, paréntesis y comas. Ningún nombre usa $\forall$, por la definición de tipo, y las variables tampoco: en una atómica no hay ningún $\forall$, así que ${\phi }^{\prime }=\phi$.

El caso que importa es $Qv{\phi }_1$. Las posiciones de $v$ tienen una $\mathrm{X}$ o un numeral, así que ninguna ocurrencia empieza ahí. Las que empiezan en ${\phi }_1$ caen adentro de ${\phi }_1$, porque ${\phi }_1$ es el final de la palabra. Queda una sola posibilidad nueva: una ocurrencia en la posición 1. Si $Qv{\phi }_1$ empieza con $\forall \mathrm{X}1\exists$, entonces:

• $Q=\forall$, porque es el primer símbolo.
• $v$ empieza en la posición 2 y termina en su único numeral negrita. El de la posición 3 es $1$, negrita, así que el negrita cierra la variable ahí: $v=\mathrm{X}1=x_1$. Si la variable fuera $\mathrm{X}12$, el $1$ sería itálico y la palabra no ocurriría: en $\forall \mathrm{X}12\exists \mathrm{X}2\mathrm{r}(\mathrm{X}1,\mathrm{X}2)$ no hay ninguna ocurrencia de $\forall \mathrm{X}1\exists$.
• Entonces ${\phi }_1$ empieza en la posición 4, con $\exists$. Por la lectura única, una fórmula que empieza con $\exists$ es de la quinta forma: ${\phi }_1=\exists w\psi$, con $w\in \mathrm{Var}$ y $\psi \in F^{\tau }$.

O sea: $\forall \mathrm{X}1\exists$ sólo ocurre en una fórmula como el comienzo de una subfórmula $\forall x_1\exists w\psi$. La prueba no necesita enunciar esto aparte: lo va viendo, nivel por nivel, al mirar qué hay en la posición 1 de cada $Qv{\phi }_1$.

Dos ocurrencias no se pisan. Si dos ocurrencias de una palabra de cuatro símbolos se superpusieran sin coincidir, un tramo final propio de la palabra sería un tramo inicial propio de ella misma. Los tramos finales propios de $\forall \mathrm{X}1\exists$ empiezan con $\mathrm{X}$, $1$ o $\exists$, y los iniciales empiezan con $\forall$: no hay ninguno común. Las ocurrencias son disjuntas, en cualquier palabra, y el reemplazo simultáneo tiene sentido.

Dos pisos abajo. En $\phi =\forall \mathrm{X}1\exists w\psi$, la ocurrencia de la posición 1 se come el $\forall$ de $\phi$ y el $\exists$ de ${\phi }_1=\exists w\psi$: está a caballo entre dos pisos de la construcción. Las demás ocurrencias no pueden empezar en la $\mathrm{X}1$, ni en el $\exists$, ni en $w$, así que están todas adentro de $\psi$, y

$${\phi }^{\prime }=\exists \mathrm{X}1\forall w{\psi }^{\prime }$$

con ${\psi }^{\prime }$ el resultado de reemplazar cada ocurrencia de $\forall \mathrm{X}1\exists$ en $\psi$. La hipótesis inductiva no se aplica a ${\phi }_1$, que no se reemplaza «por dentro»: su primer símbolo cambia. Se aplica a $\psi$, que está dos niveles abajo de $\phi$. Si $\phi \in F_{k+1}^{\tau }$, la lectura única pone ${\phi }_1$ en $F_k^{\tau }$ y $\psi$ en $F_{k-1}^{\tau }$. Para que ${\mathrm{Enu}}_k$ hable de $\psi$ hacen falta dos decisiones al escribirlo:

• Que hable de toda $\phi \in F_k^{\tau }$, no de las de nivel exactamente $k$. Como $F_{k-1}^{\tau }\subseteq F_k^{\tau }$, $\psi$ está en $F_k^{\tau }$ y ${\mathrm{Enu}}_k$ la cubre. Con «$\phi \in F_k^{\tau }-F_{k-1}^{\tau }$» no la cubriría.
• Que concluya ${\phi }^{\prime }\in F^{\tau }$, sin pedir el nivel. Es verdad que ${\phi }^{\prime }$ tiene el mismo nivel que $\phi$ —lo tiene en el ejemplo de arriba, y medido sobre 2417 fórmulas de ese tipo, armadas con hasta tres capas de $\neg$, $\wedge$ y cuantificadores sobre $\mathrm{X}1$, $\mathrm{X}2$, $\mathrm{X}12$ y $\mathrm{X}21$, ninguna cambia de nivel—, pero un ${\mathrm{Enu}}_k$ que concluya ${\phi }^{\prime }\in F_k^{\tau }$ no cierra el paso: aplicado a $\psi \in F_k^{\tau }$ da ${\psi }^{\prime }\in F_k^{\tau }$, y entonces $\exists x_1\forall w{\psi }^{\prime }$ queda en $F_{k+2}^{\tau }$, no en $F_{k+1}^{\tau }$. Para conservar el nivel haría falta ${\mathrm{Enu}}_{k-1}$, que la Regla de Inducción desde 0 no da en el paso de $k$ a $k+1$. Pedir menos es lo que deja probar.

Abajo se ve cada ocurrencia con la fórmula $\forall x_1\exists w\psi$ que empieza en ella, y su $\psi$ subrayada. Escribí también una fórmula propia y buscá una ocurrencia que no sea el principio de una fórmula así.

Con $\forall \mathrm{X}12$ o con un $\neg$ entre los cuantificadores no hay ocurrencia: la palabra pide los cuatro símbolos pegados. Y con la fórmula de arriba se ve el detalle de la sección 01: después de dar vuelta, ${\phi }^{\prime }$ tiene una ocurrencia que $\phi$ no tenía, y no es el principio de ningún $\forall x_1\exists w\psi$ que estuviera en $\phi$.

04 · El escarabajo: la prueba escrita

Prueba. Primero dos observaciones sobre la palabra $\forall \mathrm{X}1\exists$, cuyos símbolos son $\forall$, $\mathrm{X}$, $1$ y $\exists$.

• (O1) Las ocurrencias de $\forall \mathrm{X}1\exists$ en cualquier palabra son disjuntas entre sí. Si dos se superpusieran sin coincidir, un tramo final propio de $\forall \mathrm{X}1\exists$ sería tramo inicial propio de $\forall \mathrm{X}1\exists$; pero los primeros empiezan con $\mathrm{X}$, $1$ o $\exists$ y los segundos con $\forall$. Por lo tanto el resultado de reemplazar cada ocurrencia de $\forall \mathrm{X}1\exists$ en $\phi$ por $\exists \mathrm{X}1\forall$ está bien definido, como reemplazo simultáneo.
• (O2) Una ocurrencia de $\forall \mathrm{X}1\exists$ no contiene ningún paréntesis, coma, nexo, $\neg$ ni $\equiv$, y empieza con $\forall$.

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

${\mathrm{Enu}}_k$: Si $\phi \in F_k^{\tau }$ y ${\phi }^{\prime }$ es el resultado de reemplazar cada ocurrencia de la palabra $\forall \mathrm{X}1\exists$ en $\phi$ por $\exists \mathrm{X}1\forall$, entonces ${\phi }^{\prime }\in F^{\tau }$.

Prueba de que ${\mathrm{Enu}}_0$ es verdadero. Sea $\phi \in F_0^{\tau }$. Entonces $\phi =(t\equiv s)$ o $\phi =r(t_1,\dots ,t_n)$, con $t,s,t_1,\dots ,t_n\in T^{\tau }$. Los símbolos de un término son símbolos de variables (la $\mathrm{X}$ y numerales), de nombres de constante o de función, paréntesis y comas; los de $\phi$ son ésos, los de $r$ y quizás $\equiv$. Por la definición de tipo, ningún nombre usa el símbolo $\forall$. Luego $\forall$ no ocurre en $\phi$, por (O2) tampoco $\forall \mathrm{X}1\exists$, y ${\phi }^{\prime }=\phi \in F^{\tau }$.

Prueba de que si ${\mathrm{Enu}}_k$ es verdadero entonces ${\mathrm{Enu}}_{k+1}$ lo es. Supongamos que vale ${\mathrm{Enu}}_k$. Sea $\phi \in F_{k+1}^{\tau }$ y sea ${\phi }^{\prime }$ el resultado de reemplazar cada ocurrencia de $\forall \mathrm{X}1\exists$ en $\phi$ por $\exists \mathrm{X}1\forall$. Por definición de $F_{k+1}^{\tau }$ hay cuatro casos.

• Caso $\phi \in F_k^{\tau }$. Ya que vale ${\mathrm{Enu}}_k$, ${\phi }^{\prime }\in F^{\tau }$.
• Caso $\phi =\neg {\phi }_1$, con ${\phi }_1\in F_k^{\tau }$. Por (O2), ninguna ocurrencia de $\forall \mathrm{X}1\exists$ en $\phi$ contiene el $\neg$ de la posición 1, así que cada una sucede dentro de ${\phi }_1$; y cada ocurrencia en ${\phi }_1$ es una ocurrencia en $\phi$. Luego ${\phi }^{\prime }=\neg {\phi }_1^{\prime }$, donde ${\phi }_1^{\prime }$ es el resultado de reemplazar cada ocurrencia de $\forall \mathrm{X}1\exists$ en ${\phi }_1$ por $\exists \mathrm{X}1\forall$. Por ${\mathrm{Enu}}_k$, ${\phi }_1^{\prime }\in F^{\tau }$: digamos ${\phi }_1^{\prime }\in F_m^{\tau }$. Entonces ${\phi }^{\prime }=\neg {\phi }_1^{\prime }\in F_{m+1}^{\tau }\subseteq F^{\tau }$.
• Caso $\phi =({\phi }_1\eta {\phi }_2)$, con $\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}$ y ${\phi }_1,{\phi }_2\in F_k^{\tau }$. Por (O2), ninguna ocurrencia contiene el $($ inicial, el $\eta$ ni el $)$ final, así que cada una sucede dentro de ${\phi }_1$ o dentro de ${\phi }_2$, y recíprocamente las de ${\phi }_1$ y ${\phi }_2$ son ocurrencias en $\phi$. Luego ${\phi }^{\prime }=({\phi }_1^{\prime }\eta {\phi }_2^{\prime })$, con ${\phi }_1^{\prime }$ y ${\phi }_2^{\prime }$ los resultados de reemplazar cada ocurrencia en ${\phi }_1$ y en ${\phi }_2$. Por ${\mathrm{Enu}}_k$, ${\phi }_1^{\prime }\in F_{m_1}^{\tau }$ y ${\phi }_2^{\prime }\in F_{m_2}^{\tau }$ para ciertos $m_1,m_2$. Con $M=\max (m_1,m_2)$, como los niveles crecen, ${\phi }_1^{\prime },{\phi }_2^{\prime }\in F_M^{\tau }$, y entonces ${\phi }^{\prime }\in F_{M+1}^{\tau }\subseteq F^{\tau }$.
• Caso $\phi =Qv{\phi }_1$, con $Q\in \{\forall ,\exists \}$, $v\in \mathrm{Var}$ y ${\phi }_1\in F_k^{\tau }$. En las posiciones $2,\dots ,|Qv|$ están los símbolos de $v$, que son $\mathrm{X}$ o numerales: por (O2) ninguna ocurrencia empieza ahí. Las que empiezan después de $|Qv|$ suceden dentro de ${\phi }_1$, que es el tramo final de $\phi$ que sigue a $Qv$, y son exactamente las ocurrencias de $\forall \mathrm{X}1\exists$ en ${\phi }_1$. Hay dos subcasos.
  • Ninguna ocurrencia empieza en la posición 1. Entonces ${\phi }^{\prime }=Qv{\phi }_1^{\prime }$, con ${\phi }_1^{\prime }$ el resultado de reemplazar cada ocurrencia en ${\phi }_1$. Por ${\mathrm{Enu}}_k$, ${\phi }_1^{\prime }\in F_m^{\tau }$ para algún $m$, y ${\phi }^{\prime }\in F_{m+1}^{\tau }\subseteq F^{\tau }$.
  • Una ocurrencia empieza en la posición 1. Entonces $[\phi {]}_1=\forall$, así que $Q=\forall$. La variable $v$ empieza en la posición 2 y termina en su único numeral negrita; como $[\phi {]}_3=1$ es negrita, $v=\mathrm{X}1=x_1$ y $|Qv|=3$. Luego ${\phi }_1$ empieza en la posición 4 y $[{\phi }_1{]}_1=[\phi {]}_4=\exists$. Por el Teorema 7 de la Guía 9 (lectura única), como ${\phi }_1$ empieza con $\exists$, no es de la forma $(t\equiv s)$ ni $({\phi }_2\eta {\phi }_3)$, que empiezan con $($, ni $r(t_1,\dots ,t_n)$, porque ningún nombre de relación usa $\exists$, ni $\neg {\phi }_2$; así que ${\phi }_1=\exists w\psi$ con $w\in \mathrm{Var}$ y $\psi \in F^{\tau }$. Además ${\phi }_1$ no es atómica, por lo que $k\ge 1$, y como ${\phi }_1\in F_{(k-1)+1}^{\tau }$, el mismo teorema da $\psi \in F_{k-1}^{\tau }\subseteq F_k^{\tau }$.
    Así $\phi =\forall \mathrm{X}1\exists w\psi$. Las otras ocurrencias no empiezan en las posiciones 2, 3 o 4, que tienen $\mathrm{X}$, $1$ y $\exists$, ni en las de $w$, que tienen $\mathrm{X}$ o numerales; empiezan en $\psi$ y, como $\psi$ es el tramo final de $\phi$, suceden dentro de $\psi$. Son exactamente las ocurrencias de $\forall \mathrm{X}1\exists$ en $\psi$. Por (O1) la de la posición 1 no comparte símbolos con ellas, y entonces $${\phi }^{\prime }=\exists \mathrm{X}1\forall w{\psi }^{\prime }$$ con ${\psi }^{\prime }$ el resultado de reemplazar cada ocurrencia de $\forall \mathrm{X}1\exists$ en $\psi$ por $\exists \mathrm{X}1\forall$. Como $\psi \in F_k^{\tau }$, por ${\mathrm{Enu}}_k$ se tiene ${\psi }^{\prime }\in F^{\tau }$: digamos ${\psi }^{\prime }\in F_m^{\tau }$. Entonces $\forall w{\psi }^{\prime }\in F_{m+1}^{\tau }$ y ${\phi }^{\prime }=\exists x_1\forall w{\psi }^{\prime }\in F_{m+2}^{\tau }\subseteq F^{\tau }$.

Por la Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ vale para todo $k\in \omega$. Si $\phi \in F^{\tau }$, entonces $\phi \in F_k^{\tau }$ para algún $k$, y por ${\mathrm{Enu}}_k$, ${\phi }^{\prime }\in F^{\tau }$. ∎

05 · Lo que se lleva a otros ejercicios

Mirar de qué símbolos está hecha la palabra decide dónde puede caer. Si la palabra que se reemplaza no tiene paréntesis, nexos, comas ni $\neg$, sus ocurrencias viven adentro de las piezas, y el paso de la inducción es mecánico salvo en el caso que construye con los símbolos que la palabra sí tiene. Es el mismo razonamiento de la coma delata un argumento (Ejercicio 3), donde la palabra $,\mathrm{X}1$ tiene una coma y por eso puede caer justo en la costura de dos argumentos; y del Ejercicio 1, donde lo que se reemplaza es un término entero.

Cuando una ocurrencia cruza dos pisos, la hipótesis inductiva se aplica más abajo. Para que se pueda, ${\mathrm{Enu}}_k$ habla de todo $F_k^{\tau }$ —que contiene a los niveles anteriores— y concluye sólo que el resultado es fórmula. El molde general del reemplazo en fórmulas es el Lema 8(g) de la Guía 9, cuya prueba deja «los otros casos» al lector; los casos $\neg$ y $Qv$ de ese lema se escriben como los de esta prueba. Con términos adentro de fórmulas, la versión que pide cuidar la variable que sigue al cuantificador es el Ejercicio 13.

Lo que hace perder puntos. Escribir ${\mathrm{Enu}}_k$ sin nombrar la Regla de Inducción desde 0, o con ${\phi }^{\prime }\in F_k^{\tau }$ como conclusión. Aplicar la hipótesis a ${\phi }_1$ en el caso $\forall x_1\exists w\psi$, como si la ocurrencia estuviera adentro de ${\phi }_1$. Decir que $v=x_1$ sin decir por qué: es el negrita el que cierra la variable, y por eso $\forall \mathrm{X}12\exists$ no es una ocurrencia. Olvidar el caso atómico o despacharlo sin la definición de tipo, que es lo que impide un $\forall$ adentro de un nombre. Olvidar que las ocurrencias son disjuntas, sin lo cual «cada ocurrencia» no tiene sentido. Y olvidar el caso $\phi \in F_k^{\tau }$ del paso.

Para tener a mano

1. $\forall \mathrm{X}1\exists$ no tiene paréntesis, nexos, comas, $\neg$ ni $\equiv$: en $\neg {\phi }_1$ y en $({\phi }_1\eta {\phi }_2)$ cae adentro de una pieza, y en una atómica no hay $\forall$.
2. En $Qv{\phi }_1$ sólo puede empezar en la posición 1, y entonces $Q=\forall$, $v=x_1$ (el negrita cierra) y ${\phi }_1=\exists w\psi$ por lectura única.
3. Dos ocurrencias no se pisan: ningún tramo final propio de la palabra es tramo inicial de ella.
4. ${\mathrm{Enu}}_k$: si $\phi \in F_k^{\tau }$ y ${\phi }^{\prime }$ es el resultado de reemplazar cada ocurrencia, entonces ${\phi }^{\prime }\in F^{\tau }$. Habla de todo $F_k^{\tau }$ y no pide el nivel, porque en el caso $\forall x_1\exists w\psi$ se aplica a $\psi \in F_{k-1}^{\tau }\subseteq F_k^{\tau }$ y da ${\phi }^{\prime }=\exists x_1\forall w{\psi }^{\prime }$.
5. El resultado puede tener ocurrencias nuevas; el reemplazo es simultáneo sobre las de $\phi$ y no se itera.