Álgebra Abstracta/Relaciones

De Wikilibros, la colección de libros de texto de contenido libre.
Ir a la navegación Ir a la búsqueda

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 .

GrafoRel.jpg

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.