Matemáticas/Álgebra Abstracta/Apéndices/Relaciones

Introducción

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

Las Relaciones

Plantilla:DefRht

1. La relación de igualdad en un conjunto $X$ es una relación de equivalencia. Cuando queramos recordar a esta relación como un conjunto de pares, la simbolizaremos por ${\mathrm{\Delta }}_X$ o simplemente $\mathrm{\Delta }$. $\mathrm{\Delta }$ proviene de "diagonal principal" del conjunto cartesiano $A\times A$.
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 $A\subset B$ y $ℛ$ una relación en $B$. Entonces, $T=S\cap (A\times A)$ es una relación en $A$ que llamaremos la restricción de $ℛ$ a $A$ y que simbolizaremos por $ℛ|{}_A$

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

1. El conjunto de vértices del grafo es igual al conjunto $X$.
2. El conjunto de aristas del grafo está formado por todos aquellos pares $(x,y)$ tales que $xℛy$.

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 $(x,y)$ se representa por un arco de curva uniendo el vértice $x$ con el vértice $y$, con una punto de flecha del lado del vértice $y$.

Plantilla:Ejmpl La representación gráfica del grafo de la relación $\{(a,a),(b,b),(d,d),(a,b),(b,c),(d,c)\}$ en el conjunto $\{a,b,c,d\}$.

---

Las Relaciones de Equivalencia

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

Proposición. Sea $(X_i{)}_{i\in I}$ una partición del conjunto $X$. Sea $\sim$ definida en $X$, por $x\sim y$, ssi, hay un $i$ tal que $x$ y $y$ pertenecen a $X_i$. La relación $\sim$ es una relación de equivalencia en $A$.

Demostración: La reflexividad y simetría son inmediatas. Veamos la transitividad, si $x\sim y$ y $y\sim z$, podremos hallar $i$, $j$ tales que $x$ y $y$ están en $X_i$, y $y$ y $z$ están en $X_j$. Resulta entonces que $y$ es un elemento común a ambos subconjuntos, pero como estos son disjuntos dos a dos, concluimos que $i=j$. Luego, $x$ y $z$ están en el mismo $X_i$; o sea, $x\sim z$.
Plantilla:QED

---

Proposición.

1. Cada relación de equivalencia en un conjunto $A$ define una partición de $A$, 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 $A$. Por la reflexividad, cada $a$ es un elemento de $[a]$, lo que prueba que las clases de equivalencia no son vacías y que su reunión es todo $A$. Supongamos que $[a]$ y $[b]$ tienen intersección no nula, digamos que $x\in [a]\cap [b]$. Entonces, $x\in [a]$ implica que $xℛa$; análogamente se tiene que $xℛb$. Por simetría y transitividad, concluimos que $aℛb$. En particular esto dice que $a\in [b]$ y que $b\in [a]$. Sea $y$ un elemento cualquiera de $[a]$; por transitividad, nuevamente,concluimos que $y\sim b$, o sea que $y\in [b]$. En otras palabras, $[a]$ es un subconjunto de $[b]$. Pero, como los roles de $a$ y $b$ son simétricos en las relaciones anteriores, tendremos también que $[b]\subset [a]$. O sea, $[a]=[b]$. 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 $A$. La segunda parte fue probada antes.
Plantilla:QED

---

Las Relaciones de Orden

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 $X$ es una relación reflexiva, transitiva y antisimétrica.

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

$aℛb⟺b\prec a.$

La relación dual de $\prec$ comúnmente se simboliza por $\succ$. 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.

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

Plantilla:DefRht

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.

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

Sea

$A$

un conjunto y sea

$ℒ$

el conjunto formado por todas las relaciones de equivalencia en

$A$

. Si

$ℛ$

y

$𝒮$

son relaciones de equivalencia, poniendo que

$ℛ\prec 𝒮⟺\text{ para todo }x,y\in A,xℛy⟹𝒮y.$

El orden anterior es un reticulado completo.

---