Curso de Relaciones

RELACIONES : 

RELACIONES Lic. Clara Beatriz Grimblat

Producto cartesiano : 

Producto cartesiano Ejemplo: Sean A = {1, 2, 3} y B = {5, 6} A x B consta de los 6 pares de la lista (1, 5) (2, 5) (3, 5) (1, 6) (2, 6) (3, 6) Producto cartesiano. El producto cartesiano de dos conjuntos A y B es el conjunto de todos los pares ordenados (x, y) donde x?A e y ? B. En símbolos A x B = {(x, y) / x?A ? y ? B }

Producto cartesiano : 

Producto cartesiano Para representar gráficamente el producto cartesiano utilizaremos la representación cartesiana que consiste en trazar ejes perpendiculares; en el eje horizontal colocaremos los elementos del conjunto A y en el eje vertical los elementos del conjunto B, los elementos del producto cartesiano los forman los puntos de intersección que se obtienen al trazar por los elementos del conjunto A paralelas al eje vertical y por los elementos del conjunto B paralelas al eje horizontal. Ejemplo: La representación gráfica de los pares de A ? B ={(1, 5), (2, 5),(3, 5),(1, 6),(2, 6),(3, 6) } B 6 5 1 2 3 A

Slide 4: 

¿ A x B = B x A? No son iguales ... Por ej., sean los conjuntos A = {a, b, c}, B = {1, 2} A x B = { (a,1), (a,2), (b,1), (b, 2), (c, 1), (c,2) } B x A = { (1,a), (1,b), (1,c), (2, a), (2, b), (2,c) } Si A y B son finitos el número de elementos de A x B es llamado cardinal de A x B y denotado por ?A x B? ?A x B?= ?A?. ?B? Además ?A?. ?B? = ?B?. ?A?= ?B x A? Entonces ?A x B?= ?B x A?

Producto cartesiano de conjuntos de infinitos elementos : 

Producto cartesiano de conjuntos de infinitos elementos A={x ?R/-2<x<3} y B ={x ?R/-1<x<2} No podemos enlistar los elementos de AxB pero tenemos en el rectángulo sombreado de azul todos los elementos (puntos) del mismo.

: 

A={x ?R/-2<x<3} y B ={x ?R/-1<x<2} Los puntos del rectángulo en rosa constituyen el producto cartesiano BxA

Ejemplo : 

Ejemplo Sean A = {1, 2, 3} y B = {0, 1, 2, 3}. La lista de los elementos de A x B. es :{(1,0),(1,1),(1,2),(1,3),(2,0),(2,1),(2,2),(2,3),(3,0).(3,1),(3,2),(3,3)} Representar gráficamente al subconjunto R = { (a, b) ? A x B / a + b ? 3} 0 Nos interesan algunos subconjuntos del producto cartesiano

RELACIONES BINARIAS : 

RELACIONES BINARIAS Dados dos conjuntos A y B, una relación R binaria es cualquier subconjunto de AxB Dados a?A y b?B, a está relacionado con b por R si (a,b)?R, aRb. Si a no está relacionado con b, entonces (a,b)?R. Si B=A, R es una relación binaria en A o bien R es una relación binaria definida sobre un mismo conjunto A, es decir: R ? A × A

Ejemplos : 

Ejemplos x R y sii x es el doble de y (Relación definida en N) Algunos elementos de la relación son: (4, 2) (10, 5) En N se define la relación R por: “x R y sii x divide a y” Entonces: 1 R 2, 2 R 2, 2 R 6, 2 R 18, 3 R 18, 3 R 21, 3 R 3, .... R={(x,y)/x es el doble de y}, un subconjunto de NxN

Relaciones: Matriz(Booleana) MR: Hay 1 en la matriz si el par está en la relación y cero si no está. Digrafo: Si aRb, de a parte una flecha hacia b : 

Relaciones: Matriz(Booleana) MR: Hay 1 en la matriz si el par está en la relación y cero si no está. Digrafo: Si aRb, de a parte una flecha hacia b

Relaciones en notación Matricial : 

Relaciones en notación Matricial Ejemplo: Sea U = {a, e, i, o, u}, A = {a, o} y B = { i, u} A x B= {(a,i), (a,u), (o,i), (o,u)} Son relaciones de A en B: R1= Ø R2 = {(a,i), (a,u)} R3 = {(a, i) } R4 = A x B La matriz del producto cartesiano tiene en todas las filas 1 porque todos los pares ordenados están en la relación. a R4 i, a R4 u, o R4 i, o R4 u La matriz de R2 tiene 1 en la primera fila porque corresponde al elemento a de A que se relaciona con los dos elementos i, u de B; a R2 i, a R2 u y ceros en la segunda fila porque el elemento o de A no se relaciona con ningún elemento de B en R2

Relaciones binarias:propiedades : 

Relaciones binarias:propiedades Propiedades: Sea R una relacion binaria sobre un conjunto A. Diremos que R es: Reflexiva: si ?x ? A se verifica que x R x Simétrica: si ?x, y ? A se verifica que xR y ? y R x Transitiva: si ?x, y, z ? A se verifica que x R y, y R z ? x Rz Antisimétrica: si ?x, y ? A se verifica que x R y, y R x ? x = y Otra manera de expresarlo: Si x?y ? [ (x,y) ? R ? (y,x) ? R ]

Ejemplos: : 

Ejemplos: 1) En N la relación R definida por: “x R y ? x divide a y” es reflexiva ya que ?x?N, x R x porque x divide a x 2) En N la relación R definida por: “a R b ? a es el doble de b”. no es reflexiva ya que (1, 1) ?R puesto que 1 no es el doble de 1 3) En Z la relación R definida por: “a R b ? a – b es múltiplo de 2”. es simétrica ya que si a R b ? hay p?Z tal que a – b =2p ? b – a = 2(-p) con -p ? Z ? b R a 4) En N la relación R definida por: “x R y ? x divide a y” no es simétrica ya que 2 R 4 porque 2 divide a 4 pero 4 no divide a 2 por lo tanto (4,2) ?R

Ejemplos: : 

Ejemplos: 5) En N la relación R definida por: “x R y ? x divide a y” es transitiva ya que si a R b y b R c entonces existen n, m ?N tales que: b = an y c = bm. Combinándolas, c = bm = (a.n).m= a(n.m) con n.m ?N ? a R c 6) En N la relación R definida por: “a R b ? a es el doble de b”. no es transitiva ya que (4, 2) ? R y (2, 1) ? R puesto que 4 es el doble de 2 y 2 es el doble de 1, sin embargo 4 no es el doble de 1, de donde (4,1)?R 7) En N la relación R definida por: “x R y ? x divide a y” es antisimétrica ya que si a R b y b R a entonces existen n, m ?N tales que: b = an y a = bm. Combinándolas, a = bm = (a.n).m ? n.m = 1 ? n = m = 1 ? a = b 8) En Z la relación R definida por: “a R b ? a – b es múltiplo de 2” no es anti simétrica ya que 2R4 y 4R2, pero 2?4

Resúmen : 

Resúmen Propiedades: Reflexiva: se satisface sii ?x ? A x R x no se satisface sii ? x?A/ (x,x)?R Simétrica:se satisface sii ? x, y ?A x R y ? y R x no se satisface sii ? x, y ?A / (x, y) ?R ? (y, x) ? R Transitiva: se satisface sii ?x, y, z ? A se verifica que x R y, y R z ? x Rz no se satisface sii ? x, y, z ?A:(x, y) ? R ? (y, z) ? R ? (a,z) ? R Antisimétrica: se satisface sii ?x, y ? A se verifica que x R y, y R x ? x = y no se satisface sii ? x, y ?A: (x, y) ? R ? (y, x) ? R ? x ?y

Propiedades de las Relaciones según la Matriz MR y su grafo dirigido (digrafo) : 

Propiedades de las Relaciones según la Matriz MR y su grafo dirigido (digrafo) Sea R una relación binaria sobre un conjunto A. Diremos que R es: Reflexiva: Si en la diagonal principal de la matriz MR todos los elementos son 1 (MATRIZ) Todo elemento tiene una flecha que comienza y termina en sí mismo (un bucle). (DIGRAFO) Simétrica: Sii MR = (MR)t : La matriz asociada a la relación coincide con su traspuesta. (MATRIZ) Todo par de elementos que tiene una flecha, la tiene en las dos direcciones (DIGRAFO) Transitiva: Sea MR2 = MR x MR (Producto booleano de matrices); Sii el elemento de la fila i columna j de MR2 es 1 entonces el elemento de MR en la misma posición también es 1 es decir la relación R2 es un subconjunto de R; en particular pueden coincidir. (MATRIZ) La relación R es transitiva si cada vez que hay un camino de longitud 2 entre dos elementos, también hay un camino de longitud uno entre los mismos. (DIGRAFO) Antisimétrica : Sii hay 1 en la fila i columna j de MR entonces hay 0 en la misma posición de (MR)t y viceversa, salvo en la diagonal principal. (MATRIZ) Sii para cada par de elementos distintos relacionados la flecha está solo en un sentido (DIGRAFO)

Relaciones de orden: Definición ynotación : 

Relaciones de orden: Definición ynotación Dada una relación binaria R definida sobre A, se dice que R es una relación de orden en A si verifica las propiedades – reflexiva – antisimétrica – transitiva Se dice entonces que A está ordenado por R Notación Utilizaremos el símbolo = para las relaciones de orden aRb a = b Se lee a es anterior a b (menor o igual) o bien b es posterior a a (mayor o igual) Distintas relaciones sobre un mismo conjunto, dan lugar a distintos conjuntos ordenados. a,b?A son comparables si aRb o bRa

Orden total y parcial : 

Orden total y parcial (A, =) está totalmente ordenado si cualquier par de elementos son comparables, se dice entonces que = es de orden total. En otro caso, se dice que (A, =) está parcialmente ordenado y que = es de orden parcial. Por ejemplo: (N, ?) es un conjunto totalmente ordenado. Sea U = {1, 2, 3} y en P(U) se define la relación “A R B sii A ? B”. (P(U), R) no es un conjunto totalmente ordenado ya que existen elementos tales como {1} y {2, 3} de P(U) que no son comparables, es decir que no están relacionados

Ejemplo : 

Ejemplo En N, a = b ? ?n ?N / b=an Es una relación de orden ya que es: reflexiva: a=a1 ?a?N antisimétrica: ?a,b?N si a = b y b = a ? n,m ?N / b=any a=bm, entonces b= [bm]n=bm·n luego m·n=1 y como n,m ?N m=n=1, así a=b transitiva: ?a,b,c?N si a = b y b = c ? n,m ?N /b=any c=bm, entonces c= [an]m=an·m luego c=a n·m, si k = n.m, ? k?N /c=ak, es decir, a = c

Elementos notables (a) : 

Elementos notables (a) Dados (A,=) y C?A, C?Ø a?A es cota superior de C si ?c?C, c=a C está acotado superiormente – La menor de las cotas superiores es el supremo. a?A es cota inferior de C si ?c?C, a=c – C está acotado inferiormente – La mayor de las cotas inferiores es el ínfimo. El supremo y el ínfimo, si existen, han de ser comparables con el resto de las cotas superiores o inferiores, respectivamente.

Elementos notables (b) : 

Elementos notables (b) Dados (A,=) y C?A, C?Ø a?C es elemento maximal de C si ?c?C, a=c?a=c m?C es máximo de C si ?c?C, c=m si existe, es el único elemento maximal de C a?C es elemento minimal de C si ?c?C, c=a?a=c. m?C es mínimo de C si ?c?C, m=c si existe, es el único elemento minimal de C

Elementos notables (c) : 

Elementos notables (c) Pueden existir uno, varios o ningún elemento maximal y minimal. El máximo (mínimo), cuando existe, es el único elemento maximal (minimal). Si en C existe supremo (ínfimo) es único. Si C tiene máximo (mínimo) coincide con el supremo (ínfimo).

: 

Diagramas de Hasse: Sea (A, R ) es un conjunto parcialmente ordenado y finito. A cada elemento del conjunto A se le asocia un punto en el plano (o en el espacio), que llamaremos vértice. Un diagrama de Hasse es el gráfico resultante al unir dos elementos consecutivos mediante un segmento de recta, que llamaremos arista. Ejemplo: Sea A = {a,b,c} y la relación R R = {(a,a), (b,b), (c,c), (b,a), (b,c), (a,c)} Es de orden total. Su diagrama de Hasse es:

Ejemplos : 

Ejemplos 1) Sea B = {1, 2}, en P(B )= {?, {1}, {2}, {1,2}} se define la relación de inclusión, la cual es de orden parcial ? ? {1} ? {1,2} y ? ? {2} ? {1,2} Entonces, B es el elemento maximal y ? es el elemento minimal, pues no existe otro elemento en P(B ) que esté “por debajo” del minimal, ni “por encima” del maximal El elemento máximo de P(B) es el elemento maximal B, el universo y el elemento mínimo de P(B) es el conjunto vacío. 2) En el conjunto C = {?, {1}, {2}} se define la relación de inclusión. Observar que ? ? {1} y ? ? {2}. ? es el elemento minimal y es el mínimo del conjunto C y tanto {1} como {2} son los elementos maximales. No existe elemento máximo en C

Diagrama de Hasse para la relación inclusión en P(B) : 

Diagrama de Hasse para la relación inclusión en P(B)

: 

Diagrama de Hasse para A = {2, 3, 4, 6, 8, 12, 24 } con la relación “(a, b) ? R sii a divide a b : a|b” Retorno

Slide 27: 

Relaciones de equivalencia

Slide 28: 

Sea A un conjunto no vacío en el conjunto Universal U. Una relación binaria R sobre A, es una relación de equivalencia si R satisface las tres propiedades: R es reflexiva R es simétrica R es transitiva Una relación de equivalencia identifica los elementos de un conjunto que satisfacen una misma propiedad y los llama elementos equivalentes. Relaciones de equivalencia

Partición de un conjunto : 

Partición de un conjunto Definición: Ejemplos: Sea A = {1, 2, 3, 4, 5} una partición P de A, con 3 celdas, es P = { {1,3}, {4}, {2,5} }, donde A1={1,3}, A2={4}, A3={2,5}. En efecto {1,3}? {4}=? ? {1,3} ? {2,5}= ? ? {4} ? {2,5}=?. Además {1,3} ? {4}? {2,5} = {1, 2, 3, 4, 5} = A

Clase de equivalencia : 

Clase de equivalencia Definición: Sea R una relación de equivalencia en un conjunto A no vacío. Sea a ? A, llamaremos clase de equivalencia de a y la escribiremos por [a] al conjunto de todos los elementos que están relacionados con a, es decir [a] = { x ? A / x R a } Ejemplo: La relación R sobre Z : a R b ? a – b es múltiplo de 2. Hay dos clases de equivalencia distintas, la del 0 y la del 1: [0] = { 0, ±2, ±4, ±4,… } y [1] = { ±1, ±3, ±5,… }

Clase de equivalencia : 

Clase de equivalencia Definición: Sea R una relación de equivalencia en A. El conjunto de las clases de equivalencia se llama conjunto cociente de A por R. El conjunto cociente es una partición de A En efecto, Las clases de equivalencia son disjuntas dos a dos. La unión de todas las celdas coincide con el conjunto A.

Clase de equivalencia : 

Clase de equivalencia Demostración: 1) Sean ?x, ?y ? A ? [x]= [y] ? [x] ? [y] = ? i) Si x R y ? [x]= [y]; sea z ? [x] ? z R x ? x R y ? z R y (transitividad) ? z ? [y], de donde [x] ? [y]. Razonando de manera similar se prueba que [y] ? [x]. Por lo tanto, [x] = [y]. ii) Si (x,y) ? R entonces [x] ? [y] = ?. En efecto, si existiera z ? [x] ? [y] entonces z R x ? z R y por lo tanto, x R y, lo cual es un absurdo.

Clase de equivalencia : 

Clase de equivalencia Demostración: 2) Veamos que En efecto, si ?x ? A, como R es reflexiva, x R x ? x ? [x] Por otro lado, sea z tal que

Ejemplo : 

Ejemplo A={palabras de n bits} w(a) el número de unos que contiene a aRb ?w(a) = w(b) (mod 2) R es de equivalencia: Reflexiva: aRa w(a) = w (a)(mod 2) Simétrica: aRb?bRa w(a) = w(b)(mod 2) ? w(b)=w(a)(mod 2) Transitiva: aRb y bRc?aRc w(a)=w(b)(mod 2) y w(b)=w(c)(mod 2) ?w(a)=w(c) R define en A una partición formada por dos clases de equivalencia, cada una con 2n-1 elementos [0]={a?A / a tiene un número par de unos} [1]={a?A / a tiene un número impar de unos} Para n=3 [0]={000, 011, 101, 110} [1]={001, 010, 100, 111}

Clase de equivalencia : 

Clase de equivalencia Toda relación de equivalencia sobre A genera una partición en A. Toda partición sobre el conjunto A, genera una relación de equivalencia

Ejemplos : 

Ejemplos Relaciones de equivalencia La relación R sobre Z2 definida por: (x,y) R (a,b) ? x+y = a+b La relación R sobre ?2 definida por: (x,y) R (a,b) ? x.y = a.b Se puede demostrar que ambas son relaciones de equivalencia ya que verifican las propiedades reflexiva, simétrica y transitiva. A continuación veremos los conjuntos cocientes de ambas relaciones

Conjunto cociente de (x,y)R(a,b) sii x+y=a+b, R definida sobre Z2; los puntos (resaltados), unidos por trazos de color verde pertenecen a la misma clase de equivalencia, esto es: [(5;0)]={(10;-5), (0;5), (-5;10), (-10;15)……….} [(0;0)]={(-5;5), (-10;10), (10;-10), (5;-5), ……….} puntos (resaltados) ,unidos por trazos azules : 

Conjunto cociente de (x,y)R(a,b) sii x+y=a+b, R definida sobre Z2; los puntos (resaltados), unidos por trazos de color verde pertenecen a la misma clase de equivalencia, esto es: [(5;0)]={(10;-5), (0;5), (-5;10), (-10;15)……….} [(0;0)]={(-5;5), (-10;10), (10;-10), (5;-5), ……….} puntos (resaltados) ,unidos por trazos azules

(x,y)R(a,b) sii x.y=a.b, R definida sobre ?2 ; los puntos que están en una misma curva pertenecen a la misma clase de equivalencia, esto es: [(12;2)]={(10;2,4), (2,4;10), (-10;-2,4), (-12;2)……….} puntos en la curva celeste (todos) [(12;1)]={(10;1,2), (1,2;10), (-12;-1), (-4,8;-2,5), (4,8;2,5)……….} ,puntos en la curva rosa (todos) : 

(x,y)R(a,b) sii x.y=a.b, R definida sobre ?2 ; los puntos que están en una misma curva pertenecen a la misma clase de equivalencia, esto es: [(12;2)]={(10;2,4), (2,4;10), (-10;-2,4), (-12;2)……….} puntos en la curva celeste (todos) [(12;1)]={(10;1,2), (1,2;10), (-12;-1), (-4,8;-2,5), (4,8;2,5)……….} ,puntos en la curva rosa (todos)