Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Equivalence Classes


Date: 02/19/99 at 03:41:21
From: Wayne Chow
Subject: Discrete Mathematics

Is there an equivalence class containing exactly 271 elements?


Date: 02/19/99 at 19:22:14
From: Doctor Kate
Subject: Re: Discrete Mathematics

To define an equivalence class, one needs to define an equivalence 
relation. There are all sorts of equivalence relations one could use, 
and to answer your question, it would help to know if you had a 
particular equivalence relation in mind. I will assume you do not.

Let's define an equivalence relation. Let a and b be numbers.

To say a is equivalent to b, I will write a ~ b.

An equivalence relation is any relation that satisfies these rules:

1)  a ~ a always (this rule is called reflexivity)
2)  if a ~ b, then b ~ a (this is called symmetry)
3)  if a ~ b and b ~ c, then a ~ c (called transitivity)

So there are all sorts of equivalences:

Example 1:

Equals (=) is an equivalence relation because:

1)  a = a all the time
2)  if a = b, b = a
3)  if a = b and b = c, a = c

Example 2:

Let us define a ~ b if a and b have the same sign (let's pretend 0 has 
positive sign for the purpose of this example).

For example, 3 ~ 5, 7 ~ 2, -5 ~ -18, but -6 is NOT equivalent to 3.

1)  a has the same sign as a, so a ~ a
2)  if a has the same sign as b, b has the same sign as a
3)  if a has the same sign as b, and b has the same sign as c, a and c                        
must have the same sign!

Example 3:

We will say a ~ b if a and b have the same remainder when you divide by 
three. (Notice that I've just changed what ~ (equivalent) means - it's 
different now than in the last example. I can define it in lots of 
ways, as long as I follow the three rules for equivalence relations.)

For example, 3 ~ 6, because both have remainder 0 when you divide by 
three. Further, 1 ~ 16, because both have remainder 1 when you divide 
by three, but 2 is NOT equivalent to 7 because 2 has remainder 2, but 
7 has remainder 1.

For fun, try to check the three rules yourself. Here's the first one:

1)  a ~ a because you always get the same remainder when you divide a 
by three (yes, it's really easy).

Back to your question:

An equivalence class is a set of things that are equivalent to each 
other.

So for '=', every equivalence class is size 1, since the only thing 
equivalent (equal) to a is a itself. For the second example, the 
equivalence classes are infinitely big, because there are infinitely 
many things with positive sign, and infinitely many things with 
negative sign.

Now in the third example, what possibilities do we have? We can have 
a remainder of 0, 1 or 2, so there are really three equivalence 
classes:

1) the things with remainder 0 when you divide by three (multiples 
   of 3)

2) the things with remainder 1 when you divide by three (like 1, 4, 
   7, 10...)

3) the things with remainder 2 when you divide by three (like 2, 5, 
   8, 11...)

But how big are they? They're infinite again.

These are pretty normal examples of equivalence classes, but if you 
want to find one with an equivalence class of size 271, what could you 
do? Well, we could be silly, for a moment, and define an equivalence 
class like this:

Let's talk about the integers. Let a and b be integers.

If a and b are both between 1 and 271, a ~ b. If a and b are both 
outside the interval 1 to 271, a ~ b.  If one of a and b is between 1 
and 271 and the other is not, a is NOT equivalent to b.

I know it is silly! But it's a perfectly good equivalence relation.  
I will let you check the three rules yourself. Now, what equivalence 
classes do we have here? Clearly, we have two:

1)  1, 2, 3, .... 271
2)  everything else

And what size does the first one have?  You guessed it.

I can imagine you asking whether there is a less silly example. Dodging 
the question of what "silly" means exactly, I will say that there is 
not really (well, maybe slightly better, but nothing as nice as my 
examples above), if you want to work with integers. However, you can 
define equivalence relations on all sorts of sets. You can define 
equivalence relations on your socks: all socks of the same colour are 
equivalent. So you may have three equivalence classes: grey, blue, and 
pink. These equivalence classes probably won't have size 271, but you 
never know. They're your socks, not mine.

So the answer to your question is yes.

- Doctor Kate, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/