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

• reflexiva: $\forall a\in A,\ aRa$,
• simétrica: $\forall a,b\in A,\ aRb \Rightarrow bRa$, y
• transitiva: $\forall a,b,c\in A,\ aRb\&bRc \Rightarrow aRc$.

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

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

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=A² la relación que identifica a cualesquiera dos elementos en A. La única clase de equivalencia es A² 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

$$\forall a_1,a_2\in A:\ a_1 R a_2\Leftrightarrow f(a_1) S f(a_2)$$

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

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

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:

$$\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),$$

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

Proposición 2.8   Sean (S₁,*₁,u₁) y (S₂,*₂,u₂) dos monoides y sea $h:S_1\rightarrow S_2$ un homomorfismo. Entonces $\mbox{\it n\'uc\/}(h)$ es una congruencia en S₁.

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(x₁*₁y₁)=h(x₁)*₂h(y₁)=h(x₂)*₂h(y₂)=h(x₂*₁y₂).

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:

$$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,$$

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

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

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{array}{\vert\vert c\vert cc\vert\vert}\hline\hline *_... ...e{1} & \overline{1} & \overline{0} \\ \hline\hline \end{array}$$

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 (S₁,*₁,u₁) y (S₂,*₂,u₂) dos monoides y sea $h:S_1\rightarrow S_2$ un homomorfismo. h se dice ser

• un monomorfismo si h es inyectiva, es decir, si $\forall s,t\in S_1: h(s)=h(t)\Rightarrow s=t$,
• un epimorfismo si h es suprayectiva, es decir, si $\forall s_2\in S_2\exists s_1\in S_1: h(s_1)=s_2$, y
• un isomorfismo si h es a la vez un monomorfismo y un epimorfismo.

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 S₁ y S₂ 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(S₁) es un submonoide de S₂.

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 S₂=h(S₁)

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 S₁₁ es un submonoide de S₁ entonces h(S₁₁) es un submonoide de S₂ y $S_{11}/\mbox{\it n\'uc\/}(h)$ es un submonoide isomorfo a h(S₁₁).

2.

Si S₂₁ es un submonoide de S₂ entonces $h^{-1}(S_{21})=\{s_1\in S_1\vert h(s_1)\in S_{21}\}$ es un submonoide de S₁ y $h^{-1}(S_{21})/\mbox{\it n\'uc\/}(h)$ es un submonoide isomorfo a S₂₁.

Siguiente: Propiedades de lenguajes Un nivel arriba: Monoide de cadenas Anterior: Homomorfismos