I have a homework question that asks me to determine determine whether given relations are reflexive, symmetric, anti-symmetric, asymmetric or transitive.

One relation is:

$\rho \subseteq \mathbb \times \mathbb Z$, where $a~\rho~b$ if and only if there is $n \in \mathbb Z$ such that $a = bn$

The answer says it's reflexive and transitive. How come is it not anti-symmetric?

We only find $x~\rho~y$ and $y~\rho~x$ if $x = y$.

like in (1,1) or (2,2).


migrated from cs.stackexchange.com Sep 24 '16 at 9:05

This question came from our site for students, researchers and practitioners of computer science.

  • $\begingroup$ Domain is integers, not natural numbers: $(1,-1)$ as well as $(-1,1)$. $\endgroup$ – Hendrik Jan Sep 23 '16 at 22:52
  • $\begingroup$ thank you this is it! You can put it as an answer (as a counter example that proves anti-symmetry false) @HendrikJan $\endgroup$ – Mina Michael Sep 23 '16 at 22:59

Take $a=0,b=5$. Then $a~\rho~b$ (take $n=0$) and $b~\rho~a$ (take $n=0$). However, $a\neq b$.

Antisymmetry requires that if $a~\rho~b$ and $b~\rho~a$ for some $a,b$, it must hold that $a=b$. Since the antecedent is true in the above example, but the consequent is not, $\rho$ cannot be antisymmetric.

  • $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review $\endgroup$ – Qwerty Sep 24 '16 at 9:30
  • 1
    $\begingroup$ @Qwerty it does provide an answer; it shows why $\rho$ is not antisymmetric by providing a counter argument. I will edit to make that clearer. $\endgroup$ – user63495 Sep 24 '16 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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