1
$\begingroup$

I have the following question where i have to verify if the relation is partial order:

$A=\{1,2,3,\ldots,100\}$, relation $x\mathrel{R}y \leftrightarrow \frac{y}x=2^k$, where $k\ge 0$ is an integer.

This how i am thinking :

Reflexive: $x\mathrel{R}x\implies\frac{x}x=1$, therefore the relation is reflexive !

Symmetric: $x\mathrel{R}y\implies\frac{y}x=2^k \Leftrightarrow\frac{x}y=2^k$? $\frac42=2$ while $\frac24= 0.5$, thefore not symmetric !

AntiSymmetric: $\implies\frac{y}x=2^k$, $\frac{x}y=2^k\implies \frac{y}x=\frac{x}y\implies x=y$. eg $\frac21=\frac12$? clearly not, therefore not AntiSymmetric !

Transitive: $\implies\frac{y}x=2^k,\frac{z}y=2^k\implies \frac{z}x=2^k$? not really sure how to check the transitivity here

$\endgroup$
1
  • $\begingroup$ Partial orders are not symmetric unless they're the identity relation :) So you don't need, and don't want, to check that: for this relation, in general it's just not true ($2 R 4$, for example). $\endgroup$
    – BrianO
    Commented Oct 22, 2015 at 22:11

1 Answer 1

2
$\begingroup$

Your argument for reflexivity is correct: if $x\in A$, then $\frac{x}x=1=2^0$, so $x\mathrel{R}x$. Your example showing that $R$ is not symmetric is correct, though you’ve not explained it adequately: $\frac42=2=2^1$, so $2\mathrel{R}4$, but $\frac24=\frac12$ is not of the form $2^k$ for any integer $k\ge 0$, so $4\not\mathrel{R}2$, and therefore $R$ is not symmetric.

However, $R$ is antisymmetric. Suppose that $x,y\in A$, $x\mathrel{R}y$, and $y\mathrel{R}x$. Then by definition $\frac{y}x=2^k$ for some integer $k\ge 0$, and $\frac{x}y=2^\ell$ for some integer $\ell\ge 0$. But then

$$2^\ell=\frac{x}y=\left(\frac{y}x\right)^{-1}=(2^k)^{-1}=2^{-k}\;,$$

so $\ell=-k\le 0$. Thus, $0\le\ell\le 0$, so $\ell=0$, and $x=y$. This shows that if $x\mathrel{R}y$ and $y\mathrel{R}x$, then $x=y$, which is exactly what it means for $R$ to be antisymmetric.

To show that $R$ is transitive, start by assuming that $x,y,z\in A$, $x\mathrel{R}y$, and $y\mathrel{R}z$; you need to use this information to prove that $x\mathrel{R}z$. Use the definition of $R$ to translate these into more basic statements about $x,y$, and $z$. For instance, since $x\mathrel{R}y$, there is an integer $k\ge 0$ such that $\frac{y}x=2^k$. Similarly, since $y\mathrel{R}z$, there is an integer $\ell\ge 0$ such that $\frac{z}y=2^\ell$. Now combine these equations to find one involving $\frac{z}x$.

$\endgroup$
10
  • $\begingroup$ Thanks for your well explained answer, but how would you show that x=y (to prove that its antisymmetric) by the numbers that are presented in the set ? asuming that x=1 and y=2 then x are not equal y, or am i thinking wrong here ? $\endgroup$
    – humble24
    Commented Oct 22, 2015 at 22:12
  • $\begingroup$ @humble24: It looks to me as if you’re not quite understanding what it means for $R$ to be antisymmetric. $R$ is antisymmetric if it has the following property: whenever both $x\mathrel{R}y$ and $y\mathrel{R}x$, then $x=y$. This property says nothing about a pair $x,y$ unless both $x\mathrel{R}y$ and $y\mathrel{R}x$; in that case, and that case only, it says that you must have $x=y$. Thus, to check antisymmetry you start with the assumption that you have an $x$ and $y$ such that $x\mathrel{R}y$ and $y\mathrel{R}x$, and you use the definition of $R$ (as I did here) to show that in that ... $\endgroup$ Commented Oct 22, 2015 at 22:15
  • $\begingroup$ ... case it must be true that $x=y$. The only time you’d look at a particular example would be to show that $R$ isn’t antisymmetric: to do that, you’d have to find an $x$ and $y$ such that $x\mathrel{R}y$ and $y\mathrel{R}x$, but $x\ne y$. $\endgroup$ Commented Oct 22, 2015 at 22:16
  • $\begingroup$ Alright thanks , that was confusing me :) BTW is my way of proving that x=y acceptable ? or am i using the definition of $R$ in a wrong why ? $\endgroup$
    – humble24
    Commented Oct 22, 2015 at 22:25
  • $\begingroup$ @humble24: You’re welcome. I’m not sure what you mean by your way of proving that $x=y$, since you really looked only at a particular pair of $x$ and $y$ that weren’t equal. The only way I see to show that $x=y$ (assuming that each is $R$-related to the other) is essentially what I did, though the argument could be phrased in various ways. $\endgroup$ Commented Oct 22, 2015 at 22:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .