Is this relation antisymmetric?

Question

3) Let S={0,1,2,4,6}. Test the following binary relation on S for reflexivity, symmetry, antisymmetry, and transitivity:

R={(0,0),(1,1),(2,2),(4,4),(6,6),(0,1),(1,2),(2,4),(4,6)}

Don't worry about the other questions, just antisymmetry please. I'm taking an online class, and even though about half of the students have said it is, half of us have said it isn't and the professor hasn't commented on either.

The way I'm understanding it is that if there is even one element that doesn't satisfy antisymmetry than it is not antisymmetric. Other students are saying exactly the opposite, that you only need one element for antisymmetry, so (0,0) or (1,1) or (2,2) etc would make it antisymmetric. Perhaps I don't have a good enough grasp on antisymmetry in the first place but I've read our text and discussions on here about antisymmetry, but still having trouble.

Would appreciate any guidance. Thanks!

Answer 1

Antisymmetry says that if $\langle a,b\rangle\in R$ and $\langle b,a\rangle\in R$, then $a=b$. In other words, it says that there do not exist two distinct elements $a$ and $b$ such that $\langle a,b\rangle$ and $\langle b,a\rangle$ are both in $R$. Thus, whether pairs like $\langle a,a\rangle$ are in $R$ is irrelevant to the question of whether $R$ is antisymmetric.

Your relation is antisymmetric: the only elements that appear are $0,1,2,4$, and $6$, and no matter which two different ones you choose, at most one of the possible ordered pairs belongs to $R$. For instance, $\langle 0,1\rangle\in R$, but $\langle 1,0\rangle\notin R$. In the case of $1$ and $4$, neither $\langle 1,4\rangle$ nor $\langle 4,1\rangle$ is in $R$.

Answer 2

Hints. The relation $\leq$, with the usual meaning, is anti-symmetric. A subset of an anti-symmetric relation is also anti-symmetric.

Alternatively, partial and total orders are anti-symmetric. (This doesn't immediately help you because the relation isn't...well, it should be clear if you think about it why this doesn't directly help you, but understanding why partial and total orders are anti-symmetric may help you with this problem.)

Answer 3

Antisymmetry is the property that: $$\forall x\,\forall y\; \Big(\big((\langle x,y\rangle\in R)\wedge (\langle y,x\rangle\in R)\big) \to (x=y)\Big)$$

This can also be expressed by the countapositive: $$\forall x\,\forall y\; \Big((x\neq y)\to \big((\langle x,y\rangle\notin R)\vee (\langle y,x\rangle\notin R)\big)\Big)$$

Both of which are equivalent to: $$\neg\exists x\exists y\;\Big((x\neq y)\wedge (\langle x,y\rangle\in R)\wedge (\langle y,x\rangle\in R)\Big)$$

So, to claim antisymmetry it is necessary and sufficient to establish that there is no counterexample of two distinct entities that are symmetrically related.