Relaciones
- Concepto de
Relación - Representación de las
Relaciones - Tipos de Relación y
Operaciones - Propiedades de las
Relaciones
- Para los conjuntos A,
B Í Á , el producto
cartesiano, de A y B se denota con
y se define como
y se define como = {(a, b) tales que aÎ A, b
Î B}
- Decimos que los elementos de son pares ordenados.
- Se define que para todo a Î A Â [a] =
{y Î
B, a  y} - Para los conjuntos A, B Í Á , cualquier subconjunto de
es una
relación de A en B. - Cualquier subconjunto de
son pares ordenados.
es una
es una relación binaria en A.
Producto Cartesiano
Definición de Producto
Cartesiano
Sean A y B dos conjuntos cualesquiera , se define
producto cartesiano, y se denomina A x B, como el conjunto de
todos los pares ordenados cuyas primeras componentes pertenecen
al conjunto (A) y las segundas componentes pertenecen al conjunto
(B).
Conjuntos producto
Un par ordenado (a, b) es una lista de los
objetos a y b con un orden prescrito donde a aparece en primer
lugar y b en el segundo. Por consiguiente, un par ordenado es
únicamente una sucesión de extensión 2. A
partir de la explicación previa sobre las sucesiones
(véase la sección 1.2). Se tiene que los pares
ordenados (a1, b1) y (a2, b2) son iguales si y sólo si a1
= a2 y b1 =b2 Si A y B son dos conjuntos no vacíos, se
define el conjunto producto o el producto
cartesiano A x B como el conjunto de pares ordenados (a, b}
donde a £ A y b £ B. Por tanto,
A x B = {(a, b)|a £ A y b £ B]
B r s
A
1 (1,r) (1,s)
2 (2, r) (2, s)
3 (3.r) (3s)
Ejemplo 1 Sea
A ={1,2, 3} y B={r,s}
Entonces
A x B = {(1, r). (1, s), (2, r), (2, s), (3, r), (3,
s)}
Observe que los elementos de A x B se pueden acomodar
adecuadamente en un arreglo tabular como lo muestra la figura
1.
Teorema 1 Para cualquier par de conjuntos finitos
no vacíos A y B, | A x B | = | A | | B |.
Demostración. Se probará esto por inducción matemática. Sea P{n) la siguiente
proposición: Si A y B son conjuntos finitos y | B | = n,
entonces | A x B | = | A | |B|.
Paso básico. Se prueba P(1). Sea|A| = my |B| =
1.Por tanto, A = {a1 … an} y B as {fci}, por lo cual
AxB={(a1…b1),…,(am,b1)} y |A x B| = m = m-1 =
|A|.|B|
Paso inductivo. Supóngase que P(n) es
verdadera para algun n s 1, y sean A y B conjuntos finitos con
|A|=m y |B|= n+l.Se dice que A = {a1 … am} y B == {b1, …,bn,
bn+1}. Sea C = {b1, …, bn} Entonces, si (a, b) £ A x B, b
£ C o b=bn+1. El número de pares (a, b) cuando b
£ C es | A x C |, que es igual mn. También, hay m
pares (a1, bn+1), (a2, bn+1), …, (am, bn+i) con el segundo
elementó igual a bn+1. Entonces el número total de
pares en A x B es mn + m, esto es | A x B | = mn + m = m(n + 1) =
| A | • |B |, por lo cual P(n + 1) es verdadera.
Si ∏ == a, x1, x2,…, xn,-1,b, ees una trayectoria
de longitud n en una relacion de a a b, entonces la
trayectoria inversa que se escribe
∏~1.
b) Dominio y
codominio
Una relación es un subconjunto R cualquiera de un
producto cartesiano A x B, RÌ A x B Una función es
una relación F de un producto cartesiano A x B tal que si
(a1,b1) (a2,b2)Î
F entonces b1 ≠ b2-à a1 ≠ a2 esto es equivalente a decir
a1= a2 -à
b1=b2. Al conjunto A se le llama dominio de la
función F y al conjunto B se le llama codominio o
contradominio de la función.
2.-REPRESENTACIÓN DE LAS
RELACIONES
Ahora bien, cualquier relación R de un conjunto A
a un conjunto B define unívocamente un subconjunto R* de A
X B como sigue:
R* – {(a, b) : a está en relación con b} =
{(a, b) : a R b}
Por otra parte, cualquier subconjunto R* de A X B define
una' relación R de A a B como sigue:
a R b sii (a, b) Î R*
En vista de la correspondencia que hay entre las
relaciones fi de A a B y los subconjuntos de A X B, volvemos a
definir la relación como sigue:
[Definición] Una relación R
de A a B es un subconjunto de A X B.
Diagrama sagital
Una forma de representar el producto cartesiano es el
diagrama
sagital.
Escriba los elementos de a y los elementos de b en dos
discos disyuntos, y luego dibuje una flecha de " a e a " en " b e
b" cada vez que a este relacionado con b.
Para ver el gráfico seleccione la
opción "Descargar" del menú
superior
c) Grafos
Los grafos son
artefactos matemáticos que permiten expresar de una forma
visualmente muy sencilla y efectiva las relaciones que se dan
entre elementos de muy diversa índole. Un grafo simple
está formado por dos conjuntos.
d) Gráfica cartesiana
Un plano cartesiano se forma por dos rectas que se
interceptan perpendicularmente de modo que, cada una de las
rectas se asocia a un sistema
numérico, donde el punto de intersección es llamado
centro u origen del sistema y se le asigna el número
0.
La recta horizontal se llama eje de las abcisas
(x), o de las "primeras componentes". A la derecha del cero se
ubican convencionalmente valores
positivos y a la izquierda valores negativos.
El eje vertical se llama eje de las ordenadas (y)
o de las "segundas componentes". Sobre el cero, convencionalmente
se ubican los valores
positivos y bajo éste los valores negativos.
e) Matrices.
La construcción de arreglos en filas y
columnas que cumplen con las reglas de una álgebra,
denotados entre ( ), l l o [ ]. (nosotros las representaremos con
[ ]). Se construye la matriz
aumentada A’, del sistema AX=Y, Esta es la matriz mx(n+1)
cuyas primeras n columnas son las de A por X y la última
columna es Y.
f) Listas
Una lista es una sucesión ordenada de objetos, se
escribe abreviando el paréntesis y anotando los elementos
que la conforman separados por comas, y al terminar se cierra el
paréntesis. Por ejemplo (1,2,Z) es una lista cuyo primer
elemento es el numero 1, su segundo es el numero 2 y su tercer
elemento es un conjunto de los enteros.
Es importante señalar que (1,2,3) no es igual que
(3,2,1)
Los elementos de una lista pueden estar repetidos
(3,3,2).
Una lista de longitud dos tiene un nombre especial: par
ordenado.
Una lista de longitud cero se llama lista vacia y se
representa ().
Dos listas son iguales siempre y cuando tengan la misma
losngitud ylos mismos elementos en las posiciones
correspondientes de las dos sean iguales.
Sea R una relación. La inversa de R, representada por
R-1, es la relación que se forma invirtiendo el
orden de todos los pares ordenados en R.
En símbolos,
R- = {(x,y):(y,x)Î R}.
EJEMPLO
Sea
R= {(1,5), (2, 6), (3, 7), (3, 8)}
Entonces
R-1{(5.1)(6,2),(7,3),(8,3)}
Si R es una relación en A, también lo
es R-1. Si R es una relación de A a 5,
entonces R-1 es una relación de B a
A.
Obsérvese que no tiene sentido escribir 1 /R.
Formar la inversa de una Relación tan sólo quiere
decir invertir todos los pares ordenados en la relación;
no tiene nada que ver con la división. El índice
— 1 es una notación cómoda. No hemos
definido una operación general de elevar una
relación a una potencia.
c) unión de relaciones
Sean A Y B dos conjuntos
La union de A Y B es el conhunto de todos los elementos que
estan en A o en B. La union de A y B se indica A U B. en
símbolos podemos escribir lo siguiente
A U B = {x; x Î A o x Î B}
d) intersección de relaciones
Sean A y B dos conjuntos de todos los elementos que
estan tanto en A como en B. La interseccion de A y B se indica A
∩ B.
La interseccion de A y B
La figura muestra la intersección
e) composición de relaciones
Asi como hay operaciones como
+ y x, para combinar enteros y las hay para conbinar los
conjuntos, como U y ∩ hay una operación natural para
combinar relaciones.
Sean los conjuntos A, B y C, y sean F: A
-à B y
g: Bà
C. Entonces la funcion g o f es una funcion de A a C
definida por:
(g o f) (a) = g[f(a)
donde a Î A. la funcion g o f se llama composicon
de g y f.
4.PROPIEDADES DE LAS
RELACIONES
Una relación R en un conjunto A es
reflexiva si (a, a) £ R para todas las a £ A,
esto es, si a R e para todas las a e A. Una relación R en
un conjunto A es irreflexiva si a R a para toda a
£ A.
Por consiguiente, R es reflexiva si cada elemento a e A
está relacionado consigo mismo y es irreflexiva si
ningún elemento está relacionado consigo
mismo.
Ejemplo 1
(a) Sea Δ = [(a, a) a £ A], de modo que A
es la relaciσn de igualdad
en el conjunto A. Entonces A es reflexiva, ya que (a, a)
£ Δ para todas las a e A.
(b) Sea R = {(a, b) e A x A | a + b}, R es la
relación de desigualdad en el conjunto A. Entonces
R es irreflexible, ya que (a, a) £ R para todas las x
€ A.
(c) Sean A = {1, 2, 3}. y Jí = {(1, 1), (1, 2)}.
Entonces A es reflexiva ya
(2,2) R y (.3,3) € R. Por otra parte, R no es
irreflexiva, ya que (1, l) € R.
(d) Sea A un conjunto no vacio. Sea R = Ǿ A x A, la
relación vacía. Enlaces R no es reflexiva,
ya que (a, a) € R para todas las a € A (el conjunto
vacío tiene elementos). Sin embargo, R es irreflexiva.
^
Es posible caracterizar una relación reflexiva o
irreflexiva por su matriz con sigue. La matriz de una
relación reflexiva deberá tener unos en toda su
diagon principal; en cambio, la
matriz de una relación irreflexible deberá tener
ceros.
De igual manera, es posible caracterizar una
relación reflexiva o irreflexiva por su grafo dirigido
como sigue. Una relación reflexiva tiene un ciclo de
longitud 1. Que cada vértice; en cambio, una
relación irreflexiva no tendrá ciclos de longitud
1. De manera útil de decir lo mismo es usar la
relación de igualdad
Δ en un conjunto A es reflexiva si y
sσlo si Δ € R, y es irreflexible si y sσlo
si A ∩ R = 0.
Finalmente, se deberá observar que, si R es
reflexible en un conjunto A, entonces Dom(R) = Ran(.R) =
A.
Relaciones c)simétricas, d)asimétricas
y e)antisimétricas
Una relación R en un conjunto A es
simétrica si cuando a R b, entonces b R a. De esto se
sigue que R no es simétrica se tiene a y b € A con a
R b, pero b R a. Una relación R en un conjunto A es
asimétrica si cuando a R b, entonces b Ra. De esto se
sigue que R no es simétrica si se tiene a y b e A con
ambos a R b y b R a.
Una relación R en un conjunto A es
antisimétrica si cuando a R b y b R a, entonces a =
b. Otra forma de expresar esta definición es diciendo que
R es antisimétrica si cuando a ≠ b, se tiene a R b o b
R a. De esto se sigue que R no es antisimétrica si se
tiene a y b en A. a ≠ b, y ambas a R b y b R a.
Dada una relación R, sé desea determinar
qué propiedades se cumplen para R Se tendrá
presente la siguiente observación. Una propiedad no
se cumple en general si se encuentra una situación en
donde la propiedad no se cumpla. Si no hay situación
alguna en la que la propiedad no se cumpla, se deberá
concluir que la propiedad se cumple siempre.
Ejemplo sea A = Z, el conjunto de los enteros y
sea
R=[(a,b)€ A xA | a < b}
ya que R es la relación menor que.
¿Es R simétrica, asimétrica o
antisimétrica?
Solución.
simetría. Si a <b, entonces no es verdadero
que b < a, por lo cual no es simétrica.
Asimetría. Si a < b, entonces b < a (b no
es menor que a), por lo cual R es asimétrica.
Antisimetría. Si a ≠ b, entonces a < b o b
< a, por lo cual R es antismétrica.
Ejemplo 3 Sea A el conjunto de las personas y
sea
R = {(x, y) e A x A | x es primo de: y}
Entonces R es una relación
simétrica
Ejemplo 4 Sea A = {1,2,3,4} y sea
R» {(1,2). (2, 2), (3,4), (4,1)}
Entonces R no es simétrica, ya que(l, 2) e R pero
(2, 1) ^ R. Por otra parte, R no es asimétrica, ya que (2,
2) € R. Finalmente R es antisimétrica ya que, si
a≠b, (a, b) no € R o (b, a) no € R
Ejemplo 5 Sea A = Z+, el conjunto de los
enteros positivos y sea
R={(a, b) €A x A |a divide b}
¿Es R simétrica, asimétrica o
antisimétrica?
Solución.
Si a | b, no se sigue que b a, por lo cual R no es
simétrica.
Si a = b = 3, por ejemplo, entonces a R b y b R a, por
lo cual R no es asimétrica.
Si a | b y b | a, entonces a = b, por lo cual R es
antisimétrica.
Es posible caracterizar las propiedades de
simetría, asimetría o antisimetría de una
relación por las propiedades de su matriz. La matriz
m¿{ = [my] de una relación simétrica
satisface la propiedad de que
si mij = 1, entonces mji = 1
Además, si mji == 0, entonces mij = 0. Por
consiguiente, MR es una matriz tal que todo par de
componentes, colocados simétricamente alrededor de la
diagonal principal es un par de ceros o de unos. Se sigue que MR
= MTR, por lo que MR es una matriz
simétrica.
La matriz MR = [mij] de una relación
asimétrica R satisface la propiedad que
si mij == 1, entonces mji = 0.
Si R es asimétrica, se sigue que
mu =s 0 para todas las i; esto es, la diagonal
principal de la matriz MR contiene sólo ceros.
Esto tíene que ser verdadero pues la propiedad
asimetría implica que, si m,, = 1, entonces
m¡¡ = O, lo que es una contradicción.
Finalmente, la matriz MR = [miJ]de una
relación antisimétrica R satisface propiedad que si
i ≠ j, entonces miJ = 0 o miJ = 0.
|
Ejemplo 6
Examine las matrices en la
figura 1, donde cada una es la matriz de una
relación como esté indicado. Las relaciones R1 y R2
son simétricas ya que sus matrices Mr1 Y mr2 son
matrices simétricas. La relación R3 es
antisimétrica, pues no hay posiciones simétricas
dispuestas, fuera de la diagonal de mr3 que contengan un
uno. Estas posiciones pudiera tener ceros, y en la diagonal los
elementos son irrestrictos. La relación R3 no es
asimétrica porque MR3 tiene unos en la diagonal. La
relación R4 no tiene ninguna de las tres propiedades; Mr4
no es simétrica La presencia del uno en la
posición 4, 1 de Mr4 viola las dos propiedades de
asimetría y antisimetria. Finalmente, R3 es
antisimétrica pero no asimétrica, y R6 es a
la vez asimétrica y antisimétrica.
1 1 1 0 1 1 0
0 0 1 = MR11 1 0 0 =
MR2
1 1 1
(a) 1 0 1 1 (b)
0 0 1 1
1 1 1 0 0 1 1
0 1 0 =
MR3 0 0 1 0 =
Mr4
0 0 0 (c) 0 0 0 1 (d)
1 0 0 0
1 0 0 1
0 1 1 1 =
MR5 0 1 1 1
0 0 1 0 0 0 1 0 = MR6
0 0 0 1 (e) 0 0 0 1 (f)
0 0 0 0
Figura 1
Ahora se explicarán los grafos dirigidos de estos
tres tipos de relaciones. Si R es una relación
asimétrica, entonces el grafo dirigido no puede tener
simultanéame una arista del vértice i al
vértice j y una arista del vértice j
al vértice i. Esto es verdadero para cualquier i y
j y en particular si i = j, por lo cual no puede haber ciclos de
longitud 1.
Si R es una relación antisimétrica, entonces
para vértices i yj distintos no puede haber una arista del
vértice i al vértice j y una arista del
vértice j al vértice i. Cuando i = j, no se impone
condición alguna, por lo cual podrán existir ciclos
de longitud Se examinará el grafo dirigido de las
relaciones simétricas con mayor detalle El grafo dirigido
de una relación simétrica R tiene la propiedad de
que, si existe una arista del vértice j al vértice
i, entonces existe una arista del vértice j al
vértice i.
Por consiguiente, si dos vértices están
conectados por una arista, deberán siemípre estar
conectados en ambas direcciones. Por esto, es posible y muy
útil dar una representación diferente de una
relación simétrica. Se mantienen los
vértices como aparecen en un grafo dirigido, pero si los
vértices a y b están conectados por aristas en cada
dirección, se remplazarán
éstas con una sola arista no dirigida. Esta arista no
dirigida es sólo una línea sin las flechas y
conecta a y b. Al diagrama resultante se llamará grafo de
la relación simétrica.
Ejemplo 7 Sea A «= [a, b, c, d, e} y sea R la
relación simétrica dada por
R = {(a, b), (b, a), (a, c), (c, a), (b, c), (c, b), (b,
e), (e, b), (e, a), (a, e), (c, a), (a,c)}
El grafo dirigido de R se muestra en la figura 2(a),
mientras que en la figura
Grafo
dirigido de R Grafo dirigido de
R
Aparece el grado de R. Obsérvese que cada
arista no dirigida corresponde a dos pares ordenados en la
relación R.
Una arista no dirigida entre a y b, en el grafo
de la relación simétrica R, corresponde al
conjunto {a, b} tal que (a, b) € R y
(b, a) € R. Algunas veces también se referirá
a este conjunto {a, b} como una arista no dirigida
de la relación R.
A una relación simétrica R en un
conjunto A se le llamará conexa si existe
una trayectoria de cualquier elemento de A a cualquier
otro elemento de A. Esto signifíca sencillamente
que el grafo de R está todo en una pieza. En la
figura 3 se muestran los grafos de dos relaciones
simétricas. El grafo de la figura 3(a) está
conectado mientras que el de la figura 3(b) no lo
está.
(a) (b)
f) Relaciones transitivas
Se dice que una relación R en un conjunto
A es transitiva si cuando a R b y b R e,
entonces a R c. Se sigue que R no es transitiva si
y sólo si se puede encontrar elemento a, b y c en
A tal que a R b y b R c, pero a R
c.
Ejemplo 8 Sea A = Z el conjunto de los enteros y
sea R la relación considerada en el ejemplo 2 Para
ver si R es transitiva, se supone que a R b y b R
c. Por consiguiente, a < b; b < c. Entonces se
sigue que a < c, por lo cual a R c. De
aquí que R sea transitiva
Ejemplo 9 Sea A = Z+ y
sea R la relación considerada en el ejemplo 5.
¿Es R transitiva?
Solución. Supóngase que a R b y
b R c, ya que a b y b c, entonces se sigue
que a|c. [Véase la sección 1.7, teorema 2, parte
(c)]. Por consiguiente, R es transitiva.
Ejemplo 10 Sea A ={l,2, 3,4} y sea
R ={(1,2), (I, 3), (4, 2)}
¿Es R transitiva?
Solución. Ya que no es posible encontrar
elementos a. b y c en A tal que a R b y b R c,
se concluye que R es transitiva.
Es posible caracterizar la relación transitiva
por su matriz MR =
[mij] así:
si mij =1 y
mjk = 1, entonces mik
= 1
Para ver qué significa transitividad en
términos del grafo dirigido de una relación, se
traducirá esta definición a términos
geométricos.
Si se examinan los vértices particulares a y c,
las condiciones a R b y b R c
ocurrirán si y sólo si existe una
trayectoria de longitud 2 de a a c, esto es, si y
sólo si a R2 c. Es posible replantear la
definición de transitividad como sigue: Si a
R2 c, entonces a R c, esto es,
R2 £ R (como un subconjunto de
A x A).
Es posible generalizar un poco esta
característica geométrica de la transitividad en
los términos siguientes:
Teorema 1 Una relación R en un
conjunto A es transitiva si y sólo si satisface las
siguientes propiedades: Si existe una trayectoria de longitud
mayor que 1 del vértice a al vértice b, hay
una trayectoria de extensión 1 de a a b (esto es, a
está relacionada con b). Establecido
algebraicamente, R es transitiva si y sólo si
Rn £ R para todas las n
≥ 1.
g) Relaciones Equivalentes
A una relación R sobre un conjunto
A se le llama relación de equivalencia si es
reflexiva, simétrica y transitiva.
Ejemplo 11 Sea A el con junto de todos los
triángulos en un plano y sea R la
relación en A definida como sigue:
R = {(a, b) € A x A | a
es congruente con b}
Es fácil ver que R es una relación
de equivalencia.
Ejemplo 12 Sea A = {1,2, 3,4} y
sea
R = {(1, 1). (1. 2), (2, 1), (2.'2), (3, 4), (4,
3), (3. 3). (4, 4)}
Es fácil de verificar que R es una
relación de equivalencia.
R={(a,b) € A x A | a≤b}
¿Es R una relación de
equivalencia?
Solución. Ya que a ≤ a, R es reflexiva. Si a
≤ b, no necesariamente se sigue que b ≥ a, por lo cual R no
es simétrica. A propósito, R es transitiva, ya que
a ≤ b y implica que a ≤ c . Se ve que R no es una
relación de equivalencia.
Ejemplo 14 Sea A = Z y sea
R = {(a, b) e A x A |2 divide a – b}
Se escribirá a R b como
a ≡ b (mod 2) „
y se leerá "a es congruente con b
módulo 2". Demuestre que la congruencia modulo 2 es una
relación de equivalencia.
Solución. Primero,
a≡a (mod 2)
ya que 2 |(a-a).
Segundo, si a ≡ b (mod 2), entonces 2|{a-b), o a
– b = para alguna K € Z. Entonces '
b – a =2(-K)
por lo cual 2 |(b – a) -y b≡a (mod 2).
Finalmente, supóngase que a ≡ b (mod 2) y b
≡ c (mod 2). Entonces 2| (a – b) por lo
cual
a – b=2k1
donde k1 € Z. También, 2| (b — c), por
lo cual
b – c == 2k2
donde k2 € Z. Sumando las ecuaciones (1)
y (2), se obtiene
a – c = 2(k1 + k2)
por lo cual 2| (a-c), lo que significa que
a =c (mod 2)
De aquí que la congruencia módulo 2 sea
una relación de equivalencia.
Ejemplo 15 Sea A = Z y sea n €
Z+. Se generalizará la relación definida
en al ejemplo 14 como sigue. Sea
R = {(a, b) € A x A | n divide a – b}
y se escribirá a R b como
a ≡ b (mod n)
léase "a es congruente con b módulo n". Al
proceder exactamente como en el ejemplo 14, se podrá
demostrar que la congruencia módulo n es una
relación de equivalencia.
Relaciones de equivalencia y
particiones
Ahora se demostrará que una relación de
equivalencia sobre un conjunto produce una
participación de él, y recíprocamente, una
partición de un conjunto determina una
relación de equivalencia sobre éste.
Sea R una relación de equivalencia sobre el
conjunto A. Si a e A, entonces
[a]={x € A | x R
a}
se llama clase de
equivalencia de a.
Obsérvese que la clase de equivalencia [a]
nunca es vacía, ya que la propiedad reflexiva de R
implica que a € [a].
Ejemplo 16 Sea R la relación de equivalencia
definida en el ejemplo 12. Entonces
[1]={1,2} y [2] ={1,2}
ya que
(1. !),(1, 2), (2,1), y (2,2) € R
Diego Mendoza Salas
Instituto Tecnológico de
Culiacán