Relaciones de equivalencia

Un conjunto $R\subset\mbox{$\Sigma^*$}\times\mbox{$\Sigma^*$}$ es una relación (binaria sobre $\mbox{$\Sigma^*$}$).

Escribimos los pares siendo elementos de $R$ como $(x,y)$, o como $x\longrightarrow y$, o como $xRy$.

Sean $R$ y $S$ dos relaciones. Definimos

$$\begin{eqnarray*} RS&=&\{(x,y)\;\vert\;\exists z\in\mbox{$\Sigma^*$}:xRz \mbox{ ... ...^0 &=& \{(x,x)\;\vert\;x\in\mbox{$\Sigma^*$}\}\\ R^{n+1}&=&RR^n \end{eqnarray*}$$

es decir, $R^0$ es la relación de identidad, y la operación nos permite crear nuevas relaciones a partir de dos relaciones dadas, y $R^{n+1}$ es una relación construida de tal manera recursivamente. Con eso definimos:

$$\begin{eqnarray*} R^*&=&\bigcup_{n\ge 0}R^n\\ R^+&=&\bigcup_{n\ge 1}R^n \end{eqnarray*}$$

es decir, $xR^*y$ (o en otra notación $x\longrightarrow ^*y$) si $x=y$ o existe una secuencia $z_1,z_2,\dots,z_n$ con $n\ge 1$ y $xRz_1, z_1Rz_2,\dots, z_nRy$.

Una relación $R$ es

• reflexiva, si $\forall x:xRx$, es decir, la relación de identidad $R^0$ es subrelación de $R$,
• transitiva, si $xRy, yRz \Longrightarrow xRz$, es decir, si los pares $(x,y)$ y $(y,z)$ son elementos de $R$ entonces $(x,z)$ también lo es,
• simétrica, si $\forall x,y: xRy\Longleftrightarrow yRx$, es decir, con $(x,y)$ también $(y,x)$ es elemento de la relación.

Observamos que para $R$

• $R^*$ es una relación reflexiva y transitiva, llamada la clausura reflexiva y transitiva de $R$ (porque es la relación más pequeña con tal propiedad).
• $R^+$ es una relación transitiva, llamada la clausura transitiva de $R$ (porque es la relación más pequeña con tal propiedad).
• $R^+$ es también reflexiva si $R$ ya lo es.
• $R^*$ y $R^+$ son simétricas si $R$ ya lo es.

Una relacion $R$ es una relación de equivalencia si $R$ es reflexiva, simétrica, y transitiva.

Sea $R$ una relación de equivalencia. A cada elemento de $\mbox{$\Sigma^*$}$ podemos asignar el conjunto de los elementos que son equivalentes a él. Basta con anotar un representente de dicho conjunto y escribimos

$$[x]_R=\{y\;\vert\;yRx\}=\{y\;\vert\;xRy\}$$

(si desde el contexto ya conocemos $R$, obviamos del subindice $R$).

Si $xRy$ entonces $[x]=[y]$ porque ambos caen en la misma clase de equivalencia. Se suele usar como representante una de las palabras más cortas de la clase.

Si $x,y\in[z]$ escribimos también $x\equiv y$ que significa que $xRy$ e $yRx$.

Una relación de equivalencia divide $\mbox{$\Sigma^*$}$ en clases, es decir,

$$\mbox{$\Sigma^*$}=[x_1]\cup[x_2]\cup\dots\cup[x_k]\cup\dots$$

cuyo número es finito o infinito. La intersección de dos clases es vacía, es decir, $[x_i]\cap[x_j]=\emptyset$ si $i\not=j$ porque si tuviesen un elemento en común, ambas clases serían iguales.

Ejemplo: Sea $\Sigma=\{\sigma_1,\dots,\sigma_k\}$ un alfabeto (por ejemplo el alfabeto de toda la vida).

La relación

$$R=\{(x,y)\;\vert\;x \mbox{ comienza con el mismo s\'{\i}mbolo que } y\}$$

es una relación de equivalencia y nos divide $\mbox{$\Sigma^*$}$ en

$$\mbox{$\Sigma^*$}=[\sigma_1]\cup[\sigma_2]\cup\dots\cup[\sigma_k]\cup[\epsilon]$$

es decir, en todas las clases de palabras que empiezan con la misma letra más la clase para la palabra vacía (que no empieza con ninguna letra).

Entonces hay tantas clases como símbolos en $\Sigma$ más una clase.

Llamamos el número de clases que produce una relación de equivalencia el índice de la relación $\mathrm{Indice}(R)$.

En el ejemplo tenemos $\mathrm{Indice}(R)=k+1=\vert\Sigma\vert+1$, es decir, un índice finito.