Posterior: Algebras booleanas Arriba: Estructuras algebraicas básicas Anterior: Conjuntos ordenados

Retículos

Definición 2.1   Sea $(A,\leq)$ un conjunto ordenado. $A$ es un RET´iCULO INFERIOR si cualquier pareja de elementos en $A$ posee un ínfimo. $A$ es un RET´iCULO SUPERIOR si cualquier pareja de elementos en $A$ posee un supremo. $A$ es un RET´iCULO, a secas, si $A$ es, a la vez, un retículo inferior y un retículo superior.

$({\mathbb{N}}^+,\vert)$ es un retículo. Pero el conjunto unión de los divisores de $2001=3\cdot 23\cdot 29$ y de $2002=2\cdot 7\cdot 11\cdot 13$, que tiene $23=(8+16)-1$ elementos, es un retículo inferior que no es superior.

Si $A$ no es vacío, entonces su conjunto de partes $({\cal P}(A),\subset)$ es un retículo.


Sea $(A,\leq)$ un retículo. Para cualesquiera $x,y\in A$ escribamos

$$\begin{eqnarray*} \mbox{\rm Inter: }\hspace{4em} x\land y &=& \mbox{\rm Inf}(x,... ...rm Uni\'on: }\hspace{4em} x\lor y &=& \mbox{\rm Sup}(x,y) %%\\ \end{eqnarray*}$$

$\land,\lor:A^2\to A$ son pues operaciones binarias definidas en $A$.

Observación 2.1   Es evidente que las operaciones $\land,\lor:A^2\to A$ poseen las siguientes propiedades:

Asociatividad.

$\forall x,y,z\in A$:

$$\begin{array}{l@{\ \ ;\ \ }l} \begin{array}{rcl} (x\land y)... ...\lor y)\lor z &=& x\lor (y\lor z) \end{array} %%& \end{array}$$

Conmutatividad.

$\forall x,y\in A$:

$$\begin{array}{l@{\ \ ;\ \ }l} \begin{array}{rcl} x\land y &... ...{array}{rcl} x\lor y &=& y\lor x \end{array} %%& \end{array}$$

Idempotencia.

$\forall x\in A$:

$$\begin{array}{l@{\ \ ;\ \ }l} \begin{array}{rcl} x\land x &... ...\begin{array}{rcl} x\lor x &=& x \end{array} %%& \end{array}$$

Absorción.

$\forall x,y\in A$:

$$\begin{array}{l@{\ \ ;\ \ }l} \begin{array}{rcl} x\land (x\... ...ray}{rcl} x\lor (x\land y) &=& x \end{array} %%& \end{array}$$

Criterio de comparación.

$\forall x,y\in A$:

$$x\leq y \ \Leftrightarrow\ x\land y = x \ \Leftrightarrow\ x\lor y = y.$$

Las operaciones del retículo se obtienen del orden en el conjunto ordenado. También puede procederse al revés, según se enuncia en la siguiente

Proposición 2.1   Sea $(A,\land,\lor)$ una estructura algebraica tal que $\land,\lor:A^2\to A$ son operaciones binarias asociativas, conmutativas, idempotentes y que satisfacen las relaciones de ``orden'' definidas arriba. Entonces, la relación definida como

$$\forall x,y\in A:\ x\leq y \ \Leftrightarrow\ x\land y = x.$$ (1)

es de orden, con la cual $(A,\leq)$ es un retículo cuyas operaciones de unión e inter son precisamente $\lor$ y $\land$.

La demostración de esta proposición es directa de las definiciones y por ende la asignamos al lector. Primero hay que ver que la relación definida por (1) es, en efecto, reflexiva, transitiva y simétrica. Luego hay que ver que dados dos elementos $x,y\in A$, $x\land y$ es el ínfimo de esa pareja y $x\lor y$ es el supremo. $\quad\Box$

Ejemplo 2.1   $({\mathbb{Z}}^n,\leq_n)$ es un retículo con las operaciones $\land:(\mbox{\bf x},\mbox{\bf y}) \mapsto \left[\min(x_j,y_j)\right]_{j=1}^n$ y $\lor:(\mbox{\bf x},\mbox{\bf y}) \mapsto \left[\max(x_j,y_j)\right]_{j=1}^n$.

En este ejemplo, puede verse que si dos vectores $\mbox{\bf x}$, $\mbox{\bf y}$ no son comparables en ${\mathbb{Z}}^n$, entonces los segmentos $\overline{\mbox{\bf x}:\mbox{\bf y}}$ y $\overline{\mbox{\bf x}\land\mbox{\bf y}:\mbox{\bf x}\lor\mbox{\bf y}}$ son las diagonales principales de un rectángulo de dimensión $n$ con aristas paralelas a los ejes de coordenadas. $\quad\Box$

Lema 2.1   Sea $(A,\land,\lor)$ un retículo. Las siguientes relaciones son simpre verdaderas, para cualesquiera elementos involucrados en ellas:

1. $y\leq z\ \Rightarrow\ x\land y \leq x\land z\ \ \&\ \ x\lor y \leq x\lor z$.
2. $x\lor (y\land z) \leq (x\lor y)\land (x\lor z)$.
3. $x\land (y\lor z) \geq (x\land y)\lor (x\land z)$.

Demostración
1. Supongamos $y\leq z$. Se tiene: $y\land z = y$. Luego:

$$x\land y = (x\land x)\land(y\land z) = (x\land y)\land(x\land z)$$

por tanto, $x\land y \leq x\land z$. Similarmente: $y\lor z = z$. Luego:

$$x\lor z = (x\lor x)\lor(y\lor z) = (x\lor y)\lor (x\lor z)$$

por tanto, $x\lor y \leq x\lor z$.


2. Para probar esa desigualdad hay que ver que $x\lor (y\land z) \leq (x\lor y)$ y también que $x\lor (y\land z) \leq (x\lor z)$. Pero estas dos desigualdades se siguen inmediatamente del punto 1.


3. Estas desigualdades se prueban similarmente a las de 2. $\quad\Box$

Definición 2.2   Sea $(A,\land,\lor)$ un retículo. Diremos que $A$ está ACOTADO INFERIORMENTE si posee un elemento mínimo, al que denotaremos por $\mbox{\bf0}$. Diremos que $A$ está ACOTADO SUPERIORMENTE si posee un elemento máximo, al que denotaremos por $\mbox{\bf 1}$. $A$ está acotado si lo está tanto inferior como superiormente.

Por ejemplo $({\mathbb{Z}}^n,\leq_n)$ no está acotado de ninguna manera.

$({\mathbb{N}}^n,\leq_n)$ está acotado inferiormente y el elemento mínimo es $\mbox{\bf0}=[0, 0, \ldots, 0]$.

$({\mathbb{N}}^+,\vert)$ está acotado inferiormente, y su elemento mínimo es el número 1, es decir $\mbox{\bf0}=1$. En ese retículo, para cada $x\in{\mathbb{N}}^+$ el cono inferior $C_x^-$ consistente de todos los divisores de $x$ forma un subretículo acotado. En él, el mínimo es $\mbox{\bf0}=1$ y el máximo es $\mbox{\bf 1}=x$. $\quad\Box$

Naturalmente, si $(A,\land,\lor,\mbox{\bf 1},\mbox{\bf0})$ es un retículo acotado entonces $\forall x\in A$: $x\land\mbox{\bf 1}=x$ y $x\lor\mbox{\bf0}=x$. Es decir, $\mbox{\bf 1}$ y $\mbox{\bf0}$ son unidades de los operadores inter y unión respectivamente.

Definición 2.3   Sea $(A,\land,\lor,\mbox{\bf 1},\mbox{\bf0})$ un retículo acotado y sea $x\in A$ un elemento cualquiera. Un elemento $y\in A$ se dice ser un COMPLEMENTO de $x$ si se cumplen las relaciones siguientes:

$$x\land y = \mbox{\bf0}\hspace{3em} \&\hspace{3em} x\lor y = \mbox{\bf 1}.$$ (2)

En algunos retículos puede suceder que un elemento posea más de un complemento. En la figura 1.1 bosquejamos un retículo en el que cada elemento ``en la parte media'' es complemento de cualquiera otro en esa misma parte.

Figure 1.1: Retículo con elementos que poseen varios complementos.

Por otro lado, es evidente que si $y$ es complemento de $x$ entonces también $x$ es complemento de $y$. Asímismo, $\mbox{\bf0}$ es complemento de $\mbox{\bf 1}$.

Para citar otro ejemplo, en $({\mathbb{N}}^+,\vert)$ consideremos $x\in{\mathbb{N}}^+$ y su cono inferior $C_x^-$ de divisores. Si $z\in C_x^-$ es tal que $z$ y $x/z$ son primos relativos, es decir no poseen divisores comunes distintos de 1, entonces $z$ y $x/z$ son complementos, uno del otro, en el retículo $C_x^-$. $\quad\Box$

Definición 2.4   Un retículo $(A,\land,\lor)$ se dice ser DISTRIBUTIVO si posee la propiedad siguiente:
Distributividad. $\forall x,y,z\in A:$

$$\begin{eqnarray*} x\lor (y\land z) &=& (x\lor y)\land (x\lor z) \\ x\land (y\lor z) &=& (x\land y)\lor (x\land z) \end{eqnarray*}$$

Las nociones de distributividad y complementariedad están muy ligadas según se ve en el siguiente:

Lema 2.2   Sea $(A,\land,\lor,\mbox{\bf 1},\mbox{\bf0})$ un retículo acotado tal que cada elemento posee un complemento. Si $A$ es distributivo entonces cada elemento de $A$ posee un único complemento.

Demostración
Supongamos $A$ distributivo. Sea $x\in A$. Veamos que cualesquiera dos complementos de $x$ han de coincidir. En efecto, si $y$ y $y'$ satisfacen las relaciones de complementariedad (2) entonces:

$$\begin{eqnarray*} y &=& y\land \mbox{\bf 1} \\ &=& y\land (x\lor y') \\ &... ...d y') \\ &=& \mbox{\bf0}\lor (y\land y') \\ &=& y\land y' \end{eqnarray*}$$

Mutatis mutandi obtenemos $y'=y\land y'$ y en consecuencia $y=y'$.$\quad\Box$
Posterior: Algebras booleanas Arriba: Estructuras algebraicas básicas Anterior: Conjuntos ordenados