Dos complementos de lo mismo son uno solo

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

Dis1 \to \forall x \forall u \forall v ((x s u = 1 \land x i u = 0 \land x s v = 1 \land x i v = 0) \to u = v)

». Es el Lema 10 de la Guía 5 —en un reticulado acotado distributivo, todo elemento tiene a lo sumo un complemento— y el Ejercicio 22 de la Guía 7, que pide pasarlo a prueba elemental. La Guía 5 deja la prueba empezada: $b = b i 1 = b i (a s c) = \dots$ . Esos dos primeros pasos son toda la idea. Lo que cuesta es escribir el resto sin usar nada que el tipo no tenga.

01 · Antes de probar: qué dice y con qué se cuenta

Qué dice. Si el reticulado cumple Dis1, dos complementos $u$ y $v$ del mismo $x$ son iguales. O sea, cada elemento tiene a lo sumo un complemento. No dice que tenga uno: en la cadena $0 < m < 1$ , que es distributiva, $m$ no tiene ninguno, y la sentencia vale igual porque el antecedente del medio nunca se cumple para $x$ como $m$ .

El tipo es acotados. Hay dos operaciones, $s$ e $i$ , y dos nombres de constante, $0$ y $1$ , que son del tipo: por eso la sentencia es pura aunque los nombre. No hay $\leq$ ni operación de complemento. Los axiomas son los ocho de reticulados terna —(I1) a (I7), con la idempotencia partida en dos— más dos:

(I8): $\forall x (0 s x = x)$ .
(I9): $\forall x (x s 1 = 1)$ .

Las dos trampas. La primera: los dos axiomas nuevos están escritos con $s$ , y la prueba necesita $x i 1 = x$ , que no es un axioma. Hay que probarla antes, dentro de la misma prueba. La segunda: Dis1 es el antecedente, una hipótesis. Con ella sola no se tiene Dis2: usar Dis2 exige escribir antes la prueba de (Dis1 → Dis2), que son veintinueve líneas.

02 · Las herramientas

De los diez axiomas, la prueba usa cuatro, más la hipótesis:

(I3), conmutatividad del ínfimo: $\forall x \forall y (x i y = y i x)$ .
(I7), absorción: $\forall x \forall y (x i (x s y) = x)$ . Sólo para probar $x i 1 = x$ .
(I8): $\forall x (0 s x = x)$ .
(I9): $\forall x (x s 1 = 1)$ . También sólo para $x i 1 = x$ .
Dis1, la hipótesis: $\forall x \forall y \forall z (x i (y s z) = (x i y) s (x i z))$ .

Y las cuatro igualdades del antecedente del medio, que una vez supuestas son tan usables como un axioma: $a s b = 1$ , $a i b = 0$ , $a s c = 1$ , $a i c = 0$ .

03 · La mariposa: escribir el 1 con el otro complemento

Hay que llegar de $b$ a $c$ , y no hay ninguna igualdad que las relacione directamente: las cuatro hipótesis hablan de $a$ con cada una por separado. La pregunta es cómo hacer aparecer $c$ en una expresión de $b$ .

Primera pregunta: ¿dónde está escondida $c$ ? En el $1$ . La hipótesis $a s c = 1$ leída al revés dice que $1$ se puede escribir como $a s c$ . Y el $1$ se le puede pegar a $b$ sin cambiarlo, porque $b = b i 1$ . Juntando:

b = b i 1 = b i (a s c)

Segunda pregunta: ¿qué se hace con un ínfimo de un supremo? Se abre con Dis1: $b i (a s c) = (b i a) s (b i c)$ . Es el único paso que la usa.

Tercera pregunta: ¿qué se cae? $b i a$ es $a i b$ , que es $0$ por hipótesis, y $0$ es neutro para el supremo. Queda $b = b i c$ .

La misma cuenta con los papeles de $b$ y $c$ cambiados da $c = c i b$ , y la conmutatividad del ínfimo cierra: $b = b i c = c i b = c$ . Las dos cuentas no son simétricas por casualidad: la hipótesis es simétrica en $u$ y $v$ , y por eso alcanza con una idea.

El otro camino. Se podía arrancar por el otro lado: $b = b s 0 = b s (a i c)$ , abrir con Dis2, y llegar a $b = b s c$ . Funciona, pero Dis2 no es la hipótesis: habría que anteponer la prueba entera de (Dis1 → Dis2), y además probar $1 i t = t$ para descargar el $1$ que sale. Con Dis1 la cuenta es directa.

04 · Sin distributividad: el diamante

La hipótesis no está de adorno. En el diamante $M_{3}$ —un mínimo, un máximo y tres elementos incomparables en el medio, el mismo del Ejercicio 2— cualquier par de los del medio tiene supremo $1$ e ínfimo $0$ . Así, $p$ tiene dos complementos, $q$ y $r$ , y lo mismo cada uno de los otros dos.

Corriendo la cuenta de la mariposa ahí, con $x$ como $p$ , $u$ como $q$ y $v$ como $r$ : $q i 1 = q$ y $q i (p s r) = q i 1 = q$ , así que los dos primeros pasos valen. El tercero no: $(q i p) s (q i r) = 0 s 0 = 0$ . Se rompe exactamente el paso de Dis1, y ningún otro. Abajo se corre en otros reticulados.

En el pentágono $N_{5}$ pasa con un solo elemento: $c$ , el que está solo en su lado, tiene de complementos a $a$ y a $b$ . Ahí se rompe una sola de las dos cuentas. La de $a$ llega bien a $a = a i b$ , que es cierto porque $a$ está debajo de $b$ ; la que falla es la de $b$ , y otra vez en el renglón de Dis1.

Medido sobre los 78 reticulados de hasta siete elementos, contando una vez cada clase de isomorfismo: los 21 distributivos no tienen ningún elemento con dos complementos, como dice el ejercicio, y la sentencia entera, evaluada fórmula por fórmula, es verdadera en los 78. En los otros 57 hay 490 elecciones de $x, u, v$ con $u \neq v$ que cumplen las cuatro hipótesis. En las 490 el único renglón que se rompe es el de Dis1: en las dos cuentas en 282 casos, y en una sola en 208. Los primeros con un elemento de dos complementos tienen cinco elementos, y son justo los dos no distributivos de ese tamaño, $M_{3}$ y $N_{5}$ .

La vuelta no vale. De los 57 no distributivos, 32 tienen algún elemento con dos o más complementos, y 25 no. Los más chicos de esos tienen seis elementos —son cuatro— y uno está en el selector: el diamante con un techo encima. Ahí los tres del medio tienen supremo $t$ y no $1$ , así que no tienen ningún complemento, y el reticulado sigue siendo no distributivo. Complemento único no alcanza para distributivo.

05 · El escarabajo: la prueba escrita

Primero va la prueba de $\forall x (x i 1 = x)$ , porque la de abajo la usa y no es un axioma. Después la prueba del enunciado, con la segunda cuenta escrita entera.

Prueba. Sea $(L, s, i, 0, 1)$ un reticulado acotado fijo pero arbitrario.

Paso previo: $\forall x (x i 1 = x)$ . Sea $e \in L$ fijo pero arbitrario. El axioma $\forall x (x s 1 = 1)$ , tomando $x$ como $e$ , nos dice que $e s 1 = 1$ . El axioma $\forall x \forall y (x i (x s y) = x)$ , tomando $x$ como $e$ e $y$ como $1$ , nos dice que $e i (e s 1) = e$ . Reemplazando en esta igualdad $e s 1$ por $1$ , obtenemos $e i 1 = e$ . Como $e$ era arbitrario, vale $\forall x (x i 1 = x)$ .

Ahora el enunciado. Supongamos Dis1, es decir $\forall x \forall y \forall z (x i (y s z) = (x i y) s (x i z))$ . Sean $a, b, c \in L$ fijos pero arbitrarios, y supongamos

a s b = 1 \land a i b = 0 \land a s c = 1 \land a i c = 0

Primera cuenta: $b = b i c$ .

Por $\forall x (x i 1 = x)$ , tomando $x$ como $b$ , $b i 1 = b$ ; o sea, $b = b i 1$ .
Ya que supusimos $a s c = 1$ , reemplazando $1$ por $a s c$ : $b = b i (a s c)$ .
Dis1, tomando $x$ como $b$ , $y$ como $a$ y $z$ como $c$ , nos dice que $b i (a s c) = (b i a) s (b i c)$ . Luego $b = (b i a) s (b i c)$ .
El axioma $\forall x \forall y (x i y = y i x)$ , tomando $x$ como $b$ e $y$ como $a$ , nos dice que $b i a = a i b$ , y supusimos $a i b = 0$ . Luego $b i a = 0$ , y reemplazando, $b = 0 s (b i c)$ .
El axioma $\forall x (0 s x = x)$ , tomando $x$ como $b i c$ , nos dice que $0 s (b i c) = b i c$ . Luego $b = b i c$ .

Segunda cuenta: $c = c i b$ .

Por $\forall x (x i 1 = x)$ , tomando $x$ como $c$ , $c i 1 = c$ ; o sea, $c = c i 1$ .
Ya que supusimos $a s b = 1$ , reemplazando $1$ por $a s b$ : $c = c i (a s b)$ .
Dis1, tomando $x$ como $c$ , $y$ como $a$ y $z$ como $b$ , nos dice que $c i (a s b) = (c i a) s (c i b)$ . Luego $c = (c i a) s (c i b)$ .
El axioma $\forall x \forall y (x i y = y i x)$ , tomando $x$ como $c$ e $y$ como $a$ , nos dice que $c i a = a i c$ , y supusimos $a i c = 0$ . Luego $c i a = 0$ , y reemplazando, $c = 0 s (c i b)$ .
El axioma $\forall x (0 s x = x)$ , tomando $x$ como $c i b$ , nos dice que $0 s (c i b) = c i b$ . Luego $c = c i b$ .

Cierre. El axioma $\forall x \forall y (x i y = y i x)$ , tomando $x$ como $b$ e $y$ como $c$ , nos dice que $b i c = c i b$ . Juntando las dos cuentas, $b = b i c = c i b = c$ , o sea $b = c$ . Ya que habíamos supuesto las cuatro igualdades, hemos probado

(a s b = 1 \land a i b = 0 \land a s c = 1 \land a i c = 0) \to b = c

Como $a$ , $b$ y $c$ eran fijos pero arbitrarios, generalizando vale

\forall x \forall u \forall v ((x s u = 1 \land x i u = 0 \land x s v = 1 \land x i v = 0) \to u = v)

Y como todo se dedujo suponiendo Dis1, hemos probado la sentencia del enunciado. ∎

Generalizar con Dis1 todavía supuesta es legal por la razón de siempre: Dis1 no nombra a $a$ , $b$ ni $c$ . Lo que no se puede es generalizar sobre ellas con las cuatro igualdades todavía abiertas, porque ésas sí las nombran: por eso primero se descargan, y recién después se generaliza.

06 · Lo que se lleva a otros ejercicios

Escribir una constante con la hipótesis. Una igualdad supuesta, como $a s c = 1$ , se puede usar de derecha a izquierda para meter en un término algo que no estaba. Es la jugada que destraba la prueba, y aparece cada vez que hay que relacionar dos elementos que las hipótesis sólo conectan a través de un tercero.

Los tres ejercicios siguientes. El 14 es éste con $c (x)$ en el lugar de $v$ : en reticulados complementados, $x s c (x) = 1$ y $x i c (x) = 0$ son axiomas, así que $c (x)$ es un complemento de $x$ y la misma cuenta da $u = c (x)$ . Pero la prueba tiene que estar escrita de nuevo: no se puede citar ésta. El 15 es la única excepción declarada de la lista: ahí sí se puede usar esta sentencia, y (Dis1 → Dis2), como teoremas.

Lo que hace perder puntos. Usar $x i 1 = x$ sin probarla. Usar Dis2, o $0 i x = 0$ , sin probarlas. Citar el Lema 10 de la Guía 5. Despachar la segunda cuenta con «análogamente». Escribir $\leq$ , que el tipo no tiene. Y generalizar sobre $a, b, c$ antes de descargar las cuatro igualdades.

Para tener a mano

Dice «a lo sumo un complemento», no «exactamente uno». En la cadena de tres, el del medio no tiene ninguno.
Acotados: terna más $0 s x = x$ y $x s 1 = 1$ , los dos con $s$ . $x i 1 = x$ se prueba antes, con (I9) y (I7).
La idea: $b = b i 1 = b i (a s c) = (b i a) s (b i c) = 0 s (b i c) = b i c$ . Lo mismo para $c$ , y cierra la conmutatividad.
Dis1 entra una vez por cuenta. Sin ella, en $M_{3}$ $p$ tiene dos complementos y la cuenta se rompe justo ahí.
La vuelta no vale: hay reticulados no distributivos con complementos únicos, como el diamante con techo.