I am unsure of how to prove this. R is an arbitrary relation. $R_1$ is the reflexive closure of the transitive closure while $R_2$ is the transitive closure of the reflexive closure. How would you prove they are equivalent?
If $R$ contains $(a,b)$ and $(b,c)$, and $R'$ contains $(a,c)$, then $R^*$ contains $R\bigcup R'$. This is for the transitive closure. To find the reflexive closure, I would add $(a,a), (b,b), (c,c)$ and it would make $R_1$ right?
$R_2$ would be the same after going through the process of finding the reflexive closure and then the transitive closure of that. However, I do not think I am proving it correctly.
Best Answer
I’ll get you started. I’ll assume that we’re starting with a relation $R$ on a set $A$.
Start by showing that $R_1\subseteq R_2$. Let $\langle a,b\rangle\in R_1$. If $\langle a,b\rangle\in R$, then of course $\langle a,b\rangle\in R_2$, so suppose that $\langle a,b\rangle\in R_1\setminus R$. Then either $a=b$, in which case $\langle a,b\rangle=\langle a,a\rangle\in R_2$, or there is a $c\in A$ such that $\langle a,c\rangle,\langle c,b\rangle\in R$. Clearly $\langle a,c\rangle$ and $\langle c,b\rangle$ are in the reflexive closure of $R$, so $\langle a,b\rangle$ must be in $R_2$. This shows that $R_1\subseteq R_2$.
Then complete the proof by showing that $R_2\subseteq R_1$. Let $\langle a,b\rangle\in R_2$; if $\langle a,b\rangle\in R$, then certainly $\langle a,b\rangle\in R_1$, so suppose that $\langle a,b\rangle\in R_2\setminus R$. Again there are two possibilities: it might be that $a=b$, and $\langle a,b\rangle=\langle a,a\rangle$ was added in forming the reflexive closure of $R$ (and then kept when the transitive closure of that was taken to form $R_2$), or else $a\ne b$, and $\langle a,b\rangle$ was added to the reflexive closure of $R$ when its transitive closure $R_2$ was formed. Show that in both cases $\langle a,b\rangle$ would have been added to $R$ in forming $R_1$, so that $\langle a,b\rangle\in R_1$, and therefore $R_2\subseteq R_1$.