UNIDAD 5 RELACIONES

Las relaciones son muy importantes en matemáticas y sobretodo en computación, pues vienen a ser una herramienta fundamental en Bases de Datos,  Programación,  etc.;   casi en cualquier tópico de una u otra forma se utiliza el concepto de relación. El término relación es muy amplio y se puede conceptualizar en términos muy generales, pero la idea central es muy simple y entendiendo el concepto se puede aplicar en cualquier situación por diversa que sea.

Una relación es una asociación entre elementos u objetos, generalmente de dos conjuntos arbitrarios. Una manera de formalizar el concepto y al mismo tiempo hacerlo práctico para usarse en computación es considerar una relación como un conjunto de pares ordenados. Esto se puede extender posteriormente a tuplos para definir relaciones de varios elementos.

Primeramente empezaremos por el concepto de producto cartesiano entre conjuntos.

A diferencia de un conjunto en un par ordenado (a,b),  importa el orden de los elementos. Si se consideran los conjuntos A y B y formamos parejas o pares ordenados con los elementos de A como primeros elementos y los de B como segundos, se obtiene un conjunto llamado producto cartesiano. Esto es:

Definición. A x B = {(a,b) : a ∈ A, b ∈ B }

Ejemplo: A= {1,2,5}, B = {2,3}

A x B = (1,2),(1,3),(2,2),(2,3),(5,2),(5,3)

Con el producto cartesiano podemos establecer la definición formal de relación.

Definición. Una relación R de A a B es un subconjunto de A x B. Los elementos de A que aparecen en la relación forman el dominio y los de B forman el rango.

Notación: R ⊆ A X B

DOM( R ) = {x : (x,y) ∈ R }
RAN( R ) = {y : (x,y) ∈ R }

O sea que una relación de A a B es un conjunto de pares ordenado, donde los primeros elementos pertenecen al conjunto A y los segundos a B.

ejemplo:

 

Llamamos Relación de A en B a cualquier subconjunto del Producto Cartesiano de A·B

A = {a,b}, B= {1,2,3}

R = {(a,1); (a,3); (b,2); (b,3)}

Gráficos:

Para ver el gráfico seleccione la opción "Descargar" del menú superior

MR1= 1 0 1

0 1 1

 Matriz booleana Tabla Simple Doble entrada

 

Llamamos Dominio (D) de una relación al conjunto de elementos del primer conjunto que son primer componente de algún par de la relación.

Llamamos Imagen ( I) al conjunto de elementos del segundo conjunto que son segunda componente de algún par.

La Relación Complementaria (R) de otra dada es la diferencia entre el producto cartesiano de A·B y la relación R definida de A® B

La Relación Inversa (R¯¹) es la relación que contiene a los pares (x,y) / (y,x) Î R

 

RELACIONES DEFINIDAS DE UN CONJUNTO EN SI MISMO (A® A)

Reflexividad: Una relación es Reflexiva cuando para cada x Î A, el par (x,x) Î a la relación. Si está escrita en forma de pares, deben figurar tantos pares (x,x) como elementos tenga el conjunto. Si está dado matricialmente, la diagonal principal debe ser toda de "1". Si algunos pares (x,x) figuran y otros no, la relación es No Reflexiva. Si ningún par (x,x) figura, la relación es Areflexiva.

Simetría: Una relación es Simétrica si todo par tiene su inverso en la relación. Si algunos pares tienen simétrico y otros no, la relación es No Simétrica. Si ningún par tiene simétrico, la relación es Antisimétrica.

Transitividad: Una relación es Transitiva si existiendo en la relación dos pares del tipo (x,y);(y,z), entonces aparece también el par (x,y).

CLAUSURA DE UNA RELACIÓN:

Clausura Reflexiva: Es la menor relación reflexiva que contiene a la dada. Si la relación es reflexiva, es su propia Clausura Transitiva. Si la relación está dada por una matriz booleana, la Clausura Reflexiva se obtiene completando con 1 la diagonal principal.

Clausura Simétrica: Es la menor relación simétrica que contiene a la dada. Si una relación es simétrica, es su propia Clausura Simétrica. Si la relación está dada como matriz booleana, se cambian los 1 por 0 necesarios para que sea simétrica respecto de la diagonal principal.

Clausura Transitiva: Es la menor relación transitiva que contiene a la dada. Si la relación es transitiva, es su propia Clausura Transitiva. Si no lo es se halla usando el siguiente método:

1.    t

2.    Se encuentran las potencias de R (R², R³, etc.)

t t-1 i

3.    Si R es la relación total o producto cartesiano, no se buscan más potencias y esa es la Clausura Transitiva.

4.    Si R es la matriz nula, entonces la C.T es la unión generalizada R¥ = U R

t i=1

4) Si R es igual a alguna potencia anterior, entonces no se buscan más potencias y la C.T es idéntica que en el punto anterior.

Clasificación de las relaciones por sus propiedades:

Una relación es de Orden Estricto si es asimétrica y transitiva. P. Ej.: >

Una relación es de Orden Amplio si es reflexiva, antisimétrica y transitiva. P. Ej: ³

Una relación es de Equivalencia si es reflexiva, simétrica y transitiva.

Ejemplificación:

1	0	1	0	1	0
0	1	0	1	0	1
1	0	1	0	1	0
0	1	0	1	0	1
1	0	1	0	1	0
0	1	0	1	0	1

·         Al tener en su Diagonal Principal únicamente "1", la matriz es simétrica. (Diagonal principal sombreada)

·         Como los elementos que bordean a la Diagonal principal son idénticos, la matriz es reflexiva. (Elementos en cursiva)

·         Al multiplicar la matriz por si misma se obtiene otra matriz idéntica y por lo tanto se halla la clausura transitiva.

 

RELACIONES DE EQUIVALENCIA:

Una relación es de Relación de Equivalencia (º ) cuando es reflexiva, simétrica y transitiva. Estas relaciones tienen una característica muy particular: producen en el conjunto en el cual las definimos una partición.

Esta partición se caracteriza porque en cada conjunto de los que integran la partición encontramos elementos equivalentes entre si.

Sea el conjunto A y en el definido una relación de equivalencia. Tomamos el primer elemento y formamos la clase que lo contiene. Comparamos el segundo elemento: si son equivalentes, B quedará en la clase del A, y sino abrimos la clase del B que lo contiene.

Tomamos el elemento C y lo componemos con A, si es de equivalencia queda en la clase del A, sino lo comparamos con B, y sino abrimos la clase del C que lo contiene, y así sucesivamente.

Si los elementos son infinitos, con algún criterio podremos interpretar el armado de las clases de equivalencia.

El conjunto de todas las clases de equivalencia es el Conjunto Cociente.

CONJUNTO COCIENTE:

Decimos que el Conjunto Cociente es una partición porque:

a.     como cada clase se abre para cada elemento, ninguna puede ser Æ .

b) Como comparamos todos los elementos de A, la unión de todas las clases será A.

Sea X1 Î Ca ^ X1 Î Cb

X1 Î Ca Þ X1 º a Þ a º X1 Œ

X1 Î Cb Þ X1 º b

Œ y a º b Þ b Î Ca Þ Ca = Cb

Ca y Cb = Æ

Relación de equivalencia compatible con una operaciónÛ

Decimos que Û y º son compatibles cuando: si a es equivalente a b, y c es equivalente a d, entonces aÛ c es equivalente a bÛ d.

OPERACIONES BINARIAS

Llamamos Operación Binaria a cualquier función de A× B en C. Es decir, a un par ordenado con primer elemento perteneciente a A, y segundo componente perteneciente a B, le hacemos corresponder un elemento de C.

Los conjuntos A, B y C pueden ser distintos o iguales. Cuando A=B y tenemos una función A× A en C, como puede ser la resta definida en nxn que va a parar a Z, vemos que sale fuera de los números naturales. Ejemplo: 5-12= -7, donde 5 y 12 Î N y -7 Î Z.

Puede ocurrir que B y C sean iguales, y tenemos Ley de Composición Externa. Ejemplo: Producto de un escalar por un vector, que va de rxb en b.

Puede ocurrir que A=B=C. en este caso la función no va de A× A en A y decimos que es una Ley de Composición Interna, o bien una Operación Cerrada, o que cumple con la Ley de Cierre.

Propiedades:

·         Propiedad Conmutativa: AÛ B = BÛ A

·         Propiedad Asociativa: (AÛ B)Û C = AÛ (BÛ C)

Elementos Notables:

·         Idempotencia: A Û A = A

·         Elemento Neutro: A Û e = A

·         Elemento Inverso: A Û A’ = e

·         Elemento Absorbente: µ Û A = µ

·         Involución: A Û A = e

 

 

Definición. La relación inversa {$ R^{−1} $} de una relación R de A a B es la que se obtiene si invertimos el orden en las parejas.

{$ R^{−1}$} = { (y,x) : (x,y) ∈ R }

Observamos que la relació inversa es una relación de B a A.

Ejemplos.

Si A = {a,b,c,x,y,z}, B = {1,2,3,4,5}

{$ R_1 $} = (a,2),(c,2),(x,1),(y,5),(z,5)
{$ R_2 $} = (a,1),(a,5),(c,3),(x,2),(x,4)
{$ R_3 $} = (a,4),(b,2),(c,5),(x,1)
{$ R_4 $} = (a,3),b,1),(b,5),(c,3),c,5),(x,1),(y,4)

{$ DOM(R_1)$}   = {a,c,x,y,z}
{$ RAN(R_1) $} = {1,2,5}
{$ DOM(R_2) $}= {a,c,x}
{$ RAN(R_2) $}= {1,2,3,4,5}
{$ DOM(R_3) $} = {a,b,c,x}
{$ RAN(R_3) $} = {1,2,4,5}
{$ DOM(R_4) $}= {a,c,x,y}
{$ RAN(R_4) $} = {1,3,4,5}

{$ R^{−1}_1 $} = (2,a),(2,c),(1,x),(5,y),(5,z)
{$ R^{−1}_2 $} = (1,a),(5,a),(3,c),(2,x),(4,x)
{$ R^{−1}_3 $} = (4,a),(2,b),(5,c),(1,x)
{$ R^{−1}_4 $} = (3,a),(1,b),(5,b),(3,c),(5,c),(1,x),(4,y)

FUNCIONES INYECTIVA, SUPRAYECTIVA Y BIYECTIVA

"Inyectivo, sobreyectivo y biyectivo" te dan información sobre el comportamiento de una función.

Puedes entender una función como una manera de conectar elementos de un conjunto "A" a los de otro conjunto "B":

"Injectivo" significa que cada elemento de "B" tiene como mucho uno de "A" al que corresponde (pero esto no nos dice que todos los elementos de "B" tengan alguno en "A").

"Sobreyectivo" significa que cada elemento de "B" tiene por lo menos uno de "A" (a lo mejor más de uno).

"Biyectivo" significa inyectivo y sobreyectivo a la vez. Así que hay una correspondencia perfecta "uno a uno" entre los elementos de los dos conjuntos.

Definiciones formales

Inyectivo

Una función f es inyectiva si, cuando f(x) = f(y), x = y.

Ejemplo: f(x) = x² del conjunto de los números naturales  a  es una función inyectiva.

(Pero f(x) = x² no es inyectiva cuando es desde el conjunto de enteros  (esto incluye números negativos) porque tienes por ejemplo

·         f(2) = 4 y

·         f(-2) = 4)

Nota: inyectiva también se llama "uno a uno", pero esto se confunde porque suena un poco como si fuera biyectiva.

Sobreyectivo (o también "epiyectivo")

Una función f (de un conjunto A a otro B) es sobreyectiva si para cada y en B, existe por lo menos un x en Aque cumple f(x) = y, en otras palabras f es sobreyectiva si y sólo si f(A) = B.

Así que cada elemento de la imagen corresponde con un elemento del dominio por lo menos.

Ejemplo: la función f(x) = 2x del conjunto de los números naturales  al de los números pares no negativos es sobreyectiva.

Sin embargo, f(x) = 2x del conjunto de los números naturales  a  no es sobreyectiva, porque, por ejemplo, ningún elemento de  va al 3 por esta función.

Biyectiva

Una función f (del conjunto A al B) es biyectiva si, para cada y en B, hay exactamente un x en A que cumple que f(x) = y

Alternativamente, f es biyectiva si es a la vez inyectiva y sobreyectiva.

Ejemplo: La función f(x) = x² del conjunto de números reales positivos al mismo conjunto es inyectiva y sobreyectiva. Por lo tanto es biyectiva.

(Pero no desde el conjunto de todos los números reales porque podrías tener por ejemplo

·         f(2)=4 y

·         f(-2)=4)