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.

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!

share|improve this question
    
usually, we say that $R$ is a relation on a set $A$ if $R$ is a subset of the cartesian product $A\times A$. Then we say $aRb$ if and only if $(a,b)\in R$. So, I think that in your solution you mean $$R=\{(a,b)|aRb\}.$$ –  leo Oct 1 '11 at 23:46

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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.