En un reticulado, maximal ya es máximo

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

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

». Es el Ejercicio 9 de la Guía 6, pág. 13, que en el inciso (a) pide la misma cosa como prueba matemática común y en el (b) como prueba elemental. La mitad del trabajo es el inciso (a) escondido: darse cuenta de qué dice la fórmula. Una vez que se lee, la prueba es corta.

01 · Antes de probar: qué dice la fórmula

Se lee de afuera para adentro. El conectivo principal, adentro del $\forall x$, es la flecha. El $\neg$ del principio no niega la implicación: afecta sólo a la fórmula que tiene pegada, $\exists z(\dots )$. Así que hay un antecedente y un consecuente, y cada uno es una palabra de la Guía 2.

El antecedente. $x\le z\wedge \neg (z=x)$ dice que z está arriba de x y no es x: que está estrictamente arriba. Con el $\exists z$, «hay algo estrictamente arriba de x»; con el $\neg$ adelante, «no hay nada estrictamente arriba de x». Eso es ser maximal, y la Guía 6, pág. 6, da esta misma fórmula como ejemplo de lo que «dice» x es maximal.

El consecuente. $\forall z(z\le x)$ dice que todo está debajo de x: ser máximo. La z de acá no es la del antecedente: aquélla está ligada por el $\exists$ y su alcance se termina con el paréntesis; ésta la liga el $\forall$ del consecuente. Se podría haber escrito $\forall w(w\le x)$ y diría lo mismo.

En castellano, entonces: en todo reticulado cuaterna, todo elemento maximal es máximo. Lo que hay que entregar es una prueba elemental: se parte de un reticulado cuaterna $(L,s,i,\le )$ fijo pero arbitrario, del que sólo se sabe que cumple los siete axiomas, y se avanza en pasos simples, cada uno justificado.

La trampa: no es obvio. En un poset cualquiera, maximal no implica máximo. En la V —un elemento abajo y dos arriba, incomparables— los dos de arriba son maximales y ninguno es máximo. Contando todos los posets de hasta cinco elementos, 4473 con los elementos rotulados, la sentencia es falsa en 3290. En los 425 que son reticulados no falla nunca. Lo que la hace verdadera es algo que los reticulados tienen y la V no.

En los cuatro reticulados, cuando x es maximal la última columna es x de punta a punta. No es casualidad: es la prueba. Y en la V, con x = p, la fila que rompe el consecuente es la de q, justo donde la columna de $xsz$ no tiene nada que poner: $p$ y $q$ no tienen supremo, ni siquiera una cota superior común.

02 · Las herramientas: un axioma y dos movidas de lógica

De los siete axiomas de la Guía 6 hace falta uno:

• AsesC, el supremo es cota superior: $\forall x\forall y(x\le xsy\wedge y\le xsy)$.

Y dos movidas que no son axiomas sino lógica, y que toda prueba elemental puede usar:

• Una hipótesis de la forma $\neg \exists z(\dots )$ se usa ofreciéndole un candidato. No dice que algo pase: dice que algo no pasa con nadie. Sirve recién cuando aparece un elemento concreto para el que, si fuera distinto, sí pasaría. Es una reducción al absurdo.
• Reemplazar iguales. Si dos términos denotan el mismo elemento, uno se puede poner en lugar del otro en cualquier sentencia que ya se tenga.

Que alcance con AsesC también se midió: sobre un conjunto de tres elementos, tomando $\le$ como cualquiera de las 512 relaciones binarias y $s$ como cualquier operación que cumpla AsesC —sin pedir nada más, ni que $\le$ sea un orden—, salen 57 558 estructuras y la sentencia vale en todas.

03 · La mariposa: el supremo es el candidato

Con a fijo pero arbitrario, suponemos que es maximal y hay que llegar a que es máximo. Las preguntas, en orden.

Primera: ¿qué hay que probar, de verdad? $\forall z(z\le a)$. Un «para todo», así que se fija otro elemento b, también arbitrario, y la meta queda en $b\le a$.

Segunda: ¿qué sé de a? Sólo que nada está estrictamente arriba. Es una negación de existencial: no da nada hasta que se le ofrece un candidato. Si apareciera un elemento arriba de a, la hipótesis obligaría a que sea a mismo.

Tercera: ¿quién es el candidato? Algo que esté arriba de a y que además tenga que ver con b, porque la meta habla de b. Algo arriba de los dos: $asb$. AsesC lo garantiza: $a\le asb$ y $b\le asb$.

Con eso se ve el final. Como $a\le asb$ y a es maximal, $asb$ no puede ser distinto de a: $asb=a$. Y entonces $b\le asb$ dice, reemplazando, $b\le a$. El supremo sube a b hasta algo que está arriba de a, y la maximalidad de a lo aplasta contra a.

Hay otro camino, y cuesta más. De $asb=a$ se podría querer saltar a $b\le a$ con $\forall x\forall y(x\le y\leftrightarrow xsy=y)$, que la Guía 6 prueba en las págs. 11 y 12. Pero esa equivalencia, tomando x como b e y como a, pide $bsa=a$, así que además haría falta la conmutatividad del supremo. Las dos son resultados de la guía, y la cátedra pide que todo resultado que se use se enuncie y se pruebe aparte. Con $b\le asb$ ya en la mano, reemplazar iguales lo hace en una línea.

04 · El escarabajo: la prueba escrita

Prueba. Sea $a\in L$ un elemento fijo pero arbitrario, y supongamos

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

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

Paso 1. El axioma AsesC, tomando x como a e y como b, nos dice que $(a\le asb\wedge b\le asb)$. En particular se da $a\le asb$, y también $b\le asb$.

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

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

Cierre. Ya que b era fijo pero arbitrario —y no figura en (H)—, hemos probado $\forall z(z\le a)$. Como lo hicimos suponiendo (H), lo que probamos es

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

Y ya que a era fijo pero arbitrario, generalizando concluimos $\forall x(\neg \exists z(x\le z\wedge \neg (z=x))\to \forall z(z\le x))$. ∎

El testigo del paso 2 es $asb$ y no $bsa$, y lo que se niega es $asb=a$ en ese orden, porque es la instancia literal de $\neg (z=a)$ con z como $asb$. Escribir $\neg (a=asb)$ no está mal, pero pide un paso más para dar vuelta la igualdad.

05 · Lo que se lleva a otros ejercicios

Un testigo que no da el enunciado, lo fabrican los axiomas. La hipótesis es una negación de existencial, y la única forma de usarla es ofrecerle un candidato. El candidato no estaba en el enunciado: lo construye AsesC con un término. El Ejercicio 6 de la lista, el de «y tapa a x», vuelve a usar la misma jugada: fabricar un supremo y mostrar que está estrictamente arriba.

El dual es otro ejercicio. El Ejercicio 5 es esta sentencia con el orden dado vuelta —minimal implica mínimo— y se prueba con AiesC en lugar de AsesC. Igual hay que escribirla entera.

La versión de posets. El Ejercicio 11 pide lo mismo en un poset, donde no hay $s$, a cambio de suponer que todo par tiene una cota superior común. Es esta misma prueba con la cota puesta como hipótesis en lugar de fabricada: en un reticulado esa hipótesis viene gratis, con $usv$ de cota. El porqué de fondo está en Maximal no es máximo, salvo que todo par tenga cota.

Lo que hace perder puntos. Probarlo con $\text{sup}(\{a,b\})$ en lugar de $asb$: eso es la prueba del inciso (a), no una elemental. Citar «en un reticulado todo maximal es máximo» o la equivalencia entre $x\le y$ y $xsy=y$ sin probarlas: son resultados de las guías, y la cátedra pide enunciarlos y probarlos aparte. Y cerrar con «como b era arbitrario» antes de haber llegado a $b\le a$, o generalizar sobre a sin haber descargado (H).

Para tener a mano

1. $\neg \exists z(x\le z\wedge \neg (z=x))$ es «x es maximal»; $\forall z(z\le x)$ es «x es máximo». Las dos z son variables distintas.
2. En un poset es falso: la V. En los 425 reticulados rotulados de hasta cinco elementos no falla nunca.
3. Un solo axioma, AsesC, tomando x como a e y como b.
4. El candidato para la hipótesis maximal es $asb$: está arriba de a, así que es a; y está arriba de b, así que $b\le a$.
5. Reemplazar iguales en $b\le asb$, no citar $x\le y\leftrightarrow xsy=y$ sin probarla.