1
$\begingroup$

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.

  • 0
    possible duplicate of [Prove ~ is an equivalence relation: x ~ y if and only if y = (3^k)*x, for k is a real number.](http://math.stackexchange.com/questions/30648/prove-is-an-equivalence-relation-x-y-if-and-only-if-y-3kx-for-k-is-a)2011-04-03
  • 0
    Two similar questions from different users might imply this might be a homework problem?2011-04-03
  • 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.2011-04-03
  • 0
    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 statement2011-04-03
  • 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$?2011-04-03
  • 0
    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?2011-04-03
  • 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.2011-04-03
  • 0
    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?2011-04-03
  • 0
    @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.2011-04-03
  • 0
    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?2011-04-03
  • 0
    @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.2011-04-03

1 Answers 1

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