# Equivalence relation-equivalence classes

We are given the set $E=\{d,e,f \}$, $d,e,f$ different from each other and the relation $I_{E}=\{ <x,x>: x \in E\}$. Prove that $I_{E}$ is a set. In addition, show that the relation $I_{E}$ is an equivalence relation in $E$ and find all the equivalence classes.

That's what I have tried:

We define $\phi(x)=<x,x>: x \in E$.

Then, we have that $\forall <x,x>(\phi(x)) \rightarrow <x,x> \in E \times E$.

$E \times E$ is a set. So, from the theorem: "Let $\phi$ a type. If there is a set $Y$, such that $\forall x(\phi(x)) \rightarrow x \in Y$, then there is the set $\{ x: \phi(x) \}$", we have that $I_{E}=\{ <x,x>: x \in E\}$ is a set.

The relation $I_{E}$ is an equivalence relation:

• reflective: $<x,x> \in I_{E} \rightarrow <x,x> \in I_{E}$
• symmetric: $<x,y> \in I_{E} \rightarrow x=y \rightarrow <y,x> \in I_{E}$
• transitive: $<x,y> \in I_{E} \wedge <y,z> \in I_{E} \rightarrow x=y \wedge y=z \rightarrow <x,z> \in I_{E}$

Is it right so far? How could we find all the equivalence classes?

• Correct. For $x \in E$, What are the elements in the equivalence class containing $x$? – Thumbnail Nov 15 '14 at 11:42
• @Thumbnail And how can we prove that $E \times E$ is a set?  The elements are of the form $\langle <x,x>\rangle: x \in E$, right ? – evinda Nov 15 '14 at 11:45
• @Thumbnail Are the equivalence classes maybe these one: $\bigcup \{ \langle x,x \rangle: x \in E \}$ ? – evinda Nov 15 '14 at 11:48
• No. The equivalence class containing $x$ under relation $R$ is $$\{y \in E: x \ R \ y \}$$ Because R is an equivalence relation, such classes partition $E$. If you connect equivalent $x$ and $y$ with an edge, the equivalence classes are the connected components of the (unordered) graph. As for proving that $I_E$ is a set, I can't help. I guess you have rules that certain well-formed formulae involving sets are sets too. – Thumbnail Nov 15 '14 at 12:01

If $R$ is an equivalence relation then $\left[x\right]_{R}=\left\{ y\mid xRy\right\} =\left\{ y\mid\left\langle x,y\right\rangle \in R\right\}$.
Here $R=1_{E}$ leading to $xRy\iff x=y$.
So $\left[x\right]_{I_{E}}=\left\{ y\mid x=y\right\} =\left\{ x\right\}$.
• drhab A ok.. So, would it be wrong to say that $[x]_{I_E}=\bigcup \{ \langle x,x \rangle: x \in E\}$ ? – evinda Nov 15 '14 at 11:53
• Yes. On LHS $x$ is fixed and on RHS it ranges over $E$. – drhab Nov 15 '14 at 11:55
• Your proof that relation $1_E$ is an equivalence relation is correct. Further I am not familiar with what you call 'types'. To prove that $I_E$ is a set I would use the separation axiom: if $E\times E$ is a set then $\left\{ z\in E\times E\mid\psi\left(z\right)\right\}$ is a set, and for $\psi\left(z\right)$ I would take the sentence: $\exists x\left[x\in E\wedge z=\left\langle x,x\right\rangle \right]$. – drhab Nov 15 '14 at 12:07
• drhab With type I mean the $\psi(z)$.. If we have to prove that $\times E$ is a set, which else $Y$ could we use at the implication: $$\forall \langle x,x \rangle(\phi(x))\rightarrow \langle x,x \rangle \in Y$$ – evinda Nov 15 '14 at 12:12