Ejercicio 11 de la lista del parcial 3 · Guía 10 · la segunda sentencia del Ejercicio 16, por el absurdo, y por qué es el mismo fenómeno que μ
El enunciado, textual: «Sea . Pruebe matemáticamente que
es universalmente válida. (Pruébelo por el absurdo)». Es la segunda sentencia del Ejercicio 16 de la Guía 10. La guía la propone en la página 11, después de , como otra sentencia «que rompe nuestra intuición por ser siempre verdadera», y deja al lector meditar hasta entender que el fenómeno es el mismo que en : «un es en algún sentido la conjunción de muchos casos». Acá la llamamos .
Leída de corrido: «si que todos cumplan P1 alcanza para que cumpla P2, entonces hay un elemento que, con cumplir P1, ya alcanza para que cumpla P2». Suena a que tiene que haber un responsable: alguien cuyo P1 «cause» el P2 de . Y no hay ninguna razón para que exista.
Un ejemplo. , , e . No todos cumplen P1 —el 3 no—, así que es falsa y el antecedente, una implicación con antecedente falso, es verdadero. ¿Hay un que haga verdadera cuando vale ? Sí: el 3. Como 3 no cumple P1, la implicación es verdadera sin mirar . El testigo del es justamente el elemento que hacía falsa , y no tiene nada que ver con .
Eso resuelve todos los casos. Si algún elemento no cumple P1, ese elemento es testigo del . Si todos cumplen P1 y cumple P2, cualquier elemento es testigo, porque el consecuente es verdadero. Y si todos cumplen P1 y no cumple P2, el consecuente de es falso, pero el antecedente también: es verdadera y falsa. Entre las 228 estructuras de tipo con universo de hasta tres elementos, es verdadera en todas, y su consecuente es falso en exactamente 17: las de este último caso.
Estructura (Guía 8, p. 7): con no vacío, e .
Asignaciones (Guía 10, p. 1 y p. 4). Una asignación es , y es la asignación que resulta de reemplazar en el -ésimo elemento por . Las cláusulas (1) y (2) del valor de un término dan y .
Las cláusulas de (Guía 10, p. 4) que usa la prueba:
Universalmente válida (Guía 10, p. 7): para cada estructura de tipo y cada . Negado: hay una y una con . Como en el Ejercicio 10, con la asignación a la vista no hace falta el Corolario 3.
El orden es el del Ejercicio 10: exprimir lo falso, que no ramifica, y usar al final la implicación verdadera. falsa da, por la (5), el antecedente verdadero y el consecuente falso.
Un falso es la mejor noticia posible para un absurdo: por la (9) negada, ningún hace verdadera en . O sea, para cada la implicación es falsa, y por la (5) negada, para cada : verdadera y falsa, las dos en . Es la versión con muchos elementos de las líneas 3 a 5 del Ejercicio 10.
De ahí salen dos cosas. La primera mitad, para cada , es exactamente lo que la (8) pide para : es verdadera en . La segunda mitad dice que es falsa, pero en las asignaciones , y el antecedente habla de en . Hay que llevarla de una asignación a la otra.
Hay dos maneras sin lemas. La corta: elegir , el primer elemento de . Reemplazar el primer elemento de por no cambia nada: , y la segunda mitad dice directamente . La larga: por la cláusula (2) de y , si y sólo si , para cualquier , así que el valor de es el mismo en todas las asignaciones. Lo que no se puede es decir « es una sentencia» y seguir: eso es el Corolario 3, y habría que enunciarlo y probarlo.
Con verdadera y falsa en , el antecedente verdadero no tiene salida: por la (5) pide falsa o verdadera.
Prueba. Supongamos, por el absurdo, que no es universalmente válida. Entonces hay una estructura de tipo y una asignación tales que .
En la línea 6, porque reemplazar el primer elemento de por deja la misma asignación. Las líneas 6 y 8 dicen y , lo cual es absurdo. Luego para toda estructura de tipo y toda se tiene , y es universalmente válida. ∎
La línea 3 es donde más se pierde. La (9) dice «hay un tal que…»; negada dice «para cada , no…», y cada instancia vive en su propia asignación , no en . Escribir ahí es un error: eso sería la instancia sola.
Por la (8), es verdadera cuando lo es en para cada : una conjunción con un término por elemento. Por la (9), es una disyunción con un término por elemento. Con , y escribiendo «1 cumple P1» por , dice:
si (1 cumple P1 y 2 cumple P1) implica P2(c), entonces (1 cumple P1 implica P2(c)) o (2 cumple P1 implica P2(c)).
Es letra por letra, con «1 cumple P1» en el lugar de , «2 cumple P1» en el de y en el de . Con más elementos, la conjunción y la disyunción se alargan, y el argumento es el mismo: si todas las implicaciones del consecuente fallan, todos los casos de la conjunción son verdaderos y es falsa, y entonces falla el antecedente.
La intuición falla por la razón de la página 11. Se lee como «cumplir P1 hace que cumpla P2», una relación de causa. Pero es un hecho fijo sobre un elemento fijo, verdadero o falso en la estructura, y la implicación en sólo compara dos valores de verdad. Por eso el testigo puede ser cualquier elemento que no cumpla P1, aunque no tenga relación con .
Abajo se arma la estructura. El árbol despliega cada cuantificador en un renglón por elemento, con la asignación en la que se evalúa cada instancia; los testigos del van en azul.
Para dejar al sin testigos hay que poner a todos en P1 y sacar a de P2. Y en ese mismo momento pasa a ser verdadera con falsa: el antecedente se cae justo cuando el consecuente se cae. Con un solo elemento, queda leída en ese elemento, que no puede fallar.
Un falso y un verdadero dan un «para cada»; un verdadero y un falso dan un elemento, que hay que nombrar. En una prueba por el absurdo conviene llegar rápido a los primeros. La tabla completa de qué da cada cláusula está en La relación ⊨ y la validez universal.
Cada instancia de un cuantificador vive en su asignación. El cuidado de la línea 3 — y no — es el mismo que pide el Ejercicio 14, donde se compara con en cada asignación, y el Ejercicio 15, donde dos seguidos cambian dos lugares distintos de .
Lo que hace perder puntos. Negar la (9) como «hay un tal que no». Escribir las instancias en en lugar de . Pasar a sin decir por qué: con , o con la cláusula (2), o enunciando y probando el Corolario 3. Y usar el antecedente antes de tiempo, que abre dos casos.