0
$\begingroup$

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

3 Answers 3

2

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.

2

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

enter image description here

1

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.