next up previous contents
Siguiente: Propiedades de lenguajes Un nivel arriba: Monoide de cadenas Anterior: Homomorfismos

Relaciones de equivalencia congruentes

En un conjunto A, una relación de equivalencia R es un subconjunto $R\subset A^2$ tal que es Una relación de equivalencia induce una partición de manera natural: Para cada elemento $a\in A$ la clase de equivalencia de a bajo la relación R es el conjunto $[a]_R=\{b\in A\vert aRb\}$ que consta de los elementos equivalentes a a. Se tiene

\begin{eqnarray*}[a]_R\not=[b]_R &\Rightarrow& [a]_R\cap[b]_R=\emptyset \\
\forall b\in A\;\exists a\in A &:& b\in [a]_R
\end{eqnarray*}


Así pues, la colección de clases de equivalencia $A/R=\{[a]_R\vert a\in A\}$ es una partición de A. A/R se dice ser el cociente de A bajo la relación R. La cardinalidad del cociente A/R es el índice de la relación R. La función $\pi_R:a\mapsto [a]_R$, que a cada elemento le asocia su clase de equivalencia, es la proyección canónica de A sobre el cociente A/R. Toda relación de equivalencia induce pues una partición en su conjunto de definición. Recíprocamente, si ${\cal R}$ es una partición en A, es decir, si ${\cal R}$ es una colección de subconjuntos de A tal que

\begin{eqnarray*}\forall R,S\in{\cal R}&:& R\not=S \Rightarrow R\cap S=\emptyset \\
&&A=\bigcup_{R\in{\cal R}}R
\end{eqnarray*}


entonces la relación $\equiv_{\cal R}$ definida como

\begin{displaymath}\forall a,b\in A:a\equiv_{\cal R}b\Leftrightarrow\exists R\in{\cal R}(a,b\in R),\end{displaymath}

es una relación de equivalencia que determina como cociente precisamente a la partición ${\cal R}$. A manera de ejemplos, citemos a las relaciones siguientes en un conjunto $A\not=\emptyset$:
Discreta.
Sea R=(=) la relación que coincide con la identidad en A: $\forall a,b\in A,\ aRb\Leftrightarrow a=b$. Entonces, para toda a, la clase de equivalencia [a] es la mónada cuyo único elemento es a, y el cociente A/R se identifica con A. En este caso, la proyección canónica $\pi$ ``es'' la función identidad.
Tosca.
Sea R=A2 la relación que identifica a cualesquiera dos elementos en A. La única clase de equivalencia es A2 y la proyección canónica $\pi$ es una función constante.
Una manera de introducir relaciones de equivalencia en un conjunto es transportando, mediante funciones, las definidas en otros conjuntos. Si S es una relación de equivalencia en un conjunto B y $f:A\rightarrow B$ es una función con dominio en un conjunto A y contradominio en el conjunto B entonces la relación R en A definida como

\begin{displaymath}\forall a_1,a_2\in A:\ a_1 R a_2\Leftrightarrow f(a_1) S f(a_2)\end{displaymath}

es también una relación de equivalencia. Si S es la identidad en B, entonces diremos que R es el núcleo de la función f, y lo denotaremos $\mbox{\it n\'uc\/}(f)$. Así pues

\begin{displaymath}\mbox{\it n\'uc\/}(f)=\{(a_1,a_2)\in A^2\vert f(a_1)=f(a_2)\}.\end{displaymath}



Ejemplo. Consideremos a $I\!\! R$ con la identidad y sea $A=I\!\! R^2$. La función $f:(x,y)\mapsto x^2+y^2$ tiene como gráfica a un paraboloide de revolución con vértice en el origen. El núcleo de f consta de todas las parejas de puntos equidistantes al origen, y esta relación de equivalencia determina como espacio cociente a la colección de todos los círculos concéntricos con centro en el origen. Para cada punto $\mbox{\bf x}\in I\!\! R^2$, su clase de equivalencia es el círculo que pasa por él y tiene centro en el origen. El índice de la relación de equivalencia es infinito y coincide con la cardinalidad de $I\!\! R$.

Supongamos ahora que (A,*,u) es un monoide. Una relación de equivalencia R en A se dice ser una congruencia si se cumple lo siguiente:

\begin{displaymath}\forall x_1,x_2,y_1,y_2\in A:\ \left(x_1Rx_2\right) \& \left(y_1Ry_2\right)\; \Rightarrow\;\left(x_1*y_1Rx_2*y_2\right),\end{displaymath}

es decir, si ``factores equivalentes dan productos equivalentes''.

Proposición 2.8   Sean (S1,*1,u1) y (S2,*2,u2) dos monoides y sea $h:S_1\rightarrow S_2$ un homomorfismo. Entonces $\mbox{\it n\'uc\/}(h)$ es una congruencia en S1.

En efecto, supongamos que $\left(x_1,x_2\right)\in\mbox{\it n\'uc\/}(h)$ y $\left(y_1,y_2\right)\in\mbox{\it n\'uc\/}(h)$. Hemos de probar que los respectivos productos coinciden, es decir, que $\left(x_1*_1y_1,x_2*_1y_2\right)\in\mbox{\it n\'uc\/}(h)$. Pero esto es inmediato pues

h(x1*1y1)=h(x1)*2h(y1)=h(x2)*2h(y2)=h(x2*1y2).

Observación 2.2   Si (S,*,u) es un monoide y R es una congruencia en S, entonces podemos ``calcar'' la operación * de S en una nueva operación en el cociente S/R de manera que este cociente sea un monoide y la proyección canónica un homomorfismo.

En efecto, para cualesquiera dos clases de equivalencia [a]R,[b]R definamos [a]R*S/R[b]R=[a*b]R. Observamos inmediatamente que
1.
la definición de la operación *S/R no depende de los representantes que se elija en las clases [a]R,[b]R pues R es una congruencia:

\begin{displaymath}a_1\in[a]_R,b_1\in[b]_R\ \Rightarrow\ a_1*b_1\in[a*b]_R\ \Rightarrow\ [a_1*b_1]_R=[a*b]_R,\end{displaymath}

2.
la clase de equivalencia de u, [u]R, es la unidad en el cociente S/R, y
3.
la definición [a]R*S/R[b]R=[a*b]R puede ser reescrita como $\pi_R(a*b)=\pi_R(a)*_{S/R}\pi_R((b)$, lo que a su vez indica que la proyección canónica es, efectivamente, un homomorfismo.


Ejemplos. 1. Se vió que $\mbox{\it long\/}:\Sigma^*\rightarrow I\!\!N$ es un homomorfismo. Dos palabras están en el núcleo de $\mbox{\it long\/}$, llamémoslo R, si y sólo si son de igual longitud. Por tanto, para cada palabra $\sigma$ su clase de equivalencia $[\sigma]_R$ es el conjunto de palabras que tienen la misma longitud que $\sigma$. Si $n=\mbox{\it long\/}(\sigma)$ entonces podemos identificar a la clase $[\sigma]_R$ con el número n. Para dos palabras $\sigma_1,\sigma_2\in\Sigma^*$, con $n_1=\mbox{\it long\/}(\sigma_1)$ y $n_2=\mbox{\it long\/}(\sigma_2)$, tenemos que

\begin{displaymath}n_1*_{\Sigma^*/R}n_2=\mbox{\it long\/}(\sigma_1\sigma_2)=n_1+n_2,\end{displaymath}

es decir, la operación que induce la congruencia coincide con la suma usual de $I\!\!N$. Así pues, podemos identificar naturalmente al monoide $\left(\Sigma^*/R,*_{\Sigma^*/R}\right)$ con el monoide $(I\!\!N,+)$.

2. La función de paridad $\mbox{\it par\/}:(\Sigma^*,\cdot,\mbox{\it nil\/})\rightarrow(Z\!\!\!Z_2,+,0)$ es un homomorfismo. Una pareja de palabras está en el núcleo de $\mbox{\it par\/}$ si y sólo si sus dos componentes son de igual paridad: O bien ambas son de longitud par, o bien ambas son de longitud impar. Escribamos

\begin{eqnarray*}\overline{0} &=& \{\sigma\in\Sigma^*\vert\mbox{\rm la longitud ...
...igma^*\vert\mbox{\rm la longitud de $\sigma$\space es impar}\}.
\end{eqnarray*}


Entonces $\Sigma^*/\mbox{\it n\'uc\/}(\mbox{\it par\/})=\{\overline{0},\overline{1}\}$, por lo que $\mbox{\it n\'uc\/}(\mbox{\it par\/})$ es de índice 2, y la operación que induce la concatenación es, precisamente

\begin{displaymath}\begin{array}{\vert\vert c\vert cc\vert\vert}\hline\hline
*_...
...e{1} & \overline{1} & \overline{0} \\ \hline\hline
\end{array}\end{displaymath}

Así, se identifica $\left(\Sigma^*/\mbox{\it n\'uc\/}(\mbox{\it par\/}),*_{\Sigma^*/\mbox{\it\scriptsize ker\/}(\mbox{\it\scriptsize par\/})}\right)$ con el monoide $(Z\!\!\!Z_2,+)$.

3. Sea n>0 y sea $\mbox{\it suf\/}_n:\Sigma^*\rightarrow\Sigma^*$ el homomorfismo que trunca una palabra para quedarse con el sufijo de longitud a los sumo n. Una pareja de palabras estará en el núcleo de $\mbox{\it suf\/}_n$ sólo si ambas palabras poseen un sufijo común de longitud a lo más n. Así pues hay $\sum_{i=0}^n m^i=\frac{m^{n+1}-1}{m-1}$ clases de equivalencia para la relación $\mbox{\it n\'uc\/}(\mbox{\it suf\/}_n)$, donde m es el número de símbolos en el alfabeto $\Sigma$. La operación que induce la concatenación en el cociente $\Sigma^*/\mbox{\it n\'uc\/}(\mbox{\it suf\/}_n)$ coincide con la operación definida en el monoide $\Sigma^{\leq n}$: Dadas dos palabras, las concatena primero y luego toma el sufijo de longitud n. $\left(\Sigma^*/\mbox{\it n\'uc\/}(\mbox{\it suf\/}_n),*_{\Sigma^*/\mbox{\it\scriptsize ker\/}(\mbox{\it\scriptsize suf\/}_n)}\right)$ se identifica así con el monoide $\Sigma^{\leq n}$.


Sean (S1,*1,u1) y (S2,*2,u2) dos monoides y sea $h:S_1\rightarrow S_2$ un homomorfismo. h se dice ser La imagen de un homomorfismo $h:S_1\rightarrow S_2$ es $h(S_1)=\{s_2\in S_2\vert \exists s_1\in S_1: h(s_1)=s_2\}.$ Escribiremos $S_1\equiv S_2$ para denotar el hecho de que los monoides S1 y S2 son isomorfos, es decir, de que existe un isomorfismo $h:S_1\rightarrow S_2$.

Observación 2.3   Las siguientes relaciones se siguen inmediatamente para un homomorfismo $h:S_1\rightarrow S_2$:
1.
h(S1) es un submonoide de S2.
2.
h es un monomorfismo si y sólo si $\mbox{\it n\'uc\/}(h)=\{(s,s)\vert s\in S_1\}$, es decir, el núcleo de h coincide con la identidad.
3.
h es un epimorfismo si y sólo si S2=h(S1)

Teorema 2.4 (del homomorfismo.)   Para cualquier epimorfismo $h:S_1\rightarrow S_2$ se tiene $S_1/\mbox{\it n\'uc\/}(h) \equiv S_2$.

En efecto, siendo h un homomorfismo, se tiene que $\mbox{\it n\'uc\/}(h)$ es una congruencia. Por tanto, el cociente $S_1/\mbox{\it n\'uc\/}(h)$ posee una estructura de monoide. Consideremos la función $H:S_1/\mbox{\it n\'uc\/}(h) \rightarrow S_2$, $[s]\mapsto h(s)$. Es claro que H está bien definida (es decir, H([s]) no depende del representante que se tome para la clase [s]), y que es un isomorfismo.


Ejemplo. Sea $\Sigma$ un alfabeto y sea $f:\Sigma\rightarrow\Sigma^*$ una función de sustitución. Sea $T=\left(f(s)\right)_{s\in\Sigma}$ el conjunto de palabras correspondientes a símbolos de $\Sigma$ mediante la función f. Sea $f^*:\Sigma^*\rightarrow\Sigma^*$ el homomorfismo que extiende a f. Entonces $f^*(\Sigma^*)=T^*\subset \Sigma^*$. Ahora, una pareja $(\sigma_1,\sigma_2)$ está en el núcleo de f* si y sólo si bajo f* ambas se convierten en una misma palabra de T*. De acuerdo con el Primer Teorema Fundamental de Homomorfismos se tiene $\Sigma^*/\mbox{\it n\'uc\/}(f^*) \equiv T^*$.

Proposición 2.9   Sea $h:S_1\rightarrow S_2$ un homorfismo de monoides. Entonces:
1.
Si S11 es un submonoide de S1 entonces h(S11) es un submonoide de S2 y $S_{11}/\mbox{\it n\'uc\/}(h)$ es un submonoide isomorfo a h(S11).
2.
Si S21 es un submonoide de S2 entonces $h^{-1}(S_{21})=\{s_1\in S_1\vert h(s_1)\in S_{21}\}$ es un submonoide de S1 y $h^{-1}(S_{21})/\mbox{\it n\'uc\/}(h)$ es un submonoide isomorfo a S21.


next up previous contents
Siguiente: Propiedades de lenguajes Un nivel arriba: Monoide de cadenas Anterior: Homomorfismos
Guillermo Morales-Luna
2000-06-27