# Prove $\sim$ is an equivalence relation: $x \sim y$ if and only if $y = 3^kx$, where $k$ is a real number

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?

-
for reflexive set k=0 – quanta Apr 3 '11 at 11:55
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. – joriki Apr 3 '11 at 11:56
Yes, that's what I meant thank you. – meiryo Apr 3 '11 at 12:08
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. – 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.

-
Very well worded and explained, thank you so much. – 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?

-
sorry, didnt see that x,y had to be in Z+. – Kate Apr 3 '11 at 12:04
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. – André Nicolas Apr 3 '11 at 14:37
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. – Ross Millikan Apr 4 '11 at 0:31
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. – 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.

-
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. – JavaMan Apr 4 '11 at 0:31
@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". – Arturo Magidin Apr 4 '11 at 0:39
@DJC: I changed it to be consistent with the titled problem. Why do you believe the title is incorrect? Either interpretation works. – Bill Dubuque Apr 4 '11 at 0:39
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. – JavaMan Apr 4 '11 at 1:03

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