Relaciones en un conjunto

Relaciones en un conjunto.

En esta sección consideramos relaciones de un conjunto en sí mismo.

Definición Sea A un conjunto. Se dice que R es una relación en A cuando R ⊆ A × A.

Ejemplos:

• Las relaciones R6 y R7 arriba son relaciones en el conjunto R.
• La igualdad de elementos siempre es una relación en cualquier conjunto A:

R = {(a; a); a ∈ A}; es decir ∀ a; b ∈ A : aRb ⇔ a = b:

• ≤ es una relación en R, y ⊆ es una relación en P(A), cualquiera sea el conjunto A.

Sin embargo, cuando el conjunto A es _nito (como en este caso), una relación R en A se puede representar también por medio de un grafo dirigido, o sea un conjunto de puntos (llamados Vértices, que son los elementos del conjunto A) y un conjunto de echas entre los vértices, que se corresponden con los elementos relacionados: se pone una echa (que parte de a y llega a b)  para cada elemento (a; b) ∈ R, es decir cada vez que a Rb.

La teoría de grafos juega un rol esencial en varias ramas de la matemática y la computación.

Las relaciones en un conjunto dado son particularmente importantes, y algunas de las propiedades que pueden cumplir merecen un nombre.

Partición de un conjunto. Una partición de un conjunto A es una colección de subconjuntos de A, los cuales son no vacíos y disyuntos entre sí cuya unión es A. Formalmente, una partición de un conjunto A es una familia [pic 1]de subconjuntos no vacíos de A, con las siguientes propiedades:

[pic 2][pic 3]

Cada conjunto [pic 4]se llama celda o bloque de la partición.

Ejemplo:

Sea [pic 5]. Cada una de las siguientes colecciones son particiones de A.

[pic 6]

COMPOSICIÓN DE RELACIONES

Sea [pic 7] una relación de A en B y [pic 8] una relación de B en C. La composición de [pic 9] y [pic 10] es una relación consistente de los pares ordenados (a, c), donde a [pic 11] A y c [pic 12] C y para los cuales existe un b [pic 13] B tal que (a, b) [pic 14] [pic 15] y (b, c) [pic 16] [pic 17], es decir a [pic 18] b y b [pic 19]c.

...