5.1 Relaciones

Una relación es un conjunto de pares ordenados. Un par ordenado (también  llamada pareja ordenada) consta de dos elementos: (a, b) en donde el orden en que  aparece (primero a, después 

b) indica la relación: a Rb de a con b.

Una relación asocia un elemento de un conjunto A con un elemento de otro  conjunto B o con un elemento del mismo conjunto A.

 Relaciones

5.1.1 Producto cartesiano

Considere dos conjuntos arbitrarios A y B. El conjunto de todas las parejas ordenadas (a, b) en donde a ∈ A  y b ∈ B se llama producto o producto cartesiano de A y B.

La definición de producto cartesiano puede extenderse fácilmente al caso de más de dos conjuntos.

Se llama producto cartesiano de dos conjuntos A y B y se representa  A x B, al conjunto de pares ordenados (a, b), tales que el primer elemento pertenece al primer conjunto y el segundo elemento al segundo conjunto. Es decir:

A x B = {(a, b) / a ∈ A, b ∈ B}

Producto cartesiano

5.1.2 Relación binaria

La relación binaria definida en un conjunto A es un subconjunto del producto cartesiano A x A.

EJEMPLO:

Sea el conjunto  A = {x,  y,  z}. El grafo de la siguiente figura representa una relación binaria definida en A, puesto que los pares (x, z), (y, x) (y, y) constituyen un subconjunto de A x A.

Se dice que dos elementos a y b están relacionados, y se escribe a R  b, “a está relacionado con b mediante la relación binaria  R”,  cuando el par ordenado (a, b) pertenece al subconjunto del producto cartesiano que define la relación.

Si dos elementos a y b no están relacionados mediante R en algún sentido, escribiremos a R   b o b R  a o ambas cosas.

Relación Binaria

5.1.3 Representaciones de Relaciones

Representación De Relaciones Usando Matrices 

Un método para el estudio de las relaciones de manera algorítmica es utilizando matrices compuestas de ceros y unos.

 Sean A y B conjuntos finitos de la forma: 

Si R es una relación de A en B. La relación R puede ser representada por la matrizdonde:

La matriz MR se denomina matriz de R. En otras palabras la matriz, de ceros y unos, de R tiene un 1 en la posición  (i,j) cuando  ai está relacionado con bj y un 1 en está posición ai si  no está relacionado con bj.

Obsérvese en la definición anterior que los elementos de A y B han sido escritos en un orden particular pero arbitrario. Por lo tanto, la matriz que representa una relación.

Conjuntos

Un conjunto es una colección de objetos considerada como un objeto en sí. Los objetos de la colección pueden ser cualquier cosa: personas, números, colores, letras, figuras, etc. Cada uno de los objetos en la colección es un elemento o miembro del conjunto. Por ejemplo, el conjunto de los colores del arcoíris es:

AI = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta}

Un conjunto suele definirse mediante una propiedad que todos sus elementos comparten. Por ejemplo, para los números naturales, si consideramos la propiedad de ser un número primo, el conjunto de los números primos es:

P = {2, 3, 5, 7, 11, 13, …}

Un conjunto queda definido únicamente por sus miembros y por nada más. En particular el orden en el que se representen estos es irrelevante. Además, cada elemento puede aparecer de manera idéntica una sola vez, esto es, no puede haber elementos totalmente idénticos repetidos. Por ejemplo:

S = {Lunes, Martes, Miércoles, Jueves, Viernes} = {Martes, Viernes, Jueves, Lunes, Miércoles}

AI = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta} = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta, Naranja}

Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binaria entre elementos de un conjunto.

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).

Un grafo G es un par ordenado G = (V,E), donde:

· V es un conjunto de vértices o nodos, y

· E es un conjunto de aristas o arcos, que relacionan estos nodos.

Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos.

Se llama orden del grafo G a su número de vértices, | V | .

El grado de un vértice o nodo V es igual al número de arcos E que se encuentran en él.

Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.

Diagrama de flechas

Hay otra manera de visualizar una relación y es a través de una representación gráfica, donde se destaquen los puntos en el plano que pertenecen a A y los puntos que pertenecen a B. Se trazan flechas que indican la relación que existe entre cada elemento del conjunto  A y su correspondiente en el conjunto B. A esta representación gráfica se le conoce como un diagrama de flechas.

5.2 Propiedades de las relaciones (reflexiva, irreflexiva, simétrica, asimétrica, anti simétrica, transitiva)

Relaciones Reflexivas e  Irreflexivas

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:

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

Relaciones Simétricas y Asimétrica

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 asimé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 anti simétrica si cuando a ≠ b, se tiene a R b o b R a. De esto se sigue que R no es anti simétrica si se tiene a y b en A. a ≠ b, y ambas a R b y b R a.

Ejemplo:

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

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.

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.

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

5.3 Relaciones de equivalencia (cerraduras, clases de equivalencia, particiones)

Las relaciones de equivalencia son relaciones entre los elementos de un elemento cualquiera. Se caracterizan por abstraer el concepto de igualdad.

Su definición formal es la siguiente:

Sea “K” un conjunto dado no vacío y “R” una relación binaria definida sobre “K”. 

Se dice que “R” es una relación de equivalencia si cumple las siguientes propiedades:

Reflexividad: Todo elemento de “K” está relacionado consigo mismo. Es decir,

Simetría: Si un elemento de “K” está relacionado con otro, entonces ese otro elemento también se relaciona con el primero. Es decir

Transitividad: Si un elemento de “K” está relacionado con otro, y ese otro a su vez se relaciona con un tercero, entonces el primero estará relacionado también con este último. Es decir,

CLASES DE EQUIVALENCIA

La importancia de las relaciones consiste en que dividen a los elementos del conjunto en diferentes clases, llamadas clases de equivalencia, de tal suerte que cada elemento pertenece a una y sólo una clase.

Tomemos un conjunto cualquiera X y sean a y b  dos elementos en X (lo cual denotamos por  a,b Ç X). Si  a está relacionado con b  escribiremos  a-b. Una relación de equivalencia en X es una relación que satisface las propiedades antes mencionadas.

Sea x un conjunto con una relación de equivalencia  -. Tomemos un elemento a de nuestro conjunto  X, es decir  aÇX. La clase de equivalencia de  a, la cual denotaremos por  {a}, es el subconjunto de X formado por todos los elementos b de X que están relacionados con  a, es decir  b-a. En símbolos, esto se escribe así:

De todo elemento en {a}. (por ejemplo  a) decimos que es un representante de la clase  Las relaciones de equivalencia son relaciones entre los elementos de un elemento cualquiera. Se caracterizan por abstraer el concepto de igualdad.

Su definición formal es la siguiente:

Sea “K” un conjunto dado no vacío y “R” una relación binaria definida sobre “K”. 

Se dice que “R” es una relación de equivalencia si cumple las siguientes propiedades:

Reflexividad: Todo elemento de “K” está relacionado consigo mismo. Es decir, {a}.

PARTICIONES

La partición de un conjunto es tan simple como dividir el mismo en conjuntos más pequeños formados por elementos de él mismo, es decir, en subconjuntos. Aquí no se toma en cuenta el conjunto vacío.

5.4 Funciones (inyectiva, suprayectiva, biyectiva)

Sea f una relación de A en B. Entonces f es una función de A en B (denotado f : A ! B y se lee “f es una función de A en B”) si y sólo si:

a) Dom(f) = A

b) 8 x 2 A, 8 y; z 2 B [(x; y) 2 f ^ (x; z) 2 f] ! y = z.

En palabras, lo anterior dice que si f es una relación de A en B tal que para cada x 2 A existe exactamente un y 2 B tal que (x; y) 2 f, entonces f es una función.

La condición a) garantiza que para cada x 2 A existe al menos un tal “y” y la condición b) garantiza que hay a lo más uno. Así, tomados juntos, hay exactamente uno.

Si f es una función de A en B entonces la “propiedad funcional” de cada x 2 A relacionado a exactamente un y 2 B permite el uso de la notación funcional

                              y = f(x).

La mayoría de las funciones conocidas en cálculo son dadas por una fórmula. Sin embargo esto no es necesario y, en general en matemática, las funciones no están dadas por fórmulas.

Es de resaltar que el nombre de la función es f y que f(x) no es el nombre de la función sino un elemento de B. 

Si y = f(x) entonces decimos que y es la imagen de x y que x es una Pre-imagen de y.

Puedes entender una función como una manera de conectar elementos de un conjunto "A" a los de otro conjunto "B":

"Injectivo" significa que cada elemento de "B" tiene como mucho uno de "A" al que corresponde (pero esto no nos dice que todos los elementos de "B" tengan alguno en "A"). 

"Sobreyectivo" significa que cada elemento de "B" tiene por lo menos uno de "A" (a lo mejor más de uno).

"Biyectivo" significa inyectivo y sobreyectivo a la vez. Así que hay una correspondencia perfecta "uno a uno" entre los elementos de los dos conjuntos.