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

  • 1
    $\begingroup$ If you want an equivalence relation, you can always take equality. $\endgroup$ – Martin Argerami Dec 13 '15 at 15:31
  • $\begingroup$ Make everything related to everything. $\endgroup$ – Seven Dec 13 '15 at 15:32
  • $\begingroup$ Can you explain it better? I did not get it $\endgroup$ – user290335 Dec 13 '15 at 15:34
  • $\begingroup$ Two elements are related if and only if they are equal. You can work with that. $\endgroup$ – Liddo Dec 13 '15 at 15:38
  • $\begingroup$ If $n=5$, then $2^{n^2} = 2^{25}$, not $2^{10}$. $\endgroup$ – Alex M. Dec 13 '15 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.

  • $\begingroup$ 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 ? $\endgroup$ – user290335 Dec 13 '15 at 17:20
  • $\begingroup$ @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\}\}$. $\endgroup$ – Mankind Dec 13 '15 at 18:10
  • $\begingroup$ @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. $\endgroup$ – Mankind Dec 13 '15 at 18:12
  • $\begingroup$ is this correct ? {(0,0),(1,1),(3,3),(8,8),(9,9)} $\endgroup$ – user290335 Dec 13 '15 at 18:29
  • $\begingroup$ @user290335 yes, that is the equivalence relation from part 1). The partition from part 1) is then $\{\{0\},\{1\},\{3\},\{8\},\{9\}\}$. $\endgroup$ – Mankind Dec 13 '15 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.



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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.