# Prove something is a partial order

A relation $\mathrm{R}$ is defined on the set of all positive integers by:

$x\mathrm{R}y$ if and only if $y = 3^k\cdot x$ for some non-negative integer $k$.

Prove that $\mathrm{R}$ is a partial order.

• – Asaf Karagila Apr 3 '11 at 17:06
• Two similar questions from different users might imply this might be a homework problem? – Asaf Karagila Apr 3 '11 at 17:06
• It is not a duplicate. However, @Arvin, it would be nice if you asked a question rather than just stating directions of a problem, and it would be even nicer if you elaborated on where you are stuck, and gave any partial progress you have made. – Jonas Meyer Apr 3 '11 at 17:10
• @Arvin: $x=3^k\cdot x$ for a positive $x$ would require $3^k=1$. Do you know what number $k$ satisfies $3^k=1$? – Jonas Meyer Apr 3 '11 at 17:18
• I would write it $x=3^0x$, so $xRx$. You have displayed a specific $k$ that proves $xRx$. Now you just have two more to go. – Ross Millikan Apr 3 '11 at 17:34

As you mentioned in a comment, you need to show that the relation is reflexive, antisymmetric, and transitive. And you know that the reflexive step uses the fact that $3^0=1$. From there, you ask how you carefully convey the fact that the relation is reflexive.
You want: For all positive integers $x$, $x\mathrm{R}x$. This means that for all positive integers $x$, there exists a nonnegative integer $k$ such that $x=3^k\cdot x$.
To show this, let $x$ be given, and take $k=0$, which is a nonnegative integer. Then $x=3^0\cdot x$ shows that $x\mathrm{R}x$.
Hint for antisymmetry: $3^k\cdot 3^j=1\Rightarrow k=j=0$.
Hint for transitivity: A product of powers of $3$ is a power of $3$.