2
$\begingroup$

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]

Thanks in advance.

$\endgroup$
4
  • 1
    $\begingroup$ 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$. $\endgroup$ – Brian M. Scott Apr 19 '13 at 7:37
  • $\begingroup$ 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”:" $\endgroup$ – Xrave Apr 19 '13 at 7:44
  • $\begingroup$ @Xrave: The following is true when the relation $R$ is defined on a set $A$. $\endgroup$ – Mikasa Apr 19 '13 at 7:49
  • $\begingroup$ Okay; I think I see what they’re getting at. I’ll write up an answer. $\endgroup$ – Brian M. Scott Apr 19 '13 at 7:57
1
$\begingroup$

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.

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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