What the equivalence class suppose to be

[d_b]

I read the textbook 5 times now and I can't seem to figure out what the equivalence class suppose to be and how to find it, and i don't understand quotient set either (more importantly how to find it). I'm not familiar with any Equivalences at all if anyone can help me with it that would be amazing...

 

[slider142]

An equivalence class is simply a set containing all elements of the universe related to each other by an equivalence relation. An equivalence relation is a relation that satisfies three properties: symmetry, reflectivity, and transitivity. A relation is a set of ordered pairs containing elements of the universe. An ordered pair (x,y) of the relation R is usually written xRy.
As an example of a relation, consider the ordering relation > of the real numbers. We define (x,y) to be an element of > if y - x is an element of the positive real numbers. Classically written, we define x>y if y - x is positive. > is not an equivalence relation because it is not symmetric (x>y does not imply y>x).
One non-trivial equivalence relation is to consider y to be equivalent to x if y-x is divisible by 2. Call this relation =_2 . This creates a sort of circle if we collapse the real line by taking the quotient R/(=_2). Taking the quotient tells us to only consider the equivalence classes of this relation over the real numbers. Ie., 1 is in the equivalence class containing all odd integers, 2 is in the equivalence class containing all even integers, 1/2 is in the equivalence class containing all numbers 2k + 1/2 for integer k, and so on. You can visualize the quotient space as a circle parameterized with the numbers in the interval [0, 2). (2 is equivalent to 0, so you just keep wrapping the number line around the circle after 2). Each point on the circle is identified with the equivalence class of real numbers related to it.

 

[waht]

Start with the concept of a relation first. If you have two sets A and B, then you can pick an element a from A, and b from B that are related according to some rule (like pick all the green apples from A and B)

you can write that aRb or a~b

An equivalence relation is similar, except that you have to pick two elements from the same set that are related, and they must satisfy three properties

Relexivity (if x~x then x~x)
Symmetry(if x~y then y~x)
Transitivity (if x~y and y~z then x~z)

If you pick out all elements like that from a set, then you effectively split the set into distinct classes.

For example if you have a set of red and green apples mixed in order, and apply equivalence relation by picking out all apples that are green, then you will wind up with a set that is composed of all green apples (equivalence class), and what's left over is a set of red apples (another equivalence class).

Hope that helps.

 

[adriank]

To make it more clear on what a quotient set is, if ~ is an equivalence relation on a set S, then the quotient set S/~ is simply the set of equivalence classes (under ~). Thus, to find the quotient set, just find the equivalence classes.

 

[d_b]

First of, thank you all for your help, i really really appreciate it.

I understand what you are saying but I'm having a hard time implying theorems and rules to examples or exercise. For example U={1,2,3} and A=U*U. (a,b)~(a1,b1) if a+b = a1+b1 . Now why is this an equivalence and why is the quotient set of A~ is equals {[1,1], [1,2], [1,3], [2,3], [3,3]} ...I can't seem to figure out how to apply the relation on the equivalences rules and theorem to examples or excercises...

 

[adriank]

To prove it's an equivalence relation, just test the axioms for an equivalence relation. Specifically, you want to prove the following three things:

• Reflexivity: For all (a, b) in U × U, show that (a, b) ~ (a, b).
• Symmetry: For all (a, b) and (a₁, b₁) in U × U, show that if (a, b) ~ (a₁, b₁), then (a₁, b₁) ~ (a, b).
• Transitivity: For all (a, b), (a₁, b₁), and (a₂, b₂) in U × U, show that if (a, b) ~ (a₁, b₁) and (a₁, b₁) ~ (a₂, b₂), then (a, b) ~ (a₂, b₂).

These should all be easy things to prove.

To construct the set (U × U)/~ of equivalence classes, one way of doing it is just to pick any element and find its equivalence class, pick another element and find its equivalence class, and so on.

Another way of looking at it is this: Notice that (a, b) ~ (a₁, b₁) if and only if a + b = a₁ + b₁. Look at the possible values for a + b (they are 2, 3, 4, 5, and 6). Each equivalence class corresponds to one of these, so there are five equivalence classes; the equivalence class corresponding to 3, for example, is the set of all (a, b) in U × U such that a + b = 3; clearly this is the set {(1, 2), (2, 1)}.

When you list the equivalence classes, remember that each element of the set must be in exactly one equivalence class.

 

[d_b]

To prove it's an equivalence relation, just test the axioms for an equivalence relation. Specifically, you want to prove the following three things:

• Reflexivity: For all (a, b) in U × U, show that (a, b) ~ (a, b).
• Symmetry: For all (a, b) and (a₁, b₁) in U × U, show that if (a, b) ~ (a₁, b₁), then (a₁, b₁) ~ (a, b).
• Transitivity: For all (a, b), (a₁, b₁), and (a₂, b₂) in U × U, show that if (a, b) ~ (a₁, b₁) and (a₁, b₁) ~ (a₂, b₂), then (a, b) ~ (a₂, b₂).

These should all be easy things to prove.

To construct the set (U × U)/~ of equivalence classes, one way of doing it is just to pick any element and find its equivalence class, pick another element and find its equivalence class, and so on.

Another way of looking at it is this: Notice that (a, b) ~ (a₁, b₁) if and only if a + b = a₁ + b₁. Look at the possible values for a + b (they are 2, 3, 4, 5, and 6). Each equivalence class corresponds to one of these, so there are five equivalence classes; the equivalence class corresponding to 3, for example, is the set of all (a, b) in U × U such that a + b = 3; clearly this is the set {(1, 2), (2, 1)}.

When you list the equivalence classes, remember that each element of the set must be in exactly one equivalence class.

so if i was going to look for an equivalence class for 4 it would be {[1,3], [3,1] [2,2]}, am I right?

Also how is the partition rules apply to equivalences??

I'm very sorry English isn't my first language and I'm coming across this and I can't translate it to my own language. But I am very thankful to all the people that been helping me so far, I don't know what to do without any or your help, thank you,

 

[adriank]

The set {(1, 3), (3, 1), (2, 2)} is an equivalence class, yes. To show that, pick an element of it and show that the other ones are equivalent to it, and no other element of U × U outside the equivalence class is. The number 4 isn't quite related to the equivalence class (so you'd have to explain by what you mean by the equivalence class corresponding to 4); it's mostly just an easy way to find the equivalence class.

The partition idea is simple. Given a set S, a partition \mathcal P of S is a collection of sets such that the sets in \mathcal P are nonempty, every pair of sets in \mathcal P is disjoint (that is, if P and P' are in \mathcal P, then the intersection of P and P' is empty), and the union of the sets in \mathcal P is S. The set of equivalence classes form a partition (of the set that the equivalence relation is defined on).

 

[d_b]

Is the intersection of P and P' is always an empty set? and always disjoint?

 

[adriank]

That is the definition of a partition; if that's not true, then you don't have a partition.

The interesting thing is that the set S/~ of equivalence classes (of an equivalence relation ~ on a set S) form a partition of S, and any partition of S also induces an equivalence relation on S. It would be a good exercise to prove these.

 

[d_b]

The interesting thing is that the set S/~ of equivalence classes (of an equivalence relation ~ on a set S) form a partition of S, and any partition of S also induces an equivalence relation on S. It would be a good exercise to prove these.

I'm not sure if i understand what you mean here, Do you mean that any partition set is giving rises to an equivalence relation??

Since a partition set are disjoint and their intersection is an empty set i can say, any two partition set were to be equals or the same then there intersection wouldn't be an empty set, is that a correct way to say it?

 

[adriank]

Yes, any partition can give rise to an equivalence relation. Given a partition \mathcal P of a set S, you can define an equivalence relation on S by saying two elements are equivalent if and only if they belong to the same set in \mathcal P.

Also, I did make an error when I stated the definition of a partition. If P and P' are not equal, then their intersection is empty. :)