Welcome to our community

Be a part of something great, join today!

Show that ~ is an equivalence relation

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,008
Hey!! :eek:

Let $M:=\{1, 2, \ldots, 10\}$ and $\mathcal{P}:=\{\{1,3,4\}, \{2,8\}, \{7\}, \{5, 6, 9, 10\}\}$.

For $x \in M$ let $[x]$ be the unique set of $\mathcal{P}$ that contains $x$.

We define the relation on $M$ as $x\sim y:\iff [x]=[y]$.

Show that $\sim$ is an equivalence relation.



For that we have to show that the relation is reflexive, symmetric and transitive.
  • Reflexivity:

    Let $x \in M$. Then it holds, trivially, that $[x]=[x]$. Therefore $x\sim x$. So $\sim$ is reflexive.

  • Symmetry:

    Let $x,y \in M$ and $x\sim y$. Then $[x]=[y]$. Equivalently it holds that $[y]=[x]$ and therefore $y \sim x$. So $\sim$ is symmetric.

  • Transitivity:

    Let $x,y,z\in M$ and $x\sim y$ and $y\sim z$. Then it holds that $[x]=[y]$ and $[y]=[z]$. So we have that $[x]=[y]=[z]$, so $[x]=[z]$ and therefore $x\sim z$. So $\sim$ is transitive.

Is everything correct and complete? Or do we have to justify each property with more details, i.e. using the definition of $[x]$ ? (Wondering)
 
Last edited:

HallsofIvy

Well-known member
MHB Math Helper
Jan 29, 2012
1,151
Well, how obvious to you consider each of your claims?

It might be useful to specify that [1]= [3]= [4]= {1, 3, 4}, that [2]= [8]= {2, 8}, that [7]= {7}, and that [5]= [6]= [9]= [10]= {5, 6, 9, 10}.

 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,488
More generally, for all sets $A$ and $B$ and functions $f:A\to B$ the relation $x\sim y\iff f(x)=f(y)$ is an equivalence relation on $A$.