Equivalence Relations and Inverse Relations

Question

Prove that if $R$ is an equivalence relation on a set $A$, then $R^{-1}$ is also an equivalence relation on $A$.

Solution:

We know that $\forall R\in A$,

$$ R = \{(a, b) | (b, a)\in A\} $$

Similarly, $\forall R^{-1}\in A$,

$$ R^{-1} = \{(b, a) | (a, b)\in A\} $$

So, we can then prove that $R^{-1}$ is an equivalence relation on $A$. In particular, we know

1. For every $R\in A$, $RRR$.
2. If $RRA$, then $ARR$.
3. If $RRA$ and $ARR^{-1}$, then $RRR^{-1}$.

I don't think this really helps though. Someone please tell me the flaw of my proof/logic? Thanks!

Answer 1

What you write does not make much sense to me. $R$ is supposed to be relation on $A$ which means $R\subseteq A\times A$; so it makes no sense to write $R\in A$, as that will almost never happen ($A$ would have to be pretty weird for it to hold, and in any case it would be irrelevant to the fact that $R$ is an equivalence relation). Also, your description of $R$ does not make much sense. And when you write $RRR$, you seem to be trying to establish a relation $R$ with $R$ itself. Frankly, it reads like you are trying to throw symbols at the wall to see if anything sticks.

Let's start over; $R$ is a subset of $A\times A$, and we know that $R$ is: reflexive (so for every $a\in A$, $(a,a)\in R$; symmetric (if $(a,b)\in R$, then $(b,a)\in R$); and transitive (if $(a,b)\in R$ and $(b,c)\in R$, then $(a,c)\in R$). Now let $R^{-1}$ be the relation: $$R^{-1} = \{ (a,b)\in A\times A \mid ( b,a)\in R\}.$$

We want to show that $R^{-1}$ is reflexive, symmetric, and transitive.

• Reflexive: you need to show that for every $a\in A$, $(a,a)\in R^{-1}$. Why is that true? Hint. Remember that for $(a,a)$ to be an element of $R^{-1}$, you need something to be an element of $R$; what?

• Symmetric: you need to show that if $(a,b)\in R^{-1}$, then $(b,a)\in R^{-1}$. Why is that true? Hint: If $(a,b)\in R^{-1}$, then $(b,a)\in R$. In order for $(b,a)$ to be in $R^{-1}$, you need $(a,b)\in R$. Why is that the case?

• Transitive: You need to show that if $(a,b)\in R^{-1}$ and $(b,c)\in R^{-1}$, then $(a,c)\in R^{-1}$. Use the definition of $R^{-1}$ and the fact that $R$ is an equivalence relation to prove this.

Is this a sufficient push in the right direction? If not, please comment and ask follow-up questions.

Answer 2

I’m afraid that none of it makes any sense. If $R$ is an equivalence relation on $A$, $R$ is a subset of $A\times A$, so it can’t possibly be an element of $A$. Let’s look at a very small example. Suppose that $A = \{0,1\}$ and $R = \{(0,0),(1,1)\}$; this $R$ really is an equivalence relation on this $A$, so the example is certainly relevant. (In fact, it’s the relation of equality on $A$.) The elements of $A$ are $0$ and $1$; does $$\{(0,0),(1,1)\}$$ look like either of them?

Your hypothesis is that $R$ is an equivalence relation on $A$. This means, first of all, that it’s a relation on $A$, i.e., a subset of $A\times A$: every member of $R$ is an ordered pair of the form $(a,b)$, where $a$ and $b$ are members of $A$. But it’s not just any old relation on $A$: it’s reflexive, symmetric, and transitive. The first of these means that for every $a \in A$, $(a,a)\in R$. The second means that if $(a,b)\in R$, then $(b,a)\in R$. And the third means that if $(a,b)\in R$ and $(b,c)\in R$, then $(a,c)\in R$.

You want to show that $R^{-1}$ is also an equivalence relation on $A$. So what is $R^{-1}$? By definition $$R^{-1} = \{(b,a):(a,b)\in R\}.$$ (Note that we’re talking about ordered pairs in $R$, not in $A$: they aren’t in $A$.) To show that $R^{-1}$ is an equivalence relation on $A$, you have to show

$\qquad$(1) that $R^{-1}$ is a relation on $A$;
$\qquad$(2) that $R^{-1}$ is reflexive;
$\qquad$(3) that $R^{-1}$ is symmetric; and
$\qquad$(4) that $R^{-1}$ is transitive.

In other words, you have to show

$\qquad$(1) that $R^{-1}\subseteq A\times A$;
$\qquad$(2) that for every $a\in A$, $(a,a)\in R^{-1}$;
$\qquad$(3) that if $(a,b)\in R^{-1}$, then $(b,a)\in R^{-1}$; and
$\qquad$(4) that if $(a,b)\in R^{-1}$ and $(b,c)\in R^{-1}$, then $(a,c)\in R^{-1}$.

In order to do this, you’ll have to use the facts about $R$ that I mentioned in the first paragraph.