Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Are the following relations $R_1$ and $R_2$ defined on the set $\mathbb{Z}$ of integers partial orders? (A partial order is reflexive, antisymmetric and transitive.)

  1. $a$ $R_1$ $b$ if and only if $a = 2b$.
  2. $a$ $R_2$ $b$ if and only if $a^2|b$.

Would someone help me understand?

share|cite|improve this question
I'm not sure that I understand what the question is. – Merbs Dec 5 '12 at 17:23
@Merbs Why would you edit the question if you didn't understand what was being asked? If possible, it makes even less sense now. – Patrick87 Dec 5 '12 at 17:57
Nothing CS-specific here, so more appropriate for math.stackexchange. – Yuval Filmus Dec 5 '12 at 18:02
@Merbs In general, you should not edit a question you do not understand, particularly when the state you leave it in is incomprehensible. If you feel the question is incomprehensible, you should ask for clarification or vote to close. Who knows what was being asked? – Patrick87 Dec 5 '12 at 18:25
@Bartek $A = Z$ and $A \in Z$ mean different things. – Joe Dec 5 '12 at 20:36

Let's look at all the different criteria (reflexivity, symmetry or antisymmetry, and transitivity) for the first relations, $aR_1b\Leftrightarrow a=2b$ :

a) Is it reflexive, or antireflexive, or neither? For this we want to test $aR_1a$ — or in other words, whether $a=2a$. This can hold if $a=0$, but otherwise it never holds. So on $\Bbb{Z}$ the relation is neither reflexive nor antireflexive; but on $\Bbb{N}$ (the set of 'whole numbers', not counting 0) it would be antireflexive, since $a=2a$ can never hold there.

b) Is it symmetric, or antisymmetric, or neither? Here we want to compare $aR_1b$ and $bR_1a$ where $a$ and $b$ are distinct values; in other words, can we have both $a=2b$ and $b=2a$? Dividing by 2, the latter is equivalent to $a=\frac{1}{2}b$, and the only way we can have both $a=2b$ and $a=\frac{1}{2}b$ is to have $b=0$, in which case $a=0$ — but since we said that $a$ and $b$ had to be distinct, this can't hold. In other words, if we have $aR_1b$ for $a\neq b$ we can never have $bR_1a$; the relation is antisymmetric.

c) Is it transitive? (Note that we never ask about 'antitransitivity', even though the concept hypothetically makes sense). For this, we want to figure out if $(aR_1b)\wedge(bR_1c)\implies(aR_1c)$ — in other words, if $a=2b$ and $b=2c$, is $a=2c$? Well, if $a=2b$ and $b=2c$, then we have $a=2b=2(2c)=4c$, so it's definitely not the case that $a=2c$; this relation is not transitive.

Since this has the feel of homework, I'll let you do the second one yourself, but it should be relatively straightforward (as long as you know a little bit about divisibility). For looking at reflexivity, you'll have special cases again where $a=0$ and also where $a=\pm1$ to keep an eye out for; for symmetry you should be able to use the divisibility to say something about the relative order of $a$ and $b$; and for transitivity you should try to figure out how to 'staple' the two conditions $a^2|b$ and $b^2|c$ together to see if you can figure out whether $a^2|c$.

share|cite|improve this answer

Assuming that the answer to my comment is yes,

  1. The first is not a partial order, since it is not reflexive; in general, it is not true that $a = 2a$ (consider the case $a \neq 0$).
  2. The second is not a partial order, since it is not reflexive; in general, it is not true that $a^2 | a$ (consider the case $a > 1$).
share|cite|improve this answer
Since both cases fail on reflexivity, one wonders whether the partial order perhaps is meant to be a strict partial order? – Hendrik Jan Dec 6 '12 at 1:01
@HendrikJan Hey man, I just answer 'em as I reads 'em. – Patrick87 Dec 6 '12 at 16:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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