Matematicas Discretas

4.PROPIEDADES DE LAS RELACIONES

a)reflexivas y b)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 las x € 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. ^

Es posible caracterizar una relación reflexiva o irreflexiva por su matriz con sigue. La matriz de una relación reflexiva deberá tener unos en toda su diagon principal; en cambio, la matriz de una relación irreflexible deberá tener ceros.

De igual manera, es posible caracterizar una relación reflexiva o irreflexiva por su grafo dirigido como sigue. Una relación reflexiva tiene un ciclo de longitud 1. Que cada vértice; en cambio, una relación irreflexiva no tendrá ciclos de longitud 1. De manera útil de decir lo mismo es usar la relación de igualdad Δ en un conjunto A es reflexiva si y solo si Δ € R, y es irreflexible si y solo si A ∩ R = 0.

Finalmente, se deberá observar que, si R es reflexible en un conjunto A, entonces Dom(R) = Ran(.R) = A.

Relaciones c) simétricas, d)asimétricas y e)antisimétricas

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 antisimé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 antisimétrica si cuando a ≠ b, se tiene a R b o b R a. De esto se sigue que R no es antisimétrica si se tiene a y b en A. a ≠ b, y ambas a R b y b R a.

Dada una relación R, sé desea determinar qué propiedades se cumplen para R Se tendrá presente la siguiente observación. Una propiedad no se cumple en general si se encuentra una situación en donde la propiedad no se cumpla. Si no hay situación alguna en la que la propiedad no se cumpla, se deberá concluir que la propiedad se cumple siempre.

Ejemplo sea A = Z, el conjunto de los enteros y sea

R=[(a,b)€ A xA | a < b}

ya que R es la relación menor que. ¿Es R simétrica, asimétrica o antisimétrica?

Solución.

Simetría. Si a <b, entonces no es verdadero que b < a, por lo cual no es simétrica.

Asimetría. Si a < b, entonces b < a (b no es menor que a), por lo cual R es asimétrica.

Antisimetría. Si a ≠ b, entonces a < b o b < a, por lo cual R es antisimétrica.

Ejemplo 3 Sea A el conjunto de las personas y sea

R = {(x, y) e A x A | x es primo de: y}

Entonces R es una relación simétrica

Ejemplo 4 Sea A = {1,2,3,4} y sea

R» {(1,2). (2, 2), (3,4), (4,1)}

Entonces R no es simétrica, ya que(l, 2) e R pero (2, 1) ^ R. Por otra parte, R no es asimétrica, ya que (2, 2) € R. Finalmente R es antisimétrica ya que, si a≠b, (a, b) no € R o (b, a) no € R

Ejemplo 5 Sea A = Z+, el conjunto de los enteros positivos y sea

R={(a, b) €A x A |a divide b}

¿Es R simétrica, asimétrica o antisimétrica?

Solución.

Si a | b, no se sigue que b \ a, por lo cual R no es simétrica.

Si a = b = 3, por ejemplo, entonces a R b y b R a, por lo cual R no es asimétrica.

Si a | b y b | a, entonces a = b, por lo cual R es antisimétrica.

Es posible caracterizar las propiedades de simetría, asimetría o antisimetría de una relación por las propiedades de su matriz. La matriz m¿{ = [my] de una relación simétrica satisface la propiedad de que

si mij = 1, entonces mji = 1

Además, si mji == 0, entonces mij = 0. Por consiguiente, MR es una matriz tal que todo par de componentes, colocados simétricamente alrededor de la diagonal principal es un par de ceros o de unos. Se sigue que MR = MTR, por lo que MR es una matriz simétrica.

La matriz MR = [mij] de una relación asimétrica R satisface la propiedad que

si mij == 1, entonces mji = 0.

Si R es asimétrica, se sigue que mu=s 0 para todas las i; esto es, la diagonal principal de la matriz MR contiene sólo ceros. Esto tíene que ser verdadero pues la propiedad asimetría implica que, si m,, = 1, entonces m¡¡ = O, lo que es una contradicción. Finalmente, la matriz MR = [miJ]de una relación antisimétrica R satisface propiedad que si i ≠ j, entonces miJ = 0 o miJ = 0. |

Ejemplo 6

Examine las matrices en la figura 1, donde cada una es la matriz de una relación como esté indicado. Las relaciones R1 y R2 son simétricas ya que sus matrices Mr1 Y mr2 son matrices simétricas. La relación R3 es antisimétrica, pues no hay posiciones simétricas dispuestas, fuera de la diagonal de mr3 que contengan un uno. Estas posiciones pudiera tener ceros, y en la diagonal los elementos son irrestrictos. La relación R3 no es asimétrica porque MR3 tiene unos en la diagonal. La relación R4 no tiene ninguna de las

...