Bloque 1: Relaciones

Relación

Sean los conjuntos A1, A2, . . . , An. 
Una relación R sobre A1 ×A2 ×· · · ×An es cualquier subconjunto de este producto cartesiano, es decir,
R ⊆ A1 × A2 × · · · × An

Si R = ∅, llamaremos a R, la relación vacía.
Si R = A1 × A2 × · · · × An, llamaremos a R la relación universal.
Si Ai = A, ∀i = 1,2, . . . , n, entonces R es una relación n-aria sobre A.
Si n = 2, diremos que R es una relación binaria y si n = 3, una relación ternaria.


Igualdad de Relaciones

Sean R1 una relación, n-aria sobre A1×A2×· · ·×An y R2 una relación n-aria sobre B1×B2×· · ·×Bm.
Entonces R1 = R2 si, y s´olo si n = m y Ai = Bi
,∀i = 1,2, . . . , n y R1 y R2 son conjuntos de n-tuplas ordenadas iguales.


 Relaciones Binarias

La clase más importante de relaciones es la de las relaciones binarias. Debido a que este tipo de relaciones
son las más frecuentes, el termino “ relación” denota generalmente una relación binaria; adoptaremos este
criterio cuando no haya confusión y especificaremos las que no sean binarias con términos tales como
“ternaria” o “n-aria”.

Si (a, b) ∈ R diremos que a está relacionado con b y lo notaremos por aRb.
Si (a, b) ∈/ R, escribiremos aR/ b y diremos que a no está relacionado con b.

Ejemplo 


Sea A = {huevos, leche, maíz} y B = {vacas, cabras, gallinas}. Escribir la relación R 
de A a B definida por:
(a, b) ∈ R ⇐⇒ a es producido por b
Solución
La relación sería:
R = {(huevos,gallinas),(leche,vacas),(leche,cabras)}

Ejemplo 


(a) Sea R la relación “menor que” definida en el conjunto Z de los números enteros.
Escribiremos 3 < 5 para indicar que (3,5) ∈ R y 5 </ 3 para indicar que (3,5) ∈/ R

(b) Sea R la relación “es un múltiplo de” en el conjunto de los enteros positivos.
Entonces,  4R2 pero 2R/ 4. Más generalmente, xRy si, y solo si x = ky para alg´un k ∈ Z +.
Así para todo x, xR1. Si p > 1, entonces p es primo si xRp implica que x = 1 ´o x = p. Un numero x
es impar si xR/ 2.

(c) Cuando un compilador traduce un programa informático construye una tabla de símbolos que
contiene los nombres de los símbolos presentes en el programa, los atributos asociados a cada
nombre y las sentencias de programa en las que están presentes cada uno de los nombres. As´ı pues,
si S es el conjunto de los símbolos, A es el conjunto de los posibles atributos y P es el conjunto de
las sentencias de programa, entonces la tabla de símbolos incluye información representada por las
relaciones binarias de S a A y de S a P.

(d) Como dijimos anteriormente, una relación binaria sobre el conjunto de los números reales puede
representarse gráficamente en el plano cartesiano. La figura siguiente es la gráfica de la relación

R = {(x, y) ∈ R × R : |x| + |y| = 1}

|x| + |y| = 1


Ejemplo 

Sea A = {1,2,3} y R = {(1,2),(1,3),(3,2)}. R es una relación en A ya que es un
subconjunto de A × A. Con respecto a esta relación, tendremos que

1R2, 1R3, 3R2, pero 1R/ 1, 2R/ 1, 2R/ 2, 2R/ 3, 3R/ 1, 3R/ 3