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,
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).

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.

- 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
Math Forum Home || Math Library || Quick Reference || Math Forum Search