Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

An equivalence relation T on $\mathbb{N}$ is defined for all $x,y\in\mathbb{N}$ by

$$xRy \to x=2^ny\;\;\;\text{or}\;\;\; y=2^nx \;\;\; \text{for some non-nagtive integer}\;\;\; n$$

Write down the equivalence class [1] using any set notation.

MMy attempt

Since $1R\frac{1}{2^n}$, but $y$ must be a natural number so we can rule this out.

Since $1R2^n$, by $y=2^nx$, the answer must be

$$[1]=\{2^n, \;\;\;\text{for some non-negative integer}\;\;\; n\}$$

However, my answer shows $$[1]=\{2^n|n\in\mathbb{Z}, n\geq 0\}$$

I would like to clarify, do my answer mean the same thing? I was thinking more of, since the $n$ is fixed at the beginning by the word "for some", and hence, there is only 1 element in the equivalence class.

But it seems the answer is saying that there can be infinitely many elements, like $(2,4,8,16,...)$

share|cite|improve this question
Is this a question of wording? By putting the "$\text{for some non-negative integer }n$" inside the brackets, you are indicating that "for some" should be interpreted as "for all," effectively meaning that each non-negative integer $n$ gives us one element of $[1]$. This is the correct answer. If the statement was outside of the brackets, you would be saying that there is only one element, which would be wrong. – rayradjr Nov 22 '12 at 20:53
I am explicity saying there is only 1 element. – Yellow Skies Nov 22 '12 at 20:58
@SingaporeanDude: If you say there is only one element, you should specify which one that is (the notaion $[1]$ should designate one well defined set). As you did not do this, most people would read your expression as a clumsy and not entirely correct way of expressing what the second expression says more clearly. If that is not what you meant, then what you did mean makes no sense. – Marc van Leeuwen Nov 24 '12 at 11:07
up vote 2 down vote accepted

The way the equivalence relation is defined, given natural numbers $x$ and $y$, they are equivalent if and only if such an $n$ exists, but $n$ can vary between pairs in the same equivalence class.

The two answers you gave are not equivalent. Or rather I should say that the first answer is not well defined. The second one is correct.

Did this answer your questions?

share|cite|improve this answer
Yeah thanks!!!!! This part helped! "n can vary between pairs in the same equivalence class." – Yellow Skies Nov 22 '12 at 20:59
Hey espen I'm sorry one last question. I realized that according to the answer's definition of the equivalence classes, if I do the same for [2], i will get $[2]={2^n*2|n\in Z,z \geq 0}$ Dosen't that means [1] contains the element 2, and [2] also contains the element 2, and hence they are not equivalence classes? – Yellow Skies Nov 22 '12 at 21:11
No, $[1]=[2]$. By the definition of the eq. rel., $[2]=\{2\cdot 2^{n} | n\in \mathbb{Z}, n\geq -1\}$. Remember, $xRy$ iff $x=2^n y$ or $y=2^n x$ for some $n$. If two equivalence classes share an element, they are equal. This is true for any equivalence relation. – Espen Nielsen Nov 22 '12 at 21:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.