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