# Construct an equivalence relation on a given set

can anyone help me on this problem?

I have the set $\{0,1,3,8,9\}$ and I want to define an example of an equivalence relation.

I know that to be an equivalence relation it needs to be reflexive, symmetric and transitive.

I also now that for a set of $5$ elements there are $2^{n^2}$, so if $n=5$ there are $2^{10}$ of relations.

I am not sure how to start because there are $2^{10}$ relations in this set. Do I have to list all of them or is there any other method to find an equivalence relation?

Thank you

• If you want an equivalence relation, you can always take equality. Commented Dec 13, 2015 at 15:31
• Make everything related to everything. Commented Dec 13, 2015 at 15:32
• Can you explain it better? I did not get it Commented Dec 13, 2015 at 15:34
• Two elements are related if and only if they are equal. You can work with that. Commented Dec 13, 2015 at 15:38
• If $n=5$, then $2^{n^2} = 2^{25}$, not $2^{10}$. Commented Dec 13, 2015 at 15:56

Here are some suggestions:

1) Let one number be related to another, if the two numbers are equal. For instance, $3$ is only related to $3$ (itself), and likewise for all other numbers. You can check that this is an equivalence relation.

2) Let one number be related to another, if the two numbers have the same number of holes in them: $0$ has one hole, $1$ has no holes, $3$ has no holes, $8$ has two holes, and $9$ has one hole. For instance, $0$ is related to $9$, because they have the same number of holes.

3) One number is related to another, if the two numbers contain the same number of letters when spelled out. For instance, $0$ is related to $9$, because ZERO and NINE both have four letters.

4) Two numbers are related, if they are both odd, or if they are both even.

• So if I say the partion {3} of the set {0,1,3,8,9} is it a equivalence relation because {3} met the tree condition to be an equivalence relation ? Commented Dec 13, 2015 at 17:20
• @user290335 not quite. What is important for an equivalence relation is that every element in your set is part of a set in your partition. We are talking about my first example: You are right that $\{3\}$ will be part of your partition, because $3$ is not related to anything else. What else will be there? $0$ is only related to itself as well, and likewise for all other numbers, so your partition will actually be $\{\{0\},\{1\},\{3\},\{8\},\{9\}\}$. Commented Dec 13, 2015 at 18:10
• @user290335 Take my second example. There we have $0\sim 9$, $1\sim 3$, and $8$ is only related to itself. Your partition will then be $\{\{0,9\},\{1,3\},\{8\}\}$. Notice how equivalent elements are contained in the same set of the partition. Commented Dec 13, 2015 at 18:12
• is this correct ? {(0,0),(1,1),(3,3),(8,8),(9,9)} Commented Dec 13, 2015 at 18:29
• @user290335 yes, that is the equivalence relation from part 1). The partition from part 1) is then $\{\{0\},\{1\},\{3\},\{8\},\{9\}\}$. Commented Dec 13, 2015 at 18:35

Take any partition of $S=\{0,1,3,8,9\}$ for e.g. $A=\{0,1\},B=\{3,8,9\}.$ Define a relation on $S$ by $a\sim b$ iff both $a,b$ belongs to same set in the partition. Then $\sim$ is equivalence relation.

Hint:

There is a one-to-one relation between equivalence relations on a set $S$ and partitions of a set $S$.

Example: $\{\{0,8\},\{1,3,9\}\}$ is a partition of set $\{0,1,3,8,9\}$.

The corresponding equivalence relation is:

$xRy$ iff $x,y$ are both elements of the same set in the partition.

This leads to $0R0$, $0R8$, $1R3$, $3R1$ et cetera.