Álgebra Abstracta/Relaciones

Introducción

editar

Este apéndice contiene las definiciones de relaciones, relaciones de equivalencia, relaciones de orden, así como nociones asociadas.

Las Relaciones

editar

Definición. (Relación) Llamamos relación entre elementos de un conjunto   y elementos de un conjunto   a cualquier subconjunto de  . Cuando   sea una relación, usualmente escribiremos   en lugar de  .
Cuando   sea igual a   hablaremos de una relación en el conjunto  .


Definición. (Tipos de Relaciones) Decimos que una relación   en un conjunto   es:

  1. Reflexiva, cuando para todo  .
  2. Simétrica, cuando para todo  .
  3. Transitiva, cuando para todo  .
  4. Antisimétrica, cuando para todo  .
  5. De equivalencia, cuando sea reflexiva, simétrica y transitiva a la vez.
  6. De orden parcial, cuando sea reflexiva, transitiva y antisimétrica a la vez.
  7. De orden total, cuando sea de orden y dos elementos sean siempre comparables.


Ejemplos.

  1. La relación de igualdad en un conjunto   es una relación de equivalencia. Cuando queramos recordar a esta relación como un conjunto de pares, la simbolizaremos por   o simplemente  .   proviene de "diagonal principal" del conjunto cartesiano  .
  2. La relación de inclusión es una relación de orden parcial en el conjunto potencia de un conjunto.
  3. La relación de "menor o igual" en los números es una relación de orden total en el conjunto de los Enteros.
  4. Sea   y   una relación en  . Entonces,   es una relación en   que llamaremos la restricción de   a   y que simbolizaremos por  

Definición. (Grafo) Sea   una relación en un conjunto  . Llamamos grafo asociado a la relación al par   de vértices y aristas, definido de la siguiente manera:

  1. El conjunto de vértices del grafo es igual al conjunto  .
  2. El conjunto de aristas del grafo está formado por todos aquellos pares   tales que  .

Los grafos se representan gráficamente de la siguiente manera:

  • Cada vértice se representa por un punto etiquetado con el nombre del punto.
  • Cada arista   se representa por un arco de curva uniendo el vértice   con el vértice  , con una punto de flecha del lado del vértice  .

Ejemplo.

La representación gráfica del grafo de la relación   en el conjunto  .

 

Las Relaciones de Equivalencia

editar

Recordemos que llamamos relación de equivalencia a una relación reflexiva, simétrica y transitiva en un conjunto  . Veremos la noción de partición del conjunto  , que resultará ser equivalente a la noción de relación de equivalencia.

Definición. (Partición) Una partición de un conjunto   es una colección   de subconjuntos no vacíos de   cuya reunión es todo   y tal que dos a dos son disjuntos.


Proposición. Sea   una partición del conjunto  . Sea   definida en  , por  , ssi, hay un   tal que   y   pertenecen a  . La relación   es una relación de equivalencia en  .

    Demostración: La reflexividad y simetría son inmediatas. Veamos la transitividad, si   y  , podremos hallar  ,   tales que   y   están en  , y   y   están en  . Resulta entonces que   es un elemento común a ambos subconjuntos, pero como estos son disjuntos dos a dos, concluimos que  . Luego,   y   están en el mismo  ; o sea,  .


Definición. (Clase de Equivalencia) Sea   una relación de equivalencia en un conjunto  . Para todo   en  , llamaremos clase de equivalencia del elemento  , al subconjunto de   formado por todos los elementos de   que son equivalentes con  .
Notación   o  .

Cada elemento de una de las clases de equivalencia es un representante de dicha clase.


Proposición.

  1. Cada relación de equivalencia en un conjunto   define una partición de  , donde cada elemento de la partición coincide con las clases de equivalencia.
  2. Cada partición de un conjunto define una relación de equivalencia, cuyas clases de equivalencia son precisamente los elementos de la partición.
    Demostración: Sea   una relación de equivalencia en  . Por la reflexividad, cada   es un elemento de  , lo que prueba que las clases de equivalencia no son vacías y que su reunión es todo  . Supongamos que   y   tienen intersección no nula, digamos que  . Entonces,   implica que  ; análogamente se tiene que  . Por simetría y transitividad, concluimos que  . En particular esto dice que   y que  . Sea   un elemento cualquiera de  ; por transitividad, nuevamente,concluimos que  , o sea que  . En otras palabras,   es un subconjunto de  . Pero, como los roles de   y   son simétricos en las relaciones anteriores, tendremos también que  . O sea,  . Es decir que las clases de equivalencia son subconjuntos no vacíos, cuya reunión es todo el conjunto y son disjuntas dos a dos. Luego, forman una partición de  . La segunda parte fue probada antes.


Definición. (Conjunto Cociente) Sea   un conjunto y   una relación de equivalencia en  . Llamaremos conjunto cociente de   por la relación   al conjunto formado por todas las clases de equivalencias de  . Notación:  .


Las Relaciones de Orden

editar

En esta sección, introduciremos la notación y la nomenclatura asociadas con relaciones de orden. Recordemos que una relación de orden parcial en un conjunto   es una relación reflexiva, transitiva y antisimétrica.

Definición. (Conjunto parcialmente ordenado) Decimos que un conjunto   es un conjunto parcialmente ordenado, cuando haya un orden parcial   en  .


Supongamos que   es una relación de orden en un conjunto  . Llamaremos relación dual de   a la relación   definida por:

 

La relación dual de   comúnmente se simboliza por  . El grafo de la relación dual es el "mismo" que el grafo de la relación original, excepto que todas las flechas han invertido su sentido. La siguiente proposición es fácil de verificar.

Proposición. La relación dual de una relación de orden parcial es también una relación de orden parcial.

Los principales ejemplos de relaciones de orden parcial son la inclusión de conjuntos (entre subconjuntos de un conjunto fijo), "mayor que" o "menor que" en los conjuntos de números reales y la divisibilidad en los números enteros positivos. Notemos que la relación dual de "estar contenido" es "contiene a", y que "mayor que" y "menor que" son duales una de la otra.

Definición. (Elementos Comparables) Sea   una relación de orden en  . Decimos que dos elementos  ,   de   son comparables cuando se cumpla que   o  . En caso contrario, diremos que son incomparables.


Definición. (Orden Total) Decimos que un orden   es total, cuando se cumpla que dos elementos cualesquiera del conjunto son siempre comparables.

Un conjunto totalmente ordenado es un conjunto provisto de un orden total.


Definición. (Elemento Maximal, Elemento Minimal) Decimos que un elemento   de un conjunto parcialmente ordenado  , con un orden parcial   es maximal, si,

 
La noción dual de la anterior es aquella de minimal. Un elemento   de un conjunto   con un orden parcial   es minimal, si,
 


La siguiente proposición es de fácil verificación.
Proposición. Sea   un conjunto parcialmente ordenado finito, con orden  . Entonces hay al menos un elemento maximal y uno minimal del conjunto.

Definición. (Orden Lineal) Un orden es lineal cuando es parcial y se satisface la siguiente relación de tricotomía: para todo  ,  , una, y solo una, de las alternativas siguientes es válida:

 


Definición. (Cadena) Una cadena es un conjunto parcialmente ordenado cuyo orden además es lineal.


Definición. (Cotas) Sea   un conjunto parcialmente ordenado. Decimos que un elemento   de   es una cota superior de un subconjunto   de  , si,

 

Dualmente, decimos que un elemento   es una cota inferior de  , si,

 


Definición. (Cota Superior Estricta, Cota Inferior Estricta) Sea   un conjunto parcialmente ordenado.

  1. Decimos que un elemento   es un supremo o cota superior estricta o de un subconjunto  , si es una cota superior tal que para cualquier otra cota superior   se cumple que  .
  2. Decimos que un elemento   es un <ínfimo o cota inferior estricta de un subconjunto  , si es una cota inferior tal que para cualquier otra cota inferior  , se cumple que  .


Los siguientes principios, que aquí tomaremos como postulados, son importantes en el trabajo con conjuntos infinitos.

Principio de Hausdorff. Cada conjunto parcialmente ordenado tiene una cadena maximal.

Lema de Zorn Cuando en un conjunto parcialmente ordenado, cada cadena tiene una cota superior, entonces el conjunto tiene elemento maximal.

Definición. (Reticulado) Llamaremos reticulado a un conjunto parcialmente ordenado tal que cualquier par de elementos  ,   tiene cota superior e inferior estrictas.

Notación:  
 .


Definición. (Reticulado Completo) Un reticulado es completo, cuando cada conjunto no vacío tiene una cota superior y una cota inferior estricta.


Proposición. Si un conjunto parcialmente ordenado   tiene un elemento que es cota superior de todo el conjunto y si cada subconjunto de   tiene cota inferior estricta, entonces es un reticulado completo.

Ejemplo.

Sea   un conjunto y sea   el conjunto formado por todas las relaciones de equivalencia en  . Si   y   son relaciones de equivalencia, poniendo que

 

El orden anterior es un reticulado completo.