La implicación que rompe la intuición

El enunciado, textual: «Sea $\tau =(\{\mathrm{c}\},\mathrm{\varnothing },\{\mathrm{P1},\mathrm{P2},\mathrm{R}\},\{(\mathrm{P1},1),(\mathrm{P2},1),(\mathrm{R},1)\})$. Pruebe matemáticamente que

$$(((\mathrm{P1}(\mathrm{c})\wedge \mathrm{P2}(\mathrm{c}))\to \mathrm{R}(\mathrm{c}))\to ((\mathrm{P1}(\mathrm{c})\to \mathrm{R}(\mathrm{c}))\vee (\mathrm{P2}(\mathrm{c})\to \mathrm{R}(\mathrm{c}))))$$

es universalmente válida. (Pruébelo por el absurdo)». Es la sentencia que la Guía 10 llama $\mu$ en la página 10, la que presenta como un posible «monstruo» del modelo, y la primera mitad de su Ejercicio 16. La segunda mitad es el Ejercicio 11 de la lista.

La sentencia parece decir algo falso y es verdadera en toda estructura. La prueba es corta: tres cláusulas de la definición de $\models$ y una contradicción. Lo que cuesta es creerla, y lo que hace perder puntos es escribirla salteando pasos.

01 · Qué dice, leída en castellano

Leída de corrido: «si tener P1 y P2 a la vez alcanza para tener R, entonces P1 sola alcanza para R, o P2 sola alcanza». Pensada para propiedades en general suena falsa: aprobar los dos parciales alcanza para promocionar, y ninguno de los dos solo alcanza.

Pero $\mu$ no habla de propiedades en general: habla de $\mathrm{c}$. En una estructura $𝐀=(A,i)$ de tipo $\tau$, $\mathrm{c}$ es el nombre de un elemento fijo, $i(\mathrm{c})$, y cada una de las tres atómicas $\mathrm{P1}(\mathrm{c})$, $\mathrm{P2}(\mathrm{c})$ y $\mathrm{R}(\mathrm{c})$ dice una sola cosa de ese elemento: si está o no en $i(\mathrm{P1})$, en $i(\mathrm{P2})$, en $i(\mathrm{R})$. Para $\mu$, toda la estructura se reduce a tres sí o no.

Un ejemplo. $A=\{1,2,3\}$, $i(\mathrm{c})=2$, $i(\mathrm{P1})=\{1,2\}$, $i(\mathrm{P2})=\{2,3\}$, $i(\mathrm{R})=\{1\}$. El elemento 2 está en $i(\mathrm{P1})$ y en $i(\mathrm{P2})$ y no en $i(\mathrm{R})$: $\mathrm{P1}(\mathrm{c})$ y $\mathrm{P2}(\mathrm{c})$ son verdaderas y $\mathrm{R}(\mathrm{c})$ es falsa. Entonces las dos implicaciones del consecuente son falsas, y el consecuente también. Pero el antecedente, $((\mathrm{P1}(\mathrm{c})\wedge \mathrm{P2}(\mathrm{c}))\to \mathrm{R}(\mathrm{c}))$, también es falso: tiene antecedente verdadero y consecuente falso. Y una implicación con antecedente falso es verdadera. $\mu$ vale.

Las ocho combinaciones posibles, con el valor de cada pieza calculado con las cláusulas de $\models$:

El consecuente es falso en una sola fila, la del ejemplo, y justo en esa el antecedente también es falso. En las otras siete el consecuente es verdadero: si $i(\mathrm{c})$ no está en $i(\mathrm{P1})$, la implicación $(\mathrm{P1}(\mathrm{c})\to \mathrm{R}(\mathrm{c}))$ es verdadera; si no está en $i(\mathrm{P2})$, lo es $(\mathrm{P2}(\mathrm{c})\to \mathrm{R}(\mathrm{c}))$; si está en $i(\mathrm{R})$, las dos. La tabla ya es una prueba, pero no la que pide la consigna: pide el absurdo.

02 · Las herramientas

Estructura (Guía 8, p. 7). Una estructura de tipo $\tau$ es un par $𝐀=(A,i)$ con $A$ un conjunto no vacío, $i(\mathrm{c})\in A$, y $i(r)$ una relación $n$-aria sobre $A$ para cada nombre de relación $r$ de aridad $n$. Una relación de aridad 1 es un subconjunto de $A$: acá $i(\mathrm{P1}),i(\mathrm{P2}),i(\mathrm{R})\subseteq A$.

El valor de una constante (Guía 10, p. 1, cláusula (2) de $t^{𝐀}[\overrightarrow{a}]$): ${\mathrm{c}}^{𝐀}[\overrightarrow{a}]=i(\mathrm{c})$, sea cual sea la asignación $\overrightarrow{a}$.

Las cláusulas de $\models$ (Guía 10, p. 4). La prueba usa tres, para ${\phi }_1,{\phi }_2\in F^{\tau }$:

• (3) $𝐀\models ({\phi }_1\wedge {\phi }_2)[\overrightarrow{a}]$ si y sólo si $𝐀\models {\phi }_1[\overrightarrow{a}]$ y $𝐀\models {\phi }_2[\overrightarrow{a}]$.
• (4) $𝐀\models ({\phi }_1\vee {\phi }_2)[\overrightarrow{a}]$ si y sólo si $𝐀\models {\phi }_1[\overrightarrow{a}]$ o $𝐀\models {\phi }_2[\overrightarrow{a}]$.
• (5) $𝐀\models ({\phi }_1\to {\phi }_2)[\overrightarrow{a}]$ si y sólo si $𝐀⊭{\phi }_1[\overrightarrow{a}]$ o $𝐀\models {\phi }_2[\overrightarrow{a}]$.

La (2), la de las atómicas, dice que $𝐀\models \mathrm{P1}(\mathrm{c})[\overrightarrow{a}]$ si y sólo si ${\mathrm{c}}^{𝐀}[\overrightarrow{a}]\in i(\mathrm{P1})$, o sea $i(\mathrm{c})\in i(\mathrm{P1})$. Explica de qué hablan las atómicas, pero la prueba no la necesita: las trata como cajas cerradas, verdaderas o falsas.

Universalmente válida (Guía 10, p. 7). Una sentencia $\phi$ es universalmente válida si $𝐀\models \phi$ para toda estructura $𝐀$ de tipo $\tau$, «o equivalentemente si $𝐀\models \phi [\overrightarrow{a}]$, para cada estructura $𝐀$ de tipo $\tau$ y cada asignación $\overrightarrow{a}\in A^{𝐍}$». La prueba usa la segunda forma, y su negación sale sin ningún lema: hay una $𝐀$ y una $\overrightarrow{a}$ con $𝐀⊭\mu [\overrightarrow{a}]$.

El Corolario 3 de la Guía 10 dice que el valor de verdad de una sentencia no depende de la asignación. Esta prueba no lo usa: toma la asignación que viene con la hipótesis y no la cambia nunca. Si se lo usara, la lista pide enunciarlo y probarlo, y su prueba es la inducción del Lema 2.

03 · La mariposa: exprimir lo falso primero

Por el absurdo: se supone $𝐀⊭\mu [\overrightarrow{a}]$ y se baja por la sentencia. Lo que se sabe de una fórmula falsa depende de su forma, y $\mu$ está armada con las dos formas que, falsas, dan más información:

• Una implicación falsa tiene el antecedente verdadero y el consecuente falso: es la (5) negada, porque «no (no A o B)» es «A y no B».
• Una disyunción falsa tiene los dos disyuntos falsos: es la (4) negada.

Las dos dan dos datos por el precio de uno, sin casos. Llamando $\alpha$ al antecedente y $\beta$ al consecuente, $\mu =(\alpha \to \beta )$. Que $\mu$ sea falsa da $\alpha$ verdadera y $\beta$ falsa. Que $\beta$ sea falsa da las dos implicaciones falsas. Y cada implicación falsa da su antecedente verdadero y su consecuente falso: $\mathrm{P1}(\mathrm{c})$ verdadera, $\mathrm{R}(\mathrm{c})$ falsa, $\mathrm{P2}(\mathrm{c})$ verdadera. Son exactamente los tres datos de la fila destacada de la tabla.

Queda un dato sin usar: $\alpha$ es verdadera. Una implicación verdadera es la información más pobre, porque la (5) da dos alternativas: el antecedente falso o el consecuente verdadero. Por eso se usa al final, cuando las dos alternativas ya chocan con algo. $(\mathrm{P1}(\mathrm{c})\wedge \mathrm{P2}(\mathrm{c}))$ es verdadera por la (3), así que la primera alternativa choca; $\mathrm{R}(\mathrm{c})$ es falsa, así que choca la segunda.

El orden importa. Si se empieza por $\alpha$ verdadera, la prueba se abre en dos casos desde el primer renglón, y cada caso tiene que bajar igual por $\beta$. Primero se exprime todo lo falso, que no ramifica; lo verdadero con «o» se usa último.

04 · El escarabajo: la prueba escrita

Prueba. Supongamos, por el absurdo, que $\mu$ no es universalmente válida. Entonces hay una estructura $𝐀=(A,i)$ de tipo $\tau$ y una asignación $\overrightarrow{a}\in A^{𝐍}$ tales que $𝐀⊭\mu [\overrightarrow{a}]$. Llamemos

$$\alpha =((\mathrm{P1}(\mathrm{c})\wedge \mathrm{P2}(\mathrm{c}))\to \mathrm{R}(\mathrm{c}))$$ $$\beta =((\mathrm{P1}(\mathrm{c})\to \mathrm{R}(\mathrm{c}))\vee (\mathrm{P2}(\mathrm{c})\to \mathrm{R}(\mathrm{c})))$$

de modo que $\mu =(\alpha \to \beta )$.

Las líneas 4 y 8 dicen $𝐀⊭\mathrm{R}(\mathrm{c})[\overrightarrow{a}]$ y $𝐀\models \mathrm{R}(\mathrm{c})[\overrightarrow{a}]$, lo cual es absurdo. Luego no hay tales $𝐀$ y $\overrightarrow{a}$: para toda estructura $𝐀$ de tipo $\tau$ y toda asignación $\overrightarrow{a}\in A^{𝐍}$ se tiene $𝐀\models \mu [\overrightarrow{a}]$, es decir, $\mu$ es universalmente válida. ∎

En el parcial cada línea se justifica igual que acá, con la cláusula y de qué línea sale. La línea 2 conviene escribirla entera la primera vez: «por (5), $𝐀\models (\alpha \to \beta )[\overrightarrow{a}]$ si y sólo si $𝐀⊭\alpha [\overrightarrow{a}]$ o $𝐀\models \beta [\overrightarrow{a}]$; como no se da $𝐀\models (\alpha \to \beta )[\overrightarrow{a}]$, no se da ninguna de las dos alternativas». Después alcanza con «por (5)». Si se quiere hablar de elementos, por la (2) las líneas 4 y 5 dicen $i(\mathrm{c})\in i(\mathrm{P1})$, $i(\mathrm{c})\in i(\mathrm{P2})$ e $i(\mathrm{c})\notin i(\mathrm{R})$, y la contradicción es la misma.

05 · Por qué la intuición se equivoca

La Guía 10 lo explica en la página 11: en la matemática real no se le asigna valor de verdad a una implicación entre dos afirmaciones concretas ya verdaderas o falsas, y por eso se tiende a leer las implicaciones de $\mu$ como si estuvieran «parametrizadas». Pero en una estructura dada, $\mathrm{c}$ denota un elemento concreto y fijo.

Lo que la intuición escucha es otra sentencia, con un $\forall$ delante de cada implicación:

$${\mu }^{\prime }=(\forall x_1((\mathrm{P1}(x_1)\wedge \mathrm{P2}(x_1))\to \mathrm{R}(x_1))\to (\forall x_1(\mathrm{P1}(x_1)\to \mathrm{R}(x_1))\vee \forall x_1(\mathrm{P2}(x_1)\to \mathrm{R}(x_1))))$$

Y ${\mu }^{\prime }$ sí es falsa en algunas estructuras. Con $A=\{1,2\}$, $i(\mathrm{P1})=\{1\}$, $i(\mathrm{P2})=\{2\}$ e $i(\mathrm{R})=\mathrm{\varnothing }$, ningún elemento cumple P1 y P2 a la vez, así que el antecedente es verdadero; 1 cumple P1 sin cumplir R y 2 cumple P2 sin cumplir R, así que los dos disyuntos son falsos. Entre las 1672 estructuras de tipo $\tau$ con universo de hasta tres elementos (contando cada elección de $i(\mathrm{c})$), ${\mu }^{\prime }$ es falsa en 112 y $\mu$ en ninguna.

La prueba de arriba muestra dónde está la diferencia. En ${\mu }^{\prime }$, la línea 3 daría un elemento que cumple P1 sin R y otro que cumple P2 sin R, y nada obliga a que sean el mismo: la línea 6 no se puede escribir. En $\mu$ los dos son $i(\mathrm{c})$, por fuerza, y el mismo elemento que hace falsas las dos implicaciones hace falso el antecedente.

Abajo se arma la estructura: qué elemento es $i(\mathrm{c})$ y qué elementos cumplen cada relación. El árbol muestra cada subfórmula de $\mu$ con la cláusula que la evalúa y su valor, y debajo, el valor de ${\mu }^{\prime }$ en la misma estructura.

Para que $\mu$ sea falsa hace falta el consecuente falso, y eso obliga a que $i(\mathrm{c})$ cumpla P1 y P2 sin cumplir R. Esa misma marca hace falso el antecedente. No importa qué hagan los demás elementos: $\mu$ sólo mira a $i(\mathrm{c})$. ${\mu }^{\prime }$, en cambio, mira a todos, y alcanza con repartir P1 y P2 entre dos elementos distintos para que falle.

06 · Lo que se lleva a otros ejercicios

El molde del absurdo. Suponer una estructura y una asignación donde la sentencia es falsa, bajar con las cláusulas negadas mientras no ramifiquen, y usar al final lo que es verdadero con un «o». Qué da cada cláusula cuando la fórmula es falsa está en La relación ⊨ y la validez universal.

El mismo fenómeno con un cuantificador. El Ejercicio 11 es $\mu$ con la conjunción $(\mathrm{P1}(\mathrm{c})\wedge \mathrm{P2}(\mathrm{c}))$ cambiada por $\forall x_1\mathrm{P1}(x_1)$, que es una conjunción de tantos casos como elementos tenga $A$. Su prueba sigue el mismo orden: primero el consecuente falso, después el antecedente.

Lo que hace perder puntos. Probarlo con la tabla de las ocho filas, cuando la consigna pide el absurdo. Escribir «por (5)» sin decir de qué línea sale ni qué alternativa se descarta. Empezar por el antecedente verdadero y quedar con dos casos abiertos. Escribir $𝐀⊭\mu$ sin asignación y después usar $\overrightarrow{a}$ sin decir de dónde sale: eso apoya la prueba en el Corolario 3 sin enunciarlo. Y cerrar con «absurdo» sin señalar cuáles dos líneas se contradicen.

Para tener a mano

1. $\mu$ sólo mira a $i(\mathrm{c})$: tres sí o no, ocho combinaciones, $\mu$ verdadera en las ocho.
2. Negar «universalmente válida» da una $𝐀$ y una $\overrightarrow{a}$ con $𝐀⊭\mu [\overrightarrow{a}]$. Con la asignación a la vista no hace falta el Corolario 3.
3. Implicación falsa: antecedente verdadero y consecuente falso. Disyunción falsa: los dos disyuntos falsos. Implicación verdadera: dos alternativas, y se usa última.
4. La contradicción: $𝐀⊭\mathrm{R}(\mathrm{c})[\overrightarrow{a}]$ por el consecuente, $𝐀\models \mathrm{R}(\mathrm{c})[\overrightarrow{a}]$ por el antecedente.
5. La intuición lee ${\mu }^{\prime }$, con un $\forall x_1$ en cada implicación. Ésa falla: $A=\{1,2\}$, $i(\mathrm{P1})=\{1\}$, $i(\mathrm{P2})=\{2\}$, $i(\mathrm{R})=\mathrm{\varnothing }$.