What would be good example of antisymmetry for this relation?

Question

We have set

$X=\{a,b,c,d\}$

and relation

$R=\{(a,a),(a,b),(a,c),(a,d),(b,b),(c,c),(d,b),(d,c),(d,d)\}$.

It is obvious that it is not symmetric and I suppose that it is antisymmetric but I can't come up with some good example to show it.

I know the rule of antisymmetry $xRy \wedge yRx \rightarrow x = y$, but I am not sure how to apply it on this relation.

Answer 1

A single example will not suffice.   You are required to affirm that a counterexample does not exist.

The relation $\rm R$ will not be antisymmetric if you can find any $x,y$ such that $x\neq y$, $x\operatorname{R} y$, and $y\operatorname{R} x$.   Only if you can be definite that there is no such pair can you assert antisymmetry.

This requires an exhaustive check of the elements of $\rm R$.

Answer 2

You can't “give an example” for antisimmetry. You could give an example for failure of antisymmetry.

How can you show this is antisymmetric? Let's stretch it a bit and suppose we have also proved it is transitive. Then it should be an order relation and the pairs tell us that

• $a$ precedes $b$
• $a$ precedes $c$
• $a$ precedes $d$
• $d$ precedes $b$
• $d$ precedes $c$

and no other relation between distinct elements holds. Now we can see that all pairs necessary for the order relation above are indeed present. So the relation $R$ is indeed antisymmetric and transitive.

This is the Hasse diagram for the relation.

Answer 3

You need to exhaustively check through most of $R$. The following algorithm will allow you to determine if it is antisymmetric or not.

---

isAntisymmetric $\leftarrow$ True

for each $(x,y) \in R$:

$\quad$ if $x<y$:

$\quad\quad$ if $(y,x) \in R$: //use that $R$ (in this case) is lexographically ordered to quickly determine this

$\quad\quad\quad$ isAntisymmetric $\leftarrow$ False

return isAntisymmetric