Matematicas | Page 89

3.3. RELACIONES REFLEXIVAS, SIMÉTRICAS Y TRANSITIVAS 3.3. 83 Relaciones reflexivas, simétricas y transitivas Ahora nos restringiremos a estudiar relaciones binarias definidas entre los elementos de un mismo conjunto: aquellas relaciones de A en A (es decir el caso en que A = B en la definición 3.12). En este caso diremos que R es una relación sobre A. ¿Cuántas relaciones se pueden definir sobre un conjunto? Una relación sobre A es, por definición, un subconjunto de A × A. Por lo tanto, la colección de relaciones sobre un conjunto A es precisamente P(A × A). Por esto existen tantas relaciones sobre A como elementos tenga P(A × A). Ahora bien, ¿Cuantos elementos tiene P(A × A)? Veremos más adelante que si A tiene n elementos, 2 entonces A × A tiene n2 elementos. Por lo tanto P(A × A) tiene 2n elementos. Así que, si A 2 tiene n elementos, entonces se pueden definir 2n relaciones binarias sobre A. Por ejemplo, si A es {0, 1}, entonces existen exactamente 16 relaciones binarias sobre {0, 1}. Cierto tipo de relaciones binarias aparecen con mucha frecuencia en Matemáticas y por esto han recibido un nombre especial. Introduciremos algunas de ellas a continuación. Definición 3.18. Sea R una relación binaria sobre un conjunto A. 1. Se dice que R es reflexiva si (a, a) ∈ R para todo a ∈ A. De manera equivalente, tenemos que R es reflexiva si aRa para todo a ∈ A. 2. Se dice que R es simétrica si cada vez que (a, b) ∈ R entonces también se cumple que (b, a) ∈ R. Es decir Si aRb, entonces bRa. 3. Se dice que R es antisimétrica si cada vez que (a, b) ∈ R y (b, a) ∈ R, entonces se tiene que a = b. Es decir Si aRb y bRa, entonces a = b 4. Se dice que R es transitiva si dados a, b, c ∈ A tales que (a, b) ∈ R y (b, c) ∈ R, entonces se cumple que (a, c) ∈ R. Es decir Si aRb y bRc, entonces aRc. En la vida diaria usamos con frecuencia relaciones transitivas. Por ejemplo la relación más temprano que entre sucesos en el tiempo, más pesado que entre objetos, dentro de entre objetos son todas relaciones transitivas. También usamos relaciones que no son transitivas. Por ejemplo la relación ser padre de entre personas no es una relación transitiva. Algunos juegos usan reglas que dan lugar a una relación no transitiva. Por ejemplo, la regla del conocido juego infantil Piedra (I), Papel (P) o Tijera (T) establece que I le gana a T, T le gana a P , P le gana a I. Pero I no le gana a P y por lo tanto esta relación no es transitiva.