números complejos


3.6 Relaciones de orden.
3.6.1 Conjuntos parcialmente ordenados. Una relación R en un conjunto A se llama un orden parcial si R es reflexiva, antisimétrica y transitiva. El conjunto A junto con el orden parcial R se llama conjunto parcialmente ordenado y se denota por (A, R).
 
Ejemplo 1.
Sea "Ì " la relación de inclusión en P(A). Esta relación es un orden parcial en P(A). Por lo tanto(P(A), Ì ) es un conjunto parcialmente ordenado.
 
 Ejemplo 2.
Sea Z + el conjunto de todos los enteros positivos. La relación "£ " es un orden parcial en Z + , como lo es también "³ ". Luego (Z + , £ ) es un conjunto parcialmente ordenado.
Ejemplo 3.
La relación de divisibilidad (b R a Û bï a) que se lee, b es divisor de a, es un orden parcial en Z + .
Ejemplo 4.
La relación "< " enZ + no es un orden parcial porque no es reflexiva.
 
 
Las ordenes parciales mas comunes son las relaciones ³ y £ en Z y N . Por esta razón cuando se habla en general de un orden parcial R en un conjunto A, a menudo se usan los símbolos ³ o £ para R. Siempre que (A, £ ) sea un conjunto parcialmente ordenado se usará el símbolo ³ para indicar el orden inverso de £ de modo que (A, ³ ) será elconjunto parcialmente ordenado dual.
 
 
Si (A, £ ) es un conjunto parcialmente ordenado, a los elementos a y b de A y B se les llama comparables si a £ b o b £ a.
 
 
Cuando un conjunto está parcialmente ordenado, no es necesario que todo par de elementos sean comparables.
 
 
Obsérvese que en el ejemplo 3, los elementos 2 y 7 no son comparables puesto que ni 2 divide a 7 ni 7divide a 2. Por tanto la palabra parcial en estos conjuntos, significa que algunos elementos podrán no ser comparables. Si cada par de elementos en un conjunto parcialmente ordenado son comparables, se dice que el conjunto es totalmente ordenado. También se dice que el conjunto es una cadena.
Ejemplo 5.
El conjunto parcialmente ordenado del ejemplo 2 está totalmente ordenado
 
 
3.6.2Grafo dirigido de un orden parcial y diagramas de Hasse. El grafo dirigido de un orden parcial (A, £ ) es una representación gráfica de dicho orden. El gráfico consiste en representar por medio de un pequeño círculo cada elemento del conjunto A. Estos círculos son llamados vértices.
Si a R b entonces se traza una línea orientada desde el círculo a hasta el b. Esta línea se denomina arista. Portanto, si R es una relación en A, las aristas en el grafo dirigido de R corresponden exactamente a los pares en R y los vértices a los elementos del conjunto A. Como un orden parcial es reflexivo, cada vértice estará conectado con si mismo. Para simplificar, se borrarán todas estas conexiones del grafo dirigido. Por ejemplo el grafo representado por (a) podrá representarse como aparece en (b).También podrán eliminarse todas las aristas que están implicadas por la propiedad transitiva. Por tanto, si a £ b y b £ c se sigue que a £ c. En este caso se omitirá la arista que va desde a hasta c; sin embargo se dibujarán las que van desde a hasta b y de b a c. Así que el grafo queda así:


También se conviene en dibujar el grafo dirigido de un orden parcial con todas las aristas apuntandohacia arriba, puesto que las flechas pueden omitirse de las aristas.
 
 
Finalmente, los círculos se reemplazan por puntos para representar los vértices. Así, el diagrama de la figura anterior tiene la como forma final:


El diagrama resultante de un orden parcial, mucho más simple que su grafo dirigido, se llamará diagrama de Hasse de un orden parcial o de un conjunto parcialmenteordenado.
Ejemplo 6.
Sea A = {1,2,3,4,12}. Examínese el orden parcial de divisibilidad de A. Esta es, si a, b Î A, a £ b sí y sólo sí aï b.
Dibuje el diagrama de Hasse del conjunto parcialmente ordenado (A, £ ).
 

Ejemplo 7.
Sea S = {a, b, c} y sea A = P(A). Dibuje el diagrama de Hasse del conjunto parcialmente ordenado A con el orden parcial "Ì ".
A = {0, S, {a}, {b}, {c}, {a, b},...