Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

1 Answer 1

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}$.

You might want to look at notions of connectivity and strong connectivity in undirected graphs and directed graphs. Relations are basically directed graphs, while symmetric relations are undirected graphs. One special feature is that the graph of strongly connected components forms a dag, which might be of some interesting structure. On the other hand, connected components are just isolated vertices (if some two were connected, they would just merge), these are precisely the equivalence classes.

I hope this helps $\ddot\smile$

share|improve this answer
    
@digital-Ink You didn't accepted my answer (BTW, what kind of insights did you wish for?), so I guess the bounty was applied by the system, not you. I can start another bounty for you, if you want. –  dtldarek Mar 29 at 22:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.