Mate Discretas Unidad 5

5.2 Propiedades De Las Relaciones
(Reflexiva, Simétrica, Asimétricas y Transitivas, etc...)
Relaciones Reflexivas e Irreflexivas
Una relación R en un conjunto A es reflexiva si (a, a) £ R para todas las a £ A, esto es, si a R e para todas las a e A. Una relación R en un conjunto A es irreflexiva si a R a para toda a £ A.
Por consiguiente, R es reflexiva si cada elemento a e A estárelacionado consigo mismo y es irreflexiva si ningún elemento está relacionado consigo mismo.
Ejemplo 1:
(a) Sea Δ = [(a, a)\ a £ A], de modo que A es la relación de igualdad en el conjunto A. Entonces A es reflexiva, ya que (a, a) £ Δ para todas las a e A.
(b) Sea R = {(a, b) e A x A | a + b}, R es la relación de desigualdad en el conjunto A. Entonces R es irreflexible, ya que (a, a) £ R para todas lasx € A.
(c) Sean A = {1, 2, 3}. y Jí = {(1, 1), (1, 2)}. Entonces A es reflexiva ya
(2,2) R y (.3,3) € R. Por otra parte, R no es irreflexiva, ya que (1, l) € R.
(d) Sea A un conjunto no vacio. Sea R = Ǿ A x A, la relación vacía. Enlaces R no es reflexiva, ya que (a, a) € R para todas las a € A (el conjunto vacío tiene elementos). Sin embargo, R es irreflexiva.
Relaciones Simétricas yAsimétrica
Una relación R en un conjunto A es simétrica si cuando a R b, entonces b R a. De esto se sigue que R no es simétrica se tiene a y b € A con a R b, pero b R a. Una relación R en un conjunto A es asimétrica si cuando a R b, entonces b Ra. De esto se sigue que R no es simétrica si se tiene a y b e A con ambos a R b y b R a.
Una relación R en un conjunto A es asimétrica si cuando a R b y b R a,entonces a = b. Otra forma de expresar esta definición es diciendo que R es anti simétrica si cuando a ≠ b, se tiene a R b o b R a. De esto se sigue que R no es anti simétrica si se tiene a y b en A. a ≠ b, y ambas a R b y b R a.
Ejemplo Sea A «= [a, b, c, d, e} y sea R la relación simétrica dada por
R = {(a, b), (b, a), (a, c), (c, a), (b, c), (c, b), (b, e), (e, b), (e, a), (a, e), (c,a),(a,c)}
El grafo dirigido de R se muestra en la figura 2(a), mientras que en la figura
Grafo dirigido de R Grafo dirigido de R
Aparece el grado de R. Obsérvese que cada arista no dirigida corresponde a dos pares ordenados en la relación R.
A una relación simétrica R en un conjunto A se le llamará conexa si existe una trayectoria de cualquier elemento de A a cualquier otro elemento de A. Estosignifica sencillamente que el grafo de R está todo en una pieza. En la figura 3 se muestran los grafos de dos relaciones simétricas. El grafo de la figura 3(a) está conectado mientras que el de la figura 3(b) no lo está.

Relaciones Transitivas
Se dice que una relación R en un conjunto A es transitiva si cuando a R b y b R e, entonces a R c. Se sigue que R no es transitiva si y sólo si se puedeencontrar elemento a, b y c en A tal que a R b y b R c, pero a R c.
Ejemplo: Sea A = Z el conjunto de los enteros y sea R la relación considerada en el ejemplo 2 Para ver si R es transitiva, se supone que a R b y b R c. Por consiguiente, a < b; b < c. Entonces se sigue que a < c, por lo cual a R c. De aquí que R sea transitiva.

Una relación R en un conjunto A es transitiva si y sólo sisatisface las siguientes propiedades: Si existe una trayectoria de longitud mayor que 1 del vértice a al vértice b, hay una trayectoria de extensión 1 de a a b (esto es, a está relacionada con b). Establecido algebraicamente, R es transitiva si y sólo si Rn £ R para todas las n ≥ 1.

Es posible caracterizar la relación transitiva por su matriz MR = [mij] así:

si mij =1 y mjk = 1, entonces mik= 1

Para ver qué significa transitividad en términos del grafo dirigido de una relación, se traducirá esta definición a términos geométricos.

Si se examinan los vértices particulares a y c, las condiciones a R b y b R c

ocurrirán si y sólo si existe una trayectoria de longitud 2 de a a c, esto es, si y sólo si a R2 c. Es posible replantear la definición de transitividad como sigue: Si...