Posterior: Retículos Arriba: Estructuras algebraicas básicas Anterior: Estructuras algebraicas básicas

Conjuntos ordenados

Definición 1.1   Sea $A$ un conjunto no vacío y sea ``$\leq$''$\subset A\times A$ una relación.
Se dice que $\leq$ es un ORDEN, o una RELACIÓN DE ORDEN, si cumple con las siguientes propiedades:

Reflexividad:

$\forall a\in A:\ a\leq a$.

Transitividad:

$\forall a,b,c\in A:\ (a\leq b)\;\&\; (b\leq c)\ \Rightarrow\ a\leq c$.

Antisimetría:

$\forall a,b\in A:\ (a\leq b)\;\&\; (b\leq a)\ \Rightarrow\ a=b$.

En tal caso la estructura $(A,\leq)$ se dice ser un CONJUNTO ORDENADO.
La relación ``$<$'' tal que: $\forall a,b\in A:\ a<b\ \Leftrightarrow\ (a\leq b)\;\&\; (a\not=b)$, se dice ser el ORDEN ESTRICTO inducido por $\leq$.
Si además se cumple la propiedad:

Tricotomía:

$\forall a,b\in A:\ (a< b)\;\mbox{\it\'o }\; (a=b)\mbox{\it\'o }\; (b< a)$.

entonces el orden se dice ser LINEAL o TOTAL.

Algunos autores suelen llamar ORDEN PARCIAL a todo orden que no sea total. Así que aquí hemos de considerar sólo órdenes parciales a menos de que explícitamente indiquemos que se trata de órdenes totales, cuando nos refiramos a tales órdenes.

Ejemplo 1.1   Sea $A={\mathbb{R}}$ y sea $\leq$ el orden usual de ${\mathbb{R}}$. $({\mathbb{R}},\leq)$ es un orden total.

En efecto, un número real distinto de 0 cuya parte entera es un número natural se dice ser positivo y un número real cuyo inverso aditivo es positivo se dice ser negativo. Así tenemos que todo real o bien es negativo o es cero o es positivo. Para cualesquiera dos reales $x,y\in {\mathbb{R}}$ se tiene: $x\leq y\ \Leftrightarrow\ y-x$ no es negativo. Esta relación es un orden total. $\quad\Box$

Evidentemente, si $(A,\leq_A)$ es ordenado y $B\subset A$ es un subconjunto de $A$, entonces $(B,\leq_B)$ es ordenado, donde

$$\forall a,b\in B:\ a\leq_B b\ \Leftrightarrow\ a\leq_A b.$$

$\leq_B$ se dice ser el ORDEN HEREDADO o INDUCIDO por $\leq_A$ en $B$. Así, por ejemplo, los conjuntos de números naturales, enteros y racionales ${\mathbb{N}}$, ${\mathbb{Z}}$ y ${\mathbb{Q}}$ respectivamente, son ordenados con los correspondientes órdenes inducidos por el orden usual de ${\mathbb{R}}$.

Definición 1.2   Sean $(A_1,\leq_1)$ y $(A_2,\leq_2)$ dos conjuntos ordenados. El ORDEN PRODUCTO es la relación definida en el producto cartesiano $A_1\times A_2$ siguiente: $\forall (a_1,a_2),(b_1,b_2)\in A_1\times A_2$,

$$(a_1,a_2)\leq_{12}(b_1,b_2)\ \Leftrightarrow\ \left(a_1\leq_1 b_1\right) \;\&\; \left(a_2\leq_2 b_2\right)$$ (1)

Resulta que $(A_1\times A_2,\leq_{12})$ es, en efecto, un conjunto ordenado.

Ejemplo 1.2   $({\mathbb{R}}^n,\leq_n)$, donde $\leq_n$ es la potencia $n$-ésima del orden usual de ${\mathbb{R}}$, es un conjunto ordenado.

Explícitamente, se tiene:

$$\forall \mbox{\bf x},\mbox{\bf y}\in {\mathbb{R}}^n:\ \mbox{\... ...f y}\ \Leftrightarrow\ \forall j\leq n\left(x_j\leq y_j\right).$$

$\quad\Box$

Ejemplo 1.3 (Algebra de conjuntos)   Sea $A$ un conjunto no vacío, y sea ${\cal P}(A)=\{B\vert B\subset A\}$ su CONJUNTO DE PARTES. Entonces $({\cal P}(A),\subset)$ es un conjunto ordenado.

Ejemplo 1.4 (Divisibilidad)   Sea ${\mathbb{N}}^+={\mathbb{N}}-\{0\}$ el conjunto de números naturales positivos. Para $x,y\in{\mathbb{N}}^+$ decimos que $x$ DIVIDE a $y$, y escribimos $x\vert y$, si $\exists z\in{\mathbb{N}}^+$: $y=xz$. $({\mathbb{N}}^+,\vert)$ es un conjunto ordenado.

Ejemplo 1.5 (Gráficas dirigidas)   Sea $G=(V,A)$ una gráfica dirigida, sin ciclos. En el conjunto de vértices, digamos que $v_1\leq_G v_2$ si es que hay un camino en $G$ que se inicia en $v_1$ y llega a $v_2$. $(V,\leq_G)$ es un conjunto ordenado, que se dice ser DETERMINADO por $G$.

Sea $(A,\leq)$ un conjunto ordenado y sean $B\subset A$ y $x\in A$ un subconjunto y un elemento de $A$ respectivamente.

$x$ es una COTA SUPERIOR de $B$

si $\forall b\in B$: $b\leq x$.

$x$ es una COTA INFERIOR de $B$

si $\forall b\in B$: $x\leq b$.

$x$ es un elemento MAXIMAL de $B$

si $x\in B$ y no hay elemento en $B$ que lo supere: $\forall b\in B$, $x\leq b\Rightarrow x=b$.

$x$ es un elemento MINIMAL de $B$

si $x\in B$ y no hay elemento en $B$ por debajo de él: $\forall b\in B$, $b\leq x\Rightarrow x=b$.

$x$ es el MÁXIMO de $B$

si $x\in B$ y es una cota superior de $B$.

$x$ es el M´iNIMO de $B$

si $x\in B$ y es una cota inferior de $B$.

$x$ es el SUPREMO de $B$

si $x$ es la mínima de las cotas superiores de $B$.

$x$ es el íNFIMO de $B$

si $x$ es la máxima de las cotas inferiores de $B$.

De estas definiciones, se sigue inmediatamente que si sólo hay un elemento maximal entonces ése ha de ser un máximo. Si hay más de un elemento maximal entonces no existirá un máximo. Si un máximo existe, entonces ése ha de ser un supremo. Sin embargo, puede haber supremos aunque no existan máximos. Los correspondientes enunciados duales también se siguen inmdediatamente.

Para un elemento $a\in A$ el CONO SUPERIOR de $a$ es $C^+_a=\{b\in A\vert a\leq b\}$, y el CONO INFERIOR de $a$ es $C^-_a=\{b\in A\vert b\leq a\}$. Los elementos SUCESORES de $a$ son los minimales del conjunto $C^+_a-\{a\}$ y los elementos ANTECESORES de $a$ son los maximales del conjunto $C^-_a-\{a\}$.

El conjunto ordenado $(A,\leq)$ se dice ser DISCRETO si todo elemento en él o es maximal o el cono superior de ese elemento es la unión de los conos de sus sucesores.

Para ilustrar las nociones anteriores, consideremos el conjunto ordenado $({\mathbb{N}}^+,\vert)$. El número 1 es un mínimo y no hay máximos. Para un número $x$ dado, el cono superior consta de sus múltiplos y el cono inferior de sus divisores. El supremo del conjunto formado por dos números es su mínimo común múltiplo y su ínfimo es su máximo común divisor. Los sucesores del número 1 son los números primos. Un sucesor de un número $x$ es de la forma $px$ donde $p$ es un primo, y un antecesor es de la forma $x/p$ donde $p$ es un primo que divida a $x$.

Definición 1.3   Sea $(A,\leq)$ un conjunto ordenado discreto. Su DIAGRAMA es la gráfica dirigida $G=(A, E)$ donde $E$ consta de los arcos que unen a elementos con sus sucesores: $\forall x,y\in A$,

$$\begin{eqnarray*} (x,y)\in E &\Leftrightarrow& y\mbox{\rm es sucesor de }x \\ &\Leftrightarrow& x\mbox{\rm es antecesor de }y. \end{eqnarray*}$$

Naturalmente, $(A,\leq)$ coincide con el orden determinado por su propio diagrama.
Posterior: Retículos Arriba: Estructuras algebraicas básicas Anterior: Estructuras algebraicas básicas