1. ## Equivalence classes

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

$\displaystyle P_1$~$\displaystyle P_2$ if $\displaystyle P_1-P_2$ is divisible by $\displaystyle 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: $\displaystyle a-a=0=0(X-1)$ so reflexivity holds.
2). Symmetry: if $\displaystyle a-b=m(X-1)$ then $\displaystyle b-a=-m(X-1)$ so symmetry holds.
3). Transitivity: if $\displaystyle a-b=m(X-1)$ and $\displaystyle b-c=q(X-1)$ then $\displaystyle a-b+b-c=(m+q)(X-1)$ so transitivity holds.

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

Find an explicit bijection on $\displaystyle A \rightarrow \mathbb{C}$.
Hint: What if the relation were "$\displaystyle P_1$ ~$\displaystyle P_2$ if $\displaystyle P_1-P_2$ is divisible by $\displaystyle 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?

2. Originally Posted by Showcase_22
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: $\displaystyle a-a=0=0(X-1)$ so reflexivity holds.
2). Symmetry: if $\displaystyle a-b=m(X-1)$ then $\displaystyle b-a=-m(X-1)$ so symmetry holds.
3). Transitivity: if $\displaystyle a-b=m(X-1)$ and $\displaystyle b-c=q(X-1)$ then $\displaystyle 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

3. 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:

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

so if $\displaystyle a \in \mathbb{C}$ then f(a)=a would be the bijection?

4. Originally Posted by Showcase_22
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:

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

so if $\displaystyle 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

5. 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 $\displaystyle \phi$= set of equivalence classes of ~ in $\displaystyle \mathbb{C}[x]$. The bijection f is:

$\displaystyle f:\phi \rightarrow \mathbb{C}$

6. Originally Posted by Showcase_22
This is because every complex number can be a remainder. (?)
Yes, exactly

Originally Posted by Showcase_22
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?

Originally Posted by Showcase_22
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.

Originally Posted by Showcase_22
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 $\displaystyle \phi$= set of equivalence classes of ~ in $\displaystyle \mathbb{C}[x]$. The bijection f is:

$\displaystyle 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 $\displaystyle f:\mathcal{E} \rightarrow \mathbb{C}$ where $\displaystyle \mathcal{E}$ denotes the equivalence class under consideration.

Let us define the map as $\displaystyle f(S) = s$ whenever $\displaystyle 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?

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

R2) The map is one-one. That is $\displaystyle 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

7. 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 $\displaystyle 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 $\displaystyle \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.

8. Originally Posted by Showcase_22
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 $\displaystyle \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 $\displaystyle \mathbb{C}[X]$ modulo $\displaystyle X-1$

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