# The closures of a binary relation

I have the following dilemma concerning the equivalence closure of a binary relation.

Let $X$ be a nonempty set and $R\subseteq X\times X$ (i.e., a binary relation over $X$). Consider the following notations:

• $\Delta_{X}=\{(x,x):x\in X\}$
• $R^{=}$ is the reflexive closure of $R$ (i.e., the smallest reflexive relation on $X$ that includes $R$)
• $R^{+}$ is the transitive closure of $R$ (i.e., the smallest transitive relation on $X$ that includes $R$)
• $R^{\sigma}$ is the symmetric closure of $R$ (i.e., the smallest symmetric relation on $X$ that includes $R$)
• $R^{\equiv}$ the equivalence closure of $R$ (i.e., the smallest equivalence relation on $X$ that includes $R$)

I know (i.e., proved) that:

• $R^{=}=R\cup\Delta_{X}$

• $R^{\sigma}=R\cup R^{-1}$

• $R^{+}=\bigcup_{n\geq1}R^{n}$

Starting from here, I wanted to see if the formula $$R^{\equiv}=\bigcup_{n=-\infty}^{\infty}R^{n}%$$ is true (where $R^{0}:=\Delta_{X}$). I have managed to prove that $$\left( \left( R^{+}\right) ^{\sigma}\right) ^{=}=\left( \left( R^{=}\right) ^{+}\right) ^{\sigma}=\left( \left( R^{+}\right) ^{=}\right) ^{\sigma}=\bigcup_{n=-\infty}^{\infty}R^{n}%$$ but when I took the other three permutations of the closures, I obtained only that $$\left( \left( R^{=}\right) ^{\sigma}\right) ^{+}=\left( \left( R^{\sigma}\right) ^{=}\right) ^{+}=\left( \left( R^{\sigma}\right) ^{+}\right) ^{=}\supseteq\bigcup_{n=-\infty}^{\infty}R^{n}.$$

I suspect that actually my formula for $R^{\equiv}$ is wrong and that $\bigcup_{n=-\infty}^{\infty}R^{n}$ is not transitive, meaning that the order of applying the three closures in order to obtain $R^{\equiv}$ is important (probably, the transitivity closure must be applied after the symmetric closure), but I want a confirmation from you. Any insight in this topic is very much appreciated.

Edit (Important): Can you recommend me a good textbook on the subject of binary relations (both elementary and advanced topics)

Edit: To answer a question in the commnents, if $S$ and $R$ are two binary relations on $X$, then the composition of $S$ and $R$ is the binary relation $$S\circ R=\left\{ (x,z)\in X\times X:\text{there exists }y\in X\text{ such that }(x,y)\in R\text{ and }(y,z)\in S\right\} .$$ This is an associative law, hence one can define the powers of $R$ (e.g., by $R^{n+1}=R\circ R^{n}$).

Also, $R^{-n}:=\left( R^{n}\right) ^{-1}=\left( R^{-1}\right) ^{n}$ (where $R^{-1}$ is the inverse of $R$)

-
How exactly do you define $R^n$? – fgp Mar 7 '14 at 21:56
@fgp: I edited the OP in order to answer your question. – digital-Ink Mar 7 '14 at 22:10

Consider $A = \{-1,0,1\}$ and $R \subseteq A^2$ defined as
$$R = \{(0,1),(0,-1)\} \cup \Delta_A$$ that is, $$\stackrel{\curvearrowleft}{-1}\ \leftarrow\ \stackrel{\curvearrowleft}0 \ \rightarrow\ \stackrel{\curvearrowleft}1.$$
Of course, $R^\equiv = A^2$, but $R^k = R$ and $R^{-k} = R^{-1}$ for any $k \in \mathbb{N}$. The problem here is, that $R$ and $R^{-1}$ are separated, namely there is no path $(-1) \rightarrow^* 1$ in $R$, nor $R^{-1}$.
I hope this helps $\ddot\smile$