1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Equivalence Classes

  1. Apr 1, 2013 #1
    1. The problem statement, all variables and given/known data

    Consider the relation on [itex]\mathbb{N}[/itex] given by aRb if there exists k [itex] \in [/itex] [itex]\mathbb{Z}[/itex] such that a/b = 2k.

    Give an example of two different equivalence classes (that is, find x, y [itex] \in \mathbb{N} [/itex] such that Ex [itex] \neq [/itex] Ey, where Ex and Ey are the equivalence classes of x and y; respectively).

    2. Relevant equations

    Ex = {n [itex] \in \mathbb{N} [/itex]: x ~ n}.

    Ey = {n [itex] \in \mathbb{N} [/itex]: y ~ n}.

    a ~ b by a/b = 2k

    3. The attempt at a solution

    I'm having an incredibly difficult wrapping my head around the concept of equivalence classes in the context of this problem. I'm not sure where to even begin, so forgive me if I'm off to a very incorrect start...

    Let k = 1, so 2 = a/b --> a = 2b where 2 = n [itex] \in \mathbb{N} [/itex]
    Then let k = -1, so 1/2 = a/b --> b = 2a where 1/2 = n [itex] \in \mathbb{N} [/itex]

    Then a = 2(2a), where a [itex] \neq [/itex] 4a.

    Therefore, I have no idea what any of this means...
  2. jcsd
  3. Apr 1, 2013 #2


    User Avatar
    2017 Award

    Staff: Mentor

    Don't let k be something. k can be any integer, and there are too many to consider them individually.

    It is easier to start with some arbitrary a. Let's use 6.
    We know that b ~ 6 if there is an integer k such that 6/b = 2k.
    Can we find some b? b=3 is an example, as 6/b=2 = 21. Therefore, 6~3.
    b=12 is another example, as 6/12=1/2 = -1. Therefore, 6~12.
    Can you find more examples?

    As we have an equivalence relation, this implies 12~3. As you can see, this is "equivalent to", not "equal to", therefore we don't get a contradiction "12=3".
    If you go back to your approach, you showed (in general) that a ~ 4a.
  4. Apr 1, 2013 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Start by writing down what subsets of ##\mathbb{N}## are ##E_1,\ E_2,\ E_3## and see if that gives you any ideas.
  5. Apr 1, 2013 #4

    Alright. More equivalencies of the a = 6 would be: 6~3, 6~6, 6~12, 6~24, etc.

    I did a similar process for a = 1 and obtained the equivalencies of: 1~1, 1~2, 1~4, 1~8.

    Then I chose a b that wasn't in this relationship, so b = 3.

    I let my two different equivalence classes be:

    Ea = {2n, n [itex] \in \mathbb{N} [/itex]},

    Eb = {3*2k, k [itex] \in \mathbb{Z} [/itex]}.

    I am not sure that I quite wrap my head around what is happening here, but it seems that I can say Ea and Eb are the equivalence classes of a = 1 and b = 3, respectively. Since 1 is not related to 3 by a/b=2k, can I say that their respective equivalence classes are different?
  6. Apr 2, 2013 #5


    User Avatar
    2017 Award

    Staff: Mentor


    For the definition of Eb (I would call it E3 I think), you should restrict k to the natural numbers (including 0), as 3/2, 3/4, ... are not natural numbers.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted