Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?
share|improve this question

3 Answers 3

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.

share|improve this answer

$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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.