RELACIONES 1 - Jair García

Vista previa del material en texto

Unidad III. Relaciones Definiciones básicas 
Una introducción a las matemáticas de la computación 100 
 
Unidad III: Relaciones 
 
3.1 Definiciones básicas. 
3.1.1 Relaciones binarias. 
3.1.2 Dominio e Imagen de una relación. 
3.1.3 Representación de una relación. 
3.1.4 Composición de relaciones. 
 
3.2 Propiedades de las relaciones. 
3.2.1 Propiedad Reflexiva. 
3.2.2 Propiedad Irreflexiva. 
3.2.3 Propiedad Simétrica. 
3.2.4 Propiedad Antisimétrica. 
3.2.5 Propiedad Transitiva. 
 
3.3 Relaciones de orden. 
 
3.4 Relaciones de equivalencia. 
3.4.1 Clases de equivalencia. 
3.4.2 El conjunto cociente. 
 
3.5 Funciones. 
 
3.1 DEFINCIONES BÁSICAS 
 
3.1.1 Relaciones binarias 
 
Definición 3.1.1 (Relación) 
Una relación R de un conjunto X en un conjunto Y es un subconjunto del producto 
cartesiano X×Y, es decir, R⊆XxY. 
 
Si (x,y) ∈ R se escribe “xRy” y se dice que x está relacionado con y o que x está en relación 
con y. En el caso que el conjunto X es igual al conjunto Y, afirmamos que R es una relación 
binaria sobre X o sobre Y. 
De este modo notamos que una relación queda determinada por cualquier subconjunto del 
producto cartesiano. 
 
Ejemplo 3.1.1 
Sean los conjuntos X={1,2,3} y Y={1,2}. 
El producto cartesiano de X y Y es: X×Y={(1,1), (1,2), (2,1), (2,2), (3,1), (3,2)}. 
Son relaciones de X en Y las siguientes: 
R1={(1,1), (2,1), (3,1)}. 
R2={(2,2)}. 
R3={(1,1), (1,2), (2,1), (2,2), (3,1), (3,2)}= X×Y. 
R4=φ=relación vacía. 
 
Unidad III. Relaciones Definiciones básicas 
Una introducción a las matemáticas de la computación 101 
 
Aquí presentamos cuatro relaciones de X en Y, pero ¿cuantas relaciones se podrán 
obtener?. En general ¿es posible determinar el número de relaciones que se pueden obtener a 
partir de dos conjuntos X y Y?. 
 
Recordando la definición de relación como un subconjunto del producto cartesiano, la 
pregunta se puede replantear como ¿cuántos subconjuntos hay del conjunto producto cartesiano?. 
 
Al conjunto de subconjuntos de un conjunto es lo que llamamos conjunto potencia, así hay 
que determinar el número de elementos del conjunto potencia del producto cartesiano de X y Y, 
esto es, la cardinalidad del conjunto potencia, lo cual nos dará el número de relaciones posibles 
de X en Y. 
 
En el ejemplo anterior notamos que la cardinalidad del conjunto producto cartesiano, es 
|X×Y|=6, luego el número de subconjuntos de X×Y es 26=64=23x2=2|X||Y|, es igual a 2 elevado a la 
cardinalidad de X por la cardinalidad de Y. 
 
Así en este ejemplo es posible determinar 64 posibles relaciones de X en Y, incluyendo al 
producto cartesiano, y la relación que llamamos vacía, determinada por el conjunto vacío1. 
 
Este resultado nos sugiere la propiedad siguiente. 
 
Propiedad 3.1.1 
Para conjuntos finitos X y Y con |X|=m y |Y|=n, existen 2mn relaciones de X en Y, 
incluyendo la relación vacía y la propia relación X×Y. 
 
También existen 2nm=2mn relaciones de Y en X, una de las cuales es también la relación 
vacía φ, y otra es Y×X. Esto es porque de cualquier relación R1 de Y en X puede obtenerse una 
única relación R2 de X en Y, invirtiendo simplemente los componentes de cada par ordenado en 
R1. 
 
3.1.2 Dominio e Imagen de una relación 
 
Definición 3.1.2 (Dominio de una relación) 
Sea R una relación de X en Y, el dominio de la relación R se denotas por DR y se define 
como el conjunto de todas las x tales que (x,y)∈R, es decir: 
DR={x | (x,y)∈R para algún y∈Y} 
 
Definición 3.1.3 (Imagen de una relación) 
Sea R una relación de X en Y, la imagen de la relación R se denota por IR y se define como 
el conjunto de todas las y tales que (x,y)∈R, es decir: 
IR={y | (x,y)∈R para algún x∈X} 
 
 
 
1 Recordemos que el conjunto vacío es subconjunto de cualquier conjunto. 
 
Unidad III. Relaciones Definiciones básicas 
Una introducción a las matemáticas de la computación 102 
 
Ejemplo 3.1.2 
Sean A={1,2,3} y B={a,b,c}. 
Determinar el dominio y la imagen de las relaciones dadas. 
a) R1={(1,a), (1,b), (1,c)}. 
b) R2={(1,a), (2,b), (3,c)}. 
c) R3={(1,a), (2,a), (3,a)}. 
 
Solución 
a) DR1={1} IR1={a,b,c} 
b) DR2={1,2,3} IR2={a,b,c} 
c) DR3={1,2,3} IR3={a} 
 
Para la relación R3, es posible considerar que el contradominio es {a,b,c}. Sin embargo 
notemos que el concepto que estamos usando es el de imagen y no el de contradominio ya que 
este último contiene a la imagen, tal y como se presenta en cálculo. 
 
3.1.3 Representación de una relación 
 
Una relación se puede representar de diferentes formas, estas son: con el uso de una 
condición, un conjunto (tal y como lo presenta la definición), una tabla (idea intuitiva), un dígrafo 
y una matriz. La que más usamos es la que se presenta en la definición, esto es como un conjunto. 
 
1. Representación por medio de una condición 
 
Es posible representar a la relación por medio de una condición, en este caso es necesario 
conocer donde está definida. En la mayoría de las veces esta representación es, de donde se parte 
para el uso de otras representaciones de la relación en donde ya es posible observar todos los 
elementos que están en ella. 
 
Ejemplos 3.1.3 
a) Consideramos una relación R definida como sigue: 
Decimos que x está en relación con y (xRy) si x cursa la asignatura y. 
Este enunciado nos presenta la condición que deben cumplir todos los elementos de X y Y 
para estar en la relación R. 
 
b) Sean X={1,2,3,4} y Y={1,3,5} 
Decimos que x está en relación con y (xRy) si x y y son números primos en XxY. 
Los elementos de la relación deben cumplir la condición de que sean primos. 
 
Observe que si la condición debe cumplirse en YxX la relación sería {(3,2), (3,3)}, la cual 
es diferente a la que se obtiene en XxY, por eso es importante especificar donde está definida la 
relación. 
 
c) Sea X={1,2,3,}. 
Decimos que x está en relación con y (xRy) si x + y es par en XxX. 
Los elementos de la relación deben cumplir la condición de que su suma sea par. 
 
Unidad III. Relaciones Definiciones básicas 
Una introducción a las matemáticas de la computación 103 
 
2. Representación por medio de una tabla 
 
En esta representación se especifican los elementos de x con su y correspondiente. 
 
Ejemplos 3.1.4 
Considere las relaciones definidas en el ejemplo 3.1.3. 
a) Consideremos que los elementos que están en la relación se presentan en la tabla siguiente: 
 
 
El dominio de la relación es: 
DR={Benito, María, Carmen, David} 
={B,M,C,D}. 
 
La imagen de la relación es: 
IR={Computación, Matemáticas, Artes, 
Historia}={C,M,A,H}. 
 
Observe que si una relación se representa mediante una tabla, el dominio esta formado por 
elementos de la primera columna, y la imagen por los miembros de la segunda. 
 
b) 
 
 
El dominio de la relación es DR={2,3}. 
La imagen de la relación es IR={3,5}. 
 
 
 
c) 
 
 
El dominio de la relación es DR={1,2,3}. 
La imagen de la relación es IR={1,2,3}. 
 
 
 
 
 
3. Representación por medio de un conjunto 
 
Esta representación queda determinada de la definición de relación, ya que se define a la 
relación como un conjunto. Dado que un conjunto se puede representar por extensión o por 
compresión, este puede obtenerse por medio de una condición en donde emplearemos la 
representación de la relación como una condición y posteriormente como un conjunto, o puede 
darse sólo el conjunto que representa a la relación únicamente como un subconjunto del producto 
cartesiano. 
x cursa la asignatura y 
x y 
Benito Computación 
María Matemáticas 
Benito Artes 
Carmen Historia 
Carmen Computación 
David Matemáticas 
x y y son números primos 
x y 
2 3 
2 5 
3 3 
3 5 
x + y es un número par 
x y 
1 1 
1 3 
2 2 
3 1 
3 3 
 
Unidad III. Relaciones Definiciones básicas 
Una introducción a las matemáticas de la computación 104 
 
Ejemplo 3.1.5 
Consideremos las relaciones definidas en el ejemplo 3.1.3. 
a) R={(B,C), (B,A), (M,M), (C,H), (C,C), (D,M)}. 
 
b) R={(2,3), (2,5), (3,3), (3,5)}. 
 
c) R={(1,1),(1,3), (2,2), (3,1), (3,3)}. 
 
4. Representación por medio de un digrafo 
 
El concepto de dígrafo se desarrollará en una unidad posterior por el momento daremos una 
idea gráfica del concepto; un digrafo está formado por puntos y por arcos (líneas con dirección). 
 
Así, un digrafo nos representa una relación si tomamos los elementos de los conjuntos 
dominio e imagen como los puntos y la relación entre estos como arcos del digrafo. 
 
Si los conjuntos donde está definida la relación son diferentes se presentan dos columnas de 
puntos, estos puntos se unen por medio de líneas con dirección las cuales indican la relación entre 
los mismos. Si los conjuntos son iguales (la relación está definida sobre un conjunto) sólo se 
presentan una vez los puntos. 
 
El siguiente ejemplo ilustra una relación representada por medio de un digrafo. 
 
Ejemplo 3.1.6 
Consideremos las relaciones definidas en el ejemplo 3.1.5. 
 
a) Considere los conjuntos X={B,M,C,D}, 
Y={C,A,M,H}. 
y la relación R definida como: 
R={(B,C), (B,A), (M,M), (C,H), (C,C), (D,M)}. 
El dígrafo que representa esta relación es: 
 
 
 
b) Sean X={1,2,3,4}, 
Y={1,3,5} y 
R={(2,3),(2,5)(3,3)(3,5)} 
El digrafo que representa esta relación es 
 
 
c) Sean X={1,2,3}, 
 R={(1,1), (1,3), (2,2) (3,1), (3,3)} 
El dígrafo que representa esta relación es: 
 
 
 
 
 
 
 
Unidad III. Relaciones Definiciones básicas 
Una introducción a las matemáticas de la computación 105 
 
Ejemplo 3.1.7. 
Sea X={1,2,3} y 
R={(1,2), (1,3), (2,2), (3,1)}. 
El digrafo que representa la relación es: 
 
 
5. Representación por medio de una matriz 
 
Para dar la representación de una relación por medio de una matriz empecemos por definir 
el concepto. 
 
Definición 3.1.4 (Matriz cero-uno) 
Una matriz cero-uno mxn, E=(eij)mxn es una disposición rectangular de números en m 
filas y n columnas, donde cada eij, para mi ≤≤1 y nj ≤≤1 , denota la entrada de la i–ésima fila 
y la j-ésima columna de E y cada una de dichas entradas es 0 o 1. 
 
Una matriz es una forma conveniente de representar una relación R de X en Y. Etiquetamos 
las filas con los elementos de X y las columnas con los elementos de Y. Entonces colocamos un 1 
en el renglón x y la columna y si xRy, y un 0 en caso contrario. 
 
Ejemplo 3.1.8 
La matriz 










=
0001
1010
1001
E es una matriz 3x4, donde por ejemplo e11=1, e23=0 y e31=1. 
 
Ejemplo 3.1.9 
Considere la relación definida en los incisos b) del ejemplo 3.1.3. 
Sean A={1,2,3,4}, B={1,3,5} y R={(2,3),(2,5)(3,3)(3,5)}. 
La matriz de relación es: R=












0 0 0
1 1 0
1 1 0
0 0 0
 
 
Ejemplo 3.1.10 
a) Considere la relación definida en los incisos c) del ejemplo 3.2. 
Sea A={1,2,3} y R={(1,1), (1,3), (2,2) (3,1), (3,3)}. 
Matriz de relación, R=










1 0 1
0 1 0
1 0 1
 
 
 
 
 
Unidad III. Relaciones Definiciones básicas 
Una introducción a las matemáticas de la computación 106 
 
b) Sea R={(1,b), (1,d), (2,c) (3,c), (3,b), (4,a)} de X={1,2,3,4} y Y={a, b, c, d}. 
Matriz de relación, R=












0001
0110
0100
1010
 
Ejemplo 3.1.11 
La matriz de relación de R={(a,a), (b,b), (c,c), (d,d), (b,c), (c,b)} sobre {a,b,c,d} es 
R=












1000
0110
0110
0001
 
 
Observe que la matriz sobre un conjunto X siempre es una matriz cuadrada. 
 
En el ejemplo siguiente consideraremos una relación y sus distintas formas de 
representación. 
 
Ejemplo 3.1.12 
Sea X={1,2,3,4} y definimos la relación sobre X como: 
1) Representación por condición. 
xRy si x<y. 
 
2) Representación por conjunto. 
R={(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}. 
 
3) Representación por Tabla. 
X Y 
1 2 
1 3 
1 4 
2 3 
2 4 
3 4 
 
4) Representación por Digrafo. 
 
 
 
 
 
 
 
 
 
Unidad III. Relaciones Definiciones básicas 
Una introducción a las matemáticas de la computación 107 
 
5) Representación por Matriz. 












=
0000
1000
1100
1110
R 
 
Finalmente notemos que el dominio de la relación es {1,2,3} y la imagen es {2,3,4} 
 
Definición 3.1.5 (Relación inversa) 
Sea R una relación definida en AxB. La inversa de R, denotada por R-1, es la relación de B 
en A definida como 
R-1={(y,x) | (x,y)∈R} 
 
Ejemplo 3.1.13 
a) Sean X={1,2,3,4}, Y={1,3,5} y R={(2,3),(2,5)(3,3)(3,5)} definida en XxY. 
R-1={(3,2), (5,2), (3,3), (5,3)}. 
 
b) Considere la relación definida en el ejemplo 3.1.12. 
xRy si x<y definida en X={1,2,3,4}. 
R={(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}. 
R-1={(2,1), (3,1), (4,1), (3,2), (4,2), (4,3)}. 
 
Definición 3.1.6 (Composición de relaciones) 
Sea R1 una relación de X a Y y R2 una relación de Y a Z. La composición de R1 y R2, 
denotada por R2 R1, es la relación de X a Z definida por 
R2 R1={(x,z) | (x,y)∈R1 y (y,z)∈R2 para algún y∈Y}. 
 
Propiedad 3.1.2 
La composición de relaciones es asociativa, esto es 
R3 R2 R1=R3  (R2 R1) = (R3 R2) R1 
 
Ejemplo 3.1.14 
a) Sean R1 y R2 relaciones sobre X={1,2,3,4} dadas por: 
R1={(1,1),(1,2),(3,4),(4,2)}. 
R2={(1,1),(2,1),(3,1),(4,4),(2,2)}. 
R2 R1 = {(1,1), (1,2), (3,4), (4,1), (4,2)}. 
R1 R2 = {(1,1), (1,2), (2,1), (2,2), (3,1), (3,2), (4,2)}. 
 
b) Sean X={1,2,3}, Y={2,4,6,8}, Z={u,s,t} y R1 , R2 relaciones definidas en XxY y YxZ 
respectivamente como 
R1={(1,2),(1,6),(2,4),(3,4),(3,6),(3,8)} y R2={(2,u),(4,s),(4,t),(6,t),(8,u)}. 
R2 R1={(1,u),(1,t),(2,s),(2,t),(3,s),(3,t),(3,u)} es una relación definida en XxZ. 
 
 
 
Unidad III. Relaciones Definiciones básicas 
Una introducción a las matemáticas de la computación 108 
 
Definición 3.1.7 (Potencia de una relación) 
Dado un conjunto X una relación R sobre X, definimos la potencia de R de manera 
recursiva como 
1. R1=R 
2. para n∈Z+, Rn+1=RnR 
Es decir, R2=R R, R3=R2 R=R R R, R4=R3 R=R RR R, etc. 
 
Ejemplo 3.1.15 
Considere las siguientes relaciones definidas sobre X={a,b,c}. 
a) R1={(a,b), (a,c), (c,b)}. 
2
1R ={(a,b)}. 
...41
3
1 === RR φ 
 
b) R2={(a,b), (b,c), (c,a)}. 
2
2R ={(a,c), (b,a), (c,b)}. 
3
2R ={(a,a), (b,b), (c,c)}. 
2
4
2 RR = , 
4
2
5
2 RR = , 
3
2
6
2 RR = . 
 
c) R3={(a,b), (b,c), (c,c)}. 
2
3R ={(a,c), (b,c), (c,c)}= ...
5
3
4
3
3
3 === RRR 
 
d) R4={(a,b), (b,a), (c,c)}. 
 
2
4R ={(a,a), (b.b), (c,c)=. 
4
3
4 RR = , 
2
4
4
4 RR = . 
 
Es posible decir que cuando mucho hay n potencias distintas de R. Rm, m>n, se puede 
expresar con base en R, R2,…,Rn. 
Ahora bien podemos definir R+ como ...32 ∪∪∪=+ RRRR 
 
Ejemplo 3.1.16 
Considere las relaciones definidas en el ejemplo 3.1.15. 
a) 1
3
1
2
111 ... RRRRR =∪∪∪=
+ = {(a,b), (a,c), (c,b)} 
b) 32
2
22
3
2
2
222 ... RRRRRRR ∪∪=∪∪∪=
+ = 
{(a,b),(b,c),(c,a),(a,c),(b,a),(c,b),(a,a),(b,b),(c,c)} 
c) 233
3
3
2
333 ... RRRRRR ∪=∪∪∪=
+ ={(a,b), (b,c), (c,c), (a,c)} 
d) 244
3
4
2
444 ... RRRRRR ∪=∪∪∪=
+ ={(a,b), (b,a), (c,c), (a,a), (b,b)} 
Observe que ++++ ⊆⊆⊆⊆ 44332211 y , , RRRRRRRR . 
 
 
Unidad III. Relaciones Definiciones básicas 
Una introducción a las matemáticas de la computación 109 
 
Ejemplo 3.1.17 
Sean R = {(1,2),(3,4),(2,2) y S = {(4,2),(2,5),(3,1),(1,3)} 
Encuentre: R°S, S°R, R°(S°R), (R°S)°R, R°R, S°S y R°R°R. 
Solución 
R°S={(1,5),(3,2),(2,5)}. 
S°R={(4,2),(3,2),(1,4)}. 
(R°S)°R={(3,2)}. 
R°(S°R)={(3,2)}. 
R°R={(1,2),(2,2)}. 
S°S={(4,5),(3,3),(1,1)}. 
R°R°R={(1,2), (2,2)}. 
 
Como las relaciones son conjuntos, cumplen las mismas propiedades y definiciones que 
estos. El siguiente teorema puede demostrarse basándose en las definiciones y propiedades de los 
conjuntos. 
 
Teorema 3.1.1 
Supóngase que R y S son relaciones de A en B 
a) Si .11 −− ⊂→⊂ SRSR 
b) Si .RSSR ⊂→⊂ 
c) ( ) .111 −−− ∩=∩ SRSR 
d) ( ) .111 −−− ∪=∪ SRSR 
e) ( ) .RSSR ∪=∩ 
f) ( ) .RSSR ∩=∪ 
	3.1 DEFINCIONES BÁSICAS