Dos ∀ seguidos conmutan

El enunciado, textual: «Sea $\tau$ un tipo. Para $\phi \in F^{\tau }$ definimos ${\phi }^{\prime }$ = resultado de reemplazar en $\phi$ toda ocurrencia de $\forall x_1\forall x_2\exists$ por $\forall x_2\forall x_1\exists$. Acepte sin demostración que ${\phi }^{\prime }\in F^{\tau }$. Pruebe que ${\phi }^{\prime }\sim \phi$.» Es el Ejercicio 13(d) de la Guía 10 (p. 9).

01 · Qué pide, en criollo

«Para todo $x_1$, para todo $x_2$» y «para todo $x_2$, para todo $x_1$» dicen lo mismo: en los dos casos se recorren todos los pares. El ejercicio pide probarlo en el modelo de la Guía 10, para cada lugar de una fórmula donde aparece $\forall x_1\forall x_2$ seguido de un $\exists$.

Con un tipo que tiene una relación unaria $\mathrm{P}$ y una binaria $\mathrm{R}$, la fórmula

$$\phi =\forall \mathrm{X}1\forall \mathrm{X}2\exists \mathrm{X}3(\mathrm{R}(\mathrm{X}1,\mathrm{X}3)\wedge \mathrm{R}(\mathrm{X}3,\mathrm{X}2))$$

dice que de cualquier elemento se llega a cualquier otro en dos pasos de $\mathrm{R}$. Su reemplazo es ${\phi }^{\prime }=\forall \mathrm{X}2\forall \mathrm{X}1\exists \mathrm{X}3(\mathrm{R}(\mathrm{X}1,\mathrm{X}3)\wedge \mathrm{R}(\mathrm{X}3,\mathrm{X}2))$, y evaluadas con la definición de $\models$ en las 4164 estructuras de hasta tres elementos, con todas las asignaciones de $\mathrm{X}1,\mathrm{X}2,\mathrm{X}3$, no difieren en ningún caso. Tampoco cuando el patrón está más adentro, como en $(\mathrm{P}(\mathrm{X}1)\to \forall \mathrm{X}1\forall \mathrm{X}2\exists \mathrm{X}2(\mathrm{R}(\mathrm{X}1,\mathrm{X}2)\wedge \mathrm{P}(\mathrm{X}2)))$, donde además el $\exists$ vuelve a cuantificar $\mathrm{X}2$.

Lo que no vale. Dar vuelta un $\forall$ y un $\exists$: $\forall \mathrm{X}1\exists \mathrm{X}2\mathrm{R}(\mathrm{X}1,\mathrm{X}2)$ dice que cada elemento tiene un sucesor por $\mathrm{R}$, y $\exists \mathrm{X}2\forall \mathrm{X}1\mathrm{R}(\mathrm{X}1,\mathrm{X}2)$, que hay uno que es sucesor de todos. En $\{0,1\}$ con $i(\mathrm{R})=\{(0,0),(1,1)\}$ la primera es verdadera y la segunda falsa. La razón está en la prueba: lo que conmuta son los dos cambios de la asignación, y eso le sirve a dos «para todo» o a dos «hay», no a uno de cada uno.

02 · Las herramientas

Se pueden usar sin enunciar los lemas Menú y la lectura única. Las cláusulas de la relación ⊨ que se usan (Guía 10, p. 4): (3) a (6) para los nexos, (7) para $\neg$, (8) $𝐀\models \forall x_i\phi [\overrightarrow{a}]$ sii para cada $a\in A$, $𝐀\models \phi [{\downarrow }_i^a(\overrightarrow{a})]$, y (9) $𝐀\models \exists x_i\phi [\overrightarrow{a}]$ sii hay un $a\in A$ con $𝐀\models \phi [{\downarrow }_i^a(\overrightarrow{a})]$, donde ${\downarrow }_i^a(\overrightarrow{a})$ es $\overrightarrow{a}$ con el $i$-ésimo elemento cambiado por $a$. Equivalencia (p. 8): $\phi \sim \psi$ cuando $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models \psi [\overrightarrow{a}]$, para cada modelo $𝐀$ de tipo $\tau$ y cada $\overrightarrow{a}\in A^{𝐍}$.

Lema 4(b) de la Guía 10 (p. 8). Si ${\phi }_i\sim {\psi }_i$, $i=1,2$, entonces $\neg {\phi }_1\sim \neg {\psi }_1$, $({\phi }_1\eta {\phi }_2)\sim ({\psi }_1\eta {\psi }_2)$ y $Qv{\phi }_1\sim Qv{\psi }_1$. La guía lo deja al lector, así que se prueba.

Prueba. Sean $𝐀$ un modelo de tipo $\tau$ y $\overrightarrow{a}\in A^{𝐍}$. Por (7), $𝐀\models \neg {\phi }_1[\overrightarrow{a}]$ sii $𝐀⊭{\phi }_1[\overrightarrow{a}]$ sii $𝐀⊭{\psi }_1[\overrightarrow{a}]$ sii $𝐀\models \neg {\psi }_1[\overrightarrow{a}]$. Por (3), $𝐀\models ({\phi }_1\wedge {\phi }_2)[\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ y $𝐀\models {\phi }_2[\overrightarrow{a}]$, sii $𝐀\models {\psi }_1[\overrightarrow{a}]$ y $𝐀\models {\psi }_2[\overrightarrow{a}]$, sii $𝐀\models ({\psi }_1\wedge {\psi }_2)[\overrightarrow{a}]$; con $\vee$, $\to$ y $\leftrightarrow$ es lo mismo con las cláusulas (4), (5) y (6), cuyo lado derecho también depende sólo de si $𝐀\models {\phi }_1[\overrightarrow{a}]$ y de si $𝐀\models {\phi }_2[\overrightarrow{a}]$. Para $v=x_i$, por (8), $𝐀\models \forall x_i{\phi }_1[\overrightarrow{a}]$ sii para cada $a\in A$, $𝐀\models {\phi }_1[{\downarrow }_i^a(\overrightarrow{a})]$, sii, por ${\phi }_1\sim {\psi }_1$ aplicada en la asignación ${\downarrow }_i^a(\overrightarrow{a})$, para cada $a\in A$, $𝐀\models {\psi }_1[{\downarrow }_i^a(\overrightarrow{a})]$, sii $𝐀\models \forall x_i{\psi }_1[\overrightarrow{a}]$; y con $\exists$, lo mismo con (9) y «hay un $a$». ∎

Los dos cambios conmutan. Para $a,b\in A$ y $\overrightarrow{a}\in A^{𝐍}$,

$${\downarrow }_1^a({\downarrow }_2^b(\overrightarrow{a}))={\downarrow }_2^b({\downarrow }_1^a(\overrightarrow{a}))=(a,b,a_3,a_4,\dots )$$

En la de la izquierda, primero el lugar 2 pasa a ser $b$ y después el lugar 1 pasa a ser $a$, sin tocar el 2; en la de la derecha, al revés, y el segundo cambio tampoco toca el lugar que cambió el primero. Las dos tienen $a$ en el lugar 1, $b$ en el 2 y $a_n$ en cada $n\ge 3$. Con el mismo lugar no pasa: ${\downarrow }_1^a({\downarrow }_1^b(\overrightarrow{a}))$ tiene $a$ en el lugar 1, y ${\downarrow }_1^b({\downarrow }_1^a(\overrightarrow{a}))$ tiene $b$.

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

La inducción. En el nivel de $\phi$, con ${\mathrm{Enu}}_k$: para toda $\phi \in F_k^{\tau }$, ${\phi }^{\prime }\sim \phi$. No sale del Lema 5, porque $\forall x_1\forall x_2\exists$ no es una fórmula: le falta la variable del $\exists$ y todo lo que sigue. Como en el Ejercicio 14, en los casos que no empiezan con la palabra el reemplazo pasa de largo y el Lema 4(b) sube la equivalencia. El caso que trabaja es el que empieza con ella.

Qué forma tiene una fórmula que empieza con $\forall \mathrm{X}1\forall \mathrm{X}2\exists$. Por lectura única es $\forall v{\phi }_1$, y $v$ empieza con $X$ seguida de un $1$ negrita; como en una variable el único negrita es el último, $v=\mathrm{X}1$. Lo mismo con ${\phi }_1$, que empieza con $\forall \mathrm{X}2\exists$: ${\phi }_1=\forall \mathrm{X}2{\phi }_2$, y ${\phi }_2$ empieza con $\exists$, así que ${\phi }_2=\exists w\psi$. La palabra $\forall \mathrm{X}1\forall \mathrm{X}2\exists$ sólo ocurre como comienzo de una fórmula $\forall x_1\forall x_2\exists w\psi$, y el reemplazo de esa ocurrencia la convierte en $\forall x_2\forall x_1\exists w\psi$, con $\psi$ reemplazada por dentro.

Por qué el caso cierra. Llamando $\chi =\exists w\psi$, $𝐀\models \forall x_1\forall x_2\chi [\overrightarrow{a}]$ sii para todos $a,b\in A$, $𝐀\models \chi [{\downarrow }_2^b({\downarrow }_1^a(\overrightarrow{a}))]$, y del otro lado aparece ${\downarrow }_1^a({\downarrow }_2^b(\overrightarrow{a}))$. Son la misma asignación, y «para todo $a$, para todo $b$» es lo mismo que «para todo $b$, para todo $a$». La hipótesis inductiva entra antes: cambia ${\psi }^{\prime }$ por $\psi$, y con el Lema 4(b), $\exists w{\psi }^{\prime }$ por $\exists w\psi$.

Abajo se puede elegir también otra regla de reemplazo, para ver cuál vale. La comparación recorre todas las estructuras de hasta dos elementos con todas las asignaciones de $\mathrm{X}1,\mathrm{X}2,\mathrm{X}3$.

En $\forall \mathrm{X}1\exists \mathrm{X}2(\mathrm{P}(\mathrm{X}1)\vee \mathrm{P}(\mathrm{X}2))$ dar vuelta el $\forall$ y el $\exists$ no cambia nada: las dos fórmulas dicen que algún elemento está en $\mathrm{P}$. En $\forall \mathrm{X}1\exists \mathrm{X}2\mathrm{R}(\mathrm{X}1,\mathrm{X}2)$ difieren en 64 de los 516 casos. La regla del ejercicio, y la de dos $\exists$, no dan ningún caso en ninguna fórmula.

04 · El escarabajo

Primero, cómo se calcula ${\phi }^{\prime }$. Sea $p$ la palabra $\forall x_1\forall x_2\exists$, cuyos símbolos son $\forall$, $X$, $1$, $2$ y $\exists$. Para ${\phi }_1,{\phi }_2,\psi \in F^{\tau }$ y $v,w\in \mathrm{Var}$:

• (i) Si $\phi$ es atómica, ${\phi }^{\prime }=\phi$: una atómica no contiene el símbolo $\forall$, porque los términos y los nombres del tipo no lo usan.
• (ii) $({\phi }_1\eta {\phi }_2{)}^{\prime }=({\phi }_1^{\prime }\eta {\phi }_2^{\prime })$. Una ocurrencia de $p$ empieza en un $\forall$, así que no en el primer símbolo de $({\phi }_1\eta {\phi }_2)$, ni en $\eta$, ni en el último. Si empieza en ${\phi }_1$ y no terminara dentro de ${\phi }_1$, contendría el $\eta$ que sigue a ${\phi }_1$, que no es un símbolo de $p$; si empieza en ${\phi }_2$, lo mismo con el $)$ final. Luego cada ocurrencia sucede en ${\phi }_1$ o en ${\phi }_2$, y toda ocurrencia en ellas lo es en $({\phi }_1\eta {\phi }_2)$.
• (iii) $(\neg {\phi }_1{)}^{\prime }=\neg {\phi }_1^{\prime }$: la posición 1 tiene $\neg$ y ${\phi }_1$ llega hasta el final.
• (iv) Si $Qv{\phi }_1$ no empieza con $p$, $(Qv{\phi }_1{)}^{\prime }=Qv{\phi }_1^{\prime }$: no hay ocurrencia a partir de 1, las posiciones de $v$ tienen la $X$ o numerales y no $\forall$, y las demás están en ${\phi }_1$, que llega hasta el final.
• (v) Si $\phi$ empieza con $p$, entonces $\phi =\forall x_1\forall x_2\exists w\psi$ y ${\phi }^{\prime }=\forall x_2\forall x_1\exists w{\psi }^{\prime }$. Por lectura única $\phi =\forall v{\phi }_1$, y $v$ empieza con $X1$; como el único numeral negrita de una variable es el último, $v=x_1$. Igual, ${\phi }_1$ empieza con $\forall X2$, así que ${\phi }_1=\forall x_2{\phi }_2$, y ${\phi }_2$ empieza con $\exists$, así que ${\phi }_2=\exists w\psi$. Las ocurrencias de $p$ en $\phi$: una a partir de 1; ninguna a partir de las posiciones 2, 3, 5, 6, 7 ni de las de $w$, que no tienen $\forall$; ninguna a partir de la 4, porque ahí se lee $\forall X2$ y no $\forall X1$; las demás están en $\psi$. Reemplazar la primera da $\forall x_2\forall x_1\exists$ seguido de $w\psi$, y las de $\psi$ dan ${\psi }^{\prime }$.

Prueba de que ${\phi }^{\prime }\sim \phi$. 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 }$, se tiene que ${\phi }^{\prime }\sim \phi$.

Prueba de que ${\mathrm{Enu}}_0$ es verdadero. Si $\phi \in F_0^{\tau }$, $\phi$ es atómica, por (i) ${\phi }^{\prime }=\phi$, y $\phi \sim \phi$.

Prueba de que si ${\mathrm{Enu}}_k$ es verdadero entonces ${\mathrm{Enu}}_{k+1}$ lo es. Supongamos que vale ${\mathrm{Enu}}_k$ y sea $\phi \in F_{k+1}^{\tau }$. Por definición de $F_{k+1}^{\tau }$ hay varios casos.

• Caso $\phi \in F_k^{\tau }$. Por ${\mathrm{Enu}}_k$, ${\phi }^{\prime }\sim \phi$.
• Caso $\phi =({\phi }_1\eta {\phi }_2)$, con ${\phi }_1,{\phi }_2\in F_k^{\tau }$. Por (ii), ${\phi }^{\prime }=({\phi }_1^{\prime }\eta {\phi }_2^{\prime })$; por ${\mathrm{Enu}}_k$, ${\phi }_1^{\prime }\sim {\phi }_1$ y ${\phi }_2^{\prime }\sim {\phi }_2$, y por el Lema 4(b), ${\phi }^{\prime }\sim \phi$.
• Caso $\phi =\neg {\phi }_1$, con ${\phi }_1\in F_k^{\tau }$. Por (iii), ${\phi }^{\prime }=\neg {\phi }_1^{\prime }$; por ${\mathrm{Enu}}_k$ y el Lema 4(b), ${\phi }^{\prime }\sim \phi$.
• Caso $\phi =Qv{\phi }_1$, con ${\phi }_1\in F_k^{\tau }$, que no empieza con $p$. Por (iv), ${\phi }^{\prime }=Qv{\phi }_1^{\prime }$; por ${\mathrm{Enu}}_k$ y el Lema 4(b), ${\phi }^{\prime }\sim \phi$.
• Caso $\phi =Qv{\phi }_1$, con ${\phi }_1\in F_k^{\tau }$, que empieza con $p$. Por (v), $\phi =\forall x_1\forall x_2\exists w\psi$ y ${\phi }^{\prime }=\forall x_2\forall x_1\exists w{\psi }^{\prime }$. Por lectura única, $\forall x_2\exists w\psi ={\phi }_1\in F_k^{\tau }$; no es atómica, así que $k\ge 1$ y $\exists w\psi \in F_{k-1}^{\tau }\subseteq F_k^{\tau }$, y del mismo modo $\psi \in F_k^{\tau }$. Por ${\mathrm{Enu}}_k$, ${\psi }^{\prime }\sim \psi$, y por el Lema 4(b), $\exists w{\psi }^{\prime }\sim \exists w\psi$. Llamemos $\chi =\exists w\psi$ y ${\chi }^{\prime }=\exists w{\psi }^{\prime }$. Sean $𝐀$ un modelo de tipo $\tau$ y $\overrightarrow{a}\in A^{𝐍}$. Entonces
  • $𝐀\models \forall x_2\forall x_1{\chi }^{\prime }[\overrightarrow{a}]$ sii, por (8) dos veces, para cada $b\in A$ y cada $a\in A$, $𝐀\models {\chi }^{\prime }[{\downarrow }_1^a({\downarrow }_2^b(\overrightarrow{a}))]$,
  • sii, por ${\chi }^{\prime }\sim \chi$ aplicada en esa asignación, para cada $b\in A$ y cada $a\in A$, $𝐀\models \chi [{\downarrow }_1^a({\downarrow }_2^b(\overrightarrow{a}))]$,
  • sii, porque ${\downarrow }_1^a({\downarrow }_2^b(\overrightarrow{a}))={\downarrow }_2^b({\downarrow }_1^a(\overrightarrow{a}))$, para cada $a\in A$ y cada $b\in A$, $𝐀\models \chi [{\downarrow }_2^b({\downarrow }_1^a(\overrightarrow{a}))]$,
  • sii, por (8) dos veces, $𝐀\models \forall x_1\forall x_2\chi [\overrightarrow{a}]$.
  Como $𝐀$ y $\overrightarrow{a}$ eran cualesquiera, ${\phi }^{\prime }\sim \phi$.

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 }$, ${\phi }^{\prime }\sim \phi$ para toda $\phi \in F^{\tau }$. ∎

El paso «por (8) dos veces», escrito: $𝐀\models \forall x_1\forall x_2\chi [\overrightarrow{a}]$ sii para cada $a\in A$, $𝐀\models \forall x_2\chi [{\downarrow }_1^a(\overrightarrow{a})]$, sii para cada $a\in A$ y cada $b\in A$, $𝐀\models \chi [{\downarrow }_2^b({\downarrow }_1^a(\overrightarrow{a}))]$. La primera aplicación de (8) es con la asignación $\overrightarrow{a}$; la segunda, con ${\downarrow }_1^a(\overrightarrow{a})$.

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

Lo que hace perder puntos. Citar el Lema 5: $\forall x_1\forall x_2\exists$ no es una fórmula. Afirmar que la palabra sólo ocurre al principio de $\forall x_1\forall x_2\exists w\psi$ sin el argumento del negrita, ni el de la posición 4. Escribir la igualdad de las dos asignaciones sin decir por qué: es porque los lugares 1 y 2 son distintos, y con el mismo lugar es falsa. Olvidar que la hipótesis inductiva se aplica a $\psi$, dos pisos abajo, y que hay que justificar que $\psi \in F_k^{\tau }$. Usar el Lema 4(b) sin probarlo.

Lo que se lleva. La estructura es la del Ejercicio 14, con otra palabra y otra cuenta en el caso que trabaja. Que $\forall X1\exists$ sólo ocurra como comienzo de $\forall x_1\exists w\psi$, con la hipótesis aplicada dos pisos abajo, es el Ejercicio 4. Y la cuenta con asignaciones cambiadas es la del caso cuantificador del Ejercicio 12.

Para tener a mano

1. No sale del Lema 5. Inducción en el nivel, ${\mathrm{Enu}}_k$: para toda $\phi \in F_k^{\tau }$, ${\phi }^{\prime }\sim \phi$; los casos que no empiezan con la palabra, con el Lema 4(b).
2. La palabra $\forall x_1\forall x_2\exists$ sólo ocurre como comienzo de $\forall x_1\forall x_2\exists w\psi$: el negrita cierra cada variable, y en la posición 4 se lee $\forall X2$.
3. ${\phi }^{\prime }=\forall x_2\forall x_1\exists w{\psi }^{\prime }$, con $\psi \in F_k^{\tau }$; hipótesis inductiva en $\psi$ y Lema 4(b) para $\exists w{\psi }^{\prime }\sim \exists w\psi$.
4. ${\downarrow }_1^a({\downarrow }_2^b(\overrightarrow{a}))={\downarrow }_2^b({\downarrow }_1^a(\overrightarrow{a}))$ porque tocan lugares distintos.
5. Un $\forall$ y un $\exists$ no se dan vuelta: $\forall \mathrm{X}1\exists \mathrm{X}2\mathrm{R}(\mathrm{X}1,\mathrm{X}2)$ es verdadera y $\exists \mathrm{X}2\forall \mathrm{X}1\mathrm{R}(\mathrm{X}1,\mathrm{X}2)$ falsa en $\{0,1\}$ con $i(\mathrm{R})=\{(0,0),(1,1)\}$.