Álgebra Abstracta/Relaciones

Introducción

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

Las Relaciones

Definición. (Relación) Llamamos relación entre elementos de un conjunto $A$ y elementos de un conjunto $B$ a cualquier subconjunto de $A\times B$. Cuando ${\mathcal {R}}$ sea una relación, usualmente escribiremos $x{\mathcal {R}}y$ en lugar de $(x,y)\in {\mathcal {R}}$.
Cuando $A$ sea igual a $B$ hablaremos de una relación en el conjunto $A$.

Definición. (Tipos de Relaciones) Decimos que una relación ${\mathcal {R}}$ en un conjunto $A$ es:

1. Reflexiva, cuando para todo $x,\quad x{\mathcal {R}}x$.
2. Simétrica, cuando para todo $x,y,\quad x{\mathcal {R}}y\implies y{\mathcal {R}}x$.
3. Transitiva, cuando para todo $x,y,z,\quad x{\mathcal {R}}y,\ y{\mathcal {R}}z\implies x{\mathcal {R}}z$.
4. Antisimétrica, cuando para todo $x,y,\quad x{\mathcal {R}}y,\quad x\neq y\implies y{\text{ no relacionado con }}x$.
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 $X$ es una relación de equivalencia. Cuando queramos recordar a esta relación como un conjunto de pares, la simbolizaremos por $\Delta _{X}$ o simplemente $\Delta$. $\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 ${\mathcal {R}}$ una relación en $B$. Entonces, $T=S\cap (A\times A)$ es una relación en $A$ que llamaremos la restricción de ${\mathcal {R}}$ a $A$ y que simbolizaremos por ${\mathcal {R}}\left|_{A}\right.$

Definición. (Grafo) Sea ${\mathcal {R}}$ 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{\mathcal {R}}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$.

Ejemplo.

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.

Definición. (Partición) Una partición de un conjunto $X$ es una colección $(X_{i})_{i\in I}$ de subconjuntos no vacíos de $X$ cuya reunión es todo $X$ y tal que dos a dos son disjuntos.

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$.

---

Definición. (Clase de Equivalencia) Sea ${\mathcal {R}}$ una relación de equivalencia en un conjunto $X$. Para todo $a$ en $X$, llamaremos clase de equivalencia del elemento $a$, al subconjunto de $X$ formado por todos los elementos de $X$ que son equivalentes con $a$.
Notación $[a]$ o ${\bar {a}}$.

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 $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 ${\mathcal {R}}$ 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{\mathcal {R}}a$; análogamente se tiene que $x{\mathcal {R}}b$. Por simetría y transitividad, concluimos que $a{\mathcal {R}}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.

---

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

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.

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

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

$a{\mathcal {R}}b\iff 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.

Definición. (Elementos Comparables) Sea ${\mathcal {R}}$ una relación de orden en $A$. Decimos que dos elementos $x$, $y$ de $A$ son comparables cuando se cumpla que $x{\mathcal {R}}y$ o $y{\mathcal {R}}x$. En caso contrario, diremos que son incomparables.

Definición. (Orden Total) Decimos que un orden ${\mathcal {R}}$ 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 $M$ de un conjunto parcialmente ordenado $A$, con un orden parcial $\prec$ es maximal, si,

${\text{para todo }}x,\quad x\in A,\ M\prec x\implies M=x.$ La noción dual de la anterior es aquella de minimal. Un elemento $m$ de un conjunto $A$ con un orden parcial $\prec$ es minimal, si, ${\text{para todo }}x,\quad x\in A,x\prec m\implies m=x.$

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.

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

$(x=y),\quad (x\prec y),\ quad(y\prec x).$

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

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

${\text{para todo }}x,x\in S\implies x\prec c.$

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

${\text{para todo }}x,x\in S\implies d\prec x.$

Definición. (Cota Superior Estricta, Cota Inferior Estricta) Sea $<X,\prec >$ un conjunto parcialmente ordenado.

1. Decimos que un elemento $m$ es un supremo o cota superior estricta o de un subconjunto $S$, si es una cota superior tal que para cualquier otra cota superior $c$ se cumple que $m\prec c$.
2. Decimos que un elemento $n$ es un <ínfimo o cota inferior estricta de un subconjunto $S$, si es una cota inferior tal que para cualquier otra cota inferior $d$, se cumple que $d\prec m$.

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 $x$, $y$ tiene cota superior e inferior estrictas.

Notación: $a\vee b={\text{ cota superior estricta de }}\{a,b\},$
$a\wedge b={\text{ cota inferior estricta de }}\{a,b\}$.

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 $(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.

Ejemplo.

Sea $A$ un conjunto y sea ${\mathcal {L}}$ el conjunto formado por todas las relaciones de equivalencia en $A$. Si ${\mathcal {R}}$ y ${\mathcal {S}}$ son relaciones de equivalencia, poniendo que

${\mathcal {R}}\prec {\mathcal {S}}\iff {\text{ para todo }}x,y\in A,\quad x{\mathcal {R}}y\implies {\mathcal {S}}y.$

El orden anterior es un reticulado completo.

---