2 Relaciones

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

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

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

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

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

Ejemplo.

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

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

Observación.

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

Definición 2.3 (Dominio, imagen).

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

  •  

    Dominio de R\displaystyle R como

    dom(R){aAbBaRb}\displaystyle dom(R)\coloneqq\{a\in A\mid\exists b\in B\mid aRb\}
  •  

    Imagen o rango de R\displaystyle R como

    im(R){bBaAaRb}\displaystyle im(R)\coloneqq\{b\in B\mid\exists a\in A\mid aRb\}
Definición 2.4.

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

  •  

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

    R1(D){aAbDaRb}\displaystyle R^{-1}(D)\coloneqq\{a\in A\mid\exists b\in D\mid aRb\}
  •  

    Imagen o imagen directa de C\displaystyle C por R\displaystyle R como

    R(C){bBaCaRb}\displaystyle R(C)\coloneqq\{b\in B\mid\exists a\in C\mid aRb\}
Observación.
dom(R)=R1(B)\displaystyle dom(R)=R^{-1}(B)
im(R)=R(A)\displaystyle im(R)=R(A)
Ejemplo.

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

  •  

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

    dom(R1)={1,3},im(R1)={2,3},R11(D)={1,3},R1(C)={2,3}\displaystyle dom(R_{1})=\{1,3\},\,im(R_{1})=\{2,3\},\,R^{-1}_{1}(D)=\{1,3\},% \,R_{1}(C)=\{2,3\}
  •  

    R2={(1,2),(3,3),(5,2)}\displaystyle R_{2}=\{(1,2),(3,3),(5,2)\} - Funcion.

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

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

Ejemplo.

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

  •  

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

    dom(R1)=A,im(R1)=A,R11(C)={2,5}=C,R1(C)={2,5}=C\displaystyle dom(R_{1})=A,im(R_{1})=A,R^{-1}_{1}(C)=\{2,5\}=C,R_{1}(C)=\{2,5% \}=C
  •  

    R2={(x,y)xy}=A2R1\displaystyle R_{2}=\{(x,y)\mid x\neq y\}=A^{2}\setminus R_{1}

    dom(R2)=A,im(R2)=A,R21(C)=A,R2(C)=A\displaystyle dom(R_{2})=A,im(R_{2})=A,R^{-1}_{2}(C)=A,R_{2}(C)=A
  •  

    R3={(x,y)x<y}\displaystyle R_{3}=\{(x,y)\mid x<y\}

    dom(R3)={1,2,4},im(R4)={2,4,5},R31(C)={1,2,4},R3(C)={4,5}\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\}
  •  

    R4={(x,y)xy}=R1R3\displaystyle R_{4}=\{(x,y)\mid x\leq y\}=R_{1}\cup R_{3}

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

    R5={(x,y)x es divisor de y}={(1,1),(1,2),(1,4),(1,5),(2,2),(2,4),(4,4),(5,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)\}

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

    R6={(1,1),(1,4),(2,4)}\displaystyle R_{6}=\{(1,1),(1,4),(2,4)\}

    dom(R6)={1,2},im(R6)={1,4},R61(C)=,R6(C)={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 P\displaystyle P y Q\displaystyle Q dos enunciados. La notacion

PQ\displaystyle P\Rightarrow Q

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

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

La notacion

PQ\displaystyle P\Leftrightarrow Q

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

Definición 2.6.

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

  •  

    Reflexiva si xA(xRx)\displaystyle\forall x\in A\;(xRx)

  •  

    Simetrica si x,yA(xRyyRx)\displaystyle\forall x,y\in A\;(xRy\Rightarrow yRx)

  •  

    Antisimetrica si x,yA(xRy,xyyRz)\displaystyle\forall x,y\in A\;(xRy,x\neq y\Rightarrow y\cancel{R}z)
    También se puede formular: x,yA(xRy,yRxx=y)\displaystyle\forall x,y\in A\;(xRy,yRx\Rightarrow x=y)

  •  

    Transitiva si x,y,zA(xRy,yRzxRz)\displaystyle\forall x,y,z\in A\;(xRy,yRz\Rightarrow xRz)

Definición 2.7.

Sean A\displaystyle A un conjunto no vacio y R\displaystyle R una relacion binaria en A\displaystyle A. Decimos que R\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 x,yA(xRy o yRx)\displaystyle\forall x,y\in A\;(xRy\text{ o }yRx)

Ejemplo.

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

  •  

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

  •  

    R2={(a,a),(b,b),(c,c),(a,b),(b,a),(b,c)}\displaystyle R_{2}=\{(a,a),(b,b),(c,c),(a,b),(b,a),(b,c)\}

  •  

    R3={(a,b),(c,d),(d,c)}\displaystyle R_{3}=\{(a,b),(c,d),(d,c)\}

  •  

    R4=A×A\displaystyle R_{4}=A\times A

  •  

    R5=\displaystyle R_{5}=\varnothing

  •  

    R6={(x,y)x=y}\displaystyle R_{6}=\{(x,y)\mid x=y\}

  •  

    R7=R6{(a,b),(b,a),(c,d),(d,c)}\displaystyle R_{7}=R_{6}\cup\{(a,b),(b,a),(c,d),(d,c)\}

  •  

    R8={(x,y)x va antes que y en el alfabeto}\displaystyle R_{8}=\{(x,y)\mid x\text{ va antes que }y\text{ en el alfabeto}\}

  •  

    R9=R6R8\displaystyle R_{9}=R_{6}\cup R_{8}

  •  

    R10=R6{(a,b),(c,d)}\displaystyle R_{10}=R_{6}\cup\{(a,b),(c,d)\}

Solucion:

  •  

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

    No es reflexiva porque aRa\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 aRb\displaystyle aRb pero bRa\displaystyle b\cancel{R}a. R1\displaystyle R_{1} es antisimetrica porque se cumple la definicion. Por ultimo, no es transitiva porque aRb\displaystyle aRb y bRc\displaystyle bRc pero aRc\displaystyle a\cancel{R}c.

  •  

    R2={(a,a),(b,b),(c,c),(a,b),(b,a),(b,c)}\displaystyle R_{2}=\{(a,a),(b,b),(c,c),(a,b),(b,a),(b,c)\}

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

    No es simetrica porque bRc\displaystyle bRc pero cRb\displaystyle c\cancel{R}b. Tampoco es antisimetrica porque aRb,abbRa\displaystyle aRb,a\neq b\Rightarrow bRa. Por ultimo, no es simetrica porque aRb\displaystyle aRb y bRc\displaystyle bRc pero aRc\displaystyle a\cancel{R}c.

  •  

    R3={(a,b),(c,d),(d,c)}\displaystyle R_{3}=\{(a,b),(c,d),(d,c)\}.

    No es reflexiva. Contraejemplo: aRa\displaystyle a\cancel{R}a. No es simetrica porque aRb\displaystyle aRb pero bRa\displaystyle b\cancel{R}a. No es antisimetrica porque cRd\displaystyle cRd y dRc\displaystyle dRc y dc\displaystyle d\neq c. No es transitiva porque cRd\displaystyle cRd y dRc\displaystyle dRc pero cRc\displaystyle c\cancel{R}c.

  •  

    R4=A×A\displaystyle R_{4}=A\times A.

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

    Es una relacion de equivalencia.

  •  

    R5=\displaystyle R_{5}=\varnothing.

    No es reflexiva, aRa\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.

  •  

    R6={(x,y)x=y}={(a,a),(b,b),(c,c),(d,d)}\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 (xRy,yRxx=y\displaystyle xRy,yRx\Rightarrow x=y). Tambien es transitiva, ya que no hay ningun contraejemplo (xRy,yRz\displaystyle xRy,yRz solo puede pasar si x=y=z\displaystyle x=y=z).

    R6\displaystyle R_{6} es una relacion de equivalencia y de orden. No es de orden total porque aRb\displaystyle a\cancel{R}b y bRa\displaystyle b\cancel{R}a.

  •  

    R7=R6{(a,b),(b,a),(c,d),(d,c)}\displaystyle R_{7}=R_{6}\cup\{(a,b),(b,a),(c,d),(d,c)\}.

    Es reflexiva porque estan los pares de R6\displaystyle R_{6} (es decir, R6R7\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 aRb,bRa\displaystyle aRb,bRa. Es transitiva pues no se pueden encontrar contraejemplos.

    R7\displaystyle R_{7} es de equivalencia. No es de orden y, por tanto, tampoco de orden total.

  •  

    R8={(x,y)x va antes que y en el alfabeto}\displaystyle R_{8}=\{(x,y)\mid x\text{ va antes que }y\text{ en el alfabeto}\}

    No es reflexiva. No es simetrica (aRb\displaystyle aRb y bRa\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 A\displaystyle A es el alfabeto español. |A|=27\displaystyle|A|=27 y R8\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 (αR8β\displaystyle\alpha R_{8}\beta) entonces β\displaystyle\beta no va antes que α\displaystyle\alpha, luego (βR8α)\displaystyle(\beta\cancel{R}_{8}\alpha). Entonces es antisimetrica.

  •  

    R9=R6R8={(α,β)α va antes que β o α=β}\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 R6\displaystyle R_{6}. No es simetrica porque aRb\displaystyle aRb pero bRa\displaystyle b\cancel{R}a.

    Es antisimetrica: vamos a usar la definicion αR9β,βR9αα=β\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.

    R9\displaystyle R_{9} es de orden. Tambien es de orden total porque todos los elementos estan relacionados.

  •  

    R10=R6{(a,b),(c,d)}\displaystyle R_{10}=R_{6}\cup\{(a,b),(c,d)\}

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

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

Ejemplo.

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

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

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

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

Luego R\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:

{B1,B2}\displaystyle\displaystyle\{B_{1},B_{2}\} =[B2]\displaystyle\displaystyle=[B_{2}]
{B3,B4,B5}\displaystyle\displaystyle\{B_{3},B_{4},B_{5}\} =[B3]\displaystyle\displaystyle=[B_{3}]
{B6,B7,B8,B9}\displaystyle\displaystyle\{B_{6},B_{7},B_{8},B_{9}\} =[B8]\displaystyle\displaystyle=[B_{8}]

B2\displaystyle B_{2}, B3\displaystyle B_{3} y B8\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 A/R={[B2],[B3],[B8]}\displaystyle A/R=\{[B_{2}],[B_{3}],[B_{8}]\}.

Definición 2.8 (Clase de equivalencia).

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

[a]R{bAaRb}\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 R\displaystyle R, omitiremos el subindice y escribiremos [a]\displaystyle[a]. Tambien se puede escribir a¯\displaystyle\overline{a}.

Definición 2.9 (Conjunto cociente).

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

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

R4=A×A\displaystyle R_{4}=A\times A.

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

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

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

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

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

En este caso, [a]R6={a},[b]R6={b},[c]R6={c},[d]R6={d}\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:

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

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

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

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

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

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

Proposición 2.1.

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

  •  

    aRb[a]=[b]\displaystyle aRb\Rightarrow[a]=[b].

  •  

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

Demostración.

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

  •  

    Si aRb\displaystyle aRb:

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

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

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

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

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

    Como aRb\displaystyle aRb y R\displaystyle R es transitiva, aRxx[a]\displaystyle aRx\Rightarrow x\in[a].

  •  

    Si aRb\displaystyle a\cancel{R}b:

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

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

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

Definición 2.10 (Conjuntos disjuntos).

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

Definición 2.11 (Partición).

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

  •  

    Son disjuntos dos a dos: dos conjuntos diferentes cualesquiera de la coleccion son disjuntos.

  •  

    Recubren A\displaystyle A: la union de todos ellos es A\displaystyle A.

Teorema 2.1.

Sea R\displaystyle R una relacion de equivalencia en un conjunto A\displaystyle A. Entonces las clases de equivalencia de R\displaystyle R constituyen una particion de A\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 A\displaystyle A.

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

Luego todo elemento pertenece a una clase de equivalencia. ∎

Ejemplo.

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

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

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

Entonces [a]={a},[b]={b,d},[c]={c}\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 A\displaystyle A. Definimos una relacion R\displaystyle R en A\displaystyle A de la siguiente forma:

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

Entonces la relacion R\displaystyle R es de equivalencia.

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

Demostración.

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

  •  

    R\displaystyle R es reflexiva?

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

  •  

    R\displaystyle R es simetrica?

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

    Por tanto, R\displaystyle R es simetrica.

  •  

    R\displaystyle R es transitiva?

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

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

[a]R={baRb}={ba y b estan en el mismo conjunto de particion}\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 a\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 1+7+6+1=15\displaystyle 1+7+6+1=15 relaciones de equivalencia distintas en A\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 F={aba,b,b0}\displaystyle F=\left\{\frac{a}{b}\mid a,b\in\mathbb{Z},b\neq 0\right\}:

    En el conjunto F\displaystyle F de fracciones vamos a definir una relacion R\displaystyle R tal que

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

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

    • R\displaystyle R reflexiva: a,b\displaystyle\forall a,b se cumple

      abRab\displaystyle\frac{a}{b}R\frac{a}{b}

    • Simetrica: abcd\displaystyle\forall\frac{a}{b}\cdot\frac{c}{d}

      cdRabcb=adabRcd\displaystyle\frac{c}{d}R\frac{a}{b}\Rightarrow cb=ad\Rightarrow\frac{a}{b}R% \frac{c}{d}

    • Transitiva: abcdef\displaystyle\forall\frac{a}{b}\cdot\frac{c}{d}\cdot\frac{e}{f}

      abRcd,cdRefabRef?\displaystyle\frac{a}{b}R\frac{c}{d},\frac{c}{d}R\frac{e}{f}\Rightarrow\frac{a% }{b}R\frac{e}{f}?

      abRcdad=cb\displaystyle\frac{a}{b}R\frac{c}{d}\Rightarrow ad=cb, cdRefcf=de\displaystyle\frac{c}{d}R\frac{e}{f}\Rightarrow cf=de

      Debemos llegar a que af=eb\displaystyle af=eb

      adf=cbfadf=debadf=cbf\Rightarrow adf=deb

      Como d es un denominador, implica que d0\displaystyle d\neq 0 y puedo dividir ambos enteros entre d\displaystyle d af=eb\displaystyle\Rightarrow af=eb.

    Luego la relacion R\displaystyle R es de equivalencia. Como son las clases?

    Por ejemplo:

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

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

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

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

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

    Obs: |Q|=\displaystyle|Q|=\infty.

  •  

    Enteros modulo 2.

    A=\displaystyle A=\mathbb{Z}. Dados x,y\displaystyle x,y\in\mathbb{Z}, xRyxy\displaystyle xRy\Leftrightarrow x-y es par. Es decir, k\displaystyle\exists k\in\mathbb{Z} tal que xy=2k\displaystyle x-y=2k (xy mod 2\displaystyle x\equiv y\text{ mod }2) (x\displaystyle x congruente con y\displaystyle y modulo 2).

    Veamos si esta relacion es de equivalencia:

    • Reflexiva: x,xx mod 2?\displaystyle\forall x\in\mathbb{Z},\;x\equiv x\text{ mod }2?

      Si porque xx=20=0\displaystyle x-x=2\cdot 0=0

    • Simetrica: x,y,xy mod 2yx mod 2?\displaystyle\forall x,y\in\mathbb{Z},\;x\equiv y\text{ mod }2\Rightarrow y% \equiv x\text{ mod }2?

      Si xy mod 2k\displaystyle x\equiv y\text{ mod }2\Rightarrow\exists k\in\mathbb{Z} tal que xy=2kyx=2(k)yx mod 2\displaystyle x-y=2k\Rightarrow y-x=2(-k)\Rightarrow y\equiv x\text{ mod }2.

    • Transitiva: x,y,z,xy mod 2,yz mod 2xz mod 2?\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?

      xy mod 2\displaystyle x\equiv y\text{ mod }2 k/xy=2k\displaystyle\Rightarrow\exists k\in\mathbb{Z}/x-y=2k

      yz mod 2m/yz=2m\displaystyle y\equiv z\text{ mod }2\Rightarrow\exists m\in\mathbb{Z}/y-z=2m.

      Sumando xy+yz=2k+2mxz=2(k+m)\displaystyle x-y+y-z=2k+2m\Rightarrow x-z=2(k+m). Por tanto xz mod 2\displaystyle x\equiv z\text{ mod }2.

    Hemos visto que la congruencia modulo 2 es una relacion de equivalencia.

    Ejemplos de enteros relacionados: 86 mod 2\displaystyle 8\equiv 6\text{ mod 2}, 37 mod 2\displaystyle 3\equiv 7\text{ mod }2, 44 mod 2\displaystyle 4\equiv 4\text{ mod }2.

    Clases de equivalencia:

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

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

    Luego hay 2 clases y /mod 2={[0],[1]}=2\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 𝒫(A),\displaystyle\mathcal{{P}}(A), siendo A\displaystyle A un conjunto (orden parcial si |A|2\displaystyle|A|\geq 2, orden total si |A|=1\displaystyle|A|=1 o A=\displaystyle A=\varnothing).

Definición 2.13.

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