RELACIONES

Lic. Clara Grinblat

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

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

1) ¿ A x B = B x A?

No son iguales ... Por ej. si 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) }

2)Si A y B son finitos el número de elementos de

A x B es llamado cardinal de A x B y denotado porA x B

A x B = A . BAdemás A . B = B . A = B x AEntonces A x B = B x A

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

Producto cartesiano

B

1

2

3

0

EJEMPLO

Sean A = {1, 2, 3} y B = {0, 1, 2, 3}. Entonces

A x B={(1,0),(1,1),(1,2),(1,3),(2,0),(2,1),(2,2),(2,3),(3,0).(3,1),(3,2),(3,3)}

Consideremos el siguiente subconjunto de AxB

R = { (a, b) A x B / a + b 3}

1 2 3 A

0

Nos interesan algunos

subconjuntos del

producto cartesiano

RELACIONES BINARIAS

Dados dos conjuntos A y B, una relación R binaria es cualquier subconjunto de AxB

R ⊆ A × B

Notación: Si a∈A y b∈B, para decir que a está relacionado con b por R escribimos:

(a,b)∈R o aRb

Si a no está relacionado con b, entonces (a,b)∉R

Si B=A, se dice que R es una relación binaria definida en A . Escribimos R ⊆ A × A

EJEMPLOS

Algunos elementos de la relación son:

( 2 ,1 ) , (4, 2) , ( 10, 5) , (20,10) , (100,50), etc

Sea R definida en N por medio de R={(x,y)/x es el doble de 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 divide a y} NxN

DISTINTAS FORMAS DE REPRESENTAR

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 CON 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 tieneen todas las filas 1 porque todos lospares 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 filaporque corresponde al elemento a de Aque se relaciona con los dos elementos

i, u de B; a R2 i, a R2 u y ceros en lasegunda fila porque el elemento o de A nose relaciona con ningún elemento de B enR2

00

11M R

2

00

01M R

3

11

11M R

4

DEFINICIONES:

Sea R una relación 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 x R 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 v (y,x)

∉ R ]

1) En N, “x R y ⇔ x divide a y”

es reflexiva ya que ∀x∈N, x R x porque x divide a x

2) En N, “a R b ⇔ a es el doble de b”.

no es reflexiva ya que (1,1)∉R ya que 1 no es el doble de 1

3) En Z, “a R b ⇔ a – b es múltiplo de 2”.

es simétrica ya que si a R b ⇒ p ∈ Z tal que a – b =2p

b – a = 2(-p) con -p ∈ Z ⇒ b R a

4) En N, “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, “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, “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, “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, “a R b ⇔ a – b es múltiplo de 2” no es anti simétrica ya

RESUMEN

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

ANÁLISIS 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 Y NOTACIÓ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

a R b a ≤ bSe 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 a R b o b R a

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:

1) (N, ) es un conjunto totalmente ordenado.

2) Sea U = {1, 2, 3} y en P(U) = { , {1} {2} {3} {1,2} {1,3}

{2,3} {1,2,3}} 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

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

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)

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 (CONTINUACIÓN)

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).

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:

DIAGRAMAS DE HASSE:

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

A = {2, 3, 4, 6, 8, 12 } con la relación

“(a, b) R sii a divide a b : a|b”

Observamos que no están relacionados:

2 con 3

4 con 6

3 con 4

La relación es de orden parcial ya que no todo par de elementos es comparable

Retorno

DIAGRAMA DE HASSE (CONTINUACIÓN)

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

CLASES 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,… }

PARTICIÓN DE UN CONJUNTO

Definición:

Ejemplos:

1) 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

Sea A un conjunto no vacío. Sean

Diremos que P es una partición de A y escribimos si:

y AA jJj

ji J,ji, AA ji

ΝJ J,j ,A y AAjj

jAΡ

Cada subconjunto Aj es una celda de la partición

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.

Ax/ xA/R

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

xxAx

xAAx

Demostración:

2) Veamos que

En efecto, si x A, como R es reflexiva, x R x x [x]

xAAx

AxAx

AzzRxA, xalgún para ,xzxzAx

Por otro lado, sea z tal que

EJEMPLOS

Relaciones de equivalencia

1) La relación R sobre (Z+)x(Z+) definida por: (x,y) R (a,b)

x+y = a+b

1) 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

PARTICIÓN DE (Z+)X (Z+)

Conjunto cociente de

(x,y)R(a,b) sii x+y=a+b, R

definida sobre (Z+)x (Z+); los

puntos (resaltados), unidos

por trazos pertenecen a la

misma clase de

equivalencia, esto es:

[(4;5)]={(2;7), (1;8), (3;6), (

5;4), (6;3), (7;2)}

[(2;2)]={(1;3), (3;1)}

En el gráfico vemos

[(4;5)], [(4;4)], [(4;3)], [(4;2)], [(

4;1], [(3;1)], [(1;2)]

PARTICIÓN DE 2

(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)

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

Porque de la cantidad 2n la mitad tiene un número par de 1 y la otra mitad

un número impar

[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}