Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
    
Two similar questions from different users might imply this might be a homework problem? –  Asaf Karagila Apr 3 '11 at 17:06
1  
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
1  
@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
1  
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

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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