I found this relations exercise that I couldn't finish. It involves a set's diagonal. I got it almost done - had trouble wording some parts related to the diagonal.

  • Is the procedure correct?
  • How can I better word the indicated parts?
  • Did it make sense to prove both implications separately?
  • Any kind of feedback is welcome. Still new to this stuff.

If $R = (G,A,A)$ is a relation over $A$, prove that $R$ is antisymmetric if and only if $G \cap G^{-1} \subseteq D$ where $D$ is the diagonal of $A$.

We have to prove that

$$Antisymmetric \iff (G \cap G^{-1} \subseteq D)$$

We have two implications. Let's prove each of them:


$$Antisymmetric \implies (G \cap G^{-1} \subseteq D)$$

Our premise is the fact that the relation is antisymmetric.

We have to prove that $G \cap G^{-1} \subseteq D$.

Have an arbitrary pair of elements $(a,b)$ in $G \cap G^{-1}$:

$$(a,b) \in G \cap G^{-1}$$

$$(a,b) \in G \land (a,b) \in G^{-1}$$

$$aRb \land bRa$$

Since the relation $R$ is antisymmetric:

$$a = b$$

I'm pretty sure that I'm almost done here (because, err... clearly (a,b) belongs to the diagonal...), but I don't know how to word it. Can you advice me here?


$$(G \cap G^{-1} \subseteq D) \implies Antisymmetric$$

Our premise is that $(G \cap G^{-1} \subseteq D)$.

We have to prove that the relation $R$ is antisymmetric.

Basically, we have to prove that

$$(aRb \land bRa) \implies a = b$$

Have arbitrary elements $a$ and $b$:

$$aRb \land bRa$$

Since $aRb$, the pair $(a,b)$ must be in $G$. Similarly, given that $bRa$, I know that $aR^{-1}b$, which means that $(a,b)$ is also in $G^{-1}$:

$$(a,b) \in G \land (a,b) \in G^{-1}$$

$$(a,b) \in G \cap G^{-1}$$

From our premise, we conclude that

$$(a,b) \in D$$

If a pair of elements belongs to a set's diagonal, both elements are the same (again I have problems wording this), so:

$$a = b$$

Effectively proving $(G \cap G^{-1} \subseteq D) \implies Antisymmetric$.

The exercise concludes as both implications were proven.

  • $\begingroup$ what is G and G^-1 (not familiar with these notations) $\endgroup$ – Thomas Nov 3 '13 at 11:30
  • $\begingroup$ @Thomas: $G$ is a set of all pairs $(a,b)$ where $aRb$. $G^{-1}$ is is the same, but for $R^{-1}$. If we grab $G^{-1}$ it would be the same as $G$, but the pairs' elements would be reversed and would be in the form $(b,a)$. $\endgroup$ – Zol Tun Kul Nov 3 '13 at 11:33

It’s wordier than necessary, but I can live with that. :-)

There’s really almost nothing to do, which is perhaps why you’re having trouble. To finish up the first part, after you get $a=b$, just conclude:

Thus, $\langle a,b\rangle=\langle a,a\rangle\in D$.

There’s nothing needed to finish up the second part: it’s immediate from the fact that $\langle a,b\rangle\in D$ that $a=b$, just by the definition of $D$.

  • $\begingroup$ Was it necessary to do both implications? Now that I see them, they look pretty much the same. $\endgroup$ – Zol Tun Kul Nov 3 '13 at 21:50
  • $\begingroup$ @Omega: Logically they’re distinct, so you need to prove both. And the proofs actually are different; they just use the same tools. $\endgroup$ – Brian M. Scott Nov 4 '13 at 3:00

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.