Informe Mate Discreta

Orden Parcial
Un orden parcial es una relación binaria R sobre un conjunto X que es reflexiva, antisimétrica, y transitiva, es decir, para cualesquiera a, b, y c en X se tiene que:
aRa (reflexividad).
Si aRb y bRa, entonces a = b (antisimetría).
Si aRb y bRc, entonces aRc (transitividad).
Un conjunto con un orden parcial se denomina conjunto parcialmente ordenado o poset. A veces se usa laexpresión conjunto ordenado para uno parcialmente ordenado, siempre que quede claro que no se hará referencia a otras clases de orden. En particular, a un conjunto totalmente ordenado también se lo llama ordenado a secas, en especial en campos donde éstos son más comunes que los parcialmente ordenados.
Usualmente se usa la notación de "≤" en lugar de "R" para el orden total, ya que este cumple con latricotomía.
Ejemplos de Orden Parcial:
Algunos de los ejemplos más conocidos son los siguientes:
El conjunto de los naturales con su orden usual (la relación "menor o igual"). Este orden es además un orden total.
El conjunto de los enteros con su orden usual. Este orden es también total.
Un subconjunto finito {1, 2,..., n} de los naturales. Este orden es también total.
El conjunto de naturalesordenado por la relación de divisibilidad.
El conjunto de subconjuntos de un conjunto dado (i.e. su conjunto de partes) ordenado por inclusión.
El conjunto de subespacios de un espacio vectorial, ordenado por inclusión.
El conjunto de subespacios de una topología, ordenado por inclusión.
Órdenes Parciales Estrictos
En algunos contextos, el orden parcial anteriormente definido se denomina no estricto oreflexivo; así pues, un orden parcial estricto o irreflexivo es una relación binaria que es irreflexiva y transitiva, y por lo tanto asimétrica. De forma equivalente, asimétrica (y por lo tanto irreflexiva) y transitiva.
Es decir, para cualesquiera a, b, y c en X se tiene que:
¬(aRa) (irreflexividad).
Si aRb, entonces ¬(bRa) (asimetría).
Si aRb y bRc, entonces aRc (transitividad).
Si R es unorden parcial no estricto, entonces S = R − {(a, a) | a ∈ X} es el orden parcial estricto correspondiente. Análogamente, todo orden parcial estricto S tiene uno no estricto correspondiente, a saber, S ∪ {(a, a) | a ∈ P}, o la "clausura reflexiva" de R.
Los órdenes parciales estrictos son útiles porque se corresponden más directamente con los grafos acíclicos dirigidos: todo orden parcial estricto esun G.A.D., y la clausura transitiva de un G.A.D. es, además de un orden parcial estricto, un G.A.D. en sí misma.
Diagrama de Hasse
En matemáticas, un diagrama de Hasse es una representación gráfica simplificada de un conjunto parcialmente ordenado finito. Esto se consigue eliminando información redundante. Para ello se dibuja una arista ascendente entre dos elementos solo si uno sigue a otro sinhaber otros elementos intermedios.
En un diagrama de Hasse se elimina la necesidad de representar:
Ciclos de un elemento, puesto que se entiende que una relación de orden parcial es reflexiva.
Aristas que se deducen de la transitividad de la relación.
Definición
De dos miembros x e y de un conjunto parcialmente ordenado S que «y sigue a x» si x ≤ y y no hay elemento de S entre x e y.
El ordenparcial es entonces precisamente la clausura transitiva de la relación de seguir.
El diagrama de Hasse de S se define como el conjunto de todos los pares ordenados (x, y) tales que y sigue a x, es decir, el diagrama de Hasse se puede identificar con la relación de seguir.
Ejemplo
Concretamente, uno representa a cada miembro de S como un punto negro en la página y dibuja una línea que vaya hacia arribade x a y si y sigue a x.
Por ejemplo, sea el conjunto A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} (todos los divisores de 60). Este conjunto está ordenado parcialmente por la relación de divisibilidad. Su diagrama de Hasse puede ser representado como sigue:

Por ejemplo, en el diagrama de Hasse del poset de todos los divisores de un número n, ordenados parcialmente por divisibilidad, n misma...