Thread: Equivalence Relations and Classes

I am doing my first maths class since high school three years ago and I'm having trouble at getting my head around the abstraction of equivalence relations.

The following table gives a list of 6 different relations.

a) Which of the relations are equivalence relations? Mark anXin the column under “is equivalence relation?”for those which are equivalence relations.

b) For those which are equivalence relations, give an example of an equivalence class (i.e., choose an elementxof the set, and write a list of all the elements equivalent tox, or a formula for all the elements if this isan infinite set).

c) For those which are equivalence relations, in the last column of the table, write down the number ofequivalence classes (this could be infinite.)

Each relation in this table is a relation on a given set, listed under “set”.

Set / Relation
1. R /aRb ⇐⇒ a−b is negative
2. Z / aRb ⇐⇒ a−b is even
3. R / aRb ⇐⇒ |a|=b
4. R/ aRb ⇐⇒ |a|=|b|
5. R/aRb ⇐⇒ |a|b=a|b|
6.Z/aRb⇐⇒|a| − |b| is even


Ok - What I think
To be an equivalence relation the relation on the set needs to be reflexive, symmetric and transitive. I am having trouble with understanding how the reflexive requirement applies on any of these

1. Every relation will be in Z so it is reflexive? Not symmetric. Not transitive
2. Reflexive, Symmetric, transitive. 2 equivalence classes [0] and [1]
3. Reflexive, not symmetric, not transitive.
4. Reflexive, Symmetric, transitive. Equivalence classes [0],[1],[2],...[,oo]
5. Reflexive, not symmetric, not transitive
6. The same as 2.


Any help/advice is greatly appreciated.

Hello TTim

Originally Posted by TTim

I am doing my first maths class since high school three years ago and I'm having trouble at getting my head around the abstraction of equivalence relations.

The following table gives a list of 6 different relations.

a) Which of the relations are equivalence relations? Mark anXin the column under “is equivalence relation?”for those which are equivalence relations.

b) For those which are equivalence relations, give an example of an equivalence class (i.e., choose an elementxof the set, and write a list of all the elements equivalent tox, or a formula for all the elements if this isan infinite set).

c) For those which are equivalence relations, in the last column of the table, write down the number ofequivalence classes (this could be infinite.)

Each relation in this table is a relation on a given set, listed under “set”.

Set / Relation
1. R /aRb ⇐⇒ a−b is negative

Any relation is reflexive if aRa for all a in the set. In other words every element is related to itself - hence 'reflexive'.

So for #1, is aRa for all a in the set? Clearly not, because a - a = 0, which is not negative.

A relation is symmetric if for any a and b in the set, aRb if and only if bRa. So is #1 symmetric? In other words, does a - b < 0 mean that b - a < 0? Again, clearly not. In fact, the opposite is true. (This means that the relation is anti-symmetric.)

A relation is transitive whenever aRb and bRc always means that aRc. So here if a - b < 0 and b - c < 0, does it follow that a - c < 0? A moment's thought will tell you that a - c = (a - b) + (b - c), and so the answer is yes, because we are adding together two negative numbers. So #1 is transitive.

2. Z / aRb ⇐⇒ a−b is even

(i) Is a - a even? Yes, because it's zero, of course. So it's reflexive.

(ii) If a - b is even, is b - a even? Yes, because (b - a) = -(a - b). So it's symmetric.

(iii) If a - b is even and b - c is even, is a - c even? Yes. Again, a - c = (a - b) + (b - c). So it's transitive.

So #2 is an equivalence relation, and the integers are separated (partitioned) into just two equivalence classes: all the even numbers in one class, and all the odd numbers into the other.

3. R / aRb ⇐⇒ |a|=b

(i) Reflexive? Is |a| = a, for all a in R? What about a = -3?

(ii) Symmetric? If |a| = b, does it follow that |b| = a? Again, what about a = -3 (and b = 3)?

(iii) Transitive? If |a| = b, and |b| = c, must it follow that |a| = c?

4. R/ aRb ⇐⇒ |a|=|b|

Ask the same three questions again, as we did in #3, but this time it's |a| = |b|.

5. R/aRb ⇐⇒ |a|b=a|b|

... and again here. Try some numbers, including as many combinations of positive and negative as you can think of.

6.Z/aRb⇐⇒|a| − |b| is even

Go carefully through #2 again, but this time with |a| and |b|. Does changing the signs (if necessary) to make it positive make any difference to whether the numbers are odd and even?

You might also like to look at another posting where I give further examples of equivalence relations: http://www.mathhelpforum.com/math-he...tml#post239094

Grandad

Thankyou very much. I couldn't seem to quote quotes so I will just do it in an orderly fashion.

4. R / aRb ⇐⇒ |a|=|b|
Reflexive? |a|=|a| always. Reflexive
Symmetric? if |a|=|b| then |b|=|a|. This obviously holds. Is there a proof?
Reflexive? If |a|=|b| and |b|=|c| then |a|=|c|. Proof?

So there would be infinite number of equivalent classes in R with each equivalence class only have two elements of a in R and two elements of b in R(is this worded correctly?) apart from (0,0).

{(-1,-1),(-1,1),(1,-1),(1,1)} Is this an equivalence class. If so the general term for the infinite equivalence classes where n is an element of +R would be {(-n,-n),(-n,n),(n,-n),(n,n)}

5.R/aRb ⇐⇒ |a|b=a|b|

I still feel the same about the symmetry and transititity. (not symmetric, not transitive) but I am still confused with reflexiveness. Does my combination of (a,b) have to be (a,a) ((2,2) or (-8,-8) for example) when I test it here? If it does it will be reflexive. If the combination doesn't have to be (a,a) but (a,b) where a and b can be differentb ((-2,1) for example) then it will not be reflexive.

I have to go to class now but I will continue with 6 later. In the meantime if anyone can spot errors or smooth out my confusion in q5 that would be great!

After working through this with a friend I see I still have errors in my second post. I understand it all now, if anyone wants to see the results I'll put them up if you ask.

Originally Posted by TTim

After working through this with a friend I see I still have errors in my second post. I understand it all now, if anyone wants to see the results I'll put them up if you ask.

well, it wouldn't hurt to post your final work and have someone review it

Originally Posted by Jhevon

well, it wouldn't hurt to post your final work and have someone review it

Sure, why not

3. R / aRb ⇐⇒ |a|=b

|-3| ≠ 3 therefore this is not reflexive, not an equiv relation

4. R / aRb ⇐⇒ |a|=|b|
|a|=|a| reflexive
|a|=|b| => |b|=|a| symmetric
if |a|=|b| and |b|=|c| => |a|=|c| transitive

There are infinite equivalence classes.

[1] = {1,-1)
[n] = {n,-n}

Is there an equivalence class [-1]? If there is does [-1] = [1]?

5.R/aRb ⇐⇒ |a|b=a|b|
|a|a=a|a| reflexive
if |a|b=a|b| => |b|a= b|a| (just changed the order) symm.
if |a|b=a|b|...(1) & |b|c=b|c|...(2) => |a|c=a|c| (working below) trans

to prove trans divide LHS of (1) by RHS of (2) and RHS of (1) by LHS of (2) => (|a|b)/(b|c|) = (a|b|)/(|b|c) => |a|/|c| = a/c => |a|c = a|c|

There are three equivalence classes
[1] = R+ and {0}
[0] = R
[-1] = R- and {0}

5 was the tough one for me and 4 is the one where I still have a question. Any answers for my question in bold?

Hello TTim

3. R / aRb ⇐⇒ |a|=b

|-3| ≠ 3 therefore this is not reflexive, not an equiv relation

This is correct.

4. R / aRb ⇐⇒ |a|=|b|
|a|=|a| reflexive
|a|=|b| => |b|=|a| symmetric
if |a|=|b| and |b|=|c| => |a|=|c| transitive

There are infinite equivalence classes.

[1] = {1,-1)
[n] = {n,-n}

OK, apart from a minor typo.

Is there an equivalence class [-1]? If there is does [-1] = [1]?

Yes. [n] = [-n]. You can use any element in an equivalence class to represent the whole class.

5.R/aRb ⇐⇒ |a|b=a|b|
|a|a=a|a| reflexive
if |a|b=a|b| => |b|a= b|a| (just changed the order) symm.
if |a|b=a|b|...(1) & |b|c=b|c|...(2) => |a|c=a|c| (working below) trans

to prove trans divide LHS of (1) by RHS of (2) and RHS of (1) by LHS of (2) => (|a|b)/(b|c|) = (a|b|)/(|b|c) => |a|/|c| = a/c => |a|c = a|c|

There are three equivalence classes
[1] = R+ and {0}
[0] = R
[-1] = R- and {0}

5 was the tough one for me and 4 is the one where I still have a question. Any answers for my question in bold?

The problem occurs when b = 0, and you get the familiar 'division by zero' error.

It's not transitive, of course, because if b = 0, |a|b = a|b| = 0 = |b|c = c|b| for any a and c.

Otherwise, I think you've done some good work here.

Grandad

Originally Posted by Grandad

It's not transitive, of course, because if b = 0, |a|b = a|b| = 0 = |b|c = c|b| for any a and c.

Ahhhh, so it would be transitive if the set was all R apart from zero? This one element (zero) causes the set not to be transitive and therefore not an equivalence relation so therefore it cannot have equivalence classes. Where did I go wrong in my proof?

Hello TTim

Originally Posted by TTim

Ahhhh, so it would be transitive if the set was all R apart from zero?

Yes. The equivalence classes would then be and .

This one element (zero) causes the set not to be transitive and therefore not an equivalence relation so therefore it cannot have equivalence classes. Where did I go wrong in my proof?

As I said, it's a 'division by zero' error. You said:

to prove trans divide LHS of (1) by RHS of (2) and RHS of (1) by LHS of (2) => (|a|b)/(b|c|) = (a|b|)/(|b|c) => |a|/|c| = a/c => |a|c = a|c|

But this doesn't work if , because you're relying on being able to divide by and . Essentially, you've got something equivalent to this:

, which is not correct.

The correct statement is .

Is that OK now?

Grandad

PS I've just spotted a typo in my previous posting: |b|c = c|b| should, of course, be |b|c = b|c|.

Originally Posted by Grandad

As I said, it's a 'division by zero' error.

Sorry I didn't know that was its actual name.

Thankyou very much for your help. I feel like I have a good grasp on this stuff now.

Tim