Relaciones de Orden y de Equivalencia

Vamos a introducir el concepto de lo que es una relación de equivalencia y después veremos lo que es una relación de orden. (La palabra $\text{Def}$ introducirá siempre una nueva definición y $\text{Obs}$ denotará una observación). El post de hoy es un poco más técnico, pero no es difícil de comprender, sobre todo si te animas a coger un papel y un lápiz y comprobar que lo que vamos a ir haciendo tiene sentido. Este tipo de herramientas son de las más básicas en matemáticas y por eso no conviene reducirlas a meros comentarios, puesto que entonces muchos desarrollos carecerían de sentido. Así que no te asustes, y pongámonos manos a la obra.

RELACIONES DE EQUIVALENCIA

$\text{Def.}$ Dado un conjunto, $X$, una relación de equivalencia, $R$, es una relación binaria en $X$ (relaciona un par de elementos de $X$, digamos $x$ e $y,$ y se lee $xRy:$ $x$ está relacionado con $y$), que cumple las siguientes tres propiedades:

1. Reflexiva: todo elemento de $X$ está relacionado consigo mismo:$$xRx \ \forall x \in X$$
2. Simétrica: si un elemento está relacionado con otro, entonces dicho otro está relacionado con el primero:$$xRy \Longrightarrow yRx$$
3. Transitiva: si un primer elemento está relacionado con otro segundo, y el segundo está relacionado con un tercero, entonces el primero está relacionado también con el tercero:$$xRy, \ yRz \Longrightarrow xRz$$

Vamos a ver que es muy parecida a la relación de orden (que veremos más adelante) pero se diferencian en la segunda propiedad (simétrica en las relaciones de equivalencia y antisimétrica en las de orden). Se podría entender como una generalización de la igualdad entre dos números en $\mathbb{N}$, y de hecho $=$ es una relación de equivalencia en $\mathbb{N}$.
Vamos a ver unos cuantos ejemplos de relaciones de orden para hacernos una idea de lo que significan.

$\text{Ejemplo.}$ La relación: $nRm \Longleftrightarrow n-m=k\cdot l,$ con $n,m,l \in \mathbb{Z},\ k \in \mathbb{N}$ es una relación de equivalencia. Se suele denotar: $\ nRm \Longleftrightarrow n\equiv m\ \ \text{mod }k$. Lo que realmente está estableciendo es una relación de equivalencia entre los números enteros que al ser divididos por otro, $k$, dejan el mismo resto. Por ejemplo: $5 \equiv 3 \ \ \text{mod }2 $ y $14 \equiv 34 \ \ \text{mod }10 $. Veamos que cumple las tres propiedades para ser una relación de equivalencia.
Primero:  $nRn:$ $\ \ n-n=0=k\cdot l$ es siempre cierto, podemos tomar $l=0$.
Segundo:  $nRm \Longrightarrow mRn:$ $\ \ n-m=k\cdot l \Longrightarrow m-n=-k\cdot l=k \cdot (-l)\Longrightarrow mRn.$ Dada $l$, basta tomar $-l$.
Tercero:  $nRm:$ $\ \ n-m=k\cdot l_1$ y  $mRp:$ $\ \ m-p=k\cdot l_2,$ sumando ambas igualdades, llegamos a $\ \ n-m+m-p=n-p=k\cdot l_1+k\cdot l_2 = k\cdot (l_1 + l_2) \Longrightarrow nRp.$
En efecto la relación es de equivalencia.

$\text{Ejemplo: cardinales.}$ Si tenemos dos conjuntos, queremos ver cuándo tienen el mismo cardinal (quizá esto te ayude). Decimos que dos conjuntos que tienen el mismo cardinal son equipotentes. El asunto es sencillo cuando ambos son finitos, o cuando solo uno de ellos es infinito, pero si son infinitos nadie nos dice que tengan ambos el mismo cardinal. Para ello utilizamos lo que vimos en el post de funciones: dos conjuntos tienen el mismo cardinal (son equipotentes) si podemos establecer entre ambos una biyección. La relación de equivalencia que nos interesa a nosotros es $=_{C}$, y la definimos así: $Card(A)=_{C}Card(B)$ si y sólo si $\exists f:A\longrightarrow B$ biyectiva. Falta probar que la relación es de hecho una relación de equivalencia. Pongámonos a ello.
Primero: $ARA:$ tomando la biyección $f=id$ identidad, que lleva $a$ en $a \ \ \ \forall a\in A.$
Segundo: $ARB \Longrightarrow BRA:$ Sabemos que $f:A \longrightarrow B$ es una biyección por ser $ARB.$ Por tanto, dado $b\in B$, el conjunto $F_b=\left\lbrace a\in A: \ f(a)=b\right\rbrace$, denominado "antiimagen del elemento $b$ por $f$" y denotado por $f^{-1}\left( \left\lbrace b \right\rbrace \right)$, tiene únicamente un elemento (digamos $a_b$). Por tanto la función $g:B \longrightarrow A$ definida por $g(b)=a_b$ es biyectiva y por tanto $BRA$.
Tercero: $ARB, \ BRC \Longrightarrow ARC:$ Sabemos que $f:A \longrightarrow B$ es una biyección y $g:B \longrightarrow C$ también lo es. Basta considerar $h=g \circ f$, la composición de $g$ y $f$, que tiene $f(a)=b$, $\ g(b)=c$ y por tanto $h(a)=g(b)=g(f(a)) \ \forall a \in A$. Si vemos que es biyectiva (siendolo $f$ y $g$) habremos terminado. Para ver que $h$ es biyectiva, vamos a ver que a la vez es inyectiva y sobreyectiva:
Inyectiva: veamos que la composición de inyectivas es inyectiva:$$\begin{align*} h(a)=h(a') \Leftrightarrow g(f(a))&=g(f(a')),\ {g\text{ inyec., luego:}} \\  f(a)&=f(a'),\ {f\text{ inyec., luego}} \\  a&=a'. \end{align*}$$Por tanto $h$ es inyectiva. Sobreyectiva: la composición de sobreyectivas también es sobreyectiva:$$\begin{align*} g \text{ es sobre.} &\Longrightarrow \forall c \in C \ \exists b \in B: \ c=g(b) \\ f  \text{ es sobre.} &\Longrightarrow \ \exists a \in A: \ b=f(a) \\ &\Longrightarrow \forall c \in C \ \exists a \in A: \ c=g(f(a))=h(a)\end{align*}$$Y por tanto $h$ también es sobreyectiva. Como es inyectiva y sobreyectiva, es biyectiva y $ARC$, concluyendo en que $R$ es relación de equivalencia.

RELACIONES DE ORDEN

$\text{Def.}$ Dado un conjunto, $X$, una relación de orden, $R$, es una relación binaria en $X$ que cumple las siguientes tres propiedades:

1. Reflexiva: todo elemento de $X$ está relacionado consigo mismo:$$xRx \ \forall x \in X$$
2. Antisimétrica: si dos elementos se relacionan el uno con el otro, entonces son iguales:$$xRy, \ yRx \Longrightarrow x=y$$
3. Transitiva: si un primer elemento está relacionado con otro segundo, y el segundo está relacionado con un tercero, entonces el primero está relacionado también con el tercero:$$xRy, \ yRz \Longrightarrow xRz$$

Si lo pensamos, el concepto de relación de orden abstrae la noción del orden de los números naturales a cualquier conjunto, siempre que la relación que tomemos sea lo suficientemente buena como para que cumpla las tres propiedades anteriores. Es fácil comprobar que la relación $\leq$ en los naturales, $\mathbb{N}$, es una relación de orden. Además funciona para cualquier par de números que tomemos en $\mathbb{N}$, por lo que decimos que $\mathbb{N}$ es un conjunto totalmente ordenado con la relación $\leq$, o simplemente que $\leq$ es un orden total en $\mathbb{N}$.

Vamos a ver unos cuantos ejemplos de relaciones de orden para hacernos una idea de lo que significan.

$\text{Ejemplo:}$ Vamos a ver que la relación de contención ($\subset$) es una relación de orden. Se define por $ARB \Longleftrightarrow A\subset B.$ Recordemos que $A\subset B$ si y sólo si $x\in A \Longrightarrow x \in B,$ o equivalentemente:  $\forall x \in A, \ x \in B.$ (Todo elemento de $A$ es elemento de $B$).
Primero:  $ARA:$ Es trivial comprobar que $A \subset A,$ puesto que todo elemento de $A$ es elemento de $A.$
Segundo:  $ARB, \ BRA \Longrightarrow A=B:$ Por ser $ARB,$ tenemos que todo elemento de $A$ es elemento de $B$, y por ser $BRA,$ todo elemento de $B$ es elemento de $A.$ Es decir, $a\in A \Longleftrightarrow a\in B$ y por tanto $A=B.$
Tercero:  $ARB, \ BRC \Longrightarrow ARC:$ Por ser $ARB,$ todo elemento de $A$ es elemento de $B$, y por ser $BRC,$ todo elemento de $B$ es elemento de $C,$ en particular lo serán aquellos elementos de $B$ que sean elementos de $A$ también, es decir, todos los elementos de $A$. Por tanto, todo elemento de $A$ es elemento de $C \Longrightarrow A\subset C.$

$\text{Obs.}$ Esto nos garantiza que para probar que dos conjuntos $A$ y $B$ son iguales, tenemos que probar $A\subset B$ y $B\subset A.$

$\text{Ejemplo: cardinales.}$ Vamos a ver que la relación $\leq_{C}$ que dados dos conjuntos compara sus cardinales es una relación de orden. Lo primero es recordar que dados dos conjuntos finitos, $A$ y $B$, habíamos visto que $Card(A) \leq Card(B)$ si había alguna función $f:A \longrightarrow B$ inyectiva (esto es, $f(x)=f(x') \Longrightarrow x=x'$). Por tanto vamos a definir $Card(A) \leq_{C} Card(B) \Longleftrightarrow \exists f:A \longrightarrow B$ inyectiva. (La doble implicación $\Longleftrightarrow$ se lee "si y sólo si" o "equivale"). Ahora veamos que cumple las tres propiedades anteriores y por tanto es una relación de equivalencia.
Para comprobar la primera, nos vale con tomar $f=id$, que es la función que manda $f(x)=x$, la función identidad. Claramente es inyectiva pues $x=f(x)=f(x')=x'$, luego si $f(x)=f(x')$ entonces $x=x'$.
Para comprobar la segunda propiedad tenemos que ver que si $f:A \longrightarrow B$ es inyectiva y $g:B \longrightarrow A$ también es inyectiva, entonces $Card(A)=_CCard(B)$, es decir, $\exists h:A\longrightarrow B$ biyectiva. Este resultado se conoce como "Teorema de Cantor - Bernstein" y lo demostraremos quizá en otro post. De cualquier manera, no es difícil encontrarse con una demostración en algún libro o en internet.
Para comprobar la tercera tenemos que ver que dados $A, B$ y $C$ con $Card(A)\leq_{C}Card(B)\leq_{C}Card(C)$ tenemos $Card(A)\leq_{C}Card(C)$. Es decir, conociendo $f:A \longrightarrow B$ y $g:B \longrightarrow C$ inyectivas, ¿podemos encontrar $h:A \longrightarrow C$ inyectiva también? Sí, y basta considerar $h=g \circ f$, la composición de $g$ y $f$, que vimos un poco antes que es inyectiva por serlo $f$ y $g$.
Hemos "probado" que $\leq_{C}$ es una relación de orden y tiene sentido aplicarla a conjuntos con infinitos elementos, de modo en los siguientes posts veremos cómo se comparan los cardinales de algunos de los conjuntos infinitos más famosos y veremos cómo resolver formalmente el problema del hotel de Hilbert.

$\text{Obs.}$ El Teorema de Cantor - Bernstein nos garantiza que si $Card(A)\leq_{C}Card(B)$ y $Card(B)\leq_{C}Card(A)$ entonces $Card(A)=_{C}Card(B)$, lo cual simplifica el problema de encontrar una función biyectiva en encontrar dos funciones inyectivas.

¡Perfecto! Una vez que sabemos todo esto podemos ponernos manos a la obra con resultados algo más profundos y curiosos, como el ver que hay tantos números pares como números naturales y como números enteros e incluso tantos como números racionales.