Alcanza con una cota, no hace falta el supremo

El enunciado, textual: «De una prueba elemental de posets de la sentencia elemental pura de posets:

$$(\forall u\forall v\exists z(u\le z\wedge v\le z)\to \forall x(\neg \exists z(x\le z\wedge \neg (x=z))\to \forall w(w\le x)))$$

». Es el Ejercicio 17 (e) de la Guía 7, pág. 12, que agrega una consigna: antes de probarla, explicar con palabras qué dice. Qué dice, por qué la hipótesis no es decorativa y por qué la prueba no cita ningún axioma de poset es la tesis de Maximal no es máximo, salvo que todo par tenga cota. Lo de acá es resolverlo, y ver qué cambia respecto del Ejercicio 4, que pedía lo mismo en un reticulado.

01 · Antes de probar: el tipo y la forma

El tipo. Es una prueba elemental de posets. El lenguaje tiene un solo símbolo, $\le$, y los axiomas son tres: A≤R, A≤T y A≤A. No hay $s$ ni $i$: un término como $usv$ no es una palabra de este lenguaje, y una prueba que lo escriba no es una prueba de posets aunque la estructura que uno imagina tenga supremos.

La forma. El conectivo principal es la primera flecha. A la izquierda, la hipótesis

$$\forall u\forall v\exists z(u\le z\wedge v\le z)\text{(H)}$$

«todo par de elementos tiene una cota superior común». A la derecha, la sentencia del Ejercicio 4 con dos cambios de letra: w en lugar de la segunda z, y $\neg (x=z)$ en lugar de $\neg (z=x)$. Dicen lo mismo: «todo maximal es máximo». Toda la sentencia: si todo par tiene una cota superior, todo maximal es máximo.

Qué se entrega. Tres supuestos anidados, en este orden: (H); después un a arbitrario que es maximal; después un b arbitrario, para llegar a $b\le a$. Y al final se descargan en el orden inverso. El orden no es estético: decide sobre qué se puede generalizar en cada momento.

02 · Las herramientas: ningún axioma, cuatro movidas

La prueba no cita A≤R, ni A≤T, ni A≤A; el ensayo lo mide sobre todas las relaciones de tres y de cuatro elementos. Lo que usa es lógica:

• Suponer el antecedente de una implicación, y al final descargarlo.
• Elegir un testigo. De $\exists z(a\le z\wedge b\le z)$ se pasa a «sea c uno de esos». Ese c es un nombre nuevo para un elemento que existe; no es arbitrario, y sobre él nunca se generaliza.
• Ofrecerle un candidato a $\neg \exists z(\dots )$ para llegar a un absurdo.
• Reemplazar iguales.

03 · La mariposa: lo que en el 4 hacía el supremo

El dibujo es el del Ejercicio 4: a maximal, b cualquiera, algo arriba de los dos, y la maximalidad de a que aplasta ese algo contra a. Cambia de dónde sale el algo.

En el 4 lo fabricaba un axioma. AsesC, tomando x como a e y como b, daba $a\le asb$ y $b\le asb$. El candidato era un término, $asb$, escrito en la prueba sin elegir nada.

Acá lo da la hipótesis, y hay que elegirlo. (H), tomando u como a y v como b, da $\exists z(a\le z\wedge b\le z)$: que hay uno, no cuál. Se le pone nombre, c, y desde ahí la prueba es la del 4 con c en el lugar de $asb$. Es lo que señala La misma prueba, y depende del tipo: el texto del 4 copiado acá no es una prueba, porque cita un axioma y un símbolo que este tipo no tiene.

El 4 es este ejercicio con la hipótesis pagada. En un reticulado, (H) es un teorema: la cota de u y v es $usv$. Al revés no: (H) pide mucho menos que ser reticulado. Sobre los 4473 posets rotulados de hasta cinco elementos, 425 son reticulados y 1183 cumplen (H). En la mayoría de los 758 de diferencia lo que falta es algún ínfimo, que a esta prueba no le importa, como en la Λ. Pero hay posets donde un par tiene cotas comunes y ninguna es la menor: el más chico tiene cinco elementos, la corbata con techo, y en cinco elementos es la única forma, con 30 rotulaciones. Ahí la prueba del 4 no se puede escribir, y la del 11 anda igual.

Y se usa menos de lo que se pide. La prueba instancia (H) una sola vez, con u como a. Alcanzaría con que cada elemento tenga una cota común con a; que la tengan todos los pares es más de lo necesario, y es lo que el enunciado pide porque no sabe de antemano quién es a.

En la corbata, p y q tienen tres cotas comunes, m, n y 1, y ninguna está debajo de las otras dos: no hay supremo. La prueba del 11 no lo necesita; ofrece cualquiera de las tres. En la Λ todo par tiene supremo y lo que falta es un ínfimo, que no entra en el ejercicio. Y en la V, con p y q no hay ninguna cota: ahí falla (H), y con ella la conclusión.

04 · El escarabajo: la prueba escrita

Prueba. Supongamos

$$\forall u\forall v\exists z(u\le z\wedge v\le z)\text{(H)}$$

Sea $a\in P$ un elemento fijo pero arbitrario, y supongamos

$$\neg \exists z(a\le z\wedge \neg (a=z))\text{(M)}$$

Queremos probar $\forall w(w\le a)$. Sea $b\in P$ un elemento fijo pero arbitrario; vamos a probar $b\le a$.

Paso 1. (H), tomando u como a y v como b, nos dice que $\exists z(a\le z\wedge b\le z)$. Sea c un elemento que lo testimonie, o sea que se da $(a\le c\wedge b\le c)$. En particular se da $a\le c$, y también $b\le c$.

Paso 2. Supongamos, para llegar a un absurdo, que $\neg (a=c)$. Junto con $a\le c$, se daría $(a\le c\wedge \neg (a=c))$, y entonces se daría $\exists z(a\le z\wedge \neg (a=z))$, con c como testigo. Eso contradice (M). Luego el supuesto era falso, y se da $a=c$.

Paso 3. Por el paso 1 se da $b\le c$. Como por el paso 2 a y c denotan el mismo elemento, reemplazando obtenemos $b\le a$.

Cierre. Ya que b era fijo pero arbitrario —no figura en (H) ni en (M), y c ya no aparece en $b\le a$—, hemos probado $\forall w(w\le a)$. Como lo hicimos suponiendo (M), probamos

$$(\neg \exists z(a\le z\wedge \neg (a=z))\to \forall w(w\le a))$$

Ya que a era fijo pero arbitrario —y no figura en (H)—, generalizando obtenemos $\forall x(\neg \exists z(x\le z\wedge \neg (x=z))\to \forall w(w\le x))$. Y como todo esto lo hicimos suponiendo (H), hemos probado la sentencia del enunciado. ∎

Acá el testigo del paso 2 niega $a=c$ con a a la izquierda, porque la fórmula de maximal de este enunciado es $\neg (x=z)$. En el Ejercicio 4 era $\neg (z=x)$ y el testigo negaba $asb=a$. Cada prueba copia el orden de su fórmula.

05 · Lo que se lleva a otros ejercicios

Término o elección. Cuando el tipo tiene una operación que construye el testigo, se lo escribe como término y no hay nada que elegir. Cuando el testigo sale de un $\exists$ —de una hipótesis o de un axioma—, se lo nombra con «sea c uno de esos», y ese nombre queda marcado: no se generaliza sobre él, y no puede quedar en lo que se generaliza. El Ejercicio 10 de la lista, también de posets, vive de lo mismo.

Lo que hace perder puntos. Escribir $asb$ como si fuera un reticulado: en este lenguaje no hay $s$. Citar el Ejercicio 4: es otro tipo, y aunque no lo fuera, es un resultado y habría que enunciarlo y probarlo aparte. Cerrar con «como c era arbitrario»: no lo era. Y descargar los supuestos en otro orden: (H) se descarga último, después de generalizar sobre a.

Para tener a mano

1. La sentencia: si todo par tiene una cota superior común, todo maximal es máximo.
2. Tres supuestos anidados —(H), a maximal, b arbitrario— y se descargan al revés.
3. La cota la da (H) con u como a y v como b; se la nombra c y nunca se generaliza sobre ella.
4. En el Ejercicio 4 la cota era el término $asb$; en posets ese término no existe.
5. (H) es más débil que ser reticulado: la corbata con techo, de cinco elementos, la cumple y sus dos elementos de abajo no tienen supremo.