The domain of relation $D$ is the set of positive integers. For $x, y \in \mathbb Z^+$, $xDy$ if $x$ evenly divides $y.$

I do know this: that a positive integer $x$ evenly divides positive integer $y$ if and only if there is another positive integer $n$ such that $y = xn$.

I'm pretty sure I need to use this definition to prove whether or not relation D is symmetric, anti-symmetric, or neither?

  • 1
    $\begingroup$ What I've learned is that "A relation D on set A is symmetric if an arrow from x to y implies that there is an arrow from y to x." & "A relation D on set A is anti-symmetric if there are no pairs x and y (with x ≠≠ y) in which x and y point to each other." But I am not sure how to apply that idea to this problem. $\endgroup$ – Jigar Patel Jan 11 '18 at 5:27
  • 1
    $\begingroup$ If $x$ divides $y$, when does $y$ divide $x$? $\endgroup$ – Fabio Somenzi Jan 11 '18 at 5:29
  • $\begingroup$ @JigarPatel: Please edit your question to include what you provided in your comment, since it belongs in the question not a comment. Thanks! $\endgroup$ – user21820 Feb 25 '18 at 9:54

Preliminaries: Just to be clear, when I use, e.g. $x \mid y$, that means $x$ divides $y$, (or, alternatively, that $y$ is divisible by $x$

Let's look at symmetry.

Let's pick even integers $x = 2, y=4$, just to test one case. Then $x\mid y,$ (because $2$ divides $4$, since $2\cdot 2 = 4$), but $y$ does not divide $x$ (because there is no positive integer $k$ such that $4k = 2$).

All we need is one counterexample to prove that the relation is not symmetric, because a symmetric relation requires that for all $x, y,\;\;$ if $\;x\mid y,\;\;$ then $\;\;y\mid x$.

We see that doesn't hold $x = 2, y = 4.$ Therefore, it doesn't hold for all $x, y$ such that $x\mid y$. Hence the relation, as noted, is not symmetric.

Let's look at antisymmetry.

Now there are some cases in which $x$ divides $y$, and also $y$ divides $x$. When does that happen?

This relation is antisymmetric if, for all $x, y$, whenever it happens that $x$ divides $y$ AND also $y$ divides $x$, then it must be the case that $x = y$.

So let's suppose it happens that $x$ divides $y$, and $y$ divides $x$.

Then by definition, $y=xn$ and $x = ym$, where $n, m$ are positive integers.

We can substitute $\;y = xn\;$ into the equation $x= ym = (xn)m = nmx.$ Clearly, if $x = xnm,$ then $nm = 1$. And the only way that two positive integers, when multiplied, can equal one is if they are both equal to $1$, i.e. $n=m=1$. In short, we have that $y=x$, and $x=y$. Hence, when $x\mid y$ and $y\mid x$, it follows that $x=y$.

Hence the relation D is, in fact, antisymmetric.


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.