Proving that $R$ is antisymmetric if and only if $G \cap G^{-1} \subseteq D$

Question

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:

---

Proving

$$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?

---

Proving

$$(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.

Answer 1

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$.