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.

  • $\begingroup$ possible duplicate of Prove ~ is an equivalence relation: x ~ y if and only if y = (3^k)*x, for k is a real number. $\endgroup$ – Asaf Karagila Apr 3 '11 at 17:06
  • $\begingroup$ Two similar questions from different users might imply this might be a homework problem? $\endgroup$ – Asaf Karagila Apr 3 '11 at 17:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Jonas Meyer Apr 3 '11 at 17:10
  • 1
    $\begingroup$ @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$? $\endgroup$ – Jonas Meyer Apr 3 '11 at 17:18
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.