Relaciones En Un Conjunto

Introducción

Las relaciones entre dos o más conjuntos son frecuentes tanto en las Matemáticas como en sus aplicaciones, especialmente en Informática. Ejemplos prácticos de relaciones son las de orden y divisibilidad entre números, las relaciones de equivalencia entre los datos de entrada de un programa en cuanto a la detección de posibles errores de programación (validación de programas), la relación de dependencia entre las distintas fases producción en una industria o la agrupación de datos aislados en complejas bases de datos con relaciones de dependencia entre sus campos. Desde el punto de vista matemático, estas relaciones se pueden describir simplemente como subconjuntos de un cierto producto cartesiano. De entre los diversos tipos de relaciones, las funciones pueden considerarse un caso especial en donde se interpreta que uno de los campos es el resultado de realizar una cierta operación con el resto. Asimismo, las relaciones de equivalencia describen similitudes entre elementos con respecto a una propiedad particular, y las relaciones de orden establecen una jerarquía con respecto a un criterio fijado. Por último, las relaciones entre múltiples conjuntos son el fundamento matemático del modelo relacional de bases de datos, que es el más extendido hoy en día por su simplicidad, su potencia y su coherencia teórica y práctica. Este documento esta organizado de la siguiente manera: La sección 2 trata de las definiciones generales de la terminología de relaciones, la sección 3 estudia el caso particular de las relaciones binarias, la sección 4aborda el caso de las propiedades binarias en un conjunto , analizando sus propiedades y los posibles cierres de una relación con respecto a una propiedad determinada, la sección 5 trata el caso especial de las relaciones de equivalencia, y la sección 6 de las relaciones de orden. La última parte introduce la aplicación de las relaciones en el diseño de Bases de Datos en Informática.

Conceptos generales sobre relaciones

En primer lugar introducimos el concepto de relación entre conjuntos:

Definición 2.1 Una relación entre los conjuntos es cualquier subconjunto

Los conjuntos son los dominios de la relación, el número de elementos de se llama cardinalidad, y el número se denomina grado de .

Para indicar explícitamente la relación es de grado , se dice también que es una relación -aria.

En el caso particular , una relación binaria entre dos conjuntos y es un subconjunto

Se interpreta que establece una `` relación'' entre elementos de y elementos de . También se puede interpretar, como ya se ha visto en el tema de Teoría de Conjuntos, que hace corresponder a elementos de imágenes entre los elementos de . Así, una correspondencia entre y se define como una terna donde es una relación entre y , y se denomina grafo de la correspondencia .

Nota 2.2 (Lógica y relaciones) Existe un tipo de lógica llamada `` Lógica Relacional'', basada en relaciones de grado . Esta Lógica tiene interés en la construcción de `` Bases de Datos Deductivas'', que se emplean en el diseño de `` Sistemas Expertos'' (Inteligencia Artificial).

Las operaciones conjuntistas básicas que se pueden realizar con relaciones `` compatibles'', es decir, subconjuntos del mismo producto cartesiano , son las siguientes:

1. Unión: , formada por las -uplas que están en , en o en ambas a la vez.

2. Intersección: , formada por las -uplas que están simultáneamente en y en .

3. Diferencia: , formada por las -uplas que están en pero no en .

4. Complementación: , es decir, formada por todas las -uplas que no están en .

Además, entre dos relaciones compatibles y se verifica la contención conjuntista si para toda -upla se tiene que

En particular, dos relaciones son iguales si

Relaciones binarias

El caso particular de relaciones binarias merece ser tratado aparte, por la riqueza de conceptos y resultados a que da lugar y el tipo de técnicas que pueden utilizarse. En primer lugar, si es una relación entre y , el hecho de que un par ordenado esté en suele denotarse

Asimismo, el hecho contrario, es decir , suele denotarse , o simplemente . Una relación binaria admite una representación matricial, siempre que los dominios de la relación sean finitos. En efecto, supongamos que y . Entonces la matriz asociada a es la matriz Booleana con filas y columnas

dada por

Ejemplo 3.1 Se consideran los conjuntos y , y se define la relación

(es decir, si y sólo si ). Entonces, la matriz asociada a es

Hacemos observar que las matrices asociadas a las relaciones entre y nos permiten realizar fácilmente, en el caso finito, las operaciones conjuntistas básicas mediante operaciones lógicas entre las entradas de las matrices. Efectivamente, supongamos que y , y que y . Puesto que vamos a operar con valores Booleanos, es decir, valores de verdad con los que podemos hacer las operaciones lógicas de negación, conjunción, disyunción, condicional y bicondicional, vamos a denotar, para simplificar la notación, la disyunción como una suma y la conjunción como un producto. De esta manera, tendríamos las operaciones

Con esta notación, es fácil comprobar que:

Proposición 3.2

1. La matriz asociada a es , donde la suma de matrices es entendida componente a componente.

2. La matriz asociada a es , donde ` ' representa el producto componente a componente de dos matrices.

3. La matriz asociada a es , en donde se niegan todas las entradas (Booleanas) de la matriz.

4. La matriz asociada a es .

5. si y sólo si , es decir:

6. si y sólo si , es decir, si y sólo si .

Además de la operaciones usuales, las relaciones binarias admiten algunas operaciones adicionales. En primer lugar, definimos la relación inversa a una dada:

Definición 3.3 Dada una relación , se llama relación inversa de , y se denota , a la relación definida por

Es decir, consiste en intercambiar los elementos de los pares ordenados que pertenecen a . Es evidente que, en el caso finito, la matriz asociada a la relación inversa es justamente la traspuesta de la matriz de , es decir

En segundo lugar, se define lo que se entiende por composición de relaciones:

Definición 3.4 Sean dos relaciones y . Se llama composición de y , y se denota , a la relación definida por

tal que

La

...