Relaciones en los conjuntos

Recordemos la definición de producto cartesiano: 

Dados dos conjuntos A y B, el producto cartesianos de estos dos conjuntos es el conjunto formado por todos los pares ordenados (a,b) donde a es un elemento de A y b es un elemento de B.

Relación

Dados dos conjuntos A y B una relación es un subconjunto del producto cartesiano A x B.

Un elemento a, que pertenece al conjunto A, está relacionado con un elemento b, que pertenece al conjunto B, si el par (a, b) pertenece a un subconjunto G (llamado grafo) del producto cartesiano A x B.

Ejemplo: Sean A = {a, b, c} y B = {1, 2} dos conjuntos. El producto cartesiano A x B = {(a,1), (a,2), (b,1), (b,2), (c,1), (c,2)}. Una relación sería R = {(a,1),(c,2)}.

A las relaciones también se les llama correspondencias.

Relación binaria

Dado el producto cartesiano A x A, una relación binaria es un subconjunto G (llamado grafo) de este producto cartesiano. 

Una relación binaria que cumple que para todo elemento a del conjunto A, el elemento (a,a) pertenece al grafo G tiene la propiedad reflexiva.

Una relación binaria que cumple que para todo elemento a del conjunto A, el elemento (a,a) no pertenece al grafo G tiene la propiedad irreflexiva o antireflexiva.

Una relación binaria que cumple que para todo elemento a y b perteneciente al conjunto A si (a,b) pertenece al grafo G entonces el elemento (b,a) también pertenece al grafo G, tiene la propiedad simétrica.

Una relación binaria tiene la propiedad antisimétrica si para todo elemento a y b perteneciente al conjunto A si (a,b) pertenece al grafo G y el elemento (b,a) también pertenece al grafo G, entonces a = b. 

Una relación binaria tiene la propiedad transitiva si para todo elemento a, b y c perteneciente al conjunto A si (a,b) pertenece al grafo G y (b,c) también pertenece al grafo G, entonces (a, c) pertenece al grafo G. 

Relación de equivalencia

Una relación de equivalencia es una relación binaria que tiene las propiedades:

Reflexiva: a R a
Simétrica: Si a R b, b R a
Transitiva: Si a R b y b R a, entonces a R c.

Ejemplo: La relación a - b = 2.k (múltiplo de 2), siendo a y b números enteros es una relación de equivalencia porque cumple las propiedades:
Reflexiva: a - a = 0 = 2.k (k = 0).
Simétrica: a - b = b - a porque b - a  = -(a - b). Si a - b es múltiplo de 2, -(a - b) también lo será.
Transitiva: a - b = 2.k₁   b - c = 2.k₂  Sumando queda a - c = 2.k₃ Entonces a - c es múltiplo de 2. 

Al conjunto de los elementos del conjunto A que están relacionados con él se llama clase de equivalencia. 

En el ejemplo anterior, la clase de equivalencia del número cero (uno de los elementos del conjunto de los números enteros)  C(0) = {... -4, -2, 0, 2, 4, ...}, pues 0 - (-4) es múltiplo de 2, 0 - (-2) es múltiplo de 2 ya sí sucesivamente. La clase de equivalencia del número 1 será C(1) = {... -5, -3, -1, 1, 3, 5, ...} pues la diferencia entre 1 y los números indicados es múltiplo de 2. 
Del mismo modo podríamos calcular las clases de equivalencia de más números. 

El conjunto formado por las clases de equivalencia se llama conjunto cociente.

En el ejemplo anterior el conjunto cociente Z / 2 es el conjunto formado por las clases de todos los elementos Z / 2 = {C(0), C(1), C(2), ... }.

Relación de orden

Una relación binaria es una relación de orden que tiene las propiedades:

Reflexiva: a R a
Antisimétrica: Si a R b y b R a entonces a = b.
Transitiva: Si a R b y b R a, entonces a R c.

Si en un conjunto se puede establecer una relación de orden el conjunto se dice ordenado.

Las relaciones de orden se representan con el símbolo menor igual (a <= b)

En un conjunto ordenado, si b <= a para todo b, a se llama elemento máximo. Si el máximo existe es único.

En un conjunto ordenado, si a <= b para todo b, a se llama elemento mínimo. Si el mínimo existe es único.

En un conjunto ordenado, si a <= b implica a = b, a y b se llaman elementos maximales. 

En un conjunto ordenado, si b <= a implica a = b, a y b se llaman elementos minimales.