1

I am to find how many equivalence relations are there on a set $\left\{1, 2, 3\right\}$. How it can be counted? I will appreciate a step by step solution because I'm new to set theory. Thanks!

projectilemotion
  • 15,428
Hendrra
  • 2,868
  • 1
  • 18
  • 35
  • 2
    It's easy. Do you know the proposition that every partition of a set $X$ defines one equivalence relation on $X$ and, conversly, every equivalence relation on $X$ defines a partition on $X$? – Pythagoricus Jan 15 '17 at 20:47
  • 1
    Really? I didn't know that. And it really makes things easier. So there will be 5 equivalence relations? – Hendrra Jan 15 '17 at 20:52
  • 1
    Yup, you got it! – amWhy Jan 15 '17 at 20:58
  • That's great! Thanks! :) – Hendrra Jan 15 '17 at 21:00
  • 1
    Have a look at these links; studing the proof of that theorem is central to understanding equivalence relations. http://math.stackexchange.com/questions/1333375/proof-of-theorem-about-equivalence-classes and http://math.stackexchange.com/questions/31656/every-equivalence-relation-on-a-set-s-defines-a-corresponding-partition-and-v – Pythagoricus Jan 15 '17 at 21:08
  • Nice links, @Pythagoricus! – amWhy Jan 15 '17 at 21:11

1 Answers1

1

As commented befotre, every partition of a set $X$ defines one equivalence relation on $X$ and, conversly. The different partitions of $X=\{1,2,3\}$ are: $$\begin{aligned}&P_1=\left\{\{1,2,3\}\right\}\\ &P_2=\{ \{{2,3}\},\; \{1\}\}\\ &P_3=\{\{{1,3\}},\; \{{2\}}\}\\ &P_4=\{\{3\} ,\; \{1,2\}\}\\ &P_5=\{\{3\} ,\; \{2\},\; \{1\}\}. \end{aligned}$$

Fernando Revilla
  • 3,537