Matematica discreta universidad salesiana de bolivia ing. De sistemas



Descargar 2,09 Mb.
Página17/38
Fecha de conversión02.07.2017
Tamaño2,09 Mb.
1   ...   13   14   15   16   17   18   19   20   ...   38

Definición. Sea R es una relación de equivalencia en A. El conjunto formado por todas las clases de equivalencia respecto a R, se llama conjunto cociente de A por R, y se denota A R. En consecuencia,

A R = { / x  A}.


5.5.5 Partición de un conjunto A. Una partición de un conjunto A no vacío, es una colección de subconjuntos no vacíos A1, A2, ..., An de A tal que:


  • Ai Aj = 0, i  j.

  • A1  A2  ...  An = A.



La figura anterior es una representación gráfica de la partición P = {A1, A2, A3, A4, A5, A6} de un conjunto A.


 
 Ejemplo 4.
Sea, A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
A1 = {1, 2, 3, 4}, A2 = {5, 6, 7}, A3 = {4, 5, 7, 9}, A4 = {8, 9, 10}, A5 = {1,2,3,6,8,10}. Los conjuntos P1 = {A1, A2, A4} y P2 = {A3, A5}

son particiones de A. El conjunto {A1, A3, A4} no es una parición de A puesto que 4  A1 A3.


 
Nota: El teorema anterior puede interpretarse, diciendo que una relación de equivalencia en A genera una partición del conjunto A. La partición será el conjunto cociente de A.
 
Ejemplo 5.
En la relación de congruencia módulo n se puede formar las diferentes clases de equivalencia y el conjunto cociente, así:

R = {(a, b) / a  b mod n, a, b  Z }.

a  b mod n  a  b = kn con k  Z .

Ç

a = kn  b. Luego los elementos de a son los que dejan residuo b al ser divididos por n. O sea que habrá tantas equivalencias como posibles residuos. Por esta razón a estas clases se les denomina clases residuales módulo n y se forman de la siguiente manera:



= {...,  2n,  n, 0, n, 2n,...}

= {..., 1  2n, 1  n, 1, 1  n, 1  2n,...}

= {..., 2  2n, 2  n, 2, 2  n, 2  2n,...}

.

.



.

= {...,  1  2n,  1  n,  1,  1  n,  1  2n,...}

Es posible verificar que no hay otras clases distintas de esta. Por ejemplo:



= {...,  2n,  n, 0, n, 2n,...} = 0

Análogamente, = , = , etc.
 
 

5.5.6 Teorema. Toda partición de un conjunto no vacío A, define una relación de equivalencia en A.
 
Demostración:

Sea P = { A1, A2, ..., An } una partición de A. Se define en A la siguiente relación:

R = {(x, y) / x  Ai, y  Ai  Ai  P}.

Veamos que R es una relación de equivalencia.



  • R es reflexiva, como A  0, existe x  A; ahora como P es una partición de A, x  Ai, Ai  p.

  • R es simétrica puesto que sí x R y, x e y  Ai y por tanto y R x.



  • R es transitiva. sí x R y  y R z, entonces, x  Ai  y  Ai de igual manera y  Aj  z  Aj. Luego, y  Ai Aj, por definición de

  • partición se sigue que: Ai = Aj. Por tanto, y  Ai  z  Ai, de donde x R z.

Ejemplo 6.

Sean A = {1,2,3,4} y A R = {{1,2,3},{4}} una partición de A. Determinar la relación de equivalencia correspondiente en A.

Solución: Las clases de equivalencia de A serán los subconjuntos de A que conforman la partición, así:

1 = {1,2,3} 4 = {4}.

A partir de la definición de 1 y el hecho de que R es una relación de equivalencia, se llega a que: (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3) pertenecen a R.

De igual manera (4,4) pertenece a R, entonces:



R = {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),(4,4)}
 
 Ejercicios 3.5
 
  1) ¿ Cuál de las siguientes relaciones en S son de equivalencia?

  • R = {(a, b)/ a R b sí y sólo sí a y b viven en Medellín}, donde S = {a / a vive en Medellín}.

  • R = {(a, b)/ a y b tienen la misma madre}, donde S = {a / a es cualquier persona}.



  • R = {(a, b)/ a y b tienen un pariente común}, donde S = {a / a es cualquier persona }.

2) Defina la relación " " en Z como m  n sí y sólo sí m2 = n2.

  • Muestre que  es una relación de equivalencia en Z .

  • Describa las clases de equivalencia. ¿Cuantas hay?.

3) Para m, n pertenecientes a los naturales defina m  n si m2  n2 es múltiplo de 3.

  • Muestre que  es una relación de equivalencia en N .



Dé cuatro elementos de .



Dé cuatro elementos de .

  • ¿ Piensa usted que hay más clases de equivalencia?.

4) La definición m  n (mod p) tiene sentido inclusive si p = 0 o

p = 1.


  • Describa esta relación de equivalencia para p = 1 y sus respectivas clases de equivalencia.

  • Repita el procedimiento anterior para p = 0.

5) Considere la relación en Z definida como m R n sí y sólo sí m3  n3  0 (mod 5)

¿ Es una relación de equivalencia?.

6) Dado A = {a, b, c, d, e, f}, escriba cinco relaciones de equivalencia en A diferentes.
 
7) Sea A = {a, b, c, d} y A R ={{a, b}, {c}, {d}}. Escriba la relación de equivalencia correspondiente en A. Escriba todas las clases de equivalencia.  

8) Sea S un conjunto. ¿ Es la igualdad "=" una relación de equivalencia en S?.

9) Escriba las clases de equivalencia para la relación de congruencia módulo 4. ¿Cuál es el conjunto cociente?.
10) Considere el conjunto N x N . Definamos una relación N x N de la forma siguiente:

(a, b)  (c, d) sí y sólo sí a  b = b  c. Pruebe que R es una relación de equivalencia.

11) Para cada una de las siguientes relaciones, decir cuáles son de equivalencia. Todas las relaciones son sobre el conjunto de los seres humanos.

a) x R y representa que x es hijo de y.

b) x R y representa que x es un descendiente de y.

c) x R y representa que x e y tienen los mismos padres.

d) x R y representa que x es de la misma estatura o de menor estatura que y.
 
12) Sea R una relación sobre el conjunto de los enteros positivos, tal que R = {(a, b)/a  b es entero positivo impar}. ¿Será esta relación de equivalencia?.

13) Sea R una relación simétrica y transitiva sobre un conjunto A. Demuestre que si para todo a  A existe b  A tal que (a, b)  R, entonces R es una relación de equivalencia.


 
 14) Sea R una relación reflexiva y transitiva en A. Sea T una relación en A tal que (a,b)  T sí y sólo sí tanto (a, b) como (b, a) está en R. Demuestre que T es una relación de equivalencia.
 
 15) Una relación R es una función si para todo x existe sólo una y tal que x R y. ¿Puede una función ser una relación de equivalencia?.

5.6 Relaciones de orden.

5.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 " " en Z 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á el conjunto 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 7 divide 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


5.6.2 Grafo 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. Por tanto, 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 apuntando hacia 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 parcialmente ordenado.

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}, {a, c}, {b, c}}


 


El diagrama de Hasse de un conjunto ordenado totalmente siempre será una línea recta.

Ahora, si (A,  ) es un conjunto parcialmente ordenado y (A,  ) es el conjunto parcialmente ordenado dual, el diagrama de Hasse de (A,  ) es el diagrama de Hasse de (A,  ) puesto de cabeza girado hacia abajo.


Ejemplo 8.

Sea (A,  ) representado por el siguiente diagrama:


 
 


 
 

El conjunto parcialmente ordenado dual (A,  ) estará representado por :


 


5.6.3 Elementos extremos de un conjunto parcialmente ordenado. Considérese un conjunto parcialmente ordenado (A,  ). Un elemento a  A se llama elemento maximal de a si a  x implica que a = x, para todo x perteneciente a A, es decir,

( x)( x  A  a  x  a = x )

Intuitivamente esto quiere decir, que a  A es elemento maximal sí y sólo sí no existe en A un elemento distinto que lo siga.

Un elemento a  A se llama elemento minimal x  a implica que x = a, para todo x perteneciente a A, es decir,

( x)( x  A  x  a  x = a ).

Esto quiere decir que a  A es elemento minimal sí y sólo sí no existe en A un elemento distinto que lo preceda.

Ejemplo 9.

Sea el conjunto parcialmente ordenado cuyo diagrama de Hasse es :


 
 


 
Los elementos a, b y c son elementos maximales de A, y los elementos d, e y f son los elementos minimales de A. Observe que como no existe una línea recta entre e y f, no se puede decir que e  f ni que f  e.


 

Ejemplo 10

Sea A el conjunto parcialmente ordenado de todos los números reales no negativos con el orden usual  . Entonces el cero es el elemento minimal de A y no existen elementos maximales.
Ejemplo 11.

El conjunto parcialmente ordenado Z con el orden usual  no tiene elementos maximales ni minimales.



5.6.3.1 Teorema. Sea A un conjunto parcialmente ordenado, no vacío y finito con orden parcial " ". Entonces A tiene al menos un elemento maximal y al menos un elemento minimal.

Demostración: Sea a  A, si a no es maximal, es posible encontrar b  A tal que a  b. si b no es maximal, es posible encontrar c  A tal que b  c. Como A es un conjunto finito podemos obtener una cadena de la forma a  b  c  ...  m. Luego m es un elemento maximal.


 

5.6.3.2 Definición. A un elemento a  A se le llama máximo de A, si x  a para todo x  A. A un elemento b  A se le llama mínimo de A, si b  x para todo x  A. Es decir,

a es elemento máximo de A sí y sólo sí ( x)(x  A  x  a)

b es elemento mínimo de A sí y sólo sí ( x)(x  A  b  x).
Ejemplo 12

Sea S = {a,b,c} y sea A = P(S). Entonces el conjunto vacío es el elemento mínimo de A y S es el elemento máximo con el orden parcial " ".

Ejemplo 13.

El conjunto parcialmente ordenado Z con el orden parcial habitual no tiene ni máximo ni mínimo.



5.6.3.3 Teorema. Un conjunto parcialmente ordenado tiene a lo sumo un elemento máximo y uno mínimo.

Demostración: Supongamos que a y b son los elementos máximos de un conjunto parcialmente ordenado A. Entonces a  b puesto que b es máximo y b  a porque a también e máximo. Por la propiedad antisimétrica se concluye que a = b.



5.6.3.4 Definición. Sea (A,  ) un conjunto parcialmente ordenado y B  A. Un elemento a  A se le llama cota superior de B si b  a para todo b  B. Un elemento c  A se le llama cota inferior de B si c  x para todo x  B.
Ejemplo 14.

Sea el conjunto parcialmente ordenado, A = {a, b, c, d, e, f, g, h} cuyo diagrama de Hasse es:



Hallar cotas superiores e inferiores de los siguientes subconjuntos de A:

B1 = {a, b} B2 = {c, d, e}

Solución: B1 no tiene cotas inferiores y sus cotas superiores son c, d, e, f, g, h.

B2 tiene como cotas superiores a f, g y h y como cotas inferiores c, a y b.

5.6.3.5 Definición. Sea (A,  ) un conjunto parcialmente ordenado y B  A. Un elemento a  A se le llama mínima cota superior de B si a es una cota superior de B y se cumple que a  a1 siempre que a1 sea una cota superior de B.

De igual manera, a un elemento a  A se le llama máxima cota inferior de B si a es una cota inferior de B y se cumple que a1  a siempre que a1 sea una cota inferior de B.

Las cotas inferiores en (A,  ) corresponden a las cotas superiores en (A,  ) y las cotas superiores en (A,  ) corresponden a las cotas inferiores en (A,  ). Lo mismo puede decirse de las máximas cotas inferiores y las mínimas cotas superiores.

Ejemplo 15.

Sea A, el conjunto parcialmente ordenado del ejemplo 14 con los subconjuntos B1 y B2 definidos anteriormente. Halle la mínima cota superior y la máxima cota inferior de B1 y B2.

Solución: B1 no tiene cotas inferiores por lo tanto carece de máxima cota inferior. La mínima cota superior de B1 es c.

Puesto que las cotas inferiores de B2 son c, a y b entonces la máxima cota inferior es c. Las cotas superiores de B2 son a f, g y h; pero f y g no son comparables por lo tanto B2 no tiene mínima cota superior.

5.6.3.6 Teorema. Sea (A,  ) un conjunto parcialmente ordenado. Entonces un subconjunto B de A tiene cuando más una mínima cota superior y una máxima cota inferior.

TEMA: 6




Compartir con tus amigos:
1   ...   13   14   15   16   17   18   19   20   ...   38


La base de datos está protegida por derechos de autor ©absta.info 2019
enviar mensaje

    Página principal