Verifying partial order relation

241 Views Asked by At

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

1

There are 1 best solutions below

10
On BEST ANSWER

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$.