2
$\begingroup$

Let $M$ be the set $\{1,2,3\}$. How many Equivalence relations $R \subset M \times M$ exists?

My idea is to count the disjoint partitions of M:

$K_1= \{\{1\},\{2\},\{3\}\}\Leftrightarrow\{(1,1),(2,2),(3,3)\}$

$K_2= \{\{1,2\},\{3\}\} \Leftrightarrow\{(1,1),(1,2),(2,1),(2,2),(3,3)\} $

$K_3= \{\{1,3\},\{2\}\}\Leftrightarrow\{(1,1),(1,3),(3,1),(2,2),(3,3)\}$

$K_4= \{\{1\},\{2,3\}\}\Leftrightarrow\{(1,1),(2,3),(3,2),(2,2),(3,3)\}$

$K_5=\{1,2,3\}\Leftrightarrow K_5=M^2$

So the answer would be $5$. Is this correct? Reflexivity and Symmetry are obvious, but how can i check the right side for Transitivity?

$\endgroup$
4
  • $\begingroup$ Yes, your idea is correct. $\endgroup$ – MJD Mar 14 '14 at 16:15
  • 1
    $\begingroup$ If we partition the set, all properties are obvious. $\endgroup$ – André Nicolas Mar 14 '14 at 16:15
  • $\begingroup$ Maybe to obvios for me... Could you give me an example? I was trying to imagine this to myself in a 2 dimensional coordinate system, how can i see Transitivity? ( Reflexivity is just the line through the origin, and Symmetry a Reflection at the line through the origin , but Transitivity?) $\endgroup$ – fear.xD Mar 14 '14 at 16:21
  • $\begingroup$ Every equivalence relation on $M$ induces a partition of $M$ and the inverse is also true: for a given partition declare two elements as equivalent iff they belong to the same set of that partition. $\endgroup$ – Michael Hoppe Mar 14 '14 at 16:39
2
$\begingroup$

There are good comments already above; I'm just spelling them out:

If $X = \bigsqcup_i X_i$ is partition of set $X$ into disjoint $X_i$'s, then we can declare equivalence relationon $X$ by $x\sim y$ if $x,y\in X_i$ for some $i$. Symmetry and reflexivity is obvious, and as you asked Transitivity really means asking: If $x,y\in X_i$, and $y,z\in X_j$, then are $x,z\in X_k$ for some $k$? Well, $X_i$'s were disjoint, so $y\in X_i$ and $y\in X_j$ means $X_i = X_j$, hence $x,z\in X_i$. So yes.

So any partition of a set gives a equivalence relation.

On the other hand, any equivalence relation gives a partition of a set where each disjoint sets are just equivalence classes (i.e. collect together elements that are equivalent to each other). This needs slightly more careful checking, but is very believable.

So, in conclusion, giving a equivalence relation is actually just the same thing as giving a partition of a set, as you accurately noticed already.

$\endgroup$
6
  • $\begingroup$ Transitivity would be like this: if $x, y \in X_i$ and $y, z \in X_j$, then $x, z \in X_k$ $\endgroup$ – dani_s Mar 14 '14 at 18:11
  • $\begingroup$ @dani_s: yes, I should be more careful. It's been edited. $\endgroup$ – chriseur Mar 14 '14 at 18:44
  • $\begingroup$ Ok, so for example consider $K_2:$ Transitivity of $(1,2) \sim (2,2) \Rightarrow (1,2)$? How about $(3,3)$? Just like $(3,3) \sim (3,3) \Rightarrow (3,3)$? $\endgroup$ – fear.xD Mar 14 '14 at 19:41
  • $\begingroup$ What do you mean by $(1,2) \sim (2,2)$? Saying that $(1,2)\subset R\subset M\times M$ means that 1 is equivalent to 2, i.e. $1\sim 2$. $\endgroup$ – chriseur Mar 14 '14 at 19:44
  • $\begingroup$ I mean $(1,2),(2,2) \in R \Rightarrow (1,2) \in R$. Would this be a possible way to show Transitivity individually? And for $(3,3)$ the only possibility would be $(3,3),(3,3) \in R \Rightarrow (3,3) \in R$? $\endgroup$ – fear.xD Mar 14 '14 at 19:59

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.