El complemento · Lógica

Un complemento de $x$ es un elemento que junto con $x$ sube hasta el $1$ y baja hasta el $0$ . La definición no dice cuántos hay, y la respuesta depende del reticulado: en una cadena el elemento del medio no tiene ninguno, en el rombo cada elemento tiene exactamente uno, y en el diamante cada elemento del medio tiene dos. La distributividad es lo que pone un techo: en un reticulado distributivo hay a lo sumo uno, y de ahí salen la operación $c$ bien definida y las leyes de De Morgan del álgebra de Boole.

01 · Primero hacen falta el 0 y el 1

El complemento se define con el $0$ y el $1$ , así que vive en un reticulado acotado: una 5-upla $(L, s, i, 0, 1)$ tal que $(L, s, i)$ es un reticulado terna, $0, 1 \in L$ , y se cumplen

(I8) 0 s x = x (I9) x s 1 = 1 para cada x \in L

En el orden asociado, (I8) dice $0 \leq x$ y (I9) dice $x \leq 1$ : el $0$ es el mínimo y el $1$ el máximo. Las versiones con el ínfimo, $0 i x = 0$ y $x i 1 = x$ , no son axiomas sino teoremas: la primera es el Ejercicio 1 de la Guía 5, y las dos salen de que $u \leq v$ equivale a $u i v = u$ . Todo reticulado finito tiene mínimo y máximo, así que todos los de esta nota son acotados: el $0$ es su mínimo y el $1$ , su máximo. Que esos dos elementos sean un dato de la upla y no algo que se lee del dibujo es la tesis de Complementar es elegir.

02 · La definición

Sea $(L, s, i, 0, 1)$ un reticulado acotado y $a \in L$ . Un elemento $b \in L$ es un complemento de $a$ cuando

a s b = 1 y a i b = 0

Son dos ecuaciones y tienen que valer las dos. Como $s$ e $i$ son conmutativas, la relación es simétrica: si $b$ es complemento de $a$ , $a$ es complemento de $b$ . Y la Guía 5 avisa desde la definición que $b$ «puede no ser único».

El 0 y el 1 son complementos uno del otro, y de nadie más. Es el Ejercicio 5 de la Guía 5. Que $0 s 1 = 1$ y $0 i 1 = 0$ es (I9) con $x = 0$ y el Ejercicio 1 con $x = 1$ . Si $1$ es complemento de $a$ , entonces $a i 1 = 0$ , pero $a i 1 = a$ , así que $a = 0$ . Si $a$ es complemento de $0$ , entonces $0 s a = 1$ , pero $0 s a = a$ por (I8), así que $a = 1$ .

Nadie es complemento de sí mismo, salvo en el reticulado de un solo elemento. Si $a s a = 1$ y $a i a = 0$ , como $a s a = a = a i a$ , queda $0 = a = 1$ , y entonces $x = x i 1 = x i 0 = 0$ para todo $x$ .

03 · Ninguno, uno o varios

Con cuatro reticulados chicos se ven los tres casos. Para buscar los complementos de $a$ conviene pensar las dos ecuaciones como dos filtros: los $b$ que con $a$ llegan al $1$ , y los que con $a$ bajan al $0$ . Los complementos son los que pasan los dos.

La cadena de tres, $0 < m < 1$ : ninguno. En una cadena el supremo de dos elementos es el mayor, así que $m s b = 1$ obliga a $b = 1$ . Pero $m i 1 = m \neq 0$ . El $m$ no tiene complemento. En cualquier cadena pasa lo mismo: sólo el $0$ y el $1$ tienen.

El rombo, $0 < p, q < 1$ con $p$ y $q$ incomparables: exactamente uno. $p s q = 1$ y $p i q = 0$ , así que $q$ es complemento de $p$ . Es el único: $p s 0 = p$ , $p s p = p$ y $p i 1 = p$ , ninguno de los otros pasa los dos filtros.

El diamante $M_{3}$ , $0 < p, q, r < 1$ con los tres del medio incomparables: dos. $p s q = 1$ , $p i q = 0$ , y lo mismo con $r$ . El $p$ tiene dos complementos, $q$ y $r$ , y por simetría cada elemento del medio tiene dos. Es el ejemplo que pide el Ejercicio 4 de la Guía 5; en su versión con números, el diamante ${1, 2, 3, 5, 30}$ ordenado por divisibilidad, el $2$ tiene como complementos al $3$ y al $5$ .

El pentágono $N_{5}$ , $0 < a < b < 1$ y $d$ al costado: dos, y comparables entre sí. El $d$ es incomparable con $a$ y con $b$ , así que $d s a = d s b = 1$ y $d i a = d i b = 0$ : los complementos de $d$ son $a$ y $b$ , y $a < b$ . En cambio $a$ y $b$ tienen uno solo, el $d$ .

Un caso más, el del Ejercicio 25 de la lista: si hay un elemento $m \neq 0$ que está debajo de todos los elementos no nulos —un único átomo—, sólo el $0$ y el $1$ tienen complemento. Si $x \neq 0$ y $u \neq 0$ , entonces $m \leq x$ y $m \leq u$ , así que $m \leq x i u$ y $x i u \neq 0$ . Un complemento de un $x \neq 0$ tiene que ser el $0$ , y entonces $x = x s 0 = 1$ .

En los reticulados distributivos del selector —la cadena, el rombo, los divisores de 12 y de 30, el del átomo único— la respuesta nunca es «más de uno». En el diamante, el pentágono y el hexágono sí. Y cuando ya tocaste todos los elementos aparece cuántas operaciones $c$ admite el reticulado: cero si algún elemento se quedó sin complemento.

El patrón no es de estos ocho. Medido sobre todos los reticulados de hasta siete elementos, contados salvo isomorfismo:

elementos	reticulados	complementados	distributivos	los dos	con varios complementos
1	1	1	1	1	0
2	1	1	1	1	0
3	1	0	1	0	0
4	2	1	2	1	0
5	5	2	3	0	2
6	15	6	5	0	6
hasta 6	25	11	13	3	8
7	53	18	8	0	24

«Con varios complementos» cuenta los reticulados en los que algún elemento tiene más de uno. Las columnas de reticulados y de distributivos coinciden con las tablas conocidas —1, 1, 1, 2, 5, 15, 53 y 1, 1, 1, 2, 3, 5, 8—, que es el control de que la enumeración no se salteó ninguno. Tres cosas se leen de la tabla. Con hasta cuatro elementos ningún elemento tiene dos complementos: los primeros aparecen con cinco, y son justo $M_{3}$ y $N_{5}$ . Ningún distributivo tiene un elemento con dos, en ninguna fila: eso es un teorema, y es la sección 05. Y entre los complementados que no son distributivos —2, 6 y 18— no hay ninguno en el que todos los complementos sean únicos.

04 · El reticulado complementado y la operación c

Que cada elemento tenga algún complemento es una propiedad del reticulado acotado. Un reticulado complementado es otra cosa: una 6-upla $(L, s, i, c, 0, 1)$ donde $(L, s, i, 0, 1)$ es acotado y $c$ es una operación unaria sobre $L$ tal que

(I10) x s x^{c} = 1 (I11) x i x^{c} = 0 para cada x \in L

O sea, $x^{c}$ es un complemento de $x$ , elegido. La guía escribe $x^{c}$ ; la lista, $c (x)$ : es la misma operación. Si algún elemento no tiene complemento no hay ninguna $c$ posible, y si cada elemento $x$ tiene $k_{x}$ complementos hay exactamente $\prod k_{x}$ operaciones $c$ , una por cada manera de elegir. En el diamante $1 \cdot 2 \cdot 2 \cdot 2 \cdot 1 = 8$ , que es el Ejercicio 6 de la Guía 5; en el pentágono, $2$ ; en el hexágono del selector, $16$ ; en el rombo, $1$ .

Por eso, en un reticulado complementado cualquiera, saber que $u$ es complemento de $x$ no dice que $u = x^{c}$ : en el diamante con $2^{c} = 3$ , el $5$ también es complemento del $2$ y no es $2^{c}$ . Lo que hace falta para pasar de «un complemento» a «el complemento» es la sección siguiente.

05 · En un distributivo, a lo sumo uno

Es el Lema 10 de la Guía 5 (el Ejercicio 9 lo completa, y el 13 de la lista lo pide como prueba elemental): si $(L, s, i, 0, 1)$ es distributivo, todo elemento tiene a lo sumo un complemento.

Prueba. Sean $b$ y $b^{'}$ complementos de $a$ : $a s b = a s b^{'} = 1$ y $a i b = a i b^{'} = 0$ . La idea es mostrar que $b \leq b^{'}$ y, cambiando los papeles, que $b^{'} \leq b$ .

Paso 1: multiplicar por el 1. $b = b i 1$ , porque $b \leq 1$ .
Paso 2: el 1 es $a s b^{'}$ . $b i 1 = b i (a s b^{'})$ , por hipótesis.
Paso 3: distribuir. $b i (a s b^{'}) = (b i a) s (b i b^{'})$ , por Dis1.
Paso 4: el primer término es el 0. $b i a = a i b = 0$ , y $0 s (b i b^{'}) = b i b^{'}$ por (I8).

Queda $b = b i b^{'}$ , que es $b \leq b^{'}$ . La misma cuenta con $b$ y $b^{'}$ intercambiados da $b^{'} \leq b$ , y por antisimetría $b = b^{'}$ . ∎

Sin Dis1 la cuenta se corta en el paso 3, y el diamante muestra dónde. Con $a = p$ , $b = q$ y $b^{'} = r$ : $q i (p s r) = q i 1 = q$ , pero $(q i p) s (q i r) = 0 s 0 = 0$ . El paso 3 cambia $q$ por $0$ , y la cadena deja de probar nada.

La consecuencia: $c$ queda bien definida. En un reticulado complementado distributivo cada elemento tiene un complemento —porque hay una $c$ — y a lo sumo uno, así que tiene exactamente uno, y hay una sola operación $c$ posible. Ahí sí, si $x s u = 1$ y $x i u = 0$ , entonces $u = x^{c}$ : es el Ejercicio 14 de la lista, y se prueba aplicando el Lema 10 a $u$ y a $x^{c}$ , que son dos complementos de $x$ .

La vuelta no es un teorema de la guía. En los reticulados finitos vale —un finito en el que cada elemento tiene exactamente un complemento es distributivo, y la tabla de arriba lo muestra hasta siete elementos—, pero Dilworth probó en 1945 que hay reticulados infinitos con complementos únicos que no son distributivos.

06 · De Morgan, en un distributivo complementado

El Teorema 12 de la Guía 5 junta lo que se gana con la unicidad. En un reticulado complementado distributivo, para todos $a, b$ :

{(a i b)}^{c} = a^{c} s b^{c} {(a s b)}^{c} = a^{c} i b^{c} a^{c c} = a

Las tres se prueban igual, y la forma de la prueba es lo que conviene llevarse: no se calcula ${(a i b)}^{c}$ ; se muestra que $a^{c} s b^{c}$ es un complemento de $a i b$ , y la unicidad hace el resto. Para la primera ley, con $w = a^{c} s b^{c}$ , hay que verificar las dos ecuaciones.

Arriba: $(a i b) s w = 1$ . Por Dis2, $(a i b) s w = (a s w) i (b s w)$ . Y $a s w = (a s a^{c}) s b^{c} = 1 s b^{c} = 1$ , con la asociativa y (I10); igual $b s w = 1$ . Queda $1 i 1 = 1$ .

Abajo: $(a i b) i w = 0$ . Por Dis1, $(a i b) i w = ((a i b) i a^{c}) s ((a i b) i b^{c})$ . El primero es $(a i a^{c}) i b = 0 i b = 0$ , con (I11); el segundo, $a i (b i b^{c}) = a i 0 = 0$ . Queda $0 s 0 = 0$ .

Así que $w$ es un complemento de $a i b$ , y ${(a i b)}^{c}$ también lo es por (I10) y (I11). Por el Lema 10 son iguales. La segunda ley es la misma cuenta con $s$ e $i$ intercambiados. La tercera ni siquiera pide cuentas: $a$ es complemento de $a^{c}$ por simetría, y $a^{c c}$ también, así que son iguales. La primera ley es el Ejercicio 15 de la lista.

07 · Sin distributividad, De Morgan depende de qué c elijas

El Ejercicio 12 de la Guía 5 pregunta si el Teorema 12 vale en cualquier reticulado complementado. No, y lo interesante es cómo falla: no falla siempre. Recorriendo todas las operaciones $c$ de cada reticulado, cuántas cumplen las dos leyes de De Morgan, cuántas cumplen $a^{c c} = a$ , y cuántas cumplen los cinco ítems del teorema (los otros dos son $a i b = 0 ⟺ b \leq a^{c}$ y $a \leq b ⟺ b^{c} \leq a^{c}$ ):

reticulado	operaciones c	De Morgan	a^cc = a	los cinco
diamante M₃	8	2	0	0
pentágono N₅	2	2	0	0
hexágono	16	9	2	0
divisores de 30	1	1	1	1

En el diamante, De Morgan vale para las dos elecciones «cíclicas», $2^{c} = 3, 3^{c} = 5, 5^{c} = 2$ y su inversa, y falla en las otras seis; ninguna es involutiva, porque con tres elementos del medio no se pueden aparear todos. En el pentágono las dos operaciones cumplen De Morgan, y sin embargo ninguna cumple $a^{c c} = a$ : $a^{c} = b^{c} = d$ , así que $a^{c c} = b^{c c} = d^{c}$ , y un mismo elemento no puede ser $a$ y $b$ .

El hexágono —dos cadenas $0 < a < b < 1$ y $0 < p < q < 1$ — es el caso más fino. Con $a^{c} = q$ , $b^{c} = p$ , $p^{c} = b$ y $q^{c} = a$ valen las dos leyes de De Morgan, $a^{c c} = a$ y la del orden, y aun así no es distributivo: $b i (a s p) = b i 1 = b$ y $(b i a) s (b i p) = a s 0 = a$ . Lo que falla es el ítem que queda: $b i q = 0$ y $q ≰ p = b^{c}$ . De Morgan no caracteriza a las álgebras de Boole; en ellas está garantizado, y fuera de ellas es cuestión de suerte en la elección.

08 · El álgebra de Boole: donde se junta todo

Un álgebra de Boole es un reticulado complementado distributivo. Es el caso en el que todo lo anterior funciona a la vez: cada elemento tiene exactamente un complemento, la operación $c$ es la única posible, «un complemento de $x$ » y « $x^{c}$ » dicen lo mismo, y valen las dos leyes de De Morgan, $a^{c c} = a$ , $a i b = 0 ⟺ b \leq a^{c}$ y $a \leq b ⟺ b^{c} \leq a^{c}$ .

Los ejemplos de la guía: $(P (X), \cup, \cap, c, \emptyset, X)$ con el complemento de conjuntos; el de un elemento, en el que $0 = 1$ y $1^{c} = 1$ ; el de dos, ${0, 1}$ con $\max$ y $\min$ ; y los divisores de 10 con $mcm$ , $mcd$ y $x^{c} = 10 / x$ . Los divisores de 30 también lo son, con $x^{c} = 30 / x$ : el selector de arriba lo deja comprobar. Los de 12, no: el $2$ y el $6$ no tienen complemento, aunque es distributivo.

En la tabla de la sección 03, la columna «los dos» marca exactamente las álgebras de Boole: entre los 78 reticulados de hasta siete elementos hay tres, de uno, dos y cuatro elementos. La siguiente tiene ocho, como los divisores de 30.

Para tener a mano

$b$ es complemento de $a$ si $a s b = 1$ y $a i b = 0$ , las dos. Es simétrico. El $0$ y el $1$ son complementos uno del otro y de nadie más.
Puede haber ninguno (el medio de una cadena), uno (el rombo) o varios ( $M_{3}$ , $N_{5}$ ), y dos complementos del mismo elemento pueden ser comparables.
Un reticulado complementado es una 6-upla: $c$ elige un complemento para cada elemento, y hay $\prod k_{x}$ elecciones. En $M_{3}$ , ocho.
Distributivo ⟹ a lo sumo un complemento (Lema 10): $b = b i 1 = b i (a s b^{'}) = (b i a) s (b i b^{'}) = b i b^{'}$ . El paso que usa Dis1 es el tercero.
En un distributivo complementado, $x s u = 1$ y $x i u = 0$ dan $u = x^{c}$ . Fuera de ahí, no.
De Morgan se prueba mostrando que $a^{c} s b^{c}$ es un complemento de $a i b$ y usando la unicidad. Sin distributividad puede valer o no según la $c$ elegida.
Álgebra de Boole = complementado + distributivo. Hasta siete elementos hay tres: las de 1, 2 y 4.