1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    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 Relations problem

  1. Mar 26, 2014 #1
    1. The problem statement, all variables and given/known data
    Let ## H = \{ 2^{m} : m \in Z\}##
    A relation R defined in ##Q^{+} ## by ##aRb ##, if ## \frac{a}{b} \in H##

    a.) Show that R is an equivalence Relation

    b.) Describe the elements in the equivalence class [3].

    3. The attempt at a solution
    For part a, I think I am able to solve it, tell me what you think of my solution:
    Assume:
    ##2^{m} R 2^{m} , m \in Z##
    Since, ## 2^{0} \equiv 1 \equiv \frac{2^{m} }{2^{m} } \in H##
    So, R is reflexive, for any m in Z.

    Assume:
    ##2^{m} R 2^{n} ##, then ## \frac{ 2^{m}} { 2^{m} }, m , n \in Z##
    If ##m<0 \frac{1}{2^{m} 2^{n}} ## , then it still satisfies ##2^{0} , 2^{m+n} \in H##, since m+n is in Z as well.
    Without loss of generality for n<0 or both m and n <0.
    Thus, ##2^{n} R 2^{m} ## and R is symmetric.

    Assume:
    ##2^{m} R 2^{n} ## and ##2^{n} R 2^{d} ##, since n, m, and d are in Z , they are transitive.

    I have problems in part b.
    What would an equivalence class [3] mean in this powers of 2 relation?
     
  2. jcsd
  3. Mar 26, 2014 #2

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You've gone about this the wrong way. You must prove R is an equivalence relation on Q+, not on H.

    So, you need to show the properties hold for elements of Q+.
     
  4. Mar 26, 2014 #3

    pasmith

    User Avatar
    Homework Helper

    3 is a positive rational number. [3] is the equivalence class of 3, ie. the set of all positive rational [itex]a[/itex] such that [itex]aR3[/itex].
     
  5. Mar 26, 2014 #4
    I know that a/b or 3/1 is in ## Q^{+} ##.
    Would be multiples of 3 or numbers that can be divided and reduced into 3/1?
     
  6. Mar 26, 2014 #5
    So, the purpose of mentioning H is to say that whatever a/b is in the form ## 2^{m}, m \in Z##?
    It will always be in Q+.
    Could you give one or two examples of elements in this relation class?
     
  7. Mar 26, 2014 #6

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You've still got things the wrong way round. You would start, for symmetry say:

    Let a, b be in Q+ and aRb, then a/b is in H, so ## ∃ m \in Z \ s.t. \ a/b = 2^{m} ##...
     
  8. Mar 26, 2014 #7
    This is what I don't understand, what if a/b =7. This cannot be explained by ##2^{m}##
     
  9. Mar 26, 2014 #8

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    If a/b = 7 then ## a \ notR b ##
     
  10. Mar 26, 2014 #9

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    In addition to what PeroK said, if a=7 and b=14, neither of which is of the form ##2^n##, you'd have aRb because a/b = 1/2 = 2-1.
     
  11. Mar 26, 2014 #10

    pasmith

    User Avatar
    Homework Helper

    In the definition of [itex]aRb[/itex], both [itex]a[/itex] and [itex]b[/itex] are strictly positive rationals, and [itex]aRb[/itex] if and only if there exists [itex]m \in \mathbb{Z}[/itex] such that [itex]ab^{-1} \in H = \{2^m : m \in \mathbb{Z}\}[/itex].

    Thus, for example, 4/7 and 5/41 are not equivalent, because
    [tex]\frac 47 \div \frac 5{41} = \frac{164}{35} \notin H.[/tex]
    On the other hand, 5/8 and 5/16 are equivalent, because
    [tex]
    \frac 58 \div \frac {5}{16} = 2 \in H.
    [/tex]
     
  12. Mar 26, 2014 #11
    So, to correct my 'proof' as Perok mentioned:

     
    Last edited: Mar 26, 2014
  13. Mar 26, 2014 #12

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Well, that's a new one. You have made it impossible to quote your revised post. How the hell did you do that?

    In any case, it is still messed up, even on reflexive. You have to start with ##a\in Q^+##. You aren't given that ##a## is some power of ##2##.

    If ##a\in Q^+## please state what you have to prove to show ##aRa##. Do it in response to this post, not by editing something previous.
     
  14. Mar 27, 2014 #13
    Reflexive:
    Assume ##a \in Q^+##.
    If ##a \in Q^+## and ##\frac{a}{a} \in \{2^{m}: m\in Z\}##, then ##aRa##.

    Since, ##\frac{a}{a} \equiv 1 \equiv {2^0}, 0 \in Z##, then ##aRa##.

    Is this right?
     
  15. Mar 27, 2014 #14

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, you're getting there! But, let me tidy things up for you, as you're still thinking a little back to front. And, there's no need for equivalent signs rather than equal signs:

    [tex]Let \ a \in Q^+[/tex]
    [tex]\frac{a}{a} = 1 = 2^0 \in H \ as\ 0 \in \mathbb{Z}[/tex]
    [tex]∴ \ aRa[/tex]
    [tex]∴ \ R \ is \ reflexive
    [/tex]
     
  16. Mar 27, 2014 #15
    Thanks, Perok and LCKurtz.
    Now, I want to prove symmetry.
    Let ##a,b \in Q^+##

    ## \frac{a}{b} = 2^m \in H; \frac{b}{a} = 2^n \in H## for some m,n ##\in \mathbb{Z}##

    Then, ##aRb, bRa##

    and R is symmetric.

    Is this correct?
     
  17. Mar 27, 2014 #16

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I'm afraid not, I'm sorry to say. To prove symmetry you need to show that:

    For a, b in Q+, aRb => bRa

    In other words, if aRb, then bRa.

    This stuff's hard until you get your head round what the hell is going on!
     
  18. Mar 27, 2014 #17
    Ok.
    ##a,b \in Q^+ ##

    If ## aRb , \frac{a}{b} \in H## for some ##2^m , m \in Z##

    or ##\frac{a}{b} = 2^m##

    Solve for b/a:

    ## \frac{1}{2^m} = \frac{2^0}{2^m} = 2^{-m} = \frac{b}{a}##

    Then, ##\frac{b}{a} = 2^{-m} \in H##

    So, ##aRb ## implies ## bRa##

    Correct
     
  19. Mar 27, 2014 #18

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, you've got it!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Equivalence Relations problem
  1. Equivalence relation (Replies: 4)

  2. Equivalence relations (Replies: 1)

  3. Equivalence Relations (Replies: 11)

  4. Equivalence relation (Replies: 7)

Loading...