Results 1 to 8 of 8

Math Help - Equivalence classes

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    Equivalence classes

    In \mathbb{C}[X] define a relation by:

    P_1~ P_2 if P_1-P_2 is divisible by X-1.

    Show that ~ is an equivalence relation.
    Equivalence classes have the following properties:
    1). Reflexivity a~a
    2). Symmetry if a~b then b~a
    3). Transitivity if a~b and b~c then a~c

    1). Reflexivity: a-a=0=0(X-1) so reflexivity holds.
    2). Symmetry: if a-b=m(X-1) then b-a=-m(X-1) so symmetry holds.
    3). Transitivity: if a-b=m(X-1) and b-c=q(X-1) then a-b+b-c=(m+q)(X-1) so transitivity holds.

    Let A denote the set of equivalence classes of ~ in \mathbb{C}[X].

    Find an explicit bijection on A \rightarrow \mathbb{C}.
    Hint: What if the relation were " P_1 ~ P_2 if P_1-P_2 is divisible by X"?
    I can see that this is going to have something to do with remainders, but i'm not really sure what. Surely remainders can be repeated?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Showcase_22 View Post
    Equivalence classes have the following properties:
    1). Reflexivity a~a
    2). Symmetry if a~b then b~a
    3). Transitivity if a~b and b~c then a~c

    1). Reflexivity: a-a=0=0(X-1) so reflexivity holds.
    2). Symmetry: if a-b=m(X-1) then b-a=-m(X-1) so symmetry holds.
    3). Transitivity: if a-b=m(X-1) and b-c=q(X-1) then a-b+b-c=(m+q)(X-1) so transitivity holds.



    I can see that this is going to have something to do with remainders, but i'm not really sure what. Surely remainders can be repeated?
    First step is to observe that each equivalence class is the set of complex polynomials that leave the same remainder when divided by x-1 .
    But the degree of remainder must be less than that of x-1 and hence the remainders must be complex numbers. That means each equivalence class is the set of complex polynomials that leave the same complex number when divided by x-1.

    However note that every complex number is clearly a remainder.And there is an equivalence class that contains it.(this shows the following map is onto)

    Hence if we map each equivalence class to the complex number contained in that equivalence class, we are done!

    Note: A small argument is required to establish this map is one-one
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    Okay then, that makes a little bit of sense.

    I understand the part that every equivalence class is the set of complex polynomials that leave the same remainder when divided by X-1.

    My real problem is writing this as a bijection. Since the remainders are complex numbers and we're mapping to the complex numbers themselves, wouldn't the bijection just be:

    f:\mathbb{C} \rightarrow \mathbb{C}

    so if a \in \mathbb{C} then f(a)=a would be the bijection?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Showcase_22 View Post
    My real problem is writing this as a bijection. Since the remainders are complex numbers and we're mapping to the complex numbers themselves, wouldn't the bijection just be:

    f:\mathbb{C} \rightarrow \mathbb{C}

    so if a \in \mathbb{C} then f(a)=a would be the bijection?
    We are mapping equivalence classes to complex numbers. For example consider the equivalence class of x-1. It is a set consisting all the polynomial multiples of x-1. Now we are mapping this set to a complex number.

    I asked you to search for a complex number in the set and then map the set to that complex number. With reference to the above example, convince yourself that 0 is the only complex number belonging to the set and thus map this equivalence class to the complex number 0

    So you should ask yourself a couple of questions:

    1) Why should there exists a complex number in each equivalence class?
    2) What if there are two complex numbers in the same set?Which will I map the set to? Or is it that there can be at most 1 complex number in each equivalence class?
    3)How do I know I can always find an equivalence class containing the complex number I want?

    So if you answer these questions, you will know why the map is a bijection.

    Let me say it again: The map is between equivalence classes and complex numbers and not between complex numbers
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    hmmm, i'm slightly understanding it but it's a little puzzling:

    1) Why should there exist a complex number in each equivalence class?
    This is because every complex number can be a remainder. (?)

    2) What if there are two complex numbers in the same set?Which will I map the set to? Or is it that there can be at most 1 complex number in each equivalence class?
    There can only be 1 complex number in each equivalence class. This is because when a polynomial is divided by X-1, there can only be one complex number as the remainder, not two.

    3)How do I know I can always find an equivalence class containing the complex number I want?
    Since there is a bijection between the equivalence class and the complex numbers, there is an inverse. Hence this inverse can be used to map from the complex numbers back to the equivalence classes.

    Can I use the fact there is a bijection here? I was supposed to deduce that there is a bijection between the equivalence classes and the complex numbers but it seems like I am using this fact to work backwards.

    I think these are right. I can see that it can only be a bijection, but i'm still a little unsure how to write it.

    How's this:

    Let \phi= set of equivalence classes of ~ in \mathbb{C}[x]. The bijection f is:

    f:\phi \rightarrow \mathbb{C}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Showcase_22 View Post
    This is because every complex number can be a remainder. (?)
    Yes, exactly

    Quote Originally Posted by Showcase_22 View Post
    There can only be 1 complex number in each equivalence class. This is because when a polynomial is divided by X-1, there can only be one complex number as the remainder, not two.
    To prove there is at most one complex number in an equivalence class is easy. Lets do it by contradiction. Suppose there are more than 1. Consider two complex numbers a and b in the same equivalence class. Since they are in the same equivalence class they are related. This means x-1 divides a-b. But degree of x-1 is greater than that of a-b, Contradiction!

    You are thinking of an equivalence class as the set of all polynomials leaving the same remainder.But how do you prove it? That is, how do you know if two different polynomials in the same equivalence class will leave the same remainder?

    Quote Originally Posted by Showcase_22 View Post
    Since there is a bijection between the equivalence class and the complex numbers, there is an inverse. Hence this inverse can be used to map from the complex numbers back to the equivalence classes.

    Can I use the fact there is a bijection here? I was supposed to deduce that there is a bijection between the equivalence classes and the complex numbers but it seems like I am using this fact to work backwards.
    You cant use the bijection idea. We are trying to prove it here.

    Since every complex number is a polynomial, there is an equivalence class containing the complex number.

    Quote Originally Posted by Showcase_22 View Post
    I think these are right. I can see that it can only be a bijection, but i'm still a little unsure how to write it.

    How's this:

    Let \phi= set of equivalence classes of ~ in \mathbb{C}[x]. The bijection f is:

    f:\phi \rightarrow \mathbb{C}
    What you have done is define notation. You should write the mapping also.
    That is you have to explicitly write the complex number associated with each equivalence class.


    I will define the mapping f:\mathcal{E} \rightarrow \mathbb{C} where \mathcal{E} denotes the equivalence class under consideration.

    Let us define the map as f(S) = s whenever s \in S

    Now we claim this map is well defined and bijective, completing the proof.

    Can you fill in the blanks and tell me why?
    Hint: the answer is in the three questions and their answers!

    R1) The map is well defined because of Question number _________

    R2) The map is one-one. That is f(S_1) = f(S_2) \Rightarrow S_1 = S_2 because of Question number ___________

    R3) The map is onto . That is for every complex number s there is an equivalence class S such that f(S) = s because of Question number ___________

    Good Luck,
    Iso
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    R1) The map is well defined because of Question number _________
    3-I'm not really sure of the explanation here.

    I'll try it though: Since all complex numbers are polynomials this is a mapping between polynomials.

    R2) The map is one-one. That is f(S_1) = f(S_2) \Rightarrow S_1 = S_2 because of Question number ___________
    2- Since there is only one number in each equivalence class, this one number is being mapped to only one other number in \mathbb{C}. Therefore the function is injective.

    R3) The map is onto . That is for every complex number s there is an equivalence class S such that f(S) = s because of Question number ___________
    1- Since every complex number is a remainder there is a complex number in every equivalence class. Hence there is a mapping from the equivalence classes to the complex numbers.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Showcase_22 View Post
    3-I'm not really sure of the explanation here.

    I'll try it though: Since all complex numbers are polynomials this is a mapping between polynomials.



    2- Since there is only one number in each equivalence class, this one number is being mapped to only one other number in \mathbb{C}. Therefore the function is injective.



    1- Since every complex number is a remainder there is a complex number in every equivalence class. Hence there is a mapping from the equivalence classes to the complex numbers.
    Well you have got the overall idea
    Now lets completely write down the proof and finish the problem
    Learning to write proofs clearly is an important skill. So here we go...

    Question:
    Find an explicit bijection on , where A is the set all equivalence classes of \mathbb{C}[X] modulo X-1

    Answer:
    Define f:A \to \mathbb{C} as f(S) = s (\in \mathbb{C}) whenever s \in S.

    We claim this is map is defined for every S in A, since every S contains at least 1 complex number. We claim the map is well defined since every S contains at most 1 complex number.

    The map is injective since there is a unique complex number in each equivalence class and the map is surjective because corresponding to every complex number, there is an equivalence class containing the complex number "polynomial" (of degree 0).

    Thus f is well defined and bijective, as required.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. equivalence classes of P(N)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 13th 2010, 09:26 AM
  2. Replies: 10
    Last Post: January 14th 2010, 01:28 PM
  3. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 07:36 PM
  4. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 04:39 AM
  5. Equivalence classes
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 31st 2008, 12:04 AM

Search Tags


/mathhelpforum @mathhelpforum