Math Is Fun Forum

TheMathsDude

Member

Registered: 2008-01-16

Posts: 3

Equivalence Classes / Relation Questions!

Hi guys,

Any help with these would be super!!

Many Thanks,
TheMathsDude

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Equivalence Classes / Relation Questions!

Typically proofs of this type are not very difficult.  What you are allowed to assume is generally enough to get you to your conclusion with little if any work.  Is there something specific you are having trouble with?

For (a), the reflexive property is straight forward.  Anything and everything divides 0.  Symmetry can easily be shown using the fact that |a - b| = |b - a|.  And finally, transitivity is almost just as easy.  We have m | (a - b) and m | (b - c).  So it must be that m divides their sum, which is a - b + b - c = a - c, and you're done.

To describe their equivalence class, just take a look at their remainders after division by m.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

TheMathsDude

Member

Registered: 2008-01-16

Posts: 3

Re: Equivalence Classes / Relation Questions!

Hi Ricky,

Any chance you could explain what an equivalence class / relation is? And if possible could you please give a simple example of each that I could relate to the quesion.

Many Thanks!

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Equivalence Classes / Relation Questions!

Looking through the questions, I see that the toughest part is proving transitivity for the relation defined in Question (b), so I’ll do half of that for you. The rest is not that tough; I trust you should be able to do the rest yourself.

Let

and

; in other words

We want to prove that

, i.e.

. Let

. Then either (i)

or (ii)

.

(i)
If

, then

, and so

since

. Now, either

or

. If

, then

and so

. If

, then

but

; hence

again.

Therefore

; i.e.

.

(ii)
If

, carefully follow the same procedure above and show that

.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Equivalence Classes / Relation Questions!

Any chance you could explain what an equivalence class / relation is? And if possible could you please give a simple example of each that I could relate to the quesion.

When we look at equality of numbers, we see a couple of important properties.

x = x //reflexive
x = y implies y = x //symmetric
x = y and y = z implies x = z //transitive

These three properties are able to capture exactly what we mean when we think of "equality".  Now when you are given an equivalence relation on a set S, we can define an equivalence class:

This forms what is called a partition of S.  A partition is basically dividing a set into subsets such that every element appears in exactly one subset.  That equivalence classes form a partition may be proving by showing the following statement: For the equivalence class of x and y:

That gives us that each different equivalent class does not overlap with any other one.  We get the fact that each element of the set is in an equivalence class by:

This is because of the reflexive property.

For a simple example, take the integers under the relation:

a ~ b if and only if |a| = |b|

It is obvious that |a| = |a| for any integer.  Next, if |a| = |b|, then |b| = |a|.  Finally, if |a| = |b| and |b| = |c|, then |a| = |c|.

Now we look at equivalence classes.  Once you get used to what they are, you can jump right in and say that the equivalence classes are {n, -n} for every positive integer n, and {0} for 0.  However, to find this out, it is easiest to take a few examples and construct the equivalence class by hand.

It should be plain to see that:

And similar results can be then abstracted from this example.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."