Ok, so I have this discrete math question that is bugging me for a while and I cannot solve it by myself. Here is the question :
Let $R$ be a relation defined on $\mathbb{R}_+ \times \mathbb{R}_+$ where $(x_1,y_1)\mathrel{R}(x_2,y_2)$ if and only if $x_1 \times y_2 \leq x_2 \times y_1$. Prove or refute the following : $R$ is a partial order.
So far, I know that a partial order is a relation that is antisymmetric, reflexive and transitive. So I would need to prove (or refute) that all three properties are true (or false).
For antisymetry, I would try : if $x_1 y_2 \leq x_2 y_1$ and $x_2 y_1 \leq x_1 y_2$, then $x_1 = x_2$ and $y_1 = y_2$
For reflexivity, I would try : $x_1 y_1 = x_1 y_1$
And for transitivity, I would try : if $x_1 y_2 \leq x_2 y_1$ and $x_2 y_3 \leq x_3 y_2$, then $x_1 y_3 \leq x_3 y_1$
Is this ok so far? I am stuck at this as I am not sure what to do next. I don't know how to prove (or refute) these (I am a first year comp. science student and this is my first discrete math class). Can someone complete what I have do so far? I am probably stupid and stuck on something obvious. Can you prove (or refute) that $R$ is a partial order? Thanks.
You’ve correctly identified what needs to be done; it just remains to do it!
Clearly $x_1y_1=x_1y_1$ for all $\langle x_1,y_1\rangle\in\Bbb R_+\times\Bbb R_+$, so the relation is reflexive.
Now let’s look at antisymmetry. If $x_1y_2\le x_2y_1$ and $x_2y_1\le x_1y_2$, then clearly $x_1y_2=x_2y_1$; is that enough to guarantee that $x_1=x_2$ and $y_1=y_2$? What if $x_1=1$, $y_2=4$, and $x_2=y_1=2$?
For completeness we might as well look at transitivity, too. Suppose that $x_1y_2\le x_2y_1$ and $x_2y_3\le x_3y_2$; we want to see whether this ensures that $x_1y_3\le x_3y_1$. Since all of the numbers involved are positive, we can multiply the inequalities $x_1y_2\le x_2y_1$ and $x_2y_3\le x_3y_2$ to conclude that
$$x_1x_2y_2y_3\le x_2x_3y_1y_2$$
and then divide both sides by $x_2y_2$ to find that $x_1y_3\le x_3y_1$, as desired. Thus, the relation is transitive.
Note that $\langle x_1,y_1\rangle R \langle x_2,y_2\rangle$ iff $x_1y_2=x_2y_1$ iff $\frac{x_1}{y_1}=\frac{x_2}{y_2}$. If we notice this right away, it’s very easy to see that $R$ is reflexive and transitive but not antisymmetric: for any $x_1,y_1,x_2,y_2,x_3,y_3\in\Bbb R_+$ it’s certainly true that $\frac{x_1}{y_1}=\frac{x_1}{y_1}$, and that if $\frac{x_1}{y_1}=\frac{x_2}{y_2}$ and $\frac{x_2}{y_2}=\frac{x_3}{y_3}$, then $\frac{x_1}{y_1}=\frac{x_3}{y_3}$, simply because equality is reflexive and transitive. But it’s also clear that $\frac{x}y=\frac{2x}{2y}$ for any $x,y\in\Bbb R_+$ even though $x\ne 2x$ and $y\ne 2y$.