∀ es ¬∃¬

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$ por $\neg \exists x_1\neg$. Acepte sin demostración que ${\phi }^{\prime }\in F^{\tau }$. Pruebe que ${\phi }^{\prime }\sim \phi$.» Es el Ejercicio 13(b) de la Guía 10 (p. 9).

01 · Qué pide, en criollo

«Para todo $x_1$» dice lo mismo que «no existe un $x_1$ para el que no». El ejercicio pide probar que, si en una fórmula se escribe cada $\forall x_1$ de la segunda manera, la fórmula que queda es equivalente a la original: dice lo mismo en toda estructura y para toda asignación.

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

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

tiene 25 símbolos, y la palabra $\forall \mathrm{X}1$, de tres símbolos, ocurre en ella a partir de 1 y de 14. Reemplazando las dos queda

$${\phi }^{\prime }=\neg \exists \mathrm{X}1\neg (\mathrm{P}(\mathrm{X}1)\to \exists \mathrm{X}2\neg \exists \mathrm{X}1\neg \mathrm{R}(\mathrm{X}1,\mathrm{X}2))$$

y $\phi$ y ${\phi }^{\prime }$, evaluadas con la definición de $\models$ en las 4164 estructuras de hasta tres elementos para ese tipo, con todas las asignaciones de $\mathrm{X}1,\mathrm{X}2,\mathrm{X}3$, no difieren en ningún caso. Con $\neg \exists \mathrm{X}1$ o con $\exists \mathrm{X}1\neg$ en lugar de $\neg \exists \mathrm{X}1\neg$ difieren en miles: los dos $\neg$ hacen falta.

Un detalle de palabras: en $\forall \mathrm{X}12(\mathrm{P}(\mathrm{X}12)\to \forall \mathrm{X}1\mathrm{R}(\mathrm{X}1,\mathrm{X}12))$ la palabra $\forall \mathrm{X}1$ ocurre una sola vez, a partir de 13. En $\forall \mathrm{X}12$ el $1$ es itálico, y $\forall \mathrm{X}1$ termina en un $1$ negrita.

Por qué no sale del Ejercicio 9. El Lema 5 reemplaza una fórmula por otra equivalente. Acá lo que se reemplaza es la palabra $\forall x_1$, que no es una fórmula, y su reemplazo $\neg \exists x_1\neg$ tampoco. Hace falta una inducción propia, y dentro de ella, saber exactamente dónde puede aparecer la palabra $\forall \mathrm{X}1$.

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) $𝐀\models \neg \phi [\overrightarrow{a}]$ sii $𝐀⊭\phi [\overrightarrow{a}]$, (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})]$. 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$». ∎

03 · La mariposa: dónde puede estar ∀X𝟏

La inducción. En el nivel de $\phi$, con ${\mathrm{Enu}}_k$: para toda $\phi \in F_k^{\tau }$, ${\phi }^{\prime }\sim \phi$. En la base y en los casos que no empiezan con $\forall \mathrm{X}1$, el reemplazo pasa de largo por el símbolo de afuera y se hace adentro: $({\phi }_1\eta {\phi }_2{)}^{\prime }=({\phi }_1^{\prime }\eta {\phi }_2^{\prime })$, $(\neg {\phi }_1{)}^{\prime }=\neg {\phi }_1^{\prime }$, $(Qv{\phi }_1{)}^{\prime }=Qv{\phi }_1^{\prime }$, y el Lema 4(b) sube la equivalencia. El único caso que trabaja es $\phi =\forall x_1{\phi }_1$, donde

$$(\forall x_1{\phi }_1{)}^{\prime }=\neg \exists x_1\neg {\phi }_1^{\prime }$$

y ahí se usan la hipótesis inductiva ${\phi }_1^{\prime }\sim {\phi }_1$ y las cláusulas (7), (8) y (9).

Lo que hay que justificar. Esas cuatro igualdades entre palabras no son gratis: dicen que cada ocurrencia de $\forall \mathrm{X}1$ está entera dentro de una subfórmula, o es la del principio. Dos cosas lo garantizan. Primero, los símbolos de $\forall \mathrm{X}1$ son $\forall$, la $X$ y el $1$ negrita, y ni un nexo ni $)$ son de esos, así que una ocurrencia no puede pasarse de ${\phi }_1$ a lo que le sigue en $({\phi }_1\eta {\phi }_2)$. Segundo, la palabra $\forall \mathrm{X}1$ sólo puede empezar en un cuantificador, porque es el único lugar donde hay un $\forall$; y si una fórmula $Qv{\phi }_1$ empieza con $\forall \mathrm{X}1$, entonces $Q=\forall$ y $v$ empieza con $X$ seguida de un numeral negrita, y como en una variable el único negrita es el último, $v=\mathrm{X}1$.

Por qué el caso ∀x1 cierra. «No existe $a$ con $𝐀\models \neg {\phi }_1^{\prime }[{\downarrow }_1^a(\overrightarrow{a})]$» es «para todo $a$, $𝐀\models {\phi }_1^{\prime }[{\downarrow }_1^a(\overrightarrow{a})]$». La hipótesis inductiva cambia ${\phi }_1^{\prime }$ por ${\phi }_1$ en cada una de esas asignaciones, y eso sólo se puede porque ${\phi }_1^{\prime }\sim {\phi }_1$ vale para toda asignación, no sólo para $\overrightarrow{a}$.

Abajo se hace el reemplazo sobre varias fórmulas y se comparan $\phi$ y ${\phi }^{\prime }$ en todas las estructuras de hasta dos elementos, con todas las asignaciones de $\mathrm{X}1,\mathrm{X}2,\mathrm{X}3$. Se puede elegir también un reemplazo equivocado.

En $\neg \forall \mathrm{X}1\neg \forall \mathrm{X}1\mathrm{P}(\mathrm{X}1)$ el reemplazo equivocado da $\neg \exists \mathrm{X}1\neg \neg \exists \mathrm{X}1\neg \mathrm{P}(\mathrm{X}1)$, y los dos $\neg$ que faltan se cancelan entre sí: sale equivalente por casualidad. En $\forall \mathrm{X}1\exists \mathrm{X}2\mathrm{R}(\mathrm{X}1,\mathrm{X}2)$ el mismo reemplazo da la fórmula que dice lo contrario, y difiere en los 516 casos. Con $\neg \exists \mathrm{X}1\neg$ no aparece ningún caso en ninguna de las cinco.

04 · El escarabajo

Primero, cómo se calcula ${\phi }^{\prime }$. Para ${\phi }_1,{\phi }_2\in F^{\tau }$ y $v\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, así que $\forall x_1$ no ocurre en ella.
• (ii) $({\phi }_1\eta {\phi }_2{)}^{\prime }=({\phi }_1^{\prime }\eta {\phi }_2^{\prime })$. Una ocurrencia de $\forall x_1$ en $({\phi }_1\eta {\phi }_2)$ empieza en un $\forall$, así que no empieza en el primer símbolo, ni en $\eta$, ni en el último. Si empieza en una posición de ${\phi }_1$ y no terminara dentro de ${\phi }_1$, contendría el símbolo que sigue a ${\phi }_1$, que es $\eta$; pero los símbolos de $\forall x_1$ son $\forall$, $X$ y $1$. Luego sucede en ${\phi }_1$. Igual si empieza en ${\phi }_2$, con el $)$ final. Y toda ocurrencia en ${\phi }_1$ o en ${\phi }_2$ es una ocurrencia en $({\phi }_1\eta {\phi }_2)$. Así que reemplazarlas todas en $({\phi }_1\eta {\phi }_2)$ es reemplazarlas todas en ${\phi }_1$ y todas en ${\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\ne \forall x_1$, $(Qv{\phi }_1{)}^{\prime }=Qv{\phi }_1^{\prime }$. Una ocurrencia a partir de 1 pediría $Q=\forall$ y que $v$ empiece con $X1$; en una variable el único numeral negrita es el último, así que sería $v=x_1$. Las posiciones de $v$ tienen la $X$ o numerales, no $\forall$. Luego toda ocurrencia está en ${\phi }_1$, que llega hasta el final.
• (v) $(\forall x_1{\phi }_1{)}^{\prime }=\neg \exists x_1\neg {\phi }_1^{\prime }$. Hay una ocurrencia a partir de 1; las posiciones 2 y 3 tienen $X$ y $1$, no $\forall$; las demás están en ${\phi }_1$. Reemplazar la primera da $\neg \exists x_1\neg$ seguido de ${\phi }_1$, y las de ${\phi }_1$ dan ${\phi }_1^{\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 y 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 }_1^{\prime }\eta {\phi }_2^{\prime })\sim ({\phi }_1\eta {\phi }_2)$.
• 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), $\neg {\phi }_1^{\prime }\sim \neg {\phi }_1$.
• Caso $\phi =Qv{\phi }_1$, con ${\phi }_1\in F_k^{\tau }$ y $Qv\ne \forall x_1$ (o sea, $Q=\exists$, o $Q=\forall$ y $v\ne x_1$). Por (iv), ${\phi }^{\prime }=Qv{\phi }_1^{\prime }$; por ${\mathrm{Enu}}_k$ y el Lema 4(b), $Qv{\phi }_1^{\prime }\sim Qv{\phi }_1$.
• Caso $\phi =\forall x_1{\phi }_1$, con ${\phi }_1\in F_k^{\tau }$. Por (v), ${\phi }^{\prime }=\neg \exists x_1\neg {\phi }_1^{\prime }$. Sean $𝐀$ un modelo de tipo $\tau$ y $\overrightarrow{a}\in A^{𝐍}$. Entonces
  • $𝐀\models \neg \exists x_1\neg {\phi }_1^{\prime }[\overrightarrow{a}]$ sii, por (7), $𝐀⊭\exists x_1\neg {\phi }_1^{\prime }[\overrightarrow{a}]$,
  • sii, por (9), no hay $a\in A$ tal que $𝐀\models \neg {\phi }_1^{\prime }[{\downarrow }_1^a(\overrightarrow{a})]$,
  • sii para cada $a\in A$, $𝐀⊭\neg {\phi }_1^{\prime }[{\downarrow }_1^a(\overrightarrow{a})]$, es decir, por (7), $𝐀\models {\phi }_1^{\prime }[{\downarrow }_1^a(\overrightarrow{a})]$,
  • sii, por ${\mathrm{Enu}}_k$ (${\phi }_1^{\prime }\sim {\phi }_1$, aplicada en la asignación ${\downarrow }_1^a(\overrightarrow{a})$), para cada $a\in A$, $𝐀\models {\phi }_1[{\downarrow }_1^a(\overrightarrow{a})]$,
  • sii, por (8), $𝐀\models \forall x_1{\phi }_1[\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 }$. ∎

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

Lo que hace perder puntos. Citar el Lema 5 de la Guía 10: $\forall x_1$ no es una fórmula. Escribir $({\phi }_1\eta {\phi }_2{)}^{\prime }=({\phi }_1^{\prime }\eta {\phi }_2^{\prime })$ y $(Qv{\phi }_1{)}^{\prime }=Qv{\phi }_1^{\prime }$ sin decir por qué ninguna ocurrencia pisa el nexo ni empieza en $Qv$. Olvidar que $\forall x_{12}$ también empieza con $\forall X$ y no es $\forall x_1$: el argumento es el del negrita. Usar el Lema 4(b) sin probarlo. Y en el caso $\forall x_1{\phi }_1$, aplicar la hipótesis inductiva en $\overrightarrow{a}$ y no en ${\downarrow }_1^a(\overrightarrow{a})$.

Lo que se lleva. El Ejercicio 15 tiene la misma estructura con otra palabra: los casos que no empiezan con ella se resuelven con el Lema 4(b), y el que empieza con ella, con las cláusulas. Que la palabra $\forall \mathrm{X}1$ sólo ocurra como cuantificador es el mismo tipo de hecho que en el Ejercicio 4, donde se prueba que el reemplazo da una fórmula.

Para tener a mano

1. No sale del Lema 5: la palabra $\forall x_1$ no es una fórmula. Inducción en el nivel, con ${\mathrm{Enu}}_k$: para toda $\phi \in F_k^{\tau }$, ${\phi }^{\prime }\sim \phi$.
2. $({\phi }_1\eta {\phi }_2{)}^{\prime }=({\phi }_1^{\prime }\eta {\phi }_2^{\prime })$, $(\neg {\phi }_1{)}^{\prime }=\neg {\phi }_1^{\prime }$, $(Qv{\phi }_1{)}^{\prime }=Qv{\phi }_1^{\prime }$ si $Qv\ne \forall x_1$, y $(\forall x_1{\phi }_1{)}^{\prime }=\neg \exists x_1\neg {\phi }_1^{\prime }$; cada una, con su porqué.
3. $\forall \mathrm{X}1$ sólo empieza en un cuantificador, y entonces la variable es $\mathrm{X}1$ entera, porque el negrita cierra la variable.
4. Caso $\forall x_1$: (7), (9), (7), hipótesis inductiva en ${\downarrow }_1^a(\overrightarrow{a})$, (8).
5. Medido: con $\neg \exists x_1\neg$ ninguna diferencia en las 4164 estructuras de hasta tres elementos; sin uno de los dos $\neg$, miles.