# Proving symmetry of Relation and Inverse Relation

Why is this a flawed proof?

Knowing that $a$ is an element in $A$ and $b$ is an element in $B$. $R$ being a symmetric binary relation:

“Consider any $a$ and $b$ such that $aRb$.
Since $R$ is symmetric, we have $bRa$.
Since $aRb$ and $bRa$, we have $bR^{−1}a$ and $aR^{−1}b$.
Since our choice of $a$ and $b$ was arbitrary, we have proven that $R^{−1}$ is symmetric.”

There's apparently a flaw with this, but I can't for the life of me figure it out.

[Homework Question]

• Are you sure that $R$ was specified as a subset of $A\times B$, a relation from $A$ to $B$? Normally one doesn’t discuss whether a relation is symmetric unless it is a relation on a single set, $R\subseteq A\times A$. – Brian M. Scott Apr 19 '13 at 7:37
• it wasn't strictly defined. "The following is an incorrect proof for the statement “If a relation R is symmetric, then R^−1 is also symmetric”:" – Xrave Apr 19 '13 at 7:44
• @Xrave: The following is true when the relation $R$ is defined on a set $A$. – Mikasa Apr 19 '13 at 7:49
• Okay; I think I see what they’re getting at. I’ll write up an answer. – Brian M. Scott Apr 19 '13 at 7:57

Apart from the oddity of talking about symmetry in connection with a relation $R\subseteq A\times B$, where $A$ and $B$ may be different, there is a logical flaw in the argument. The assumption is that $R$ is symmetric, and you want to prove from this that $R^{-1}$ is symmetric. That means that you want to show that

$\qquad\qquad\qquad\qquad\qquad$ if $b\in B$, $a\in A$, and $bR^{-1}a$, then $aR^{-1}b$.

That’s what you have to prove, using the assumption that $R$ is symmetric. That means that you should be starting with an arbitrary $b\in B$ and $a\in A$ such that $bR^{-1}a$, not with an arbitrary $a\in A$ and $b\in B$ such that $aRb$. Here’s a correct argument:

Suppose that $b\in B$, $a\in A$, and $bR^{-1}a$; then by definition of $R^{-1}$ we know that $aRb$. $R$ is symmetric, so $bRa$, and using the definition of $R^{-1}$ again we see that $aR^{-1}b$. Since $b\in B$ and $a\in A$ were arbitrary, this shows that $R^{-1}$ is symmetric.

I’m reasonably sure that that’s what they had in mind, but there is, as Babak suggests in his answer, a completely different way to prove the result: prove that a relation $R$ is symmetric if and only if $R=R^{-1}$, and the result that you want here is a trivial consequence. The proof that $R$ is symmetric if and only if $R=R^{-1}$ is pretty straightforward. If $R$ is symmetric, then for any $a\in A$ and $b\in B$,

\begin{align*} \langle a,b\rangle\in R\quad&\text{iff}\quad\langle b,a\rangle\in R&&\text{by symmetry of }R\\ &\text{iff}\quad\langle a,b\rangle\in R^{-1}&&\text{by definition of }R^{-1}\;, \end{align*}

so $R=R^{-1}$, and the reverse implication is essentially the same steps in reverse.

• That was a perfect answer. Thanks so much :) I'll upvote once I get enough reps >_< – Xrave Apr 19 '13 at 8:12
• @Xrave: You’re very welcome; glad it helped. – Brian M. Scott Apr 19 '13 at 8:15

Regarding to neat comment of Brian above, If $R$ is symmetric so $(x,y)\in R$ iff $(y,x)\in R$ iff $(x,y)\in R^{-1}$ so $R=R^{-1}$. Try to show the converse direction as well.

• $x,y\in A$ and I assumed $R\subseteq A\times A$. – Mikasa Apr 19 '13 at 8:02
• Nice, Babak! ;-) – amWhy Apr 20 '13 at 0:26