2 Relaciones

Definición 2.1 (Relacion binaria de dos conjuntos).

Sean $\displaystyle A$ y $\displaystyle B$ dos conjuntos no vacios. Una relacion binaria entre $\displaystyle A$ y $\displaystyle B$ es un subconjunto $\displaystyle R\subseteq A\times B$ .

Definición 2.2 (Relacion binaria en un conjunto).

Sea $\displaystyle A$ un conjunto no vacio. Una relacion binaria en $\displaystyle A$ es ub subconjunto $\displaystyle R\subseteq A\times A$ .

Sea $\displaystyle R$ una relacion entre dos conjuntos $\displaystyle A$ y $\displaystyle B$ . Si $\displaystyle(a,b)\in R$ decimos que a esta relacionado con b por $\displaystyle R$ y escribimos: $\displaystyle aRb$

Ejemplo.

$\displaystyle A\times B={1,2,3}\times{2,4}$ .

Una relacion es $\displaystyle R_{1}=\{(1,2),(1,4)\}$ o $\displaystyle R_{2}=\{(1,2),(2,2),(3,4)\}$ . El producto cartesiano $\displaystyle A\times B$ o $\displaystyle\varnothing$ tambien son relaciones.

Observación.

Como $\displaystyle A\times B$ tiene $\displaystyle 6$ elementos, puedo encontrar $\displaystyle 2^{6}=64$ relaciones distintas (porque $\displaystyle A\times B$ tiene 64 subconjuntos distintos).

Definición 2.3 (Dominio, imagen).

Sea $\displaystyle R$ una relacion binaria entre dos conjuntos $\displaystyle A$ y $\displaystyle B$ . Se definen

Dominio de $\displaystyle R$ como

$\displaystyle dom(R)\coloneqq\{a\in A\mid\exists b\in B\mid aRb\}$
Imagen o rango de $\displaystyle R$ como

$\displaystyle im(R)\coloneqq\{b\in B\mid\exists a\in A\mid aRb\}$

Definición 2.4.

Sea $\displaystyle R$ una relacion binaria entre dos conjuntos $\displaystyle A$ y $\displaystyle B$ . Sean $\displaystyle C\subseteq A$ y $\displaystyle D\subseteq B$ . Se definen:

Imagen inversa de $\displaystyle D$ por $\displaystyle R$ como

$\displaystyle R^{-1}(D)\coloneqq\{a\in A\mid\exists b\in D\mid aRb\}$
Imagen o imagen directa de $\displaystyle C$ por $\displaystyle R$ como

$\displaystyle R(C)\coloneqq\{b\in B\mid\exists a\in C\mid aRb\}$

Observación.

\displaystyle dom(R)=R^{-1}(B)

\displaystyle im(R)=R(A)

Ejemplo.

Sean $\displaystyle A=\{1,3,5\}$ , $\displaystyle B=\{2,3\}$ , $\displaystyle C=\{1,3\}\subseteq A$ , $\displaystyle D=\{2\}\subseteq B$ .

$\displaystyle R_{1}=\{(1,2),(3,2),(3,3)\}$

$\displaystyle dom(R_{1})=\{1,3\},\,im(R_{1})=\{2,3\},\,R^{-1}_{1}(D)=\{1,3\},% \,R_{1}(C)=\{2,3\}$
$\displaystyle R_{2}=\{(1,2),(3,3),(5,2)\}$ - Funcion.

$\displaystyle dom(R_{2})=A,im(R_{2})=B,R^{-1}_{2}(D)=\{1,5\},R_{2}(C)=\{2,3\}=B$

En total habia $\displaystyle 2^{6}$ relaciones entre $\displaystyle A$ y $\displaystyle B$ .

Ejemplo.

Sean $\displaystyle A=\{1,2,4,5\}$ , $\displaystyle C=\{2,5\}\subseteq A$ .

$\displaystyle R_{1}=\{(x,y)\mid x=y\}$

$\displaystyle dom(R_{1})=A,im(R_{1})=A,R^{-1}_{1}(C)=\{2,5\}=C,R_{1}(C)=\{2,5% \}=C$
$\displaystyle R_{2}=\{(x,y)\mid x\neq y\}=A^{2}\setminus R_{1}$

$\displaystyle dom(R_{2})=A,im(R_{2})=A,R^{-1}_{2}(C)=A,R_{2}(C)=A$
$\displaystyle R_{3}=\{(x,y)\mid x<y\}$

$\displaystyle dom(R_{3})=\{1,2,4\},im(R_{4})=\{2,4,5\},R^{-1}_{3}(C)=\{1,2,4\}% ,R_{3}(C)=\{4,5\}$
$\displaystyle R_{4}=\{(x,y)\mid x\leq y\}=R_{1}\cup R_{3}$

$\displaystyle dom(R_{4})=A,im(R_{4})=A,R^{-1}_{4}(C)=A,R_{4}(C)=\{2,4,5\}$
$\displaystyle R_{5}=\{(x,y)\mid x\text{ es divisor de }y\}=\{(1,1),(1,2),(1,4)% ,(1,5),(2,2),(2,4),(4,4),(5,5)\}$

$\displaystyle dom(R_{5})=A,im(R_{5})=A,R^{-1}_{5}(C)=\{2,4,5\},R_{5}(C)=\{2,4,5\}$
$\displaystyle R_{6}=\{(1,1),(1,4),(2,4)\}$

$\displaystyle dom(R_{6})=\{1,2\},im(R_{6})=\{1,4\},R^{-1}_{6}(C)=\varnothing,R% _{6}(C)=\{4\}$

Definición 2.5.

Sean $\displaystyle P$ y $\displaystyle Q$ dos enunciados. La notacion

\displaystyle P\Rightarrow Q

se lee “ $\displaystyle P$ implica $\displaystyle Q$ ”.

El unico caso en el que es falsa es cuando sucede $\displaystyle P$ y no sucede $\displaystyle Q$ . Esta situacion supone un contraejemplo a la implicacion.

La notacion

\displaystyle P\Leftrightarrow Q

se lee “ $\displaystyle P$ si y solo si $\displaystyle Q$ ” o “ $\displaystyle P$ es equivalente a $\displaystyle Q$ ” y quiere decir que $\displaystyle P\Rightarrow Q$ y $\displaystyle Q\Rightarrow P$ simultaneamente. Es falsa si sucede una de las dos afirmaciones y no la otra.

Definición 2.6.

Sean $\displaystyle A$ un conjunto no vacio y $\displaystyle R$ una relacion binaria en $\displaystyle A$ . Decimos que $\displaystyle R$ cumple la propiedad

Reflexiva si $\displaystyle\forall x\in A\;(xRx)$
Simetrica si $\displaystyle\forall x,y\in A\;(xRy\Rightarrow yRx)$
Antisimetrica si $\displaystyle\forall x,y\in A\;(xRy,x\neq y\Rightarrow y\cancel{R}z)$
También se puede formular: $\displaystyle\forall x,y\in A\;(xRy,yRx\Rightarrow x=y)$
Transitiva si $\displaystyle\forall x,y,z\in A\;(xRy,yRz\Rightarrow xRz)$

Definición 2.7.

Sean $\displaystyle A$ un conjunto no vacio y $\displaystyle R$ una relacion binaria en $\displaystyle A$ . Decimos que $\displaystyle R$ es una relacion de

Equivalencia si cumple las propiedades reflexiva, simetrica y transitiva.
Orden si cumple las propiedades reflexiva, antisimetrica y transitiva.
Orden total si es de orden y ademas $\displaystyle\forall x,y\in A\;(xRy\text{ o }yRx)$

Ejemplo.

Sea $\displaystyle A=\{a,b,c,d\}$ . Para cada una de las siguientes relaciones $\displaystyle R_{i}$ en $\displaystyle A$ , estudia si cumplen las propiedades reflexiva, simetrica, antisimetrica y transitiva. Tambien si son de equivalencia, orden y orden total.

$\displaystyle R_{1}=\{(a,b),(b,c)\}$
$\displaystyle R_{2}=\{(a,a),(b,b),(c,c),(a,b),(b,a),(b,c)\}$
$\displaystyle R_{3}=\{(a,b),(c,d),(d,c)\}$
$\displaystyle R_{4}=A\times A$
$\displaystyle R_{5}=\varnothing$
$\displaystyle R_{6}=\{(x,y)\mid x=y\}$
$\displaystyle R_{7}=R_{6}\cup\{(a,b),(b,a),(c,d),(d,c)\}$
$\displaystyle R_{8}=\{(x,y)\mid x\text{ va antes que }y\text{ en el alfabeto}\}$
$\displaystyle R_{9}=R_{6}\cup R_{8}$
$\displaystyle R_{10}=R_{6}\cup\{(a,b),(c,d)\}$

Solucion:

$\displaystyle R_{1}=\{(a,b),(b,c)\}$

No es reflexiva porque $\displaystyle a\cancel{R}a$ (contraejemplo). Por tanto no es de equivalencia ni de orden y, por tanto, no es de orden total.

Tampoco es simetrica porque $\displaystyle aRb$ pero $\displaystyle b\cancel{R}a$ . $\displaystyle R_{1}$ es antisimetrica porque se cumple la definicion. Por ultimo, no es transitiva porque $\displaystyle aRb$ y $\displaystyle bRc$ pero $\displaystyle a\cancel{R}c$ .
$\displaystyle R_{2}=\{(a,a),(b,b),(c,c),(a,b),(b,a),(b,c)\}$

$\displaystyle R_{2}$ no es reflexiva (contraejemplo: $\displaystyle d\cancel{R}d$ ). Luego no es de equivalencia, orden ni orden total.

No es simetrica porque $\displaystyle bRc$ pero $\displaystyle c\cancel{R}b$ . Tampoco es antisimetrica porque $\displaystyle aRb,a\neq b\Rightarrow bRa$ . Por ultimo, no es simetrica porque $\displaystyle aRb$ y $\displaystyle bRc$ pero $\displaystyle a\cancel{R}c$ .
$\displaystyle R_{3}=\{(a,b),(c,d),(d,c)\}$ .

No es reflexiva. Contraejemplo: $\displaystyle a\cancel{R}a$ . No es simetrica porque $\displaystyle aRb$ pero $\displaystyle b\cancel{R}a$ . No es antisimetrica porque $\displaystyle cRd$ y $\displaystyle dRc$ y $\displaystyle d\neq c$ . No es transitiva porque $\displaystyle cRd$ y $\displaystyle dRc$ pero $\displaystyle c\cancel{R}c$ .
$\displaystyle R_{4}=A\times A$ .

Es reflexiva porque se cumple la definicion (todos los elementos de $\displaystyle A$ estan relacionados consigo mismos). Es simetrica (se cumple la definicion). No es antisimetrica: $\displaystyle aRb$ y $\displaystyle bRa$ . Es transitiva.

Es una relacion de equivalencia.
$\displaystyle R_{5}=\varnothing$ .

No es reflexiva, $\displaystyle a\cancel{R}a$ . Es simetrica porque se cumple la definicion (no hay ningun contraejemplo). Tambien es antisimetrica y transitiva por la misma razon.
$\displaystyle R_{6}=\{(x,y)\mid x=y\}=\{(a,a),(b,b),(c,c),(d,d)\}$ .

Es reflexiva ya que todos los elementos estan relacionados consigo mismos. Es simetrica y antisimetrica ( $\displaystyle xRy,yRx\Rightarrow x=y$ ). Tambien es transitiva, ya que no hay ningun contraejemplo ( $\displaystyle xRy,yRz$ solo puede pasar si $\displaystyle x=y=z$ ).

$\displaystyle R_{6}$ es una relacion de equivalencia y de orden. No es de orden total porque $\displaystyle a\cancel{R}b$ y $\displaystyle b\cancel{R}a$ .
$\displaystyle R_{7}=R_{6}\cup\{(a,b),(b,a),(c,d),(d,c)\}$ .

Es reflexiva porque estan los pares de $\displaystyle R_{6}$ (es decir, $\displaystyle R_{6}\subseteq R_{7}$ ). Es simetrica porque en los pares que he añadido no he metido contraejemplos. No es antisimetrica; un contraejemplo es $\displaystyle aRb,bRa$ . Es transitiva pues no se pueden encontrar contraejemplos.

$\displaystyle R_{7}$ es de equivalencia. No es de orden y, por tanto, tampoco de orden total.
$\displaystyle R_{8}=\{(x,y)\mid x\text{ va antes que }y\text{ en el alfabeto}\}$

No es reflexiva. No es simetrica ( $\displaystyle aRb$ y $\displaystyle b\cancel{R}a$ ). Es antisimetrica porque no hay contraejemplos. Es transitiva.

Vamos a ver que es antisimetrica y transitiva solo con la definicion. Supongamos que $\displaystyle A$ es el alfabeto español. $\displaystyle|A|=27$ y $\displaystyle R_{8}$ es la misma relacion.

Si $\displaystyle\alpha$ va antes que $\displaystyle\beta$ , $\displaystyle\beta$ va antes que $\displaystyle\lambda$ , entonces $\displaystyle\alpha$ va antes que $\displaystyle\lambda$ . Luego si es transitiva.

Si $\displaystyle\alpha$ va antes que $\displaystyle\beta$ ( $\displaystyle\alpha R_{8}\beta$ ) entonces $\displaystyle\beta$ no va antes que $\displaystyle\alpha$ , luego $\displaystyle(\beta\cancel{R}_{8}\alpha)$ . Entonces es antisimetrica.
$\displaystyle R_{9}=R_{6}\cup R_{8}=\{(\alpha,\beta)\mid\alpha\text{ va antes % que }\beta\text{ o }\alpha=\beta\}$ .

Es reflexiva porque estan todos los pares de $\displaystyle R_{6}$ . No es simetrica porque $\displaystyle aRb$ pero $\displaystyle b\cancel{R}a$ .

Es antisimetrica: vamos a usar la definicion $\displaystyle\alpha R_{9}\beta,\beta R_{9}\alpha\Rightarrow\alpha=\beta$ . $\displaystyle\alpha$ va antes o es igual que $\displaystyle\beta$ y $\displaystyle\beta$ va antes o es igual que $\displaystyle\alpha$ . La unica opcion es $\displaystyle\alpha=\beta$ . Por tanto es antisimetrica.

Si $\displaystyle\alpha$ va antes o es igual a $\displaystyle\beta$ y $\displaystyle\beta$ va antes o es igual a $\displaystyle\gamma$ entonces $\displaystyle\alpha$ va antes o es igual a $\displaystyle\gamma$ . Luego si es transitiva.

$\displaystyle R_{9}$ es de orden. Tambien es de orden total porque todos los elementos estan relacionados.
$\displaystyle R_{10}=R_{6}\cup\{(a,b),(c,d)\}$

Es reflexiva porque estan todos los pares de $\displaystyle R_{6}$ . No es simetrica porque $\displaystyle aRb$ pero $\displaystyle b\cancel{R}a$ . Es antisimetrica. Es transitiva porque no se han añadido contraejemplos.

$\displaystyle R_{10}$ es una relacion de orden. No es total ( $\displaystyle a\cancel{R}_{10}c$ ).

Ejemplo.

$\displaystyle A=\{\text{conjunto formado por 9 boligrafos, dos rojos, tres % azules y 4 negros}\}$

Dados $\displaystyle x,y\in A$ , $\displaystyle xRy\Leftrightarrow\text{x es del mismo color que y}$ .

Tambien se puede definir $\displaystyle R=\{(x,y)\mid\text{x es del mismo color que y}\}$ .

Esta relacion es reflexiva: $\displaystyle\forall x,x$ es del mismo color que $\displaystyle x$ . Tambien es simetrica: si $\displaystyle xRy$ (x es del mismo color que y), entonces $\displaystyle yRx$ (y es del mismo color que x). Por ultimo, es transitiva: $\displaystyle\forall x,y,z$ si $\displaystyle x$ es del mismo color que $\displaystyle y$ , $\displaystyle y$ es del mismo color que $\displaystyle z$ , entonces $\displaystyle x$ es del mismo color que $\displaystyle z.$

Luego $\displaystyle R$ es de equivalencia. Una relacion de equivalencia genera una particion. A los elementos de la particion se les llama “clases de equivalencia”. En este caso, hay 3 clases de equivalencia: la de los bolis rojos, la de los bolis negros y la de los bolis azules:

	$\displaystyle\displaystyle\{B_{1},B_{2}\}$	$\displaystyle\displaystyle=[B_{2}]$
	$\displaystyle\displaystyle\{B_{3},B_{4},B_{5}\}$	$\displaystyle\displaystyle=[B_{3}]$
	$\displaystyle\displaystyle\{B_{6},B_{7},B_{8},B_{9}\}$	$\displaystyle\displaystyle=[B_{8}]$

$\displaystyle B_{2}$ , $\displaystyle B_{3}$ y $\displaystyle B_{8}$ son representantes de clase (elegidos de forma arbitraria).

El conjunto cociente va a ser el conjunto formado por las clases de equivalencia $\displaystyle A/R=\{[B_{2}],[B_{3}],[B_{8}]\}$ .

Definición 2.8 (Clase de equivalencia).

Sea $\displaystyle R$ una relacion de equivalencia en un conjunto $\displaystyle A$ y sea $\displaystyle a\in A$ . Llamamos clase de equivalencia de $\displaystyle a$ por la relacion $\displaystyle R$ al conjunto de todos los elementos de $\displaystyle A$ que estan relacionados con $\displaystyle a$ . Simbolicamente:

\displaystyle[a]_{R}\coloneqq\{b\in A\mid aRb\}

Si, por contexto, esta claro que solo podemos estar hablando de clases respecto de la relacion $\displaystyle R$ , omitiremos el subindice y escribiremos $\displaystyle[a]$ . Tambien se puede escribir $\displaystyle\overline{a}$ .

Definición 2.9 (Conjunto cociente).

Sea $\displaystyle R$ una relacion de equivalencia en un conjunto $\displaystyle A$ . Llamamos conjunto cociente de $\displaystyle A$ bajo la relacion $\displaystyle R$ al conjunto formado por todas las clases de equivalencia de la relacion. Simbolicamente:

\displaystyle A/R\coloneqq\{[a]_{R}\mid a\in A\}

Ejemplo.

$\displaystyle R_{4}=A\times A$ .

$\displaystyle A=\{a,b,c,d\}$ .

$\displaystyle[a]_{R_{4}}=\{a,b,c,d\}$ .

$\displaystyle[b]_{R_{4}}=\{a,b,c,d\}$ .

Hay una unica clase de equivalencia. El cociente es $\displaystyle A/R=\{[a]_{R_{4}}\}$ .

Otra relacion de equivalencia es $\displaystyle R_{6}=\{(x,y)\mid x=y\}$ .

En este caso, $\displaystyle[a]_{R_{6}}=\{a\},\,[b]_{R_{6}}=\{b\},\,[c]_{R_{6}}=\{c\},\,[d]_{% R_{6}}=\{d\}$ . El conjunto cociente esta formado por 4 elementos:

\displaystyle A/R_{6}=\{[a]_{R_{6}},[b]_{R_{6}},[c]_{R_{6}},[d]_{R_{6}}\}.

$\displaystyle R_{7}=R_{6}\cup\{(a,b),(b,a),(c,d),(d,c)\}$ . En este caso, hay 2 clases:

$\displaystyle[a]_{R_{7}}=\{a,b\}=[b]_{R_{7}}$ y $\displaystyle[c]_{R_{7}}=\{b,c\}=[c]_{R_{7}}$ .

El conjunto cociente es $\displaystyle A/R_{7}=\{[a]_{R_{7}},[d]_{R_{7}}\}$ .

Otro ejemplo es $\displaystyle R=S\cup\{(a,b),(b,a),(a,c),(c,a),(b,c),(c,b)\}$ , siendo $\displaystyle S$ la relacion de igualdad. Se puede demostrar que es una relacion de equivalencia.

Las clases de equivalencia son $\displaystyle[a]_{R}=\{a,b,c\}=[b]_{R}=[c]_{R}$ y $\displaystyle[d]_{R}=\{d\}$ . El conjunto cociente es $\displaystyle A/R=\{[a]_{R},[d]_{R}\}$ .

Proposición 2.1.

Sean $\displaystyle R$ una relacion de equivalencia en un conjunto $\displaystyle A$ y $\displaystyle a,b\in A$ . Se cumple:

$\displaystyle aRb\Rightarrow[a]=[b]$ .
$\displaystyle a\cancel{R}b\Rightarrow[a]\cap[b]=\varnothing$ .

Demostración.

Sean $\displaystyle a,b\in A$ .

Si $\displaystyle aRb$ :

Tenemos que demostrar que $\displaystyle[a]=[b]$ . Para ello, vamos a ver un doble contenido de conjuntos.

$\displaystyle\subseteq)$ Vamos a ver que $\displaystyle[a]\subseteq[b]$ .

$\displaystyle[a]=\{x\in A\mid aRx\}$ y $\displaystyle[b]=\{x\in B\mid bRx\}$ .

Sea $\displaystyle x\in[a]\Rightarrow aRx$ . Como $\displaystyle aRx$ y $\displaystyle R$ es simetrica (por ser una relacion de equivalencia), tenemos que $\displaystyle xRa$ . Como $\displaystyle xRa$ y $\displaystyle aRb$ , por ser $\displaystyle R$ transitiva, tengo que $\displaystyle xRb\overset{R\text{ simetrica}}{\Rightarrow}bRx\Rightarrow x\in[b]$ .

$\displaystyle\supseteq)$ Sea $\displaystyle x\in[b]\Rightarrow bRx$ .

Como $\displaystyle aRb$ y $\displaystyle R$ es transitiva, $\displaystyle aRx\Rightarrow x\in[a]$ .
Si $\displaystyle a\cancel{R}b$ :

Tenemos que demostrar que $\displaystyle[a]\cap[b]=\varnothing$ . Por reduccion al absurdo, supongamos que $\displaystyle[a]\cap[b]\neq\varnothing\Rightarrow\exists x\in[a]\text{ y }x\in% [b]$ .

Sin embargo, $\displaystyle x\in[a]\Rightarrow aRx$ y $\displaystyle x\in[b]\Rightarrow bRx\Rightarrow xRb\text{ (R simetrica)}$ . Como $\displaystyle aRx,xRb$ y $\displaystyle R$ es transitiva entonces $\displaystyle aRb$ . Hemos llegado a una contradiccion porque partimos de que $\displaystyle a\cancel{R}b$ .

Por tanto, $\displaystyle[a]\cap[b]=\varnothing$ .

∎

Definición 2.10 (Conjuntos disjuntos).

Sean $\displaystyle A$ y $\displaystyle B$ dos conjuntos. Decimos que son disjuntos si $\displaystyle A\cap B=\varnothing$ .

Definición 2.11 (Partición).

Sea $\displaystyle A$ un conjunto. Decimos que una coleccion de subconjuntos de $\displaystyle A$ constituye una particion de $\displaystyle A$ si se cumplen las dos condiciones siguientes:

Son disjuntos dos a dos: dos conjuntos diferentes cualesquiera de la coleccion son disjuntos.
Recubren $\displaystyle A$ : la union de todos ellos es $\displaystyle A$ .

Teorema 2.1.

Sea $\displaystyle R$ una relacion de equivalencia en un conjunto $\displaystyle A$ . Entonces las clases de equivalencia de $\displaystyle R$ constituyen una particion de $\displaystyle A$ .

Demostración.

En la proposicion 3 hemos demostrado que las clases de equivalencia son disjuntas dos a dos.

Veamos que las clases recubren $\displaystyle A$ .

Dado $\displaystyle a\in A$ se cumple que por ser $\displaystyle R$ reflexiva que $\displaystyle aRa\Rightarrow a\in[a]$ .

Luego todo elemento pertenece a una clase de equivalencia. ∎

Ejemplo.

$\displaystyle A=\{a,b,c,d\}$ .

Una particion es: $\displaystyle A_{1}=\{a\}$ $\displaystyle A_{2}=\{b,d\}$ $\displaystyle A_{3}=\{c\}$ .

Defino $\displaystyle R$ como: $\displaystyle R=\{(a,a),(b,b),(c,c),(d,d),(b,d),(d,b)\}$ .

Entonces $\displaystyle[a]=\{a\},[b]=\{b,d\},[c]=\{c\}$ . Dentro de cada conjunto de la particion he relacionado sus elementos de todas las formas posibles.

Teorema 2.2.

Supongamos que tenemos una particion de un conjunto $\displaystyle A$ . Definimos una relacion $\displaystyle R$ en $\displaystyle A$ de la siguiente forma:

\displaystyle aRb\Leftrightarrow\text{existe un subconjunto de la particion al% que }a\text{ y }b\text{ pertenecen}

Entonces la relacion $\displaystyle R$ es de equivalencia.

Ademas, las clases de equivalencia de $\displaystyle R$ coinciden con los subconjuntos de la particion.

Demostración.

Vamos a demostrar que $\displaystyle R$ es de equivalencia.

$\displaystyle R$ es reflexiva?

Dado $\displaystyle a\in A$ , como la particion recubre $\displaystyle A$ existe un conjunto de la particion al que $\displaystyle a$ pertenece. Luego $\displaystyle a$ y $\displaystyle a$ estan en el mismo conjunto de la particion $\displaystyle\Rightarrow aRa$ .
$\displaystyle R$ es simetrica?

$\displaystyle aRb\Rightarrow a$ y $\displaystyle b$ estan en el mismo conjunto de la particion $\displaystyle\Rightarrow bRa$ .

Por tanto, $\displaystyle R$ es simetrica.
$\displaystyle R$ es transitiva?

$\displaystyle aRb,bRc\Rightarrow a$ y $\displaystyle b$ estan en el mismo conjunto de la particion y $\displaystyle b$ y c estan en el mismo conjunto de la particion. Por lo tanto, $\displaystyle a$ y $\displaystyle c$ estan en el mismo conjunto y $\displaystyle aRc$ .

Las clases de $\displaystyle R$ son los conjuntos de la particion por construccion.

\displaystyle[a]_{R}=\{b\mid aRb\}=\{b\mid\text{a y b estan en el mismo % conjunto de particion}\}

Luego es el conjunto de la particion al que $\displaystyle a$ pertenece. ∎

Ejemplo.

Cuantas relaciones de equivalencia se pueden definir sobre un conjunto de 4 elementos?

Demostración.

Es lo mismo que contar cuantas particiones diferentes se pueden hacer de un conjunto de 4 elementos. Cuento por numero de “trozos”.

Con un subconjunto. Solo hay una particion que es tomar todo el conjunto.
Con 2 trozos. En total, hay 7 trozos (3 con 2 trozos iguales, 4 con un trozo de 1 elemento y otro de 3).
Con 3 trozos. Los trozos deben ser 2 de 1 elemento y otro de 2. Hay 6 distintas.
Con 4 trozos hay una unica forma.

Hay $\displaystyle 1+7+6+1=15$ relaciones de equivalencia distintas en $\displaystyle A$ . Ver: Numeros de Bell. ∎

Ejemplo.

Dos relaciones de equivalencia importantes:

Construccion de los racionales.
Enteros modulo 2.

Demostración.

Los numeros racionales como cociente.

Si defino los racionales como $\displaystyle F=\left\{\frac{a}{b}\mid a,b\in\mathbb{Z},b\neq 0\right\}$ :
En el conjunto $\displaystyle F$ de fracciones vamos a definir una relacion $\displaystyle R$ tal que

$\displaystyle\frac{a}{b}R\frac{c}{d}\Leftrightarrow a\cdot d=c\cdot b$

Vamos a demostrar que $\displaystyle R$ es de equivalencia.
- •
  
  $\displaystyle R$ reflexiva: $\displaystyle\forall a,b$ se cumple
  
  $\displaystyle\frac{a}{b}R\frac{a}{b}$
- •
  
  Simetrica: $\displaystyle\forall\frac{a}{b}\cdot\frac{c}{d}$
  
  $\displaystyle\frac{c}{d}R\frac{a}{b}\Rightarrow cb=ad\Rightarrow\frac{a}{b}R% \frac{c}{d}$
- •
  
  Transitiva: $\displaystyle\forall\frac{a}{b}\cdot\frac{c}{d}\cdot\frac{e}{f}$
  
  $\displaystyle\frac{a}{b}R\frac{c}{d},\frac{c}{d}R\frac{e}{f}\Rightarrow\frac{a% }{b}R\frac{e}{f}?$
  
  $\displaystyle\frac{a}{b}R\frac{c}{d}\Rightarrow ad=cb$ , $\displaystyle\frac{c}{d}R\frac{e}{f}\Rightarrow cf=de$
  
  Debemos llegar a que $\displaystyle af=eb$
  
  $adf=cbf\Rightarrow adf=deb$
  
  Como d es un denominador, implica que $\displaystyle d\neq 0$ y puedo dividir ambos enteros entre $\displaystyle d$ $\displaystyle\Rightarrow af=eb$ .
Luego la relacion $\displaystyle R$ es de equivalencia. Como son las clases?
Por ejemplo:

$\displaystyle\left[\frac{2}{3}\right]=\left\{\frac{2}{3},\frac{6}{9},\ldots,% \frac{-2}{-3},\frac{-4}{-6},\ldots\right\}$

$\displaystyle|[\frac{2}{3}]|=\infty$

$\displaystyle F/R=\{[\frac{a}{b}]\mid\frac{a}{b}\in F\}=\mathbb{Q}$ .

Quien es $\displaystyle[\frac{4}{6}]$ ?

Luego en este cociente $\displaystyle[\frac{2}{3}]=[\frac{4}{6}]$ .

Obs: $\displaystyle|Q|=\infty$ .
Enteros modulo 2.

$\displaystyle A=\mathbb{Z}$ . Dados $\displaystyle x,y\in\mathbb{Z}$ , $\displaystyle xRy\Leftrightarrow x-y$ es par. Es decir, $\displaystyle\exists k\in\mathbb{Z}$ tal que $\displaystyle x-y=2k$ ( $\displaystyle x\equiv y\text{ mod }2$ ) ( $\displaystyle x$ congruente con $\displaystyle y$ modulo 2).
Veamos si esta relacion es de equivalencia:
- •
  
  Reflexiva: $\displaystyle\forall x\in\mathbb{Z},\;x\equiv x\text{ mod }2?$
  
  Si porque $\displaystyle x-x=2\cdot 0=0$
- •
  
  Simetrica: $\displaystyle\forall x,y\in\mathbb{Z},\;x\equiv y\text{ mod }2\Rightarrow y% \equiv x\text{ mod }2?$
  
  Si $\displaystyle x\equiv y\text{ mod }2\Rightarrow\exists k\in\mathbb{Z}$ tal que $\displaystyle x-y=2k\Rightarrow y-x=2(-k)\Rightarrow y\equiv x\text{ mod }2$ .
- •
  
  Transitiva: $\displaystyle\forall x,y,z\in\mathbb{Z},\;x\equiv y\text{ mod }2,y\equiv z% \text{ mod }2\Rightarrow x\equiv z\text{ mod }2?$
  
  $\displaystyle x\equiv y\text{ mod }2$ $\displaystyle\Rightarrow\exists k\in\mathbb{Z}/x-y=2k$
  
  $\displaystyle y\equiv z\text{ mod }2\Rightarrow\exists m\in\mathbb{Z}/y-z=2m$ .
  
  Sumando $\displaystyle x-y+y-z=2k+2m\Rightarrow x-z=2(k+m)$ . Por tanto $\displaystyle x\equiv z\text{ mod }2$ .
Hemos visto que la congruencia modulo 2 es una relacion de equivalencia.
Ejemplos de enteros relacionados: $\displaystyle 8\equiv 6\text{ mod 2}$ , $\displaystyle 3\equiv 7\text{ mod }2$ , $\displaystyle 4\equiv 4\text{ mod }2$ .

Clases de equivalencia:

$\displaystyle[1]=\{\ldots,-3,-1,1,3,5,7,\ldots\}=[3]=[5]=\ldots$

$\displaystyle[2]=\{\ldots,-4,-2,0,2,4,\ldots\}=[4]=[0]=\ldots$

Luego hay 2 clases y $\displaystyle\mathbb{Z}/\equiv\text{mod }2=\{[0],[1]\}=\mathbb{Z}_{2}$ .

∎

Definición 2.12 (Orden parcial).

Decimos que una relacion es de orden parcial si es de orden pero no es de orden total.

Ejemplo.

Relacion “menor o igual” en $\displaystyle\mathbb{Z}$ (orden total).
Relacion “contenido o igual” en $\displaystyle\mathcal{{P}}(A),$ siendo $\displaystyle A$ un conjunto (orden parcial si $\displaystyle|A|\geq 2$ , orden total si $\displaystyle|A|=1$ o $\displaystyle A=\varnothing$ ).

Definición 2.13.

Sean $\displaystyle n\in\mathbb{N},n\geq 2$ y $\displaystyle A_{1},A_{2},\ldots,A_{n}$ conjuntos no vacios. Una relacion $\displaystyle n$ -aria entre $\displaystyle A_{1},A_{2},\ldots,A_{n}$ es un subconjunto $\displaystyle R\subseteq A_{1}\times A_{2}\times\cdots\times A_{n}$ .