Ir ao conteúdo principal

Seção 19.1 Reticulados

Subseção 19.1.1 Conjuntos 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.

  1. La relación es refleja: \((a, a) \in P\) para todo \(a \in X\text{.}\)

  2. La relación es antisimétrica: si \((a,b) \in P\) y \((b,a) \in P\text{,}\) entonces \(a = b\text{.}\)

  3. 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.

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{.}\)

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.1.3.

\begin{tikzpicture}[scale=0.7] \draw (0,2.6) -- (0,1.6); \draw (0,-2.6) -- (0,-1.6); \draw (2,0.4) -- (2,-0.4); \draw (-2,0.4) -- (-2,-0.4); \draw (1.6,1.6) -- (0.4,2.6); \draw (-1.6,-1.6) -- (-0.4,-2.6); \draw (-1.6,1.6) -- (-0.4,2.6); \draw (1.6,-1.6) -- (0.4,-2.6); \draw (1.6,0.6) -- (0.4,-0.6); \draw (-1.6,0.6) -- (-0.4,-0.6); \draw (0.4,0.6) -- (1.6,-0.6); \draw (-0.4,0.6) -- (-1.6,-0.6); \node at (0, 3) {$\{ a, b, c \}$}; \node at (-2, 1) {$\{ a, b \}$}; \node at (0, 1) {$\{ a, c \}$}; \node at (2, 1) {$\{ b, c \}$}; \node at (-2, -1) {$\{ a \}$}; \node at (0, -1) {$\{ b \}$}; \node at (2, -1) {$\{ c \}$}; \node at (0, -3) {$\emptyset$}; \end{tikzpicture}
Figura 19.1.3. Orden parcial en \(\mathcal P( \{ a, b, c \})\)

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.

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{.}\)

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.1.5. La Figura 19.1.7 muestra el orden parcial en \(X\text{.}\)

\begin{tikzpicture}[scale=0.6] \draw (1.2,2.4) -- (0.35,3.1); \draw (-1.2,2.4) -- (-0.35,3.1); \draw (1.2,-2.4) -- (0.35,-3.1); \draw (-1.2,-2.4) -- (-0.35,-3.1); \draw (1.5,1.6) -- (1.5,0.4); \draw (-1.5,1.6) -- (-1.5,0.4); \draw (1.5,-1.6) -- (1.5,-0.4); \draw (-1.5,-1.6) -- (-1.5,-0.4); \draw (-1.1,0.2) -- (1.1,1.8); \draw (-1.1,-1.8) -- (1.1,-0.2); \node at (0, 3.5) {24}; \node at (1.5, 2) {12}; \node at (1.5, 0) {6}; \node at (1.5, -2) {3}; \node at (-1.5, 2) {8}; \node at (-1.5, 0) {4}; \node at (-1.5, -2) {2}; \node at (0, -3.5) {1}; \end{tikzpicture}
Figura 19.1.7. Un 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{.}\)

Sea \(Y = \{ 2, 3, 4, 6 \}\) contenido en el conjunto \(X\) del Ejemplo 19.1.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.

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{.}\)

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{.}\)

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\) son 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.

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

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í.

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.