finding an example of an equivalence relation

Question

Find an example of an equivalence relation on the set $\mathbb{N}$.

What I know so far:

An equivalence relation is reflexive, symmetric and transitive. However I have no idea of an example.

Answer 1

Another example is congruence modulo $a$, where $a$ is a positive number:

$m\sim n\iff a|m-n\iff \exists k\in\mathbb Z$ such that $m-n=ka$.

Can you show this is an equivalence relation?

Answer 2

There are lots of examples. Perhaps the least instructive are:

• the minimal equivalence relation where $m\sim n$ only if $m=n$;
• the maximal equivalence relation where $m\sim n$ for every $m,n$.

Answer 3

Note that every partition of a set corresponds to an equivalence relation on that set (the equivalence relation being two elements are related iff they belong to the same part in the partition). Similarly every equivalence relation on a set defines a partition on the set (the parts being the equivalence classes of the relation).

So... a way to reword the question is to ask you for an example of a way to partition $\Bbb N$.

You could do so in a number of ways... partition it into the even numbers and the odd numbers, $\{1,3,5,7,\dots\},\{2,4,6,8,\dots\}$.

You could partition it into the prime numbers versus the composite numbers vs $1$, $\{1\},\{4,6,8,9,10,12,\dots\},\{2,3,5,7,11,13,\dots\}$

You could partition it into groups of numbers who all have the same number of digits: $\{1,2,3,\dots,9\},\{10,11,\dots,99\},\{100,101,\dots,999\},\dots$

You could partition it however you like. Some of these examples will be more important than others and will occur more often. Some of these examples will be easier to explain or think about. Some of these will be obscure or impossible to effectively work with. They all exist however and that is the main point.

Answer 4

I thought to add a few more things which might help see equivalence relation through a different lens and will help you easily generate equivalence relation not just on $\mathbb{N}$ but on any set you come across.

Actually, you can see equivalence relations everywhere around you. Consider your classroom for example:

1. Students having a black pen of the same color is an equivalence relation.

2. Students having a pen of the same color is, not an equivalence relation(why?)

3. Students having the same gender is an equivalence relation.

4. Students with the same eye color is an equivalence relation.

Well, now do you realize the work of an equivalence relation? It actually generates a partition (i.e it breaks the whole set into disjoint classes) on the set it is defined. See the examples above.

In 1. The classroom gets divided into 2 disjoint classes, one having a black pen and the other not having a black pen.

Now can you see why "2" is not an equivalence relation? Remember: Equivalence relation generates partition. What if a student has 1 black and 1 blue pen?

Note: Given a set, there is a one-to-one correspondence between equivalence relations and partitions defined on that set. Can you find this bijection?

Reflexivity ensures that every element of the set is present in one of the classes.

Symmetry and Transitivity together ensure the classes produced are disjoint.

Remark: An equivalence relation is actually a generalization of the notion of equality. You can explicitly construct a definition of $"="$ on a set using equivalence relations on that set.

i.e For any a,b in a set. One can define $a=b$ if for any given equivalence relation, a and b belong to the same class of the partition the relation generates.