Results 1 to 9 of 9

Math Help - Equivalence Relation Proof

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    191

    Equivalence Relation Proof

    Define a relation ~ on N whereby a~b if and only if there exists k \in Z such that \frac{a}{b} = 2^k.

    (a) Prove that ~ is an equivalence relation.
    (b) Write out the equivalence classes for ~ on the set {1,2,3,....10}

    Here's my attempt at part (a):

    To show that ~ is an equivalence relation, I must show that it's reflexive,symmetric and transitive:

    * ~ is reflexive \Longleftrightarrow a~a \forall a \in Z
    \Longleftrightarrow \frac{a}{a} = 2^k

    But we know: \frac{a}{a} = 1, well I'm sort of stuck here and I don't know how to conclude that ~ is reflexive...

    * ~ is symmetric \Longleftrightarrow a~b \Rightarrow b~a

    \Longleftrightarrow \frac{a}{b} = 2^k \Rightarrow \frac{b}{a} = 2^k

    We can suppose \frac{a}{b} = 2^k and then try to show that \frac{b}{a} = 2^k but I don't know how to do it...

    * ~ is transitive if and only if a~b \wedge b~c \Rightarrow a~c

    \Longleftrightarrow \frac{a}{b}=2^k \wedge \frac{b}{c} = 2^k \Rightarrow \frac{a}{c} = 2^k

    Suppose  \frac{a}{b}=2^k \wedge \frac{b}{c} = 2^k then:

     \frac{a}{c} = \frac{a}{b} + \frac{b}{c} = 2^k + 2^k = 2^{2k} = 4.2^k

    I'm not sure how to continue this part either... any help with this problem is greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Your problems in parts 1 and 2 - reflexivity and symmetricity (is that a word?) - are easily resolved if you remember that k \in \mathbb{Z}. In the first one, take k=0, and in the second remember that 1/2^k = 2^{-k}.

    For the 3rd part note that the value of k does not matter, as long as some k exists. Thus, you have shown that the k in this instance is actually just k'=4k.

    For instance, if we take the equivalence class of all numbers of the form 2^n, clearly 4/2=2 so 4 \sim 2. Also, 2/4=1/2=2^{-1} so 2 \sim 4. Further, 16/4=4 so 16 \sim 4, and also 4/16=4^{-1} so 4 \sim 16. Then, 16/2=8 so 16 \sim 2.

    So we have an example of symmetricity and transitivity.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    Note: We are assuming that  \mathbb{N}=\{1,2,3,..\}.

    For the reflexive property: a^0~\&~0\in \mathbb{Z}.

    For the symmetric property note that a^{-1}=\frac{1}{a}~\&~-1\in \mathbb{Z}.

    For the transitive property note that \frac{a}{b}=2^m~\&~\frac{b}{c}=2^n \Rightarrow\frac{a}{c}=2^{m+n}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Apr 2008
    Posts
    191
    OK thanks very much Plato and Swlabr! I got it.

    Now I need some help with part (b), I don't really understand what to do:

    (b) Write out the equivalence classes for ~ on the set {1,2,3,....10}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    Now I need some help with part (b), I don't really understand what to do:
    (b) Write out the equivalence classes for ~ on the set {1,2,3,....10}
    Can you show that [1]=\{1,2,4,8\}?
    Can you show that [3]=\{3,6\}?
    Can you show that [5]=\{5,10\}?
    What about [7]~\&~[9]?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Apr 2008
    Posts
    191
    Quote Originally Posted by Plato View Post
    Can you show that [1]=\{1,2,4,8\}?
    Can you show that [3]=\{3,6\}?
    Can you show that [5]=\{5,10\}?
    What about [7]~\&~[9]?
    Frankly I can't follow what you've done there... I know that if ~ is a relation then for a \in A we define the set of relatives of "a" as:
    T_{a} = { x \in A : a~x}
    And in the case when ~ is an equivalence relation on a set A then each T_{a} is called an equivalent class.

    I appreciate it if you can explain what you've done in your last post so that I can follow, and why did you choose the odd numbers? What about {2,4,6,8}?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    The equivalence relation basically amounts to two things are equivalent if and only if the ratio of the two integers have a ratio that is a power of two (note this includes 2^0=1 this is the reflexive part of the equivalence relation). We know that equivalence relations partition, so what he has done is just figured out which things are in equivalence classes together.


    start with 1, what things have ratios that are powers of two with 1.
    2 does because \frac{2}{1}=2=2^1. 4 does because \frac{4}{1}=4=2^2. 8 does because \frac{8}{1}=8=2^3. That is all of them. You have already verified that the relation is transitive, so there is no need to check them against one another, it will work out pretty obviously.

    So what have we missed? 3 is the next one, anything that is a ratio of a power of two? yeah 6 is because \frac{6}{3}=2=2^1. That's it.

    Next is 5. Well \frac{10}{5}=2=2^1 so 10 is in there, and that is it.

    next is 7, the only thing left that hasn't already been assigned is 9, clearly they are not a ratio of a power of 2, so they can't be in the same equivalence class. This means each of these must be in their own class.

    That is why Plato's post is complete.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    In general,

    [a]=[b] \Leftrightarrow a=k2^m and b=k2^n, with a k fixed natural number and m and n natural numbers. This is because in the rations the k's will cancel.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,536
    Thanks
    1391
    Quote Originally Posted by Roam View Post
    Frankly I can't follow what you've done there... I know that if ~ is a relation then for a \in A we define the set of relatives of "a" as:
    T_{a} = { x \in A : a~x}
    And in the case when ~ is an equivalence relation on a set A then each T_{a} is called an equivalent class.

    I appreciate it if you can explain what you've done in your last post so that I can follow, and why did you choose the odd numbers? What about {2,4,6,8}?
    The first thing you should have done on this problem, in order to make sure you understood what you were given, was to actually write down some "equivalent" pairs. For example, what numbers are equivalent to 1? Since a~b if and only if a/b= 2^k for some k, taking b= 1, we are looking for numbers, a, such that a/1=a= 2^k. It should be clear that those are just the powers of 2: 2, 4, 8, 16, etc. Since you are asked onlyfor numbers from 1 to 10, those are {1, 2, 4, 8}.

    What numbers are equivalent to 2? That's easy, since 2 was in that previous set, it is just {1, 2, 4, 8} again.

    What numbers are equivalent to 3? Now, taking b= 3, we have a/3= 2^k so that a= 3(2^k)- 3 times powers of 2: 3(2^0)= 2, 3(2^1)= 6, 3(2^2)= 12, etc. The "equivalence class" is {3, 6} (12 is not between 1 and 10).

    4 was already in the first equivalence class so its class is {1, 2, 4, 8} again.

    If b= 5, a/5= 2^k yields a= 5(2^k): 5 times different powers of 2: 5(2^0)= 5, 5(2^1)= 10 5(2^2)= 20. The only ones of those between 1 and 10 are 5 and 10: {5, 10}

    6 was in the class {3, 6} so its class is also {3, 6}.

    If b= 7, a/7= 2^k so a= 7(2^k), {7, 14, 28, ...} the only one of which is between 1 and 10 is 7: {7}.

    8 is already in {1, 2, 4, 8} and 10 is in {5, 10}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. equivalence relation proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 3rd 2011, 05:18 AM
  2. Equivalence relation proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 17th 2011, 04:30 PM
  3. Equivalence Relation Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 25th 2011, 08:32 AM
  4. [SOLVED] Equivalence relation proof?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 22nd 2010, 11:09 AM
  5. equivalence relation proof
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: July 3rd 2006, 01:46 PM

Search Tags


/mathhelpforum @mathhelpforum