asda

LOGICA MATEMÁTICA Y TEORÍA DE ALGORITMOS
TEMA: CONJUNTOS ORDENADOS
CONJUNTOS PARCIALMENTE ORDENADOS
Suponga que R es una relación sobre un conjunto A, que satisface las tres propiedades siguientes:
1) Reflexiva, es decir: (a, a) R, para todo a
2) Antisimétrica, es decir: si (a, b) R y (b, a) R, entonces a = b
3) Transitiva, es decir: si (a, b) R y (b, c) R, entonces (a, c) REntonces R se denomina orden parcial o, simplemente una relación de orden, y se dice que R define un orden parcial de A.
El conjunto A con el orden parcial se denomina conjunto parcialmente ordenado. Se escribe (A, R) cuando se desea especificar la relación R. La relación de orden más conocida, que se denomina orden usual, es la relación (que se lee “menor o igual que”) sobre los enterospositivos forma más general sobre cualquier subconjunto de los números reales Debido a esto, una relación de orden parcial se denota por .
a se lee: “a precede a b”
En relación con los conjuntos parcialmente ordenados, se emplean además las notaciones siguientes:
a significa a y a b; que se lee “a precede estrictamente a b”
b a significa a ; que se lee “b sucede a a”.
basignifica a que se lee “b sucede estrictamente a a”.
Ejemplos
1.- Sea R una relación definida en los números naturales por “x es múltiplo de y”; R es un orden parcial en, así se tiene:
6 2; 15 3; 12 4; 17 17
2.- Sea R una relación definida en los números naturales por “x divide a y”, lo que se escribe x/y, si existe un entero c tal que xc = y. Porejemplo: 2/4; 3/12; 7/21 y así sucesivamente. Esta relación de divisibilidad es un orden parcial de .
CONJUNTOS TOTALMENTE ORDENADOS
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.
Definición: Un orden total en un conjunto A es un orden parcial en A más la propiedad: a ;a = b o ab, para cualesquiera dos elementos a y b de A. Un conjunto A y un orden total dado en A constituyen un conjunto totalmente ordenado.
Nota: Dos elementos a y b de un conjunto parcialmente ordenado se dice que es comparable si: a b y b a.
Ejemplo 3. Sea R el orden parcial en A = {1, 2, 3, 4, 5, 6} definido por “x divide a y”.
Solución: Se observa que R no es de un ordentotal en A, ya que 3 y 5 no son comparables.
DIAGRAMAS DE HASSE

El diagrama de Hasse de un conjunto ordenado finito es una representación del mismo en la que cada elemento se representa por un punto del plano. Si aRb se dibuja a por debajo y se une por medio de un segmento. Finalmente se suprimen los segmentos que corresponden a la propiedad transitiva, es decir, si aRb y bRc se suprimeel segmento correspondiente a aRc.

Ejemplo: Diagramas de Hasse del conjunto ordenado Divisores de 30, D(30).







Figura Diagrama de Hasse para el conjunto D(30)

SUBCONJUNTOS DE CONJUNTOS ORDENADOS
Suponiendo una relación que define un orden parcial en un conjunto A, o sea que (A, ) es un conjunto ordenado, sea B un subconjunto de A. Entonces el ordenparcial en A induce un orden parcial B de la siguiente manera: Si a, b B entonces: (a, b) esto es, a como elementos de B, si, y solamente si, (a, b) , es decir a como elementos de A. Se dice entonces que el conjunto ordenado (B, ) es un subconjunto (parcialmente ordenado) del conjunto ordenado (A, ).
Ejemplo
SUBCONJUNTOS ORDENADOS
Sea A un conjunto parcialmente ordenado.Entonces como ya se vio, el orden parcial en A induce un orden parcial en todo subconjunto de A. Algunos de los subconjuntos de A quedarán en realidad totalmente ordenados.
Nótese que si A es un conjunto totalmente ordenado, todo subconjunto de A es totalmente ordenado.
Ejemplo Sea, los números naturales, ordenado por “x es múltiplo de y”: N = {1, 2, 3, 4, 5, 6, 7, 8, 9,...} Entonces no es...