Show that a relation is a partial ordering

Question

Show that the relation $R$ on $\Bbb N$ given by $aRb \text{ iff } b = a2^k$ for some integer $k\ge 0$ is a partial ordering.

Answer 1

Recall that to show a relation $R$ is a partial order, you need to verify the following properties hold for all elements in the set $A$ on which the order is defined:

1. $R$ is reflexive: for all $a \in A$, $a R a$.
2. $R$ is antisymmetric: for all $a, b \in A,\;$ if $aRb$ and $bR a$, then it must be the case that $a = b$.
3. $R$ is transitive: for all $a, b, c \in A, \;$ if $aRb$ and $bR c$, then $a R c$.

This is mostly an exercise in applying the definitions of these properties given the relation $$R: \{(a, b)\mid b = a2^k, \;\text{for some non-negative integer}\;k\}$$ where $a\,R\,b$ means $a, b \in \mathbb N, (a, b) \in R$.

1. $R$ is reflexive ?:
   
   Is it true that for all $a \in \mathbb N,$ there exists an integer $k \geq 0\,$ such that $\,a = a2^k\;?$ Hint: let $\,k = 0.$

2. $R$ is antisymmetric ?:
   
   Is it true that for all $a, b \in \mathbb N$, if we know $a R b$ (that is, if there exists an integer $k_1 \geq 0$ such that $b = a2^{k_1}$) and we also know that $b R a$, so that there is some integer $k_2 \geq 0$ such that $a = b2^{k_2},\;$ then it has to be the case that $a = b$?
   
   I'll start you out: Assume $a R b$ and $b R a$. So there exist non-negative integers $k_1, k_2$ such that $b = a2^{k_1},\;$ and $\;a = b2^{k_2}$. Now, try to determine whether it must follow then that $a = b$.

3. $R$ is transitive?:
   
   Is it true that for all $a, b, c \in \mathbb N$, if we know $a R b\;$ and know that $\;b R c,\;$ then it is also true that $a R c\;?$ Try to write our what this means in terms of your given relation.