Con frecuencia queremos expresar que dos objetos mantienen entre sí una determinada relación.
Por ejemplo:
Podemos representar todas estas situaciones mediante relaciones.
Las relaciones permiten estudiar de manera general propiedades como la simetría, la transitividad o la reflexividad. También sirven para construir otras estructuras importantes.
En particular, las funciones pueden entenderse, desde un enfoque conjuntista, como relaciones que satisfacen determinadas condiciones adicionales.
Sean A y B dos conjuntos.
Una relación R de A en B es un subconjunto del producto cartesiano
A x B.
Por tanto,
R sub A x B.
Si
(a,b) en R,
decimos que a está relacionado con b mediante R.
Podemos escribir esta afirmación de forma más breve como
a R b.
Por tanto,
a R b <-> (a,b) en R.
Sean
A = {1,2,3}
y
B = {a,b}.
Podemos definir la relación
R = {(1,a),(1,b),(3,b)}.
Como
(1,a) en R,
podemos escribir
1 R a.
También tenemos
1 R b
y
3 R b.
En cambio,
2 R a
es falso, porque
(2,a) noen R.
Una relación no tiene por qué relacionar todos los elementos de A con algún elemento de B, ni tiene por qué relacionar cada elemento con un único elemento.
En este ejemplo, 2 no está relacionado con ningún elemento de B, mientras que 1 está relacionado con dos elementos distintos.
Estas posibilidades serán importantes cuando comparemos posteriormente las relaciones con las funciones.
El dominio de una relación R sub A x B es el conjunto de los elementos de A que están relacionados con algún elemento de B.
Podemos definirlo como
dom(R) = {a en A : exi b en B: a R b}.
En el ejemplo anterior,
R = {(1,a),(1,b),(3,b)},
por lo que
dom(R) = {1,3}.
El elemento 2 pertenece a A, pero no pertenece al dominio efectivo de R porque no está relacionado con ningún elemento de B.
La imagen de una relación R es el conjunto de los elementos de B que están relacionados con algún elemento de A.
Podemos escribir
im(R) = {b en B : exi a en A: a R b}.
En nuestro ejemplo,
im(R) = {a,b}.
Algunas fuentes utilizan también el término rango para este conjunto.
Conviene distinguir el conjunto B con el que hemos definido la relación de su imagen efectiva: pueden existir elementos de B que no estén relacionados con ningún elemento de A.
Dada una relación
R sub A x B,
podemos invertir el orden de cada par y obtener una relación
R^-1 sub B x A.
La definimos mediante
b R^-1 a <-> a R b.
Equivalentemente,
R^-1 = {(b,a) en B x A : (a,b) en R}.
Por ejemplo, si
R = {(1,a),(1,b),(3,b)},
entonces
R^-1 = {(a,1),(b,1),(b,3)}.
Invertir dos veces una relación devuelve la relación original:
(R^-1)^-1 = R.
Supongamos que tenemos
R sub A x B
y
S sub B x C.
Podemos construir una nueva relación entre A y C.
Decimos que a está relacionado con c mediante la composición cuando existe algún elemento b de B que conecta ambos pasos:
a R b
y
b S c.
Escribiremos la composición como
S comp R.
Por definición,
a (S comp R) c <-> exi b en B: a R b y b S c.
Obsérvese el orden: primero se aplica R, de A a B, y después S, de B a C.
Por ejemplo, supongamos
R = {(1,a),(2,b)}
y
S = {(a,x),(b,y)}.
Entonces
S comp R = {(1,x),(2,y)}.
La composición de relaciones es asociativa:
T comp (S comp R) = (T comp S) comp R
siempre que los conjuntos implicados permitan realizar las composiciones.
En general, no es conmutativa:
S comp R != R comp S.
De hecho, una de las dos composiciones puede estar definida en un contexto en el que la otra ni siquiera tenga los conjuntos intermedios adecuados.
Un caso especialmente importante aparece cuando relacionamos elementos de un conjunto A con otros elementos del mismo conjunto.
Una relación sobre A es una relación
R sub A x A.
Por ejemplo, la relación
<
es una relación sobre los números reales.
También lo son
<=
=
y muchas otras relaciones habituales.
Las relaciones sobre un mismo conjunto pueden satisfacer diferentes propiedades estructurales.
Una relación R sobre A es reflexiva cuando todo elemento está relacionado consigo mismo:
pt a en A: a R a.
Por ejemplo, la relación
<=
sobre los números reales es reflexiva porque
a <= a
para todo número real a.
La igualdad también es reflexiva:
a = a.
En cambio, la relación
<
no es reflexiva, porque nunca se cumple
a < a.
Una relación R sobre A es irreflexiva cuando ningún elemento está relacionado consigo mismo:
pt a en A: no(a R a).
Por ejemplo,
<
es irreflexiva sobre los números reales.
No debe confundirse “no ser reflexiva” con “ser irreflexiva”.
Una relación no reflexiva sólo necesita que exista algún elemento a para el que no se cumpla a R a.
Una relación irreflexiva exige que no se cumpla a R a para ningún elemento.
Una relación R sobre A es simétrica cuando
pt a,b en A: a R b -> b R a.
Por ejemplo, la relación
a R b <-> |a-b| <= 1
sobre los números reales es simétrica.
Si a está a una distancia menor o igual que 1 de b, entonces b está a la misma distancia de a.
La igualdad también es simétrica:
a=b -> b=a.
En cambio,
<
no es simétrica.
De
2 < 3
no sigue
3 < 2.
Una relación R sobre A es antisimétrica cuando
pt a,b en A: a R b y b R a -> a=b.
Esto no significa que la relación sea “lo contrario de simétrica”.
Una relación puede ser simultáneamente simétrica y antisimétrica.
La igualdad es un ejemplo.
La relación
<=
también es antisimétrica, porque
a <= b
y
b <= a
implican
a=b.
Una relación R sobre A es asimétrica cuando
pt a,b en A: a R b -> no(b R a).
Por ejemplo,
<
es asimétrica.
Si
a < b,
entonces no puede cumplirse
b < a.
Toda relación asimétrica es irreflexiva. Si a R a, la asimetría exigiría
no(a R a),
lo que resulta imposible.
Toda relación asimétrica es también antisimétrica.
La antisimetría exige
a R b y b R a -> a=b.
Pero, por asimetría, nunca pueden cumplirse simultáneamente
a R b
y
b R a.
Por tanto, el antecedente de la implicación es siempre falso y la implicación es verdadera por vacuidad.
En consecuencia,
asimétrica -> irreflexiva
y
asimétrica -> antisimétrica.
Los recíprocos no son ciertos en general.
Una relación R sobre A es transitiva cuando
pt a,b,c en A: a R b y b R c -> a R c.
Por ejemplo,
<
es transitiva sobre los números reales.
Si
a < b
y
b < c,
entonces
a < c.
La relación
<=
también es transitiva.
No todas las relaciones lo son.
Por ejemplo, consideremos sobre los números reales la relación
a R b <-> |a-b| <= 1.
Tenemos
0 R 1
y
1 R 2,
pero
0 R 2
es falso, porque
|0-2| = 2 > 1.
Por tanto, esta relación no es transitiva.
Para una relación R sobre A:
Estas propiedades son independientes en muchos casos. No conviene intentar deducirlas simplemente por el significado cotidiano de sus nombres.
Una relación de equivalencia sobre A es una relación que satisface simultáneamente:
La igualdad es el ejemplo más inmediato.
Sin embargo, las relaciones de equivalencia permiten expresar formas más generales de considerar dos objetos como equivalentes respecto de alguna propiedad.
Por ejemplo, sobre los números enteros podemos definir
a R b
cuando a y b dejan el mismo resto al dividirlos por 3.
Así,
1 R 4
4 R 7
y
1 R 7.
Los números relacionados de esta manera pueden agruparse en clases de equivalencia.
Las relaciones de equivalencia y los conjuntos cociente se estudiarán con más detalle en Relaciones de equivalencia.
Determinadas combinaciones de las propiedades anteriores permiten definir relaciones de orden.
Una relación es un orden parcial cuando es:
Por ejemplo, consideremos la relación de divisibilidad sobre los números naturales positivos. En este ejemplo, a, b y c representarán siempre números naturales mayores que cero.
Escribimos
a divide b
cuando existe un número natural positivo k tal que
b=a*k.
Veamos las propiedades de esta relación.
Reflexividad:
pt a en N: a divide a.
Todo número natural se divide a si mismo. Por lo tanto la relación es reflexiva.
Antisimetría:
pt a,b en N: a divide b y b divide a -> a=b.
Si a divide b,
b=a*k_1
donde k_1 es natural.
Si b divide a,
a=b*k_2
donde k_2 es natural.
Por tanto si a divide b y b divide a,
a=b*k_2=(a*k_1)*k_2=a*(k_1*k_2)
Si a*(k_1*k_2)=a, k_1*k_2=1, y para k_1 y k_2 naturales, k_1=k_2=1.
Por tanto,
a=1*b y b=1*a, así que a=b.
En consecuencia, se cumple la antisimetría.
Transitividad:
pt a,b,c en N: a divide b y b divide c -> a divide c.
Si a divide b podemos escribir
b=a*k_1
donde k_1 es un número natural.
Igualmente, si b divide a c,
c=b*k_2
donde k_2 es natural.
De lo que deducimos:
c=b*k_2=(a*k_1)*k_2=a*(k_1*k_2)
y ya que k_1 y k_2 son naturales, k_1*k_2 también lo es, y por tanto,
a divide c.
Por tnato, se verifica la transitividad.
Sin embargo, esta relación no ordena todos los números naturales.
Tomemos como ejemplo 2 y 3.
2 no divide a 3, ni 3 divide a 2.
Los números 2 y 3 son, por tanto, incomparables respecto de esta relación.
Otro ejemplo,
sub
es un orden parcial sobre P(A).
Dados dos subconjuntos B y C de A, puede ocurrir que
B sub C,
que
C sub B,
o que ninguno sea subconjunto del otro.
Por eso hablamos de un orden parcial.
Un orden total añade la condición de que cualesquiera dos elementos puedan compararse.
Para cualesquiera a y b,
a R b o b R a.
La relación
<=
sobre los números reales es un orden total.
Las relaciones de orden merecen un tratamiento más detallado en Relaciones de orden.
Una relación
R sub A x B
puede relacionar un elemento de A con ninguno, uno o varios elementos de B.
Para obtener una función necesitamos imponer dos condiciones adicionales.
Para cada a en A debe existir algún b en B relacionado con a:
pt a en A: exi b en B: a R b.
Además, ese b debe ser único.
Si
a R b
y
a R c,
entonces
b=c.
Una relación que satisface ambas condiciones puede representar una función
f:A -> B.
Por tanto, desde un enfoque conjuntista, una función es una relación que asigna a cada elemento de su dominio exactamente un elemento del codominio.
Esta idea se desarrollará en Funciones.
Para demostrar que una relación posee una propiedad debemos utilizar directamente su definición.
Por ejemplo, supongamos que sobre los números enteros definimos
a R b <-> a-b es par.
Queremos demostrar que R es simétrica.
Supongamos
a R b.
Por definición,
a-b
es par.
Por tanto, existe un entero k tal que
a-b = 2k.
Multiplicando por -1,
b-a = -2k = 2(-k).
Como -k también es un entero,
b-a
es par.
Por definición de R,
b R a.
Por tanto, R es simétrica.
Este procedimiento es general:
Para demostrar que una relación no satisface una propiedad universal basta encontrar un contraejemplo.
Por ejemplo, para demostrar que
a R b <-> |a-b| <= 1
no es transitiva, basta encontrar a, b y c tales que
a R b
y
b R c,
pero
no(a R c).
Podemos escoger
a=0,
b=1,
c=2.
Entonces
|0-1| = 1
y
|1-2| = 1,
por lo que
0 R 1
y
1 R 2.
Sin embargo,
|0-2| = 2,
por lo que
no(0 R 2).
Hemos encontrado un contraejemplo y, por tanto, la relación no es transitiva.
Sean
A = {1,2,3}
y
B = {a,b}.
Considera
R = {(1,a),(2,a),(2,b)}.
Determina:
Sobre los números enteros definimos
a R b <-> a-b es par.
Determina si R es:
Justifica cada respuesta.
Sobre los números reales definimos
a R b <-> a <= b.
Determina cuáles de las propiedades estudiadas satisface R.
Sobre los números reales definimos
a R b <-> |a-b| < 1.
Demuestra que R es reflexiva y simétrica.
Encuentra un contraejemplo que demuestre que no es transitiva.
Sea A un conjunto.
Considera la relación sub sobre P(A).
Demuestra que es reflexiva, antisimétrica y transitiva.
Sean
R = {(1,a),(2,b),(3,a)}
y
S = {(a,x),(b,y)}.
Calcula
S comp R.
Explica por qué la relación
R = {(1,a),(1,b),(2,a)}
no puede representar una función de
{1,2}
en
{a,b}.
Construye una relación sobre
A = {1,2,3}
que sea simétrica pero no reflexiva.
Después construye otra que sea reflexiva pero no simétrica.
Los elementos de A que aparecen como primera componente de algún par de R son 1 y 2.
Por tanto,
dom(R) = {1,2}.
Los elementos de B que aparecen como segunda componente son a y b.
Por tanto,
im(R) = {a,b}.
Invirtiendo los pares,
R^-1 = {(a,1),(a,2),(b,2)}.
La relación es reflexiva.
Para cualquier entero a,
a-a=0,
y 0 es par.
Por tanto,
a R a.
Es simétrica.
Si
a R b,
entonces
a-b
es par.
El número
b-a = -(a-b)
también es par.
Por tanto,
b R a.
No es antisimétrica.
Por ejemplo,
1 R 3
y
3 R 1,
pero
1 != 3.
Es transitiva.
Si
a R b
y
b R c,
entonces existen enteros k y m tales que
a-b=2k
y
b-c=2m.
Sumando,
a-c = (a-b)+(b-c) = 2k+2m = 2(k+m).
Como k+m es entero,
a-c
es par.
Por tanto,
a R c.
Así, R es reflexiva, simétrica y transitiva: es una relación de equivalencia.
La relación <= sobre los números reales es reflexiva porque
a <= a.
Es antisimétrica porque
a <= b
y
b <= a
implican
a=b.
Es transitiva porque
a <= b
y
b <= c
implican
a <= c.
No es simétrica: por ejemplo,
2 <= 3
pero no
3 <= 2.
Tampoco es irreflexiva ni asimétrica, porque
a <= a
para todo a.
Por tanto, <= es un orden parcial y, además, un orden total.
Para cualquier número real a,
|a-a| = |0| = 0 < 1.
Por tanto,
a R a,
y R es reflexiva.
Si
a R b,
entonces
|a-b| < 1.
Por la simetría de la distancia,
|b-a| = |a-b| < 1.
Por tanto,
b R a,
y R es simétrica.
No es transitiva.
Por ejemplo, tomemos
a=0,
b=3/4,
c=3/2.
Entonces
|a-b| = 3/4 < 1
y
|b-c| = 3/4 < 1,
pero
|a-c| = 3/2 > 1.
Por tanto,
a R b
y
b R c,
pero
no(a R c).
Para cualquier B en P(A),
B sub B,
por lo que sub es reflexiva.
Si
B sub C
y
C sub B,
entonces B y C tienen exactamente los mismos elementos.
Por la igualdad de conjuntos,
B=C.
Por tanto, sub es antisimétrica.
Finalmente, supongamos
B sub C
y
C sub D.
Todo elemento de B pertenece a C, y todo elemento de C pertenece a D.
Por tanto, todo elemento de B pertenece a D:
B sub D.
Así, sub es transitiva.
Por consiguiente, sub es una relación reflexiva, antisimétrica y transitiva sobre P(A), y por tanto es un orden parcial.
No es necesariamente un orden total.
Por ejemplo, si
A = {1,2},
los conjuntos
{1}
y
{2}
pertenecen a P(A), pero
{1} no es subconjunto de {2}
y
{2} no es subconjunto de {1}.
Por tanto, {1} y {2} son incomparables respecto de sub.
Tenemos
R = {(1,a),(2,b),(3,a)}
y
S = {(a,x),(b,y)}.
Para obtener S comp R buscamos los elementos intermedios que relacionan cada elemento mediante R y después mediante S.
Tenemos
1 R a
y
a S x,
por lo que
1 (S comp R) x.
También,
2 R b
y
b S y,
por lo que
2 (S comp R) y.
Finalmente,
3 R a
y
a S x,
por lo que
3 (S comp R) x.
Por tanto,
S comp R = {(1,x),(2,y),(3,x)}.
La relación es
R = {(1,a),(1,b),(2,a)}.
Para representar una función de
{1,2}
en
{a,b},
cada elemento del dominio debe estar relacionado con exactamente un elemento del codominio.
Sin embargo,
1 R a
y
1 R b,
con
a != b.
Por tanto, el elemento 1 está relacionado con dos valores distintos.
La relación no satisface la condición de unicidad y no puede representar una función.
Queremos primero una relación simétrica pero no reflexiva sobre
A = {1,2,3}.
Podemos tomar
R = {(1,2),(2,1)}.
Es simétrica porque cada vez que aparece un par (a,b), aparece también (b,a).
No es reflexiva porque, por ejemplo,
(1,1) noen R.
Para obtener una relación reflexiva pero no simétrica podemos tomar
S = {(1,1),(2,2),(3,3),(1,2)}.
Es reflexiva porque contiene
(1,1),
(2,2)
y
(3,3).
Sin embargo,
(1,2) en S
pero
(2,1) noen S.
Por tanto, S no es simétrica.