Equivalence Classes Homework Solutions

[davon806]

Homework Statement

Hi,I am stuck on my maths assignment.
Describe equivalence classes for the following equivalence relations on the given set S.
(i) S = R, and a ∼ b ⇐⇒ a = b or −b.
(iii) S = R, and a ∼ b ⇐⇒ a^2 + a = b^2 + b.
(v) S is the set of all points in the plane, and a ∼ b means a and b are the same distance from the origin. (vi) S = N, and a ∼ b ⇐⇒ ab is a square.
(viii) S = R × R, and (x, y) ∼ (a, b) ⇐⇒ x^2 + y^2 = a^2 + b^2 .

Homework Equations

The Attempt at a Solution

I am asking because I don't know what does an equivalence class mean.

For example,in (i) given a is equal to b or -b.So what do I need to answer?I have been searching for some solved examples but I am still fail to understand.Which one is the variable?a or b?If b is fixed then a must be equal to b or -b to satisfy the relation.But then what do I need to show?

For (v),the equivalence class is the set of solution lies on the circle of radius a,but again what do I need to show?I don't know what to do with the b.

Thanks

 

[fresh_42]

To start with. An equivalence relation ~ on S means, it sets two elements in relation to one another. Equivalence now means that the following rules hold:

1.) x ~ x for all x of S : ~ is called a reflexive relation
2.) x ~ y ⇒ y ~ x : ~ is called a symmetric relation
3.) x ~ y ∧ y ~ z ⇒ x ~ z : ~ is called a transitive relation

All three make ~ an equivalence relation.
Now you can start and pick up all elements from S and see if two are equivalent. You put those into the same box which we will call equivalence class.

For example let us consider all integers and see what happens if we divide them by 3. We are interested in the remainders.
That defines an equivalence:
x has clearly the same remainder as x when divided by 3.
If x has the same remainder as y then y has the same remainder as 3.
If x has the same remainder as y and y the same as z so x has the same as z.
Therefore we can pick up all integers and see what remainder they have. By putting all multiples of 3 in one box, those with remainder 1 in another and those with remainder 2 in a third box we have all integers in some of these boxes, called equivalence class of remainders 0, 1 or 2.
The remainders 0,1,2 are called representatives of their equivalence class.

One can do such a an arrangement or classification whenever one has an equivalence relation ~.

In (i) of your task ~ means you don't care the sign. So +3 is equivalent to -3 but not to 2 or -2.
Therefore every box, i.e equivalence class consists of two numbers +x and -x. We can choose the +x as the representative of each class.
In (v) you consider all points of a plane as equivalent if they lie on the same circle around the origin. So in your boxes, equivalence classes will be all points of a circle and you have as many boxes as there are concentric circles in the plane. I think it would be a pleasant idea to label the boxes with the radius r of that circle. As representatives you could choose (r,0), but any point on it will do.

 

[Orodruin]

I am asking because I don't know what does an equivalence class mean.

So, obviously, the first order of business is to figure this out. Typing "equivalence class" into your favourite search engine or looking it up in your course book should do the trick.

 

[davon806]

To start with. An equivalence relation ~ on S means, it sets two elements in relation to one another. Equivalence now means that the following rules hold:

1.) x ~ x for all x of S : ~ is called a reflexive relation
2.) x ~ y ⇒ y ~ x : ~ is called a symmetric relation
3.) x ~ y ∧ y ~ z ⇒ x ~ z : ~ is called a transitive relation

All three make ~ an equivalence relation.
Now you can start and pick up all elements from S and see if two are equivalent. You put those into the same box which we will call equivalence class.

For example let us consider all integers and see what happens if we divide them by 3. We are interested in the remainders.
That defines an equivalence:
x has clearly the same remainder as x when divided by 3.
If x has the same remainder as y then y has the same remainder as 3.
If x has the same remainder as y and y the same as z so x has the same as z.
Therefore we can pick up all integers and see what remainder they have. By putting all multiples of 3 in one box, those with remainder 1 in another and those with remainder 2 in a third box we have all integers in some of these boxes, called equivalence class of remainders 0, 1 or 2.
The remainders 0,1,2 are called representatives of their equivalence class.

One can do such a an arrangement or classification whenever one has an equivalence relation ~.

In (i) of your task ~ means you don't care the sign. So +3 is equivalent to -3 but not to 2 or -2.
Therefore every box, i.e equivalence class consists of two numbers +x and -x. We can choose the +x as the representative of each class.
In (v) you consider all points of a plane as equivalent if they lie on the same circle around the origin. So in your boxes, equivalence classes will be all points of a circle and you have as many boxes as there are concentric circles in the plane. I think it would be a pleasant idea to label the boxes with the radius r of that circle. As representatives you could choose (r,0), but any point on it will do.

Hi,
Thx for your reply.Actually,the only example my textbook had illustrated is similar to what you did,i.e.the congruence class.That's why I am stuck on the more general idea of equivalence class.(Forgive me please,I have been searching and looking up on wiki but I couldn't grasp the idea).

For(i),Do you mean we can ignore the set of negative numbers?Since x = -x for all x in S.So the equivalence classes are [1],[1.1],[3.1415...],...
but there are infinite classes,so what should I write?Is it possible to say "The equivalence classes of ~ contain the sets of positive real numbers?But it seems not precise enough,I mean,I need to separate out all the numbers on the positive number line,how can I describe it in words?

For(v),is it correct to write = {x,y ∈ℝ|x^2 + y ^2 = b^2},but b can be any positive real numbers.It seems weird to have a variable in [ ].

 

[fresh_42]

For(i),Do you mean we can ignore the set of negative numbers?Since x = -x for all x in S.So the equivalence classes are [1],[1.1],[3.1415...]

No, that's not what I've said. x ≠ -x, that doesn't change. However, x ~ -x, which means they belong into the same class, they are equivalent. So classifying all numbers, you'll get as many boxes as there are different |x| in S.
So in (i) you have S / ~ = ℝ / ~ = { |x| with x ∈ ℝ}. For each box labeled by |x| there are two numbers in it: {+x} and {-x}, {0} in the box |x| = 0.

...but there are infinite classes,so what should I write?Is it possible to say "The equivalence classes of ~ contain the sets of positive real numbers?But it seems not precise enough ...

Right. The fact that there are infinite many classes is totally of no interest here. Not the equivalence classes of ~ contain all positive reals, they contain only two elements. There are just equally many classes as there are positive reals. Plus {0}, which is also a class but contains only one element. I've already given a more precise answer above.

For(v),is it correct to write = {x,y ∈ℝ|x^2 + y ^2 = b^2},but b can be any positive real numbers.It seems weird to have a variable in [ ]

Again. {$x,y ∈ℝ|x^2 + y ^2 = b^2$} is a single class. One only. It contains all elements on the circle of radius b. Changing b gives you another class. So you can label your boxes, classes with a "b" and write next to it on the label: This box contains the circle with radius "b".
The number of classes is again of no interest. What is of interest, however, is that you forgot the origin 0. {0} builds its own class as the circle of radius 0. I suggest to write non-negative instead of positive.

Those infinite classes are by no means "weird". You use them on each Saturday you visit a bakery to buy cake for your guests on Sunday. Sometimes you might buy 6 pieces of a pie which has been cut into 12. Another day you want to keep it more fresh and buy an uncut half of a pie. Surely not the same, but an equivalent amount of cake. And for every quotient, say (2 / 3), you have infinite many elements in that (2 / 3) class: (4 / 6), (-6 / -9), (3456 / 5187) ... And not enough, you also have as many classes with infinite many numbers in it as you have irreducible quotients! And if you say, c'mon, that's the same, then I advice you to buy 150 / 300 pieces of a pie next time you're at the bakery. Hope you're fast on the short track

 

[davon806]

So,for (i),the equivalence class [x] = {x,-x |x∈R}?But 0 is in x or -x so we do not need [0]={0}?
For (v),there are 2 equivalence classes:[0] = {0} for the origin and [p] = {p∈R | p is the radius of circle centered at O} ?

Edit:
For (iii),x^2 + x = a^2 + a
(x-a)(x+a) + (x-a) = 0
x = a or -a-1
so the only equivalence class is [x] = {x,-x-1 | x∈R} ?

 

[fresh_42]

So,for (i),the equivalence class [x] = {x,-x |x∈R}?But 0 is in x or -x so we do not need [0]={0}?
For (v),there are 2 equivalence classes:[0] = {0} for the origin and [p] = {p∈R | p is the radius of circle centered at O} ?

Go back to my description of the boxes. An equivalence class contains all equivalent elements: {+x ,-x} or {0} in (i) and a circle of radius b in (v). The classes in (i) differ as |x| does, in (v) they differ as b does.
Since |0| ≠ |x| for a x ≠ 0 they cannot represent the same class, whereas |+x| = |-x| so they represent the same class.
Since $0^2$ ≠ $b^2$ for $b≠0$ they cannot represent the same class, whereas $|| (0,b) ||_2 = || (b,0) ||_2$ so they represent the same class.
Therefore all |x| (including 0) represent all classes in (i). In the class are +/- x or 0 (in its own class).
Therefore all radius (including 0) represent all classes in (v). In the class are the circles of radius b or 0 (in its own class).

Half a pie is what you pay. It's a class, since here it doesn't matter if it's cut into pieces or not.
A whole pie is another class and you have to pay more for it. And again it doesn't matter how it's cut.
You pay for the equivalence class "amount of pie", independent of whether it's cut or not.
Cut into pieces or not is just to illustrate, that it is not the same. Your 6$ for half a pie is for the class. When you arrive at home and your better half or who ever says you should have had it cut into smaller pieces, then you know it is not the same. The 6$ can be seen as representative of the equivalence class "half a pie".