# What is $D$ in $G \cap G^{-1} \subseteq D$?

My book has an example that goes like this:

$$A = \{1,2,3,4\}$$ $$R = (G,A,A)$$ Prove that $R$ is antisymmetric if and only if $G \cap G^{-1} \subseteq D$

We have to prove two implications. The first one being "supposing that $R$ is antisymmetric, prove that $G \cap G^{-1} \subseteq D$ occurs". So here it goes:

$$(a,b) \in G \cap G^{-1} \implies (a,b) \in G \land (a,b) \in G^{-1}$$ $$\implies aRb \land aR^{-1}b \implies aRb \land bRa$$

Since $aRb \land bRa$, using our hypothesis that $R$ is antisymmetric, we can say that $a = b$. Therefore, $(a,b) \in D$

There are two things I don't entirely understand in this proof:

• What is $D$? Is it an arbitrary set or something else I'm missing?
• How exactly can proving that $a = b$ imply that $(a,b) \in D$?
-

It seems that $D$ is the "diagonal", $$D=\{(x,x)\mid x\in A\}.$$ Thus $a=b$ and $(a,b)\in D$ are just different wordings for the same thing.

-

$D$ is the diagonal of $A\times A$, meaning that $D=\{\langle a,a\rangle:a\in A\}$. This picture may help to explain the terminology. The square represents the Cartesian product $A\times A$; the points $\langle a,d\rangle$ with the same first and second component are exactly the ones that lie along the diagonal $D$ in the picture.

-

For the forward implication:

Definition: A relation $R$ is antisymmetric on a set $S$ if and only if it satisfies the following property for every $x, y \in S$:

If it is true that $x R y\land y R x$, then it must be that $x = y$.

So...

$a = b$ follows from

• (1) the hypothesis "Assuming $R$ is antisymmetric",
• (2) the definition of an antisymmetric relation, and
• (3) the fact that you have proven that $a R b \land b R a$

Hence, $a = b$, and $a = b \implies (a, b) = (a, a) \in D \implies G\cap G^{-1} \subseteq D$, where $D$ is the diagonal, of $A \times A$ as Brian's answer so aptly shows.

Note: it must also be proven that if $G\cap G^{-1} \subseteq D$, then $R$ is antisymmetric.

-