1

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.

Jonas Meyer
  • 53,602
Arvin
  • 1,733
  • possible duplicate of Prove ~ is an equivalence relation: x ~ y if and only if y = (3^k)*x, for k is a real number. – Asaf Karagila Apr 03 '11 at 17:06
  • Two similar questions from different users might imply this might be a homework problem? – Asaf Karagila Apr 03 '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 03 '11 at 17:10
  • My mistake, I'll give more details: I know that a poset requires reflexivity, antisymmetry and transitivity. I was just trying to do a quick check on reflexivity but I got confused:

    x = y = 1; 1 = 3^k * 1 but no value of integer k can make this a true statement

     – Arvin Apr 03 '11 at 17:11
  • 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 03 '11 at 17:18
  • Ah, I forgot that anything to the power of 0 is 1. and 0 is a non-negative number. So we know that it is reflexive but how would we write that as a formal proof? Does it suffice to say x = 3^k * x hence reflexive? – Arvin Apr 03 '11 at 17:25
  • 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 03 '11 at 17:34
  • Thanks guys, now with antisymmetry. if xRy and yRx then x = y. I know this much but I don't know how you can write it as a proof. Hang on, what about if i set k = 0 again, then I just have y = x. Is that an acceptable proof? – Arvin Apr 03 '11 at 17:36
  • @Arvin: No, this time you don't get to choose $k$. Each statement xRy and yRx implies the existence of nonnegative integers which you cannot specify a priori. Rather, given the hypothesis that $x=3^k\cdot y$ for some $k$ and $y=3^j\cdot x$ for some $j$, you have to deduce that $x$ must equal $y$, and in doing so you will determine what $k$ and $j$ must be. – Jonas Meyer Apr 03 '11 at 17:40
  • I think I see; as x = 3^k y and y = 3^j x then 3^k and 3^j must equal 1 and hence k and j must be 0? – Arvin Apr 03 '11 at 17:53
  • @Arvin: That is true, but to show more explicitly why $k$ and $j$ must be $0$ I recommend substituting $3^k\cdot y$ for $x$ in the second equation. – Jonas Meyer Apr 03 '11 at 18:33

1 Answers1

2

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

Jonas Meyer
  • 53,602