The relation $\sim$ is defined on $\mathbb{Z}^+$ (all positive integers). We say $x\sim y$ if and only if $y=3^kx$ for some real number $k$.

I need to prove that $\sim$ is an equivalence relation.

To prove an equivalence relation we must certify that:

  • It is reflexive
  • It is symmetric
  • It is transitive

I am not sure how to start this off since if I want to prove for:

Reflexive: I would replace $y$ with $x$, so that $x = (3^k)*x$ which is a positive integer when $k > 0$. Thus $x \sim x$ and $\sim$ is reflexive (?).

Symmetric: Suppose $x \sim y$ so that $y = (3^k)*x$ then $x = (3^k)*y$ is also an element of $\mathbb{Z}^+$. Thus $y \sim x$ and $\sim$ is symmetric (?).

Transitive: I'm not too sure about this last one. I think my entire proof is wrong anyways.

Can anyone help me on this?

  • $\begingroup$ for reflexive set k=0 $\endgroup$ – quanta Apr 3 '11 at 11:55
  • 2
    $\begingroup$ It does make sense if you define the relation more unambiguously than you did. What you meant is probably "x~y if and only if there is a real number $k$ such that $y=3^kx$. If that's the relation then "x~x if and only if there is a real number $k$ such that $x=3^kx$" makes perfect sense. $\endgroup$ – joriki Apr 3 '11 at 11:56
  • $\begingroup$ Yes, that's what I meant thank you. $\endgroup$ – meiryo Apr 3 '11 at 12:08
  • 2
    $\begingroup$ Please make the bodies of your posts self-contained. The key information about $\sim$ was hidden in the title; you should not rely on the title to provide necessary information. $\endgroup$ – Arturo Magidin Apr 3 '11 at 19:28

You are misunderstanding what needs to be shown in order to show that something is an equivalence relation. None of the arguments you present is a valid argument for the proposition you are trying to establish.

Your equivalence relation is defined on the set of positive integers. So if you write $x\sim y$, you are already assuming that $x$ and $y$ are positive integers, there is no need to prove that they are.

The relation is defined as follows: if $x$ and $y$ are positive integers, then $$x\sim y\Longleftrightarrow \text{there exists a real number }k\text{ such that }y = 3^kx.$$

That means that in order to show that two given numbers $x$ and $y$ are related, then you need to produce a real number $k$ that witnesses the identity $y=3^kx$. For example, to show that $y=9$ and $x=3$ are related, I just need to say: "take $k=1$. Then $9 = 3^1\cdot 3$; that is, $y = 3^1x$, so $x\sim y$ holds." To show that $18\sim 6$, I say "take $k=-1$; then $6 = 3^{-1}(18)$ holds." Etc.

And if you know that $x\sim y$, then you know that there exists a real number $k$ such that $y=3^kx$.

Thus, to show that $\sim$ is reflexive, you need to show that given any positive integer $x$, you can find a real number $k$ (which may depend on $x$) such that $x = 3^k x$. You need to say who $k$ is. Your argument about "being positive when $k\gt 0$" doesn't get you there in any way.

To show that $\sim$ is symmetric, you have to show that if you already know that $x\sim y$, so that you know there is a real number $k$ such that $y=3^k x$, then you can find some real number $\ell$ such that $x=3^{\ell}y$. This will witness the fact that $y\sim x$ holds, showing symmetry. You already know that $x$ and $y$ are positive integers. You know that simply because you know that $x\sim y$ holds, and that means that $x$ and $y$ have to be positive integers in the first place.

To show that $\sim$ is transitive, you have to show that if you already know $x\sim y$ and $y\sim z$, then you can exhibit a real number $r$ such that $z=3^rx$; this will witness $x\sim z$. You know there is a real number $k$ such that $y=3^kx$ (because $x\sim y$); and you know there is a real number $\ell$ such that $z=3^{\ell}y$ (because $y\sim z$); now you need to produce that number $r$ somehow. Again, you already know that $x$, $y$, and $z$ are positive integers, because you already know that $x\sim y$ and $y\sim z$ are true, which means, inter alia, that $x$, $y$, and $z$ are all positive integers.

  • 1
    $\begingroup$ Very well worded and explained, thank you so much. $\endgroup$ – meiryo Apr 4 '11 at 9:41

Isn't this relation true for all $x,y$ with the same sign? Since $3^k$, $k$ in reals, can take any positive real number?

  • $\begingroup$ sorry, didnt see that x,y had to be in Z+. $\endgroup$ – Kate Apr 3 '11 at 12:04
  • 6
    $\begingroup$ There is no need to be sorry, the answer to the question as stated was perfectly correct. I would guess, however, that the real question is the following. Define the relation $\equiv$ on the positive integers by $x \equiv y$ if there is an integer $k$ (positive, negative, or $0$) such that $y=(3^k)x$. Show that $\equiv$ is an equivalence relation. $\endgroup$ – André Nicolas Apr 3 '11 at 14:37
  • 2
    $\begingroup$ This allows an alternative proof: as $\forall x,y \in \mathbb{Z}^+ x \sim y$, the three requirements for an equivalence relation are easily verified. $\endgroup$ – Ross Millikan Apr 4 '11 at 0:31
  • $\begingroup$ my answer was added before an edit where I believe the extra condition was entered. if x,y are in reals, this should be equivilent to saying $x \sim y \leftrightarrow x,y>0$ OR $x,y<0$ OR $x=y=0$ right? since for all r in reals there exists a k s.t $3^k = r$ and signs are kept when a real is multiplied by a positive real. $\endgroup$ – Kate Apr 4 '11 at 1:22

Put $\rm\: G = \{ 3^r\: :\: r\in \mathbb R\}\:.\:$ It's reflexive by $\rm\: x/x = 1\in G\:.\:$ It's symmetric by $\rm\:G\:$ is closed under inverses $\rm\ x/y \in G\ \Rightarrow\ y/x\in G\:.\ $ It's transitive by $\rm\:G\:$ is closed under products $\rm\ x/y,\ y/z \in G\ \Rightarrow\ x/z \in G\:.\:$

Therefore the proof requires only that $\rm\:G\:$ contains $1\:$ and is closed under products and inverses or, equivalently, that $\rm\:G\:$ is nonempty and $\rm\:G\:$ is closed under quotients, i.e. $\rm\:G\:$ is a commutative group. This equivalence relation (congruence) will come to the fore when you study quotient groups.

  • $\begingroup$ Why did you change the set $G$ to $\{3^r : r \in \mathbb R\}$? The title of this post is incorrect, as $k$ is meant to be an integer. $\endgroup$ – JavaMan Apr 4 '11 at 0:31
  • $\begingroup$ @DJC: Both relations are equivalence relations; while it is possible (nay, likely) the original was meant to be that $k$ is an integer, the OP said "real number" from his very first edit. Bill edited his post to reflect the question asked, not the hypothetical question "meant to be asked". $\endgroup$ – Arturo Magidin Apr 4 '11 at 0:39
  • $\begingroup$ @DJC: I changed it to be consistent with the titled problem. Why do you believe the title is incorrect? Either interpretation works. $\endgroup$ – Bill Dubuque Apr 4 '11 at 0:39
  • $\begingroup$ I figured the title of this post was incorrect as the case $k in \mathbb{R}$ is trivial. I was just curious why you edited your post. $\endgroup$ – JavaMan Apr 4 '11 at 1:03

My short answer:

Reflexive: $k = 0$.

Symmetric: negate $k$ - $y = 3^k x \Longleftrightarrow x = 3^{-k} y$.

Transitive: $y = 3^k x$ and $z = 3^h y \Longrightarrow z = 3^{k+h} x$.

I don't see why there is anything more to it than this.


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.