Fórmulas equivalentes y reemplazo

Dos fórmulas son equivalentes cuando no hay manera de separarlas: ninguna estructura y ninguna asignación hace verdadera a una y falsa a la otra. Que coincidan en muchas estructuras no alcanza, y que coincidan en una estructura con una asignación tampoco: la definición pide todas, y es justamente eso lo que hace funcionar el reemplazo. Si ${\phi }_1\sim {\phi }_2$, cambiar ${\phi }_1$ por ${\phi }_2$ adentro de cualquier fórmula da una fórmula equivalente, aunque el cambio quede debajo de un cuantificador.

01 · La definición

Dadas $\phi ,\psi \in F^{\tau }$, se dice que $\phi$ y $\psi$ son equivalentes cuando se da la siguiente condición:

y se escribe $\phi \sim \psi$ (Guía 10, p. 8). Las dos cuantificaciones son las que importan: todas las estructuras del tipo, y para cada una, todas las asignaciones. Por eso se puede hablar de equivalencia entre fórmulas con variables libres, y la asignación cuenta: $\forall x_{1}r(x_1,x_2)$ y $\forall x_{1}r(x_1,x_3)$ dicen lo mismo de dos variables distintas, y no son equivalentes. En $A=\{0,1\}$ con $r^{𝐀}=\{(0,0),(1,0)\}$ y $\overrightarrow{a}=(0,0,1,\dots )$, la primera dice «todos están relacionados con $a_2=0$», que es verdad, y la segunda «todos están relacionados con $a_3=1$», que es falso.

Algunas equivalencias que salen directo de las cláusulas de $\models$: $(\phi \wedge \psi )\sim (\psi \wedge \phi )$, por la cláusula (3) y la conmutatividad del «y»; $\neg \neg \phi \sim \phi$, porque la cláusula (7) aplicada dos veces da $𝐀\models \neg \neg \phi [\overrightarrow{a}]$ sii $𝐀⊭\neg \phi [\overrightarrow{a}]$ sii $𝐀\models \phi [\overrightarrow{a}]$; y $\forall x_1\phi \sim \neg \exists x_1\neg \phi$, por las cláusulas (7), (8) y (9).

Un caso menos evidente, el Ejercicio 12 (d) de la guía: $\exists x_1\forall x_{1}r(x_1,x_1)\sim \forall x_{1}r(x_1,x_1)$. Sean $𝐀$ y $\overrightarrow{a}$ cualesquiera. Por la cláusula (9), $𝐀\models \exists x_1\forall x_{1}r(x_1,x_1)[\overrightarrow{a}]$ sii hay un $a\in A$ con $𝐀\models \forall x_{1}r(x_1,x_1)[{\downarrow }_1^a(\overrightarrow{a})]$, y por la (8) eso es: hay un $a$ tal que para todo $b\in A$, $𝐀\models r(x_1,x_1)[{\downarrow }_1^b({\downarrow }_1^a(\overrightarrow{a}))]$. Como ${\downarrow }_1^b({\downarrow }_1^a(\overrightarrow{a}))={\downarrow }_1^b(\overrightarrow{a})$, el $a$ no aparece en lo que hay que cumplir, y como $A\ne \varnothing$ siempre hay alguno: queda «para todo $b\in A$, $𝐀\models r(x_1,x_1)[{\downarrow }_1^b(\overrightarrow{a})]$», que por la (8) es $𝐀\models \forall x_{1}r(x_1,x_1)[\overrightarrow{a}]$. El $\exists x_1$ de afuera no tiene nada que ligar: el $\forall x_1$ le pisa el lugar 1 de la asignación.

02 · Es una relación de equivalencia

La guía lo anota al pasar: $\{(\phi ,\psi )\in F^{\tau }\times F^{\tau }:\phi \sim \psi \}$ es una relación de equivalencia sobre $F^{\tau }$. Es porque «si y sólo si» lo es, estructura por estructura y asignación por asignación. Reflexiva: $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models \phi [\overrightarrow{a}]$. Simétrica: si para cada $𝐀$ y $\overrightarrow{a}$ vale $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models \psi [\overrightarrow{a}]$, vale la misma equivalencia leída al revés. Transitiva: si $\phi \sim \psi$ y $\psi \sim \chi$, dados $𝐀$ y $\overrightarrow{a}$, $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models \psi [\overrightarrow{a}]$ sii $𝐀\models \chi [\overrightarrow{a}]$. Con esto se pueden encadenar equivalencias, que es lo que hacen los Ejercicios 14 y 15 de la lista.

La tabla sirve para una sola cosa: encontrar dónde difieren. Si difieren en una estructura con una asignación, no son equivalentes, y esa fila es el contraejemplo. Si coinciden en las 530, no prueba nada: la definición habla de todas las estructuras del tipo, de cualquier tamaño, y la equivalencia se prueba con las cláusulas de $\models$, como el 12 (d) de arriba. Los dos pares de $\exists x_1\forall x_1$ se parecen mucho, y uno es equivalente y el otro no.

03 · El Lema 4 (a): equivalencia es validez universal

Lo que dice: la equivalencia no es una noción nueva, es la validez universal de un bicondicional, cerrado con un $\forall$ por cada variable libre. La lectura de la columna «clausura» del widget: la sentencia $\forall x_1\forall x_2\forall x_3(\phi \leftrightarrow \psi )$ es falsa exactamente en las estructuras donde el par difiere.

Prueba. Para cada $k$ entre 0 y $n$, sea ${\chi }_k=\forall x_{i_{k+1}}\dots \forall x_{i_n}(\phi \leftrightarrow \psi )$: ${\chi }_n=(\phi \leftrightarrow \psi )$, y cada ${\chi }_{k-1}=\forall x_{i_k}{\chi }_k$. La cadena es:

1. $\phi \sim \psi$
2. ⇕ $𝐀\models (\phi \leftrightarrow \psi )[\overrightarrow{a}]$, para todo $𝐀$ y toda $\overrightarrow{a}\in A^{𝐍}$cláusula (6) de ⊨
3. ⇕ $𝐀\models {\chi }_k[{\downarrow }_{i_k}^a(\overrightarrow{a})]$, para todo $𝐀$, todo $a\in A$ y toda $\overrightarrow{a}$(con k = n)
4. ⇕ $𝐀\models \forall x_{i_k}{\chi }_k[\overrightarrow{a}]$, para todo $𝐀$ y toda $\overrightarrow{a}$cláusula (8) de ⊨
5. ⇕ …lo mismo para $k=n-1,\dots ,1$…
6. ⇕ $𝐀\models \forall x_{i_1}\dots \forall x_{i_n}(\phi \leftrightarrow \psi )[\overrightarrow{a}]$, para todo $𝐀$ y toda $\overrightarrow{a}$
7. ⇕ $\forall x_{i_1}\dots \forall x_{i_n}(\phi \leftrightarrow \psi )$ es universalmente válidaes sentencia

Los porqués que la guía no escribe. El primer paso es la cláusula (6): $𝐀\models (\phi \leftrightarrow \psi )[\overrightarrow{a}]$ sii se dan las dos o no se da ninguna, que es «$𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models \psi [\overrightarrow{a}]$». El paso de «toda $\overrightarrow{a}$» a «todo $a$ y toda $\overrightarrow{a}$, en ${\downarrow }_{i_k}^a(\overrightarrow{a})$» va en las dos direcciones: para ir, ${\downarrow }_{i_k}^a(\overrightarrow{a})$ es una asignación; para volver, dada $\overrightarrow{a}$ se toma $a=a_{i_k}$, y ${\downarrow }_{i_k}^{a_{i_k}}(\overrightarrow{a})=\overrightarrow{a}$. El último usa que la fórmula es una sentencia: por el Lema 10 de la Guía 9, $\mathrm{Li}(\forall x_{i_1}\dots \forall x_{i_n}(\phi \leftrightarrow \psi ))=(\mathrm{Li}(\phi )\cup \mathrm{Li}(\psi ))-\{x_{i_1},\dots ,x_{i_n}\}=\varnothing$, que es donde entra la hipótesis; y una sentencia es universalmente válida cuando es verdadera en cada $𝐀$ para cada $\overrightarrow{a}$ (p. 7). ∎

04 · El Lema 4 (b): ∼ pasa a través de los conectivos

La guía lo deja como Ejercicio 11. La prueba es directa, sin inducción: cada caso es una cláusula de $\models$ aplicada de los dos lados. Sean $𝐀$ una estructura de tipo $\tau$ y $\overrightarrow{a}\in A^{𝐍}$ cualesquiera.

• ¬. $𝐀\models \neg {\phi }_1[\overrightarrow{a}]$ sii $𝐀⊭{\phi }_1[\overrightarrow{a}]$ (cláusula 7) sii $𝐀⊭{\psi }_1[\overrightarrow{a}]$ (porque ${\phi }_1\sim {\psi }_1$) sii $𝐀\models \neg {\psi }_1[\overrightarrow{a}]$ (cláusula 7).
• ∧. $𝐀\models ({\phi }_1\wedge {\phi }_2)[\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ y $𝐀\models {\phi }_2[\overrightarrow{a}]$ (cláusula 3) sii $𝐀\models {\psi }_1[\overrightarrow{a}]$ y $𝐀\models {\psi }_2[\overrightarrow{a}]$ (por ${\phi }_1\sim {\psi }_1$ y ${\phi }_2\sim {\psi }_2$) sii $𝐀\models ({\psi }_1\wedge {\psi }_2)[\overrightarrow{a}]$ (cláusula 3).
• ∨. Igual, con la cláusula (4): «$𝐀\models {\phi }_1[\overrightarrow{a}]$ o $𝐀\models {\phi }_2[\overrightarrow{a}]$» sii «$𝐀\models {\psi }_1[\overrightarrow{a}]$ o $𝐀\models {\psi }_2[\overrightarrow{a}]$».
• →. Con la cláusula (5): «$𝐀⊭{\phi }_1[\overrightarrow{a}]$ o $𝐀\models {\phi }_2[\overrightarrow{a}]$» sii «$𝐀⊭{\psi }_1[\overrightarrow{a}]$ o $𝐀\models {\psi }_2[\overrightarrow{a}]$», porque $𝐀⊭{\phi }_1[\overrightarrow{a}]$ sii $𝐀⊭{\psi }_1[\overrightarrow{a}]$ y $𝐀\models {\phi }_2[\overrightarrow{a}]$ sii $𝐀\models {\psi }_2[\overrightarrow{a}]$.
• ↔. Con la cláusula (6): «se dan ${\phi }_1$ y ${\phi }_2$, o no se da ninguna» sii lo mismo con ${\psi }_1$ y ${\psi }_2$, cambiando cada afirmación por su equivalente.
• ∀. Sea $v=x_j$. $𝐀\models \forall x_j{\phi }_1[\overrightarrow{a}]$ sii para cada $a\in A$, $𝐀\models {\phi }_1[{\downarrow }_j^a(\overrightarrow{a})]$ (cláusula 8) sii para cada $a\in A$, $𝐀\models {\psi }_1[{\downarrow }_j^a(\overrightarrow{a})]$ (por ${\phi }_1\sim {\psi }_1$, aplicado a la asignación ${\downarrow }_j^a(\overrightarrow{a})$) sii $𝐀\models \forall x_j{\psi }_1[\overrightarrow{a}]$ (cláusula 8).
• ∃. Igual con la cláusula (9): hay un $a\in A$ con $𝐀\models {\phi }_1[{\downarrow }_j^a(\overrightarrow{a})]$ sii hay un $a\in A$ con $𝐀\models {\psi }_1[{\downarrow }_j^a(\overrightarrow{a})]$.

Como $𝐀$ y $\overrightarrow{a}$ eran cualesquiera, valen las tres equivalencias. ∎

El caso del cuantificador es el único donde la hipótesis se usa en otra asignación, y muestra por qué no alcanzaría con que ${\phi }_1$ y ${\psi }_1$ coincidan en la asignación que se está mirando. En $A=\{0,1\}$ con $\overrightarrow{a}=(0,0,0,\dots )$, $(x_1\equiv x_2)$ y $(x_1\equiv x_1)$ son verdaderas las dos; pero $\forall x_1(x_1\equiv x_2)$ es falsa en $\overrightarrow{a}$ —con $a=1$, ${\downarrow }_1^1(\overrightarrow{a})$ da $1\ne 0$— y $\forall x_1(x_1\equiv x_1)$ es verdadera. El $\forall$ prueba ${\phi }_1$ en asignaciones que no son $\overrightarrow{a}$, y ahí las dos se separan.

05 · El Lema 5: reemplazar por una equivalente

El Lema de Ocurrencias de Fórmulas en Fórmulas de la Guía 9 dice, en su ítem (f), que las distintas ocurrencias de ${\phi }_1$ en $\alpha$ son disjuntas y que reemplazar algunas de ellas por otra fórmula ${\phi }_2$ da una fórmula. Más aún:

Por ejemplo, como $\neg \neg r(x_1,x_1)\sim r(x_1,x_1)$, se tiene $\forall x_1\neg \neg r(x_1,x_1)\sim \forall x_{1}r(x_1,x_1)$, y $\exists x_2\neg \neg r(x_1,x_2)\sim \exists x_{2}r(x_1,x_2)$, que es uno de los pares del widget.

La idea de la prueba. Regla de Inducción desde 0 sobre el nivel de $\alpha$, con ${\phi }_1$, ${\phi }_2$ y las ocurrencias cuantificadas adentro del ${\mathrm{Enu}}_k$: «Sean ${\phi }_1,{\phi }_2\in F^{\tau }$ tales que ${\phi }_1\sim {\phi }_2$ y sea $\alpha \in F_k^{\tau }$. Sea ${\alpha }^{\prime }$ el resultado de reemplazar en $\alpha$ algunas (posiblemente 0) ocurrencias de ${\phi }_1$ por ${\phi }_2$. Entonces $\alpha \sim {\alpha }^{\prime }$». En la base, $\alpha$ es atómica y no tiene subfórmulas propias, así que o no se reemplazó nada (${\alpha }^{\prime }=\alpha$) o se reemplazó $\alpha$ entera ($\alpha ={\phi }_1$ y ${\alpha }^{\prime }={\phi }_2$); en los dos casos $\alpha \sim {\alpha }^{\prime }$. En el paso, si $\alpha ={\phi }_1$ y se la reemplazó entera, ${\alpha }^{\prime }={\phi }_2\sim {\phi }_1$. Si no, por el Lema de Ocurrencias cada ocurrencia reemplazada cae adentro de una pieza de $\alpha$: $\alpha =({\alpha }_1\eta {\alpha }_2)$ da ${\alpha }^{\prime }=({{\alpha }_1}^{\prime }\eta {{\alpha }_2}^{\prime })$, $\alpha =\neg {\alpha }_1$ da ${\alpha }^{\prime }=\neg {{\alpha }_1}^{\prime }$, $\alpha =Qv{\alpha }_1$ da ${\alpha }^{\prime }=Qv{{\alpha }_1}^{\prime }$, con ${{\alpha }_i}^{\prime }$ el resultado de reemplazar en ${\alpha }_i$. Por ${\mathrm{Enu}}_k$, ${\alpha }_i\sim {{\alpha }_i}^{\prime }$, y el Lema 4 (b) sube la equivalencia a $\alpha$.

La guía hace sólo el caso del nexo y deja los demás; la prueba entera, con cada caso y el Lema 4 (b) enunciado y probado, es el Ejercicio 9 de la lista. El Lema 4 (b) es lo que hace que el reemplazo funcione debajo de un $\forall$: sin las asignaciones cuantificadas en la definición de $\sim$, el caso $Qv{\alpha }_1$ no cerraría.

06 · Cómo se usa en los ejercicios

El Ejercicio 9 es el Lema 5 entero. El 12 es la versión del Lema 5 en una estructura fija: «equivalentes en $𝐀$» cuantifica todas las asignaciones pero no todas las estructuras, y la prueba es la misma porque el caso $Qv$ sólo cambia la asignación. El 13 hace lo mismo con términos que valen lo mismo en lugar de fórmulas equivalentes. El 14 y el 15 reemplazan todas las ocurrencias de una palabra ($\forall x_1$ por $\neg \exists x_1\neg$, $\forall x_1\forall x_2$ por $\forall x_2\forall x_1$) y se prueban por inducción con el Lema 4 (b) en el paso; el caso que importa es el del cuantificador que se reemplaza, donde se usa una equivalencia de las de la sección 01 y la transitividad.

Para tener a mano

1. $\phi \sim \psi$: $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models \psi [\overrightarrow{a}]$, para toda estructura $𝐀$ de tipo $\tau$ y toda $\overrightarrow{a}\in A^{𝐍}$. Es relación de equivalencia porque «sii» lo es.
2. Para refutar alcanza una estructura y una asignación donde difieren. Para probar, las cláusulas de $\models$: ninguna cantidad de ejemplos alcanza.
3. Lema 4 (a): con $\mathrm{Li}(\phi )\cup \mathrm{Li}(\psi )\subseteq \{x_{i_1},\dots ,x_{i_n}\}$, $\phi \sim \psi$ sii $\forall x_{i_1}\dots \forall x_{i_n}(\phi \leftrightarrow \psi )$ es universalmente válida. Cláusula (6), y la (8) una vez por variable.
4. Lema 4 (b): $\sim$ pasa por $\neg$, los cuatro nexos y $Qv$. En $Qv$ la hipótesis se aplica en ${\downarrow }_j^a(\overrightarrow{a})$.
5. Lema 5: reemplazar algunas ocurrencias de ${\phi }_1$ por ${\phi }_2\sim {\phi }_1$ da una equivalente. Inducción en el nivel de $\alpha$; la ocurrencia es $\alpha$ entera o vive en una pieza; Lema 4 (b).