AATA Reticulados

Sección19.1Reticulados

SubsecciónConjuntos Parcialmente Ordenados

Comenzamos nuestro estudio de los reticulados y las álgebras Booleanas generalizando la idea de desigualdad. Recordemos que una relación en un conjunto $X$ es un subconjunto de $X \times X\text{.}$ Una relación $P$ en $X$ se denomina orden parcial de $X$ si satisface los siguientes axiomas.

La relación es refleja: $(a, a) \in P$ para todo $a \in X\text{.}$
La relación es antisimétrica: si $(a,b) \in P$ y $(b,a) \in P\text{,}$ entonces $a = b\text{.}$
La relación es transitiva: si $(a, b) \in P$ y $(b, c) \in P\text{,}$ entonces $(a, c) \in P\text{.}$

Usualmente escribiremos $a \preceq b$ si $(a, b) \in P$ salvo que algún símbolo esté naturalmente asociado a un orden parcial en particular, tal como $a \leq b$ para los enteros $a$ y $b\text{,}$ o $A \subset B$ para conjuntos $A$ y $B\text{.}$ Un conjunto $X$ junto a un orden parcial $\preceq$ se denomina conjunto parcialmente ordenado, o copo.

Ejemplo19.1

El conjunto de los enteros (o racionales o reales) es un conjunto parcialmente ordenado donde $a \leq b$ tiene el significado usual para dos enteros $a$ y $b$ en ${\mathbb Z}\text{.}$

Ejemplo19.2

Sea $X$ un conjunto cualquiera. Definiremos el conjunto potencia de $X$ como el conjunto de todos los subconjuntos de $X\text{.}$ Denotaremos el conjunto potencia de $X$ como ${\mathcal P}(X)\text{.}$ Por ejemplo, sea $X = \{ a, b, c \}\text{.}$ Entonces ${\mathcal P}(X)$ es el conjunto de todos los subconjuntos del conjunto $\{ a, b, c \}\text{:}$

$\begin{align*} & \emptyset & & \{ a \} & & \{ b \} & & \{ c \} &\\ & \{ a, b \} & & \{ a, c\} & &\{ b, c\} & & \{ a, b, c \}. & \end{align*}$

En el conjunto potencia de cualquier conjunto $X\text{,}$ la inclusión conjuntista, $\subset\text{,}$ es un orden parcial. Podemos representar el orden en $\{ a, b, c \}$ esquemáticamente con un diagrama como el de la Figura 19.3.

Figura19.3Orden parcial en

$\mathcal P( \{ a, b, c \})$

Ejemplo19.4

Sea $G$ un grupo. El conjunto de los subgrupos de $G$ es un conjunto parcialmente ordenado, donde el orden parcial es la inclusión conjuntista.

Ejemplo19.5

Puede haber más de un orden parcial en un conjunto dado. Podemos formar un orden parcial en ${\mathbb N}$ por $a \preceq b$ si $a \mid b\text{.}$ La relación es ciertamente refleja pues $a \mid a$ para todo $a \in {\mathbb N}\text{.}$ Si $m \mid n$ y $n \mid m\text{,}$ entonces $m = n\text{;}$ luego, la relación también es antisimétrica. La relación es transitiva, pues si $m \mid n$ y $n \mid p\text{,}$ entonces $m \mid p\text{.}$

Ejemplo19.6

Sea $X = \{ 1, 2, 3, 4, 6, 8, 12, 24 \}$ el conjunto de los divisores de 24 con el orden parcial definido en el Ejemplo 19.5. La Figura 19.7 muestra el orden parcial en $X\text{.}$

Figura19.7Un orden parcial en los divisores de 24

Sea $Y$ un subconjunto de un conjunto parcialmente ordenado $X\text{.}$ Un elemento $u$ en $X$ es una cota superior de $Y$ si $a \preceq u$ para cada elemento $a \in Y\text{.}$ Si $u$ es una cota superior de $Y$ tal que $u \preceq v$ para cualquier cota superior $v$ de $Y\text{,}$ entonces $u$ es la menor de las cotas superiores o supremo de $Y\text{.}$ Un elemento $l$ en $X$ se dice cota inferior de $Y$ si $l \preceq a$ para todo $a \in Y\text{.}$ Si $l$ es una cota inferior de $Y$ tal que $k \preceq l$ para toda cota inferior $k$ de $Y\text{,}$ entonces $l$ es la mayor cota inferior o ínfimo de $Y\text{.}$

Ejemplo19.8

Sea $Y = \{ 2, 3, 4, 6 \}$ contenido en el conjunto $X$ del Ejemplo 19.6. Entonces $Y$ tiene cotas superiores 12 y 24, con 12 una menor cota superior. La única cota inferior es 1; luego, debe ser una mayor cota inferior.

Resulta que, la mayor cota inferior y la menor cota superior resultan ser únicas cuando existen.

Teorema19.9

Sea $Y$ un subconjunto no vacío de un conjunto parcialmente ordenado $X\text{.}$ Si $Y$ tiene una menor cota superior, entonces $Y$ tiene una única menor cota superior. Si $Y$ tiene una mayor cota inferior, entonces $Y$ tiene una única mayor cota inferior.

Demostración

Sean $u_1$ y $u_2$ menores cotas superiores para $Y\text{.}$ Por la definición de menor cota superior, $u_1 \preceq u$ para toda cota superior $u$ de $Y\text{.}$ En particular, $u_1 \preceq u_2\text{.}$ Similarmente, $u_2 \preceq u_1\text{.}$ Por lo tanto, $u_1 = u_2$ por antisimetría. Un argumento similar muestra que la mayor cota inferior es única.

En muchos conjuntos parcialmente ordenados es posible definir operaciones binarias usando la menor cota superior y la mayor cota inferior de dos elementos. Un reticulado es un conjunto parcialmente ordenado $L$ tal que cada par de elementos en $L$ tiene una menor cota superior y una mayor cota inferior. La menor cota superior de $a, b \in L$ se llama el supremo de $a$ y $b$ y se denota por $a \vee b\text{.}$ La mayor cota inferior de $a, b \in L$ se llama el ínfimo de $a$ y $b$ y se denota por $a \wedge b\text{.}$

Ejemplo19.10

Sea $X$ un conjunto. Entonces el conjunto potencia de $X\text{,}$ ${\mathcal P}(X)\text{,}$ es un reticulado. Para dos conjuntos $A$ y $B$ en ${\mathcal P}(X)\text{,}$ el supremo de $A$ y $B$ es $A \cup B\text{.}$ Ciertamente $A \cup B$ es una cota superior de $A$ y $B\text{,}$ pues $A \subset A \cup B$ y $B \subset A \cup B\text{.}$ Si $C$ es algún conjunto que contiene tanto a $A$ como a $B\text{,}$ entonces $C$ contiene a $A \cup B\text{;}$ luego, $A \cup B$ es la menor de las cotas superiores de $A$ y $B\text{.}$ Similarmente, el ínfimo de $A$ y $B$ es $A \cap B\text{.}$

Ejemplo19.11

Sea $G$ un grupo y supongamos que $X$ es el conjunto de subgrupos de $G\text{.}$ Entonces $X$ es un conjunto parcialmente ordenado por inclusión conjuntista, $\subset\text{.}$ El conjunto de subgrupos de $G$ también es un reticulado. Si $H$ y $K$ so subgrupos de $G\text{,}$ el ínfimo de $H$ y $K$ es $H \cap K\text{.}$ El conjunto $H \cup K$ puede no ser un subgrupo de $G\text{.}$ Dejamos como ejercicio demostrar que el supremo de $H$ y $K$ es el subgrupo generado por $H \cup K\text{.}$

En teoría de conjuntos tenemos ciertas condiciones de dualidad. Por ejemplo, por las leyes de De Morgan, todo enunciado sobre conjuntos que sea válido para $(A \cup B)'$ también debe ser válido para $A' \cap B'\text{.}$ También tenemos un principio de dualidad para reticulados.

Axioma19.12Principio de Dualidad

Cualquier enunciado que sea verdadero para todos los reticulados, sigue siendo verdadero se reemplazamos $\preceq$ por $\succeq$ e intercambiamos $\vee$ y $\wedge$ en todo el enunciado.

El siguiente teorema nos dice que un reticulado es una estructura algebraica con dos operaciones bianria que satisfacen ciertos axiomas.

Teorema19.13

Si $L$ es un reticulado, entonces las operaciones binarias $\vee$ y $\wedge$ satisfacen las siguientes propiedades para $a, b, c \in L\text{.}$

Leyes conmutativas: $a \vee b = b \vee a$ y $a \wedge b = b \wedge a\text{.}$
Leyes asociativas: $a \vee ( b \vee c) = (a \vee b) \vee c$ y $a \wedge (b \wedge c) = (a \wedge b) \wedge c\text{.}$
Leyes idempotentes: $a \vee a = a$ y $a \wedge a = a\text{.}$
Leyes de absorción: $a \vee (a \wedge b) = a$ y $a \wedge ( a \vee b ) =a\text{.}$

Demostración

Por el Principio de Dualidad, solo debemos demostrar el primer enunciado de cada parte.

(1) Por definición $a \vee b$ es el supremo de $\{ a, b\}\text{,}$ y $b \vee a$ es el supremo de $\{ b, a \}\text{;}$ pero, $\{ a, b\} = \{ b, a \}\text{.}$

(2) Mostraremos que $a \vee ( b \vee c)$ y $(a \vee b) \vee c$ son ambos ínfimos de $\{ a, b, c \}\text{.}$ Sea $d = a \vee b\text{.}$ Entonces $c \preceq d \vee c = (a \vee b) \vee c\text{.}$ También sabemos que

\begin{equation*} a \preceq a \vee b =d \preceq d \vee c = (a \vee b) \vee c. \end{equation*}

Un argumento similar demuestra que $b \preceq (a \vee b) \vee c\text{.}$ Por lo tanto, $(a \vee b) \vee c$ es una cota superior de $\{ a, b, c \}\text{.}$ Ahora debemos mostrar que $(a \vee b) \vee c$ es el supremo de $\{ a, b, c\}\text{.}$ Sea $u$ alguna cota superior para $\{ a, b, c \}\text{.}$ Entonces $a \preceq u$ y $b \preceq u\text{;}$ luego, $d = a \vee b \preceq u\text{.}$ Como $c \preceq u\text{,}$ sigue que $(a \vee b) \vee c = d \vee c \preceq u\text{.}$ Por lo tanto, $(a \vee b) \vee c$ es el supremo de $\{ a, b, c\}\text{.}$ El argumento que muestra que $a \vee ( b \vee c)$ es el supremos de $\{ a, b, c \}$ es igual. En consecuencia, $a \vee ( b \vee c) = (a \vee b) \vee c\text{.}$

(3) El supremo de $a$ y $a$ es el supremo de $\{ a \}\text{;}$ luego, $a \vee a = a\text{.}$

(4) Sea $d = a \wedge b\text{.}$ Entonces $a \preceq a \vee d\text{.}$ Por otra parte, $d = a \wedge b \preceq a\text{,}$ y así $a \vee d \preceq a\text{.}$ Por lo tanto, $a \vee ( a \wedge b) = a\text{.}$

Dado cualquier conjunto $L$ con las operaciones $\vee$ y $\wedge\text{,}$ que satisfacen las condiciones del teorema previo, es natural preguntarse si este conjunto proviene o no de un reticulado. El siguiente teorema dice que esto siempre es así.

Teorema19.14

Sea $L$ un conjunto no-vacío con dos operaciones binarias $\vee$ y $\wedge$ que satisfacen las leyes conmutativa, asociativa, idempotente, y de absorción. Podemos definir un orden parcial en $L$ por $a \preceq b$ si $a \vee b = b\text{.}$ Más aún, $L$ es un reticulado respecto a $\preceq$ si para todo $a, b \in L\text{,}$ definimos un supremo y un ínfimo de $a$ y $b$ por $a \vee b$ y $a \wedge b\text{,}$ respectivamente.

Demostración

Mostraremos primero que $L$ es un conjunto parcialmente ordenado por $\preceq\text{.}$ Como $a \vee a = a\text{,}$ $a \preceq a$ y tenemos que $\preceq$ es refleja. Para mostrar que $\preceq$ es antisimétrica, sean $a \preceq b$ y $b \preceq a\text{.}$ Entonces $a \vee b = b$ y $b \vee a = a\text{.}$ Por la ley conmutativa, $b = a \vee b = b \vee a = a\text{.}$ Finalmente, debemos mostrar que $\preceq$ es transitiva. Sean $a \preceq b$ y $b \preceq c\text{.}$ Entonces $a \vee b = b$ y $b \vee c = c\text{.}$ Luego,

\begin{equation*} a \vee c = a \vee (b \vee c ) = ( a \vee b) \vee c = b \vee c = c, \end{equation*}

y $a \preceq c\text{.}$

Para mostrar que $L$ es un reticulado, debemos demostrar que $a \vee b$ y $a \wedge b$ son, respectivamente, el supremo y el ínfimo de $a$ y $b\text{.}$ Como $a=(a \vee b) \wedge a = a \wedge (a \vee b)\text{,}$ concluimos que $a \preceq a \vee b\text{.}$ Similarmente, $b \preceq a \vee b\text{.}$ Por lo tanto, $a \vee b$ es una cota superior para $a$ y $b\text{.}$ Sea $u$ cualquier cota superior para $a$ y $b\text{.}$ Entonces $a \preceq u$ y $b \preceq u\text{.}$ Pero $a \vee b \preceq u$ pues

\begin{equation*} (a \vee b) \vee u = a \vee (b \vee u) = a \vee u = u. \end{equation*}

La demostración de que $a \wedge b$ es el ínfimo de $a$ y $b$ se deja como ejercicio.