Divisibility relations on $\Bbb N, \Bbb Z^*$, and properties thereof

Question

I have two problems for which I need to find whether it is reflexive, irreflexive, symmetric, antisymmetric, or transitive.

1. The relation $T$ on $\mathbb{N}$ as defined by $$aTb \iff a \mid b$$
2. The relation $U$ on the set $\mathbb{Z}^*$ is defined as $$aUb \iff a \mid b$$

For #1, the way I worked it out was:

• Reflexive: Yes, because $a \mid a$ for any positive integer $a$

• Irreflexive: No, see above

• Symmetry: No, because $a \mid b$ does not necessarily mean $b \mid a$ example, $4 \mid 12$ but $12$ does not divide $4$

• Antisymmetric: Yes, because if $a \mid b$ and $b \mid a$ then $a$ must equal $b$

• Transitive: Yes, because if $a \mid b$ and $b \mid c$ then $a \mid c$

For question #2, however I am lost because the answer is reflexive and transitive.

I get that it is reflexive and transitive and not symmetric for the same reasons as #1 but I don't understand why #2 is not antisymmetric but #1 is. I am guessing that it has something to do with #2 being a relation of $\mathbb{Z}^*$, but that just means a non-zero integer. Can someone help me understand why #1 is antisymmetric and #2 isn't antisymmetric?

Answer 1

It is always best to reference the definitions. Namely, a typical definition is

$$a \mid b \iff \exists k \in \Bbb Z \text{ such that } b = ak$$

Suppose we consider this relation on $\Bbb N$. Let's investigate the properties.

• Reflexivity: Trivially true; take $k=1$.
• Irreflexive: Untrue, as $1 \mid 1$ ($k=1$).
• Symmetry: Untrue. $2 \mid 4$ ($k=2$) but $4 \not \mid 2$ ($k = 1/2 \not \in \Bbb Z$).
• Antisymmetry: True. If $a \mid b$ and $b \mid a$, then there are $k,\ell \in \Bbb Z$ such that $$b = ak \qquad a = b\ell$$ Substitute the latter into the former, and vice versa, and we have $$b = b\ell k \qquad a = ak\ell$$ Thus, $\ell k = 1$. The only integers that ensure this are $\ell = k = +1$ or $\ell = k = -1$. Since we're working in $\Bbb N$, though, $a,b > 0$, and thus $\ell = k = +1$. Thus, $a = b$.
• Transitivity: True. Suppose $a \mid b$ and $b \mid c$. Then $\exists p,q \in \Bbb Z$ such that $$b = ap \qquad c = bq$$ Substitute the former into the latter, and we have $$c = apq$$ Since $p,q \in \Bbb Z \implies pq \in \Bbb Z$, then $a \mid c$, giving transitivity.

What if we consider things on $\Bbb Z^*$ instead?

• Reflexivity: Still holds for the same reason.
• Irreflexive: Same deal - not irreflexive.
• Symmetry: Again, same deal - not symmetric. It doesn't hold for $\Bbb N \subseteq \Bbb Z$ after all.
• Antisymmetry: Now something has changed. Before, we had to completely neglect the case of $k = \ell = -1$ since that would result in $a$ or $b$ not being in $\Bbb N$. However, now that case is permissible, and gives us cases like $2 \mid -2$ and $-2 \mid 2$, but $2 \ne -2$. (Just take $k = -1$ for each divisibility relation.)
• Transitivity: Still holds, nothing fundamentally changed here.

In short, the fundamental difference is that negative integers can divide positive integers, and vice versa!

---

...granted, this question is quite old, so I imagine you don't need help now. But hopefully this helps someone in the future, and, if nothing else, gets this question out of the unanswered queue.