0

Calculation of total no. of equivalence relation can be defined on a set containing $\{a,b,c\}$

$\bf{Solution::}$ A relation is said to be equivalence, If it satisfy the following relation:

$(1)$ It must be Reflexive.

$(2)$ It must be Symmetric.

$(3)$ It must be Transitive.

But when i search in net, i get

$\bf{The\ no.\; of\; equivalence\; relation\; on\; n-\; set\; is \; equal\; to \ no.\; of \; partition \; of \; n-set }$

So partition of $\{a,b,c\}$ is $\{a|b|c\}\;,\{a|b,c\}\;,\{b|c,a\}\;,\{c|a,b\}\;,\{a,b,c\}$

But I did not understand how can we prove that these $5$ partition are Reflexive, Symmetric and Transitive.

Please explain.

Thanks

usukidoll
  • 2,074
juantheron
  • 53,015
  • Which class is this? I know there are definitions for reflexive, symmetric, and transitive, but I'm not sure if we need to use them. – usukidoll Apr 15 '14 at 05:55

2 Answers2

4

You don't prove the partitions are equivlaence relations: you prove that there is a one-to-one correspondence between partitions and equivalence relations. That is,

  1. Given an equivalence relation on a set, you can use it to construct a partition of the set.
  2. Given a partition of a set, you can use it to construct an equivalence relation on the set

and furthermore:

  • Given an equivalence relation, if you do (1) then (2), you end up with your original equivalence relation
  • Given a partition, if you do (2) then (1), you end up with your original partition

Thus, counting the number of partitions gives you the same number as if you counted the number of equivalence relations.

Have you seen this one-to-one correspondence proven in your book? If not, the actual constructions (1) and (2) aren't that complicated, and you might be able to figure them out yourself. If not, ask again. (or maybe ask in a new question)

1

What you need to show is that the relation "is in the same partition as" is reflexive, transitive, and symmetric. Then it follows that the count of possible partitions of the set is the count of possible equivalent classes for the set.

For set $\mathbb{S}$, let $\operatorname{R}$ be the relation: "is in the same partition as"

$\forall x \in \mathbb{S} : x\operatorname{R}x$, and thus it is reflexive.

$\forall x,y \in \mathbb{S}: x \operatorname{R} y \iff y \operatorname{R} x$, and thus it is symmetric.

$\forall x,y,z \in \mathbb{S}: x \operatorname{R} y \land y\operatorname{R} z \implies x\operatorname{R}z$, and thus it is transitive.

Graham Kemp
  • 129,094