Definición 3.3.1
Sea \(\mathcal{R}\) una relación en \(A\text{.}\) Se dice que \(\mathcal{R}\) es una relación de equivalencia en \(A\) si y sólo si \(\mathcal{R}\) es refleja, simétrica y transitiva.
Sección 3.3 Relación de Equivalencia
¶Ejemplo 3.3.2
Sea \(n\in\mathbb{N}\text{,}\) se define en \(\mathbb{Z}\)
\begin{equation*}
x\mathcal{R}y \Leftrightarrow x-y=\overset{.}{n}.
\end{equation*}
Demuestre que \(\mathcal{R}\) es una relación de equivalencia.
-
Refleja: \((\forall x\in\mathbb{Z})(x\mathcal{R}x)\text{,}\) donde
\begin{equation*} x\mathcal{R}x\Leftrightarrow x-x=0=\overset{.}{n}=0n, \end{equation*}por lo tanto se cumple la proposición.
-
Simétrica: \((\forall x,y\in\mathbb{Z})(x\mathcal{R}y\Rightarrow y\mathcal{R}x)\text{,}\) es decir,
\begin{equation*} x-y=\overset{.}{n}\Rightarrow y-x=\overset{.}{n}, \end{equation*}suponemos que se cumple que \(x\mathcal{R}y\text{,}\) entonces
\begin{equation*} \begin{array}{rl} x\mathcal{R}y \amp \Leftrightarrow x-y=\overset{.}{n}\\ \amp \Leftrightarrow x-y=nk\quad(k\in\mathbb{Z})\\ \amp \Leftrightarrow-(x-y)=-nk\\ \amp \Leftrightarrow y-x=n(-k)\quad(-k\in\mathbb{Z})\\ \amp \Leftrightarrow y-x=\overset{.}{n}\\ \amp \Leftrightarrow y\mathcal{R}x. \end{array} \end{equation*}Luego es simétrica
-
Transitiva: \((\forall x,y,z\in\mathbb{Z})[(x\mathcal{R}y\wedge y\mathcal{R}z)\Rightarrow x\mathcal{R}z]\text{.}\)
Suponemos que se cumple que \(x\mathcal{R}y\wedge y\mathcal{R}z\text{,}\) es decir:
\begin{equation*} x-y=\overset{.}{n}\wedge y-z=\overset{.}{n}, \end{equation*}si sumamos las dos expresiones se obtiene
\begin{equation*} \begin{array}{rl} (x-y)+(y-z) \amp =\overset{.}{n}+\overset{.}{n}\\ x-z \amp =nk_{0}+nk_{1}\\ x-z \amp =n(k_{0}+k_{1})\\ x-z \amp =nk_{2}\\ x-z \amp =\overset{.}{n}, \end{array} \end{equation*}luego \(x\mathcal{R}z\text{,}\) por ello es transitiva.
De este modo, tenemos que \(\mathcal{R}\) es una relación de equivalencia en \(\mathbb{Z}\text{.}\)
Subsección Ejercicios
Se define en \(\mathbb{R}\) la relación
\begin{equation*}
x\mathcal{R}y\Leftrightarrow(\exists k\in\mathbb{Z})(x-y=k).
\end{equation*}
Demuestre que \(\mathcal{R}\) es una relación de equivalencia en \(\mathbb{R}\text{.}\)
Subsección Ejercicios
Se define en \(\mathbb{Z}\) la relación
\begin{equation*}
x\mathcal{R}y\Leftrightarrow(\exists k\in\mathbb{N})(x=yk^{2}).
\end{equation*}
Determinar si \(\mathcal{R}\) es una relación de equivalencia.
Definición 3.3.3
Sea \(\mathcal{R}\) una relación de equivalencia en \(A\text{.}\) Para todo \(x\in A\) se define la clase de equivalencia de \(x\) modulo \(\mathcal{R}\) al conjunto
\begin{equation*}
\mathcal{R}(x)=\{y\in A\mid x\mathcal{R}y\}.
\end{equation*}
Proposición 3.3.4
Sea \(\mathcal{R}\) una relación de equivalencia en \(A\text{,}\) entonces se cumple
- \((\forall x,y\in A)(x\mathcal{R}y\Leftrightarrow\mathcal{R}(x)=\mathcal{R}(y))\)
- \((\forall x,y\in A)(x\diagup\!\!\!\!\mathcal{R}y\Leftrightarrow\mathcal{R}(x)\not =\mathcal{R} (y))\)
- \((\forall x,y\in A)(x\diagup\!\!\!\!\mathcal{R}y \Leftrightarrow \mathcal{R}(x)\cap\mathcal{R}(y)=\phi)\)
Definición 3.3.5
Sea \(\mathcal{R}\) una relación de equivalencia en \(A\text{.}\) Se define el conjunto cuociente de \(A\) por \(\mathcal{R}\) al conjunto de las clases de equivalencia
\begin{equation*}
A\diagup\mathcal{R}=\{\mathcal{R}(x)\mid x\in A\}
\end{equation*}
Ejemplo 3.3.6
Sean \(x,y\in J_{8}= \{0,1,2,3,4,5,6,7,8\}\text{,}\) y la relación de equivalencia
\begin{equation*}
x\mathcal{R}y\Leftrightarrow x-y=\overset{.}{3},
\end{equation*}
Encontraremos las clases de equivalencias para los elementos de \(J_{8}\text{.}\)
- \begin{equation*} \begin{array}{rl} \mathcal{R}(0) \amp =\{y\in J_{8}\mid0\mathcal{R}y\}\\ \amp =\{y\in J_{8}\mid0-y=\overset{.}{3}\}\\ \amp =\{0,3,6\}. \end{array} \end{equation*}
- \begin{equation*} \begin{array}{rl} \mathcal{R}(1) \amp =\{y\in J_{8}\mid1\mathcal{R}y\}\\ \amp =\{y\in J_{8}\mid1-y=\overset{.}{3}\}\\ \amp =\{1,4,7\}. \end{array} \end{equation*}
- \begin{equation*} \begin{array}{rl} \mathcal{R}(2) \amp =\{y\in J_{8}\mid2\mathcal{R}y\}\\ \amp =\{y\in J_{8}\mid2-y=\overset{.}{3}\}\\ \amp =\{2,5,8\}. \end{array} \end{equation*}
Luego concluimos que
\(\mathcal{R}(0)=\mathcal{R}(3)=\mathcal{R}(6)\text{,}\)
\(\mathcal{R}(1)=\mathcal{R}(4)=\mathcal{R}(7)\text{,}\)
\(\mathcal{R}(2)=\mathcal{R}(5)=\mathcal{R}(8)\text{.}\)
Así obtenemos que el conjunto cuociente esta dado por
\begin{equation*}
J_{8}\diagup\mathcal{R}=\{\{0,3,6\},\{1,4,7\},\{2,5,8\}\}.
\end{equation*}
Subsección Ejercicios
Sean \(x,y\in\mathbb{Z}\text{,}\) donde
\begin{equation*}
x\mathcal{R}y\Leftrightarrow x-y=\overset{.}{3}.
\end{equation*}
\(\mathcal{R}\) es una relación de equivalencia. Determinar \(\mathcal{R} (0),\mathcal{R}(1)\) y \(\mathcal{R}(2)\text{.}\)
Recordemos el Algoritmo de la División que dice lo siguiente
Sean \(a,b\in\mathbb{Z}\text{,}\) entonces existen \(d,r\in\mathbb{Z}\) tales que
\begin{equation*}
a= bd+ r,\quad0\leq r\lt b
\end{equation*}
Definición 3.3.7
Sea \(\mathcal{R}\) una relación de equivalencia en \(A\text{,}\) y \(S \subseteq A\text{.}\)
Se dice que \(S\) es un Sistema de Representante de la relación de equivalencia \(\mathcal{R}\) si y sólo si
- \((\forall x,y \in S)(x\neq y \Rightarrow \mathcal{R}(x)\neq \mathcal{R}(y))\)
- \((\forall x \in A)(\exists y \in S)(x \mathcal{R} y)\)
En el ejemplo anterior habíamos obtenido que
\begin{equation*}
J_{8}\diagup\mathcal{R}=\{\{0,3,6\},\{1,4,7\},\{2,5,8\}\}.
\end{equation*}
En este caso, podemos comprobar que
\(S_1=\{0,1,2 \}\) es un sistema de representante,
\(S_1=\{3,7,2 \}\) es un sistema de representante,
\(S_1=\{0,1 \}\) no es un sistema de representante,
\(S_1=\{0,1,5,8 \}\) no es un sistema de representante,
Teorema 3.3.8
Sea \(\mathcal{R}\) una relación de equivalencia en \(A\text{,}\) entonces
\begin{equation*}
A=\underset{x\in A\diagup\mathcal{R}}{\overset{.}{\cup}}\mathcal{R}(x),
\end{equation*}
es decir \(A\diagup\mathcal{R}\) es una partición de \(A\text{.}\)
En el ejemplo anterior teníamos en \(J_{8}\) las clases \(\mathcal{R} (0),\mathcal{R}(1)\) y \(\mathcal{R}(2)\text{,}\) luego
\begin{equation*}
J_{8}\diagup\mathcal{R}=\{\mathcal{R}(0),\mathcal{R}(1),\mathcal{R}
(2)\}=\{\{0,3,6\},\{1,4,7\},\{2,5,8\}\},
\end{equation*}
por lo tanto
\begin{equation*}
J_{8}=\{0,3,6\}\overset{.}{\cup}\{1,4,7\}\overset{.}{\cup}\{2,5,8\},
\end{equation*}
es decir \(J_{8}\) es la unión disjunta de las tres clases de equivalencia.
Teorema 3.3.9
Sea \(A\) un conjunto y \(C\) una partición de \(A\) \((A=\underset{B\in C}{\overset{.}{\cup}}B)\text{,}\) entonces se define la relación en \(A\) dada por
\begin{equation*}
x\mathcal{R}y\Leftrightarrow(\exists B\in C)(x,y\in B),
\end{equation*}
esta es una relación de equivalencia en \(A\) y \(A\diagup\mathcal{R}=C\text{.}\)
Entero Módulo \(n\text{.}\)
Recordemos que
\begin{equation*}
x\mathcal{R} y \Leftrightarrow x-y= \overset{.}{n},
\end{equation*}
es una relación de equivalencia en \(\mathbb{Z}\text{,}\) luego la clase de un elemento \(x\) esta dado por
\begin{equation*}
\begin{array}{rl}
\mathcal{R}(x) \amp = \{y\in\mathbb{Z} \mid x-y=\overset{.}{n}\}\\
\amp = \{y\in\mathbb{Z} \mid-y= \overset{.}{n}-x\}\\
\amp = \{y\in\mathbb{Z} \mid y= \overset{.}{n}+x\}
\end{array}
\end{equation*}
luego
\begin{equation*}
\mathbb{Z}/\mathcal{R}= \{\mathcal{R}(0), \mathcal{R}(1), \ldots,
\mathcal{R}(n-1) \},
\end{equation*}
es decir, un sistema de representante de la relación de equivalencia es \(\{0,1,2,\ldots, n-1\}\text{,}\) de donde se obtiene que \(\#(\mathbb{Z}/\mathcal{R})= n\text{.}\)
Notación: Para la relación dada anteriormente establecemos una notación particular, dada por:
\(\mathbb{Z}\diagup\mathcal{R}=\mathbb{Z}_{n}\text{.}\)
\(\mathcal{R}(a)=\overline{a}\text{,}\) denotando la clase de \(a\text{.}\)
\(a\mathcal{R}b\Leftrightarrow a\equiv b\quad (n)\text{,}\) se lee \(a\) es congruente con \(b\) módulo \(n\text{.}\)
Ejemplo 3.3.10
Para \(n=4\) tenemos que \(\mathbb{Z}_{4}=\{\overline{0},\overline{1},\overline{2},\overline{3}\}\text{,}\) ya que todo elemento al dividir por \(4\) obtenemos resto un numero entre \(0\) y \(3\text{.}\)
Proposición 3.3.11
Sean \(x,y,z,w\in\mathbb{Z}\) y \(n\in\mathbb{N}\text{,}\) tales que
\begin{equation*}
x\equiv y\quad (n)\quad\wedge\quad z\equiv w\quad (n).
\end{equation*}
Entonces
- \(x+z \equiv w+y\quad(n).\)
- \(xz \equiv wy\quad(n).\)
Demostración
Sean \(x,y,z,w\in\mathbb{Z}\) tal que \(x\equiv y(n)\quad\wedge\quad z\equiv w(n).\) Luego tenemos que
\begin{equation*}
\begin{array}{rcl}
x-y \amp =\amp \overset{.}{n} \\
z-w \amp =\amp \overset{.}{n}
\end{array}
\end{equation*}
Sumando las dos ecuaciones tenemos que
\begin{equation*}
\begin{array}{rcl}
x-y+z-w \amp =\amp \overset{.}{n} \\
(x+z)-(y+w) \amp =\amp \overset{.}{n}
\end{array}
\end{equation*}
Así obtenemos la primera igualdad.
\begin{equation*}
x+z \equiv w+y\quad(n).
\end{equation*}
Para la segunda amplificamos las ecuaciones por \(z\) la primera y por \(y\) la segunda sumando obtenemos
\begin{equation*}
\begin{array}{rcl}
z(x-y)+y(z-w) \amp =\amp \overset{.}{n} \\
(xz)-(yw) \amp =\amp \overset{.}{n}
\end{array}
\end{equation*}
Lo cual demuestra la proposición.
Definición 3.3.12
Sean \(\overline{x},\overline{y}\in\mathbb{Z}_{n}\text{,}\) se define
- \(\overline{x}+\overline{y}=\overline{x+y}.\)
- \(\overline{x}\cdot\overline{y}=\overline{xy}.\)
Ejemplo 3.3.13
En \(\mathbb{Z}_{7}\)se tiene que
- \(\overline{3}\cdot\overline{4}=\overline{12}=\overline{5}.\)
- \(\overline{2}\cdot\overline{5}=\overline{10}=\overline{3}.\)
- \(\overline{3}\cdot\overline{4}+\overline{2}\cdot\overline{6}=\overline {12}+\overline{12}=\overline{24}=\overline{3}.\)
Proposición 3.3.14
La suma cumple:
-
Asociatividad: Dado \(\overline{x} , \overline{y}, \overline{z} \in \mathbb{Z}_n\) entonces
\begin{equation*} (\overline{x}+\overline{y})+\overline{z}=\overline{x}+(\overline{y} +\overline{z}) \end{equation*} -
Neutro: Dado \(\overline{x} \in \mathbb{Z}_n \) entonces
\begin{equation*} \overline{x}+ \overline{0}= \overline{0}+ \overline{x}= \overline{x} \end{equation*} -
Inverso: Dado \(\overline{x} \in \mathbb{Z}_n \) entonces
\begin{equation*} \overline{x}+ \overline{-x}= \overline{-x}+ \overline{x}= \overline{0} \end{equation*} -
Conmutatividad: Dado \(\overline{x} , \overline{y} \in \mathbb{Z}_n\) entonces
\begin{equation*} \overline{x}+ \overline{y}=\overline{y}+ \overline{x}. \end{equation*}
Proposición 3.3.15
La multiplicación cumple:
-
Asociatividad: Dado \(\overline{x} , \overline{y}, \overline{z} \in \mathbb{Z}_n\) entonces
\begin{equation*} (\overline{x}\cdot\overline{y})\cdot\overline{z}=\overline{x}\cdot(\overline{y} \cdot\overline{z}) \end{equation*} -
Neutro: Dado \(\overline{x} \in \mathbb{Z}_n \) entonces
\begin{equation*} \overline{x}\cdot \overline{1}= \overline{1}\cdot \overline{x}= \overline{x} \end{equation*} -
Conmutatividad: Dado \(\overline{x} , \overline{y} \in \mathbb{Z}_n\) entonces
\begin{equation*} \overline{x}\cdot \overline{y}=\overline{y}\cdot \overline{x}. \end{equation*}Además
-
Distributividad: Dado \(\overline{x} , \overline{y}, \overline{z} \in \mathbb{Z}_n\) entonces
\begin{equation*} \overline{x}\cdot(\overline{y}+\overline{z})=\overline{x}\cdot\overline{y} + \overline{x}\cdot\overline{z}) \end{equation*}