3
$\begingroup$

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?

  • 2
    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.2011-04-03

4 Answers 4

10

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
    Very well worded and explained, thank you so much.2011-04-04
8

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?

  • 0
    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.2011-04-04
4

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.

  • 0
    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.2011-04-04
3

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.