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